Aritalab:Lecture/Bioinformatics/PartialDigestion - Revision history

Adm: /* 複数解の存在 */

2011-11-10T06:00:10Z

‎複数解の存在

Adm at 05:57, 10 November 2011

2011-11-10T05:57:45Z

Adm: /* DNAの制限酵素による切断 */

2011-11-07T07:21:05Z

‎DNAの制限酵素による切断

Adm at 11:32, 6 November 2011

2011-11-06T11:32:40Z

Adm at 08:00, 6 November 2011

2011-11-06T08:00:29Z

Adm at 08:07, 2 June 2011

2011-06-02T08:07:28Z

Adm at 16:21, 9 November 2010

2010-11-09T16:21:08Z

Adm: Aritalab:Lecture/Bioinformatics/PartialDigestProblem moved to Aritalab:Lecture/Bioinformatics/PartialDigestion

2010-11-08T07:34:35Z

Aritalab:Lecture/Bioinformatics/PartialDigestProblem moved to Aritalab:Lecture/Bioinformatics/PartialDigestion

Adm: New page: ==DNAの制限酵素による切断== DNAを制限酵素で処理したとき、制限酵素の認識配列部分は確率的に切断されたり、されなかったりします。従...

2010-11-07T20:51:52Z

New page: ==DNAの制限酵素による切断== DNAを制限酵素で処理したとき、制限酵素の認識配列部分は確率的に切断されたり、されなかったりします。従...

New page

==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 }
|
{| class="wikitable"
! || 0 || 2 || 5 || 10
|-
! 0
| || 2 || 5 || 10
|-
! 2
| || || 3 || 7
|-
! 5
| || || || 5
|-
! 10
| || || ||
|}
|}

問題への解が一つみつかれば、それを一次元上で平行移動してもやはり解になります。だから一般に、解は無限個存在します。
ここで集合 ''U'', ''V'' から ''U'' Θ ''V'', ''U'' &oplus; ''V'' として作成した二つの集合であれば、同じ距離集合 ''L'' を生成することを示しましょう。

;証明
与えられた集合 ''U'' に対して、''V''の要素を個別に考えます。
''V''の各要素 ''v'' に対し、''v + u'' と ''v - u'' (''u'' ∈ ''U'') で生成される集合が同じ距離集合 ''L'' をつくることは自明です。（2''v''の平行移動にあたるから。）

ここで数学的帰納法を用います。距離集合が等しい ''U Θ V'', ''U'' &oplus; ''V'' に対して、''V'' へ新たに要素を追加すると仮定しましょう。新しい要素 ''v'' が ''U'' と生成する距離集合は上記の通り同じなので、要素を追加しても距離集合は変わりません。これで証明が終わりました。

===アルゴリズム===
距離集合 ''L'' から点集合を予測する際、''L'' 中の最大値を ''M0'' とするとこれが全体の幅を決定します。
そこで、求めたい点集合の両端を [0, ''M0''] と設定し、距離集合の中から ''M0'' を消去します。次に、''L'' - { ''M0'' } の中から最大値 ''M1'' を選びます。
これは　[0, ''M1''] から生成されているか、[''M0-M1, M0''] から生成されるかのどちらかです。ですから、左右のどちらかを選んでいく作業を続けます。

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

このアルゴリズムは、各ステップで常に左右の選択が生じるため、''n'' 点を予測するための計算時間を ''T(n)'' とすると
: ''T''(''n'') = 2 ''T''(''n''-1) + ''O''(''n'') 時間
かかります。これは[[Aritalab:Lecture/Basic/Towers of Hanoi|ハノイの塔問題]]で見たように、指数時間アルゴリズムです。

@@ Line 46: / Line 46: @@
 ;例
 U = { 0, 1, 3 }, V = { 0, 8, 12 } について考えてみます。
