Aritalab:Lecture/Bioinformatics/PartialDigestion

From Metabolomics.JP
< Aritalab:Lecture | Bioinformatics(Difference between revisions)
Jump to: navigation, search
m (→‎複数解の存在)
 
(6 intermediate revisions by one user not shown)
Line 2: Line 2:
  
 
DNAを制限酵素で処理したとき、制限酵素の認識配列部分は確率的に切断されたり、されなかったりします。
 
DNAを制限酵素で処理したとき、制限酵素の認識配列部分は確率的に切断されたり、されなかったりします。
−
従って、処理後のDNA断片をゲル電気泳動で流して長さを確認すると、もとのDNA中の認識配列位置間を組み合わせ的に選んで生じる断片が出てくるはずです。
+
従って、処理後の DNA 断片をゲル電気泳動で流して長さを確認すると、もとの DNA 中の認識配列位置間を組み合わせ的に選んで生じる断片が出てくるはずです。
−
この断片からもとのDNA全体を推定する問題は、以下のように定式化できます。
+
この断片からもとの DNA 全体を推定する問題は、以下のように定式化できます。
  
−
: '''問題'''　: 一次元上に配置された ''n'' 個の点からなる集合 ''X'' を、その全ての要素間の距離からなる（重複を含めた）集合 ''L'' ( |''L''| = ''n''(''n''-1)/2 ) から求めよ。
+
: '''問題'''　: 一次元上に配置された n 個の点からなる集合 X を、その全ての要素間の距離からなる（重複を含めた）多重集合 L ( | L | = n (n &minus; 1)/2 ) から求めよ。
  
 
{|
 
{|
 
|
 
|
−
'''例.''' &nbsp; ''X'' = { 0, 2, 5, 10} のとき<br/>
+
'''例.''' &nbsp; ''X'' = { 0, 2, 5, 10 } のとき<br/>
−
: ''L'' = { 2-0, 5-0, 10-0, 5-2, 10-2, 10-5}<br/>
+
: ''L'' = { 2 &minus; 0, 5 &minus; 0, 10 &minus; 0,
 +
:::5 &minus; 2, 10 &minus; 2,
 +
:::10 &minus; 5}<br/>
 
:: = { 2, 3, 5, 5, 8, 10 }
 
:: = { 2, 3, 5, 5, 8, 10 }
 +
| &nbsp;
 
|
 
|
 
{| class="wikitable"
 
{| class="wikitable"
−
! || 0 || 2 || 5 || 10
+
! ||　0 ||　2 ||　5 || 10
 
|-
 
|-
 
! 0
 
! 0
Line 20: Line 23:
 
|-
 
|-
 
! 2
 
! 2
−
|  || || 3 || 7
+
|  || || 3 || 8
 
|-
 
|-
 
! 5  
 
! 5  
Line 28: Line 31:
 
| || || ||  
 
| || || ||  
 
|}
 
|}
 +
| &nbsp;
 +
|
 +
{ 2, 3, 5, 5, 8, 10 } を与えられて、<br/>{ 0, 2, 5, 10 } を答えるのが問題になります。
 +
 
|}
 
|}
  
−
問題への解が一つみつかれば、それを一次元上で平行移動してもやはり解になります。だから一般に、解は無限個存在します。
+
==問題の性質==
−
ここで集合 ''U'', ''V'' から ''U'' &Theta; ''V'', ''U'' &oplus; ''V'' として作成した二つの集合であれば、同じ距離集合 ''L'' を生成することを示しましょう。
+
問題への解が一つみつかれば、それを一次元上で平行移動または符号を反転してもやはり解になります。上の L = { 2, 3, 5, 5, 8, 10 } なら、X = { 0, 2, 5, 10 } としても { 1, 3, 6, 11 } としても L を構成します。ですから一般に、解は無限個存在します。
 +
 
 +
===複数解の存在===
 +
単なる平行移動や符号反転の他にも、解は複数ありえます。同じ距離集合 L を生成する点集合はホモメトリック (homometric) であると定義し、その関係を &cong; で表します。まず、適当な二つの集合 U, V に対して U &Theta; V と U &oplus; Vを、それぞれ要素の総当たりの引き算、総当たりの足し算と定義します。
 +
このとき、U &Theta; V  &cong; U &oplus; V であることを示しましょう。
 +
 
 +
;例
 +
U = { 0, 1, 3 }, V = { 0, 8, 12 } について考えてみます。
 +
: U &oplus; V = { 0+0, 0+8, 0+12, 1+0, 1+8, 1+12, 3+0, 3+8, 3+12 } = { 0, 1, 3, 8, 9, 11, 12, 13, 15 }
 +
: U &Theta; V = { 0-0, 0-8, 0-12, 1-0, 1-8, 1-12, 3-0, 3-8, 3-12 } = { -12, -11, -9, -8, -7, -5, 0, 1, 3 } &cong; { 0, 1, 3, 4, 5, 7, 12, 13, 15 }
 +
こうして作成したU &oplus; V,  U &Theta; V は見た目に一致していませんが、ホモメトリックです。
  
 
;証明
 
;証明
−
与えられた集合 ''U'' に対して、''V''の要素を個別に考えます。
+
与えられた集合 U に対して、V に要素を一つずつ加えていく場合を考えます。
−
''V''の各要素 ''v'' に対し、''v + u'' と ''v - u'' (''u'' &isin; ''U'') で生成される集合が同じ距離集合 ''L'' をつくることは自明です。（2''v''の平行移動にあたるから。）
+
V に順次新しい要素 v を加え、v + u と v &minus; u (u &isin; U) で新たに生成される距離集合を、数学的帰納法で考えましょう。
 +
* V = { } のとき
 +
生成される点集合は U の要素を &minus; v, + v して平行移動するだけなので、同じ距離集合 L をつくることは自明。
 +
* V &ne; { } のとき
 +
帰納法の仮定から U &Theta; V, U &oplus; V の作る距離集合が同じとし、V に要素 v を追加する場合を考えます。点集合には U の要素を &minus; v, + v した点がそれぞれ追加されます。一般形として、 U に既に含まれていた要素 u ' を v ' だけシフトした点と、要素 u を v だけシフトする点との間の距離を考えましょう。シフトが正の場合の距離は以下のように、負のシフトに変形できます。
 +
: ( u ' + v ' ) &minus; ( u + v ) = ( u ' &minus; v ) &minus; ( u &minus; v ' )
 +
式の左側が表しているのは U &oplus; { v, v ' } として生成される距離で、右側が表すのが U &Theta; { v, v ' } で生成される距離になります。U 中の値は、V 中の値と総当りで組み合わせて点集合を形成するため、上記の対応によって生成される距離集合は同じになります。また、上記の式は u = u ' の場合も成立します。これで証明が終わりました。
  
−
ここで数学的帰納法を用います。距離集合が等しい ''U &Theta; V'', ''U'' &oplus; ''V'' に対して、''V'' へ新たに要素を追加すると仮定しましょう。新しい要素 ''v'' が ''U'' と生成する距離集合は上記の通り同じなので、要素を追加しても距離集合は変わりません。これで証明が終わりました。
+
==点集合を求めるアルゴリズム==
 +
距離集合 L から点集合を予測するアルゴリズムを考えましょう。距離集合の情報は全て正確に与えられると仮定します。
  
−
===アルゴリズム===
+
===基本方針===
−
距離集合 ''L'' から点集合を予測する際、''L'' 中の最大値を ''M<sub>0</sub>'' とするとこれが全体の幅を決定します。
+
# 式 | L | = n (n &minus; 1)/2 から点集合のサイズを決定し、X = { x<sub>1</sub>, x<sub>2</sub>, ... x<sub>n</sub> } とします。
−
そこで、求めたい点集合の両端を [0, ''M<sub>0</sub>''] と設定し、距離集合の中から ''M<sub>0</sub>'' を消去します。次に、''L'' - { ''M<sub>0</sub>'' } の中から最大値 ''M<sub>1</sub>'' を選びます。
+
# L 中の最大値 M<sub>1</sub> を求め、一般性を失わずに x<sub>1</sub> = 0, x<sub>n</sub> = M<sub>1</sub> とします。L からは M<sub>1</sub> を消去します。
−
これは　[0, ''M<sub>1</sub>''] から生成されているか、[''M<sub>0</sub>-M<sub>1</sub>, M<sub>0</sub>''] から生成されるかのどちらかです。ですから、左右のどちらかを選んでいく作業を続けます。
+
# 次に L 中の最大値 M<sub>2</sub> を求めます。この値は、x<sub>1</sub> (= 0) から M<sub>2</sub> の所に点があるか、x<sub>n</sub> (= M<sub>1</sub>) から M<sub>2</sub> のところに点があるかのどちらかです。どちらか選んで x<sub>2</sub> または x<sub>n-1</sub> とします。L からは M<sub>2</sub> と M<sub>1</sub> &minus; M<sub>2</sub> を消去します。
 +
# 以降、順次　L 中の最大値を求め、x<sub>i</sub> とできる i を見つけて配置していきます。
  
−
もし生成されるはずの断片が ''L'' の中に見つからない場合、左右の選択が誤っていたことになります。その場合はバックトラックして、もう一方の選択を選ばなくてはなりません。
+
もし生成されるはずの断片が L の中に見つからない場合、左右の選択が誤っていたことになります。その場合はバックトラックして、もう一方の選択を選ばなくてはなりません。
  
−
このアルゴリズムは、各ステップで常に左右の選択が生じるため、''n'' 点を予測するための計算時間を ''T(n)'' とすると
+
このアルゴリズムは、各ステップで常に左右の選択が生じるため、n 点を予測するための計算時間を T(n) とすると
−
: ''T''(''n'') = 2 ''T''(''n''-1) + ''O''(''n'') 時間
+
: T( n ) = 2 T(n &minus; 1) + O( n ) 時間
−
かかります。これは[[Aritalab:Lecture/Basic/Towers of Hanoi|ハノイの塔問題]]で見たように、指数時間アルゴリズムです。
+
かかります。これは[[Aritalab:Lecture/Algorithm/Towers of Hanoi|ハノイの塔問題]]で見たように、指数時間アルゴリズムです。

Latest revision as of 15:00, 10 November 2011

Contents

[edit] DNAの制限酵素による切断

DNAを制限酵素で処理したとき、制限酵素の認識配列部分は確率的に切断されたり、されなかったりします。 従って、処理後の DNA 断片をゲル電気泳動で流して長さを確認すると、もとの DNA 中の認識配列位置間を組み合わせ的に選んで生じる断片が出てくるはずです。 この断片からもとの DNA 全体を推定する問題は、以下のように定式化できます。

問題　: 一次元上に配置された n 個の点からなる集合 X を、その全ての要素間の距離からなる（重複を含めた）多重集合 L ( | L | = n (n − 1)/2 ) から求めよ。

例.   X = { 0, 2, 5, 10 } のとき

L = { 2 − 0, 5 − 0, 10 − 0,
5 − 2, 10 − 2,
10 − 5}
= { 2, 3, 5, 5, 8, 10 }
 
　0 　2 　5 10
0 2 5 10
2 3 8
5 5
10
  
{ 2, 3, 5, 5, 8, 10 } を与えられて、
{ 0, 2, 5, 10 } を答えるのが問題になります。

[edit] 問題の性質

問題への解が一つみつかれば、それを一次元上で平行移動または符号を反転してもやはり解になります。上の L = { 2, 3, 5, 5, 8, 10 } なら、X = { 0, 2, 5, 10 } としても { 1, 3, 6, 11 } としても L を構成します。ですから一般に、解は無限個存在します。

[edit] 複数解の存在

単なる平行移動や符号反転の他にも、解は複数ありえます。同じ距離集合 L を生成する点集合はホモメトリック (homometric) であると定義し、その関係を ≅ で表します。まず、適当な二つの集合 U, V に対して U Θ V と U ⊕ Vを、それぞれ要素の総当たりの引き算、総当たりの足し算と定義します。 このとき、U Θ V ≅ U ⊕ V であることを示しましょう。

例

U = { 0, 1, 3 }, V = { 0, 8, 12 } について考えてみます。

U ⊕ V = { 0+0, 0+8, 0+12, 1+0, 1+8, 1+12, 3+0, 3+8, 3+12 } = { 0, 1, 3, 8, 9, 11, 12, 13, 15 }
U Θ V = { 0-0, 0-8, 0-12, 1-0, 1-8, 1-12, 3-0, 3-8, 3-12 } = { -12, -11, -9, -8, -7, -5, 0, 1, 3 } ≅ { 0, 1, 3, 4, 5, 7, 12, 13, 15 }

こうして作成したU ⊕ V, U Θ V は見た目に一致していませんが、ホモメトリックです。

証明

与えられた集合 U に対して、V に要素を一つずつ加えていく場合を考えます。 V に順次新しい要素 v を加え、v + u と v − u (u ∈ U) で新たに生成される距離集合を、数学的帰納法で考えましょう。

  • V = { } のとき

生成される点集合は U の要素を − v, + v して平行移動するだけなので、同じ距離集合 L をつくることは自明。

  • V ≠ { } のとき

帰納法の仮定から U Θ V, U ⊕ V の作る距離集合が同じとし、V に要素 v を追加する場合を考えます。点集合には U の要素を − v, + v した点がそれぞれ追加されます。一般形として、 U に既に含まれていた要素 u ' を v ' だけシフトした点と、要素 u を v だけシフトする点との間の距離を考えましょう。シフトが正の場合の距離は以下のように、負のシフトに変形できます。

( u ' + v ' ) − ( u + v ) = ( u ' − v ) − ( u − v ' )

式の左側が表しているのは U ⊕ { v, v ' } として生成される距離で、右側が表すのが U Θ { v, v ' } で生成される距離になります。U 中の値は、V 中の値と総当りで組み合わせて点集合を形成するため、上記の対応によって生成される距離集合は同じになります。また、上記の式は u = u ' の場合も成立します。これで証明が終わりました。

[edit] 点集合を求めるアルゴリズム

距離集合 L から点集合を予測するアルゴリズムを考えましょう。距離集合の情報は全て正確に与えられると仮定します。

[edit] 基本方針

  1. 式 | L | = n (n − 1)/2 から点集合のサイズを決定し、X = { x1, x2, ... xn } とします。
  2. L 中の最大値 M1 を求め、一般性を失わずに x1 = 0, xn = M1 とします。L からは M1 を消去します。
  3. 次に L 中の最大値 M2 を求めます。この値は、x1 (= 0) から M2 の所に点があるか、xn (= M1) から M2 のところに点があるかのどちらかです。どちらか選んで x2 または xn-1 とします。L からは M2 と M1 − M2 を消去します。
  4. 以降、順次　L 中の最大値を求め、xi とできる i を見つけて配置していきます。

もし生成されるはずの断片が L の中に見つからない場合、左右の選択が誤っていたことになります。その場合はバックトラックして、もう一方の選択を選ばなくてはなりません。

このアルゴリズムは、各ステップで常に左右の選択が生じるため、n 点を予測するための計算時間を T(n) とすると

T( n ) = 2 T(n − 1) + O( n ) 時間

かかります。これはハノイの塔問題で見たように、指数時間アルゴリズムです。

Retrieved from "http://metabolomics.jp/mediawiki/index.php?title=Aritalab:Lecture/Bioinformatics/PartialDigestion&oldid=254793"
Personal tools
Namespaces

Variants
Actions
Navigation
metabolites
Toolbox