Aritalab:Lecture/Bioinformatics/PartialDigestion
From Metabolomics.JP
< Aritalab:Lecture | Bioinformatics(Difference between revisions)
m |
m (→複数解の存在) |
||
| (5 intermediate revisions by one user not shown) | |||
| Line 2: | Line 2: | ||
DNAを制限酵素で処理したとき、制限酵素の認識配列部分は確率的に切断されたり、されなかったりします。 | DNAを制限酵素で処理したとき、制限酵素の認識配列部分は確率的に切断されたり、されなかったりします。 | ||
| − | + | 従って、処理後の DNA 断片をゲル電気泳動で流して長さを確認すると、もとの DNA 中の認識配列位置間を組み合わせ的に選んで生じる断片が出てくるはずです。 | |
| − | + | この断片からもとの DNA 全体を推定する問題は、以下のように定式化できます。 | |
| − | : '''問題''' : 一次元上に配置された | + | : '''問題''' : 一次元上に配置された n 個の点からなる集合 X を、その全ての要素間の距離からなる（重複を含めた）多重集合 L ( | L | = n (n − 1)/2 ) から求めよ。 |
{| | {| | ||
| | | | ||
| − | '''例.''' ''X'' = { 0, 2, 5, 10} のとき<br/> | + | '''例.''' ''X'' = { 0, 2, 5, 10 } のとき<br/> |
: ''L'' = { 2 − 0, 5 − 0, 10 − 0, | : ''L'' = { 2 − 0, 5 − 0, 10 − 0, | ||
:::5 − 2, 10 − 2, | :::5 − 2, 10 − 2, | ||
:::10 − 5}<br/> | :::10 − 5}<br/> | ||
:: = { 2, 3, 5, 5, 8, 10 } | :: = { 2, 3, 5, 5, 8, 10 } | ||
| + | | | ||
| | | | ||
{| class="wikitable" | {| class="wikitable" | ||
| Line 30: | Line 31: | ||
| || || || | | || || || | ||
|} | |} | ||
| + | | | ||
| + | | | ||
| + | { 2, 3, 5, 5, 8, 10 } を与えられて、<br/>{ 0, 2, 5, 10 } を答えるのが問題になります。 | ||
| + | |||
|} | |} | ||
| − | + | ==問題の性質== | |
| − | + | 問題への解が一つみつかれば、それを一次元上で平行移動または符号を反転してもやはり解になります。上の L = { 2, 3, 5, 5, 8, 10 } なら、X = { 0, 2, 5, 10 } としても { 1, 3, 6, 11 } としても L を構成します。ですから一般に、解は無限個存在します。 | |
| − | + | ===複数解の存在=== | |
| − | + | 単なる平行移動や符号反転の他にも、解は複数ありえます。同じ距離集合 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 ' の場合も成立します。これで証明が終わりました。 | ||
| − | + | ==点集合を求めるアルゴリズム== | |
| − | + | 距離集合 L から点集合を予測するアルゴリズムを考えましょう。距離集合の情報は全て正確に与えられると仮定します。 | |
| − | + | ||
| − | + | ||
| + | ===基本方針=== | ||
| + | # 式 | L | = n (n − 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>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> − M<sub>2</sub> を消去します。 | ||
| + | # 以降、順次 L 中の最大値を求め、x<sub>i</sub> とできる i を見つけて配置していきます。 | ||
| − | もし生成されるはずの断片が | + | もし生成されるはずの断片が L の中に見つからない場合、左右の選択が誤っていたことになります。その場合はバックトラックして、もう一方の選択を選ばなくてはなりません。 |
| − | + | このアルゴリズムは、各ステップで常に左右の選択が生じるため、n 点を予測するための計算時間を T(n) とすると | |
| − | : | + | : T( n ) = 2 T(n − 1) + O( n ) 時間 |
| − | かかります。これは[[Aritalab:Lecture/ | + | かかります。これは[[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 } のとき
|
|
{ 2, 3, 5, 5, 8, 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] 基本方針
- 式 | L | = n (n − 1)/2 から点集合のサイズを決定し、X = { x1, x2, ... xn } とします。
- L 中の最大値 M1 を求め、一般性を失わずに x1 = 0, xn = M1 とします。L からは M1 を消去します。
- 次に L 中の最大値 M2 を求めます。この値は、x1 (= 0) から M2 の所に点があるか、xn (= M1) から M2 のところに点があるかのどちらかです。どちらか選んで x2 または xn-1 とします。L からは M2 と M1 − M2 を消去します。
- 以降、順次 L 中の最大値を求め、xi とできる i を見つけて配置していきます。
もし生成されるはずの断片が L の中に見つからない場合、左右の選択が誤っていたことになります。その場合はバックトラックして、もう一方の選択を選ばなくてはなりません。
このアルゴリズムは、各ステップで常に左右の選択が生じるため、n 点を予測するための計算時間を T(n) とすると
- T( n ) = 2 T(n − 1) + O( n ) 時間
かかります。これはハノイの塔問題で見たように、指数時間アルゴリズムです。