-: U &oplus; V = { 0, 8, 12, <span style="color:red">1, 9, 13,</span> 3, 11, 15 } = { 0, 1, 3, 8, 9, 11, 12, 13, 15 }
+: 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, -8, -12, <span style="color:red">1, -7, -11,</span> 3, -5, -9 } = { -12, -11, -9, -8, -7, -5, 0, 1, 3 } &cong; { 0, 1, 3, 4, 5, 7, 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 は見た目に一致していませんが、ホモメトリックです。

@@ Line 38: / Line 38: @@
 ==問題の性質==
-問題への解が一つみつかれば、それを一次元上で平行移動してもやはり解になります。上の L = { 2, 3, 5, 5, 8, 10 } なら、X = { 0, 2, 5, 10 } としても { 1, 3, 6, 11 } としても L を構成します。ですから一般に、解は無限個存在します。
+問題への解が一つみつかれば、それを一次元上で平行移動または符号を反転してもやはり解になります。上の L = { 2, 3, 5, 5, 8, 10 } なら、X = { 0, 2, 5, 10 } としても { 1, 3, 6, 11 } としても L を構成します。ですから一般に、解は無限個存在します。
 ===複数解の存在===
-ここでは単なる平行移動や左右反転の他にも、解が複数あることをみてみましょう。同じ距離集合 L を生成する点集合はホモメトリック (homometric) である、と定義します。まず、適当な二つの集合 U, V から U &Theta; V, U &oplus; V として作成した二つの集合どうしはホモメトリックであることを示しましょう。
+単なる平行移動や符号反転の他にも、解は複数ありえます。同じ距離集合 L を生成する点集合はホモメトリック (homometric) であると定義し、その関係を &cong; で表します。まず、適当な二つの集合 U, V に対して U &Theta; V と U &oplus; Vを、それぞれ要素の総当たりの引き算、総当たりの足し算と定義します。
 ;証明

@@ Line 33: / Line 33: @@
 | &nbsp;
+|
-  { 2, 3, 5, 5, 8, 10 } を与えられて、{ 0, 2, 5, 10 } を答えるのが問題になります。
+  { 2, 3, 5, 5, 8, 10 } を与えられて、<br/>{ 0, 2, 5, 10 } を答えるのが問題になります。
 |}

@@ Line 37: / Line 37: @@
 |}
 問題への解が一つみつかれば、それを一次元上で平行移動してもやはり解になります。上の L = { 2, 3, 5, 5, 8, 10 } なら、X = { 0, 2, 5, 10 } としても { 1, 3, 6, 11 } としても L を構成します。ですから一般に、解は無限個存在します。
-ここで、同じ距離集合 L を生成する点集合はホモメトリック (homometric) である、と定義しましょう。
+===複数解の存在===
-まず、適当な二つの集合 U, V から U &Theta; V, U &oplus; V として作成した二つの集合どうしはホモメトリックであることを示しましょう。
+ここでは単なる平行移動や左右反転の他にも、解が複数あることをみてみましょう。同じ距離集合 L を生成する点集合はホモメトリック (homometric) である、と定義します。まず、適当な二つの集合 U, V から U &Theta; V, U &oplus; V として作成した二つの集合どうしはホモメトリックであることを示しましょう。
 ;証明
@@ Line 52: / Line 53: @@
 式の左側が表しているのは U &oplus; { v, v ' } として生成される距離で、右側が表すのが U &Theta; { v, v ' } で生成される距離になります。U 中の値は、V 中の値と総当りで組み合わせて点集合を形成するため、上記の対応によって生成される距離集合は同じになります。また、上記の式は u = u ' の場合も成立します。これで証明が終わりました。
-===アルゴリズム===
+==点集合を求めるアルゴリズム==
 距離集合 L から点集合を予測するアルゴリズムを考えましょう。距離集合の情報は全て正確に与えられると仮定します。
 # 式 | L | = n (n &minus; 1)/2 から点集合のサイズを決定し、X = { x<sub>1</sub>, x<sub>2</sub>, ... x<sub>n</sub> } とします。
 # L 中の最大値 M<sub>1</sub> を求め、一般性を失わずに x<sub>1</sub> = 0, x<sub>n</sub> = M<sub>1</sub> とします。L からは M<sub>1</sub> を消去します。
-# 次に L 中の最大値 M<sub>2</sub> を求め、一般性を失わずに x<sub>n-1</sub> = M<sub>n-1</sub> とします。L からは M<sub>2</sub> を消去し、同時に M<sub>1</sub> &minus; M<sub>2</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 の中に見つからない場合、左右の選択が誤っていたことになります。その場合はバックトラックして、もう一方の選択を選ばなくてはなりません。

@@ Line 2: / Line 2: @@
 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 &minus; 0, 5 &minus; 0, 10 &minus; 0,
 :::5 &minus; 2, 10 &minus; 2,
 :::10 &minus; 5}<br/>
 :: = { 2, 3, 5, 5, 8, 10 }
+|
 {| class="wikitable"
@@ Line 30: / Line 31: @@
 | || || ||
 |}
 |}
-問題への解が一つみつかれば、それを一次元上で平行移動してもやはり解になります。上の ''L'' = { 2, 3, 5, 5, 8, 10 } なら、''X'' = {0, 2, 5, 10} としても {1, 3, 6, 11} としても ''L''を構成します。ですから一般に、解は無限個存在します。ここでは、同じ距離集合 ''L'' を生成する点集合はホモメトリックで(homometric) である、と定義しましょう。
+問題への解が一つみつかれば、それを一次元上で平行移動してもやはり解になります。上の L = { 2, 3, 5, 5, 8, 10 } なら、X = { 0, 2, 5, 10 } としても { 1, 3, 6, 11 } としても L を構成します。ですから一般に、解は無限個存在します。
-集合 ''U'', ''V'' から ''U'' &Theta; ''V'', ''U'' &oplus; ''V'' として作成した二つの集合であれば、ホモメトリックであることを示します。
 ;証明
-与えられた集合 ''U'' に対して、''V''に要素を一つずつ加えていく場合を考えます。
+与えられた集合 U に対して、V に要素を一つずつ加えていく場合を考えます。
-''V'' に順次新しい要素 ''v'' を加え、''v + u'' と ''v - u'' (''u'' &isin; ''U'') で新たに生成される距離集合を、数学的帰納法で考えましょう。
+V に順次新しい要素 v を加え、v + u と v &minus; u (u &isin; U) で新たに生成される距離集合を、数学的帰納法で考えましょう。
-* ''V'' = {} のとき
+* V = { } のとき
-生成される点集合は ''U'' の要素を -''v'', +''v'' して平行移動するだけなので、同じ距離集合 ''L'' をつくることは自明。
+生成される点集合は U の要素を &minus; v, + v して平行移動するだけなので、同じ距離集合 L をつくることは自明。
-* ''V'' &ne; {} のとき
+* V &ne; { } のとき
-帰納法の仮定から ''U'' &Theta; ''V'', ''U'' &oplus; ''V'' の作る距離集合が同じとし、''V'' に要素 ''v'' を追加する場合を考えます。点集合には ''U'' の要素を -''v'', +''v'' した点がそれぞれ追加されます。一般形として、 ''U'' に既に含まれていた要素 ''u'' ' を ''v'' ' だけシフトした点と、要素 ''u'' を ''v'' だけシフトする点との間の距離を考えましょう。シフトが正の場合の距離は以下のように、負のシフトに変形できます。
+帰納法の仮定から U &Theta; V, U &oplus; V の作る距離集合が同じとし、V に要素 v を追加する場合を考えます。点集合には U の要素を &minus; v, + v した点がそれぞれ追加されます。一般形として、 U に既に含まれていた要素 u ' を v ' だけシフトした点と、要素 u を v だけシフトする点との間の距離を考えましょう。シフトが正の場合の距離は以下のように、負のシフトに変形できます。
-: ( ''u'' ' + ''v'' ' ) - ( ''u'' + ''v'' ) = ( ''u'' ' - ''v'' ) - ( ''u'' - ''v'' ' )
+: ( u ' + v ' ) &minus; ( u + v ) = ( u ' &minus; v ) &minus; ( u &minus; v ' )
-''U'' 中の値は、''V'' 中の値と総当りで組み合わせて点集合を形成するため、上記の対応によって生成される距離集合が同じことがわかります。上記の式は ''u'' = ''u''' の場合も成立します。これで証明が終わりました。
+式の左側が表しているのは U &oplus; { v, v ' } として生成される距離で、右側が表すのが U &Theta; { v, v ' } で生成される距離になります。U 中の値は、V 中の値と総当りで組み合わせて点集合を形成するため、上記の対応によって生成される距離集合は同じになります。また、上記の式は u = u ' の場合も成立します。これで証明が終わりました。
 ===アルゴリズム===
-距離集合 ''L'' から点集合を予測するアルゴリズムを考えましょう。距離集合の情報は全て正確に与えられると仮定します。
+距離集合 L から点集合を予測するアルゴリズムを考えましょう。距離集合の情報は全て正確に与えられると仮定します。
-# 式 |''L''| = ''n'' (''n''-1)/2 から点集合のサイズを決定し、''X'' = { ''x''<sub>1</sub>, ''x''<sub>2</sub>, ... ''x''<sub>n</sub> } とします。
+# 式 | L | = n (n &minus; 1)/2 から点集合のサイズを決定し、X = { x<sub>1</sub>, x<sub>2</sub>, ... x<sub>n</sub> } とします。
-# ''L'' 中の最大値 ''M''<sub>1</sub> を求め、一般性を失わずに ''x''<sub>1</sub> = 0, ''x''<sub>n</sub> = ''M''<sub>1</sub> とします。''L'' からは ''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> を消去します。
-# 次に ''L'' 中の最大値 ''M''<sub>2</sub> を求め、一般性を失わずに ''x''<sub>n-1</sub> = ''M''<sub>n-1</sub> とします。''L'' からは ''M''<sub>2</sub> を消去し、同時に ''M''<sub>1</sub> &minus; ''M''<sub>2</sub> も消去できます。
+# 次に L 中の最大値 M<sub>2</sub> を求め、一般性を失わずに x<sub>n-1</sub> = M<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 中の最大値を求め、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/Algorithm/Towers of Hanoi|ハノイの塔問題]]で見たように、指数時間アルゴリズムです。

@@ Line 5: / Line 5: @@
 この断片からもとのDNA全体を推定する問題は、以下のように定式化できます。
-: '''問題'''　: 一次元上に配置された ''n'' 個の点からなる集合 ''X'' を、その全ての要素間の距離からなる（重複を含めた）集合 ''L'' ( |''L''| = ''n''(''n''-1)/2 ) から求めよ。
+: '''問題'''　: 一次元上に配置された ''n'' 個の点からなる集合 ''X'' を、その全ての要素間の距離からなる（重複を含めた）多重集合 ''L'' ( |''L''| = ''n'' (''n''-1)/2 ) から求めよ。
 {|
+|
 '''例.''' &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,
 :: = { 2, 3, 5, 5, 8, 10 }
+|
 {| class="wikitable"
-! || 0 || 2 || 5 || 10
+! ||　0 ||　2 ||　5 || 10
 |-
 ! 0
@@ Line 20: / Line 22: @@
 |-
 ! 2
-|  || || 3 || 7
+|  || || 3 || 8
 |-
 ! 5
@@ Line 30: / Line 32: @@
 |}
-問題への解が一つみつかれば、それを一次元上で平行移動してもやはり解になります。だから一般に、解は無限個存在します。
+問題への解が一つみつかれば、それを一次元上で平行移動してもやはり解になります。上の ''L'' = { 2, 3, 5, 5, 8, 10 } なら、''X'' = {0, 2, 5, 10} としても {1, 3, 6, 11} としても ''L''を構成します。ですから一般に、解は無限個存在します。ここでは、同じ距離集合 ''L'' を生成する点集合はホモメトリックで(homometric) である、と定義しましょう。
-ここで集合 ''U'', ''V'' から ''U'' &Theta; ''V'', ''U'' &oplus; ''V'' として作成した二つの集合であれば、同じ距離集合 ''L'' を生成することを示しましょう。
+集合 ''U'', ''V'' から ''U'' &Theta; ''V'', ''U'' &oplus; ''V'' として作成した二つの集合であれば、ホモメトリックであることを示します。
 ;証明
-与えられた集合 ''U'' に対して、''V''の要素を個別に考えます。
+与えられた集合 ''U'' に対して、''V''に要素を一つずつ加えていく場合を考えます。
-''V''の各要素 ''v'' に対し、''v + u'' と ''v - u'' (''u'' &isin; ''U'') で生成される集合が同じ距離集合 ''L'' をつくることは自明です。（2''v''の平行移動にあたるから。）
+''V'' に順次新しい要素 ''v'' を加え、''v + u'' と ''v - u'' (''u'' &isin; ''U'') で新たに生成される距離集合を、数学的帰納法で考えましょう。
+* ''V'' = {} のとき
-ここで数学的帰納法を用います。距離集合が等しい ''U &Theta; V'', ''U'' &oplus; ''V'' に対して、''V'' へ新たに要素を追加すると仮定しましょう。新しい要素 ''v'' が ''U'' と生成する距離集合は上記の通り同じなので、要素を追加しても距離集合は変わりません。これで証明が終わりました。
+生成される点集合は ''U'' の要素を -''v'', +''v'' して平行移動するだけなので、同じ距離集合 ''L'' をつくることは自明。
 ===アルゴリズム===
-距離集合 ''L'' から点集合を予測する際、''L'' 中の最大値を ''M<sub>0</sub>'' とするとこれが全体の幅を決定します。
+距離集合 ''L'' から点集合を予測するアルゴリズムを考えましょう。距離集合の情報は全て正確に与えられると仮定します。
-そこで、求めたい点集合の両端を [0, ''M<sub>0</sub>''] と設定し、距離集合の中から ''M<sub>0</sub>'' を消去します。次に、''L'' - { ''M<sub>0</sub>'' } の中から最大値 ''M<sub>1</sub>'' を選びます。
-これは　[0, ''M<sub>1</sub>''] から生成されているか、[''M<sub>0</sub>-M<sub>1</sub>, M<sub>0</sub>''] から生成されるかのどちらかです。ですから、左右のどちらかを選んでいく作業を続けます。
+# 式 |''L''| = ''n'' (''n''-1)/2 から点集合のサイズを決定し、''X'' = { ''x''<sub>1</sub>, ''x''<sub>2</sub>, ... ''x''<sub>n</sub> } とします。
 もし生成されるはずの断片が ''L'' の中に見つからない場合、左右の選択が誤っていたことになります。その場合はバックトラックして、もう一方の選択を選ばなくてはなりません。