Aritalab:Lecture/Bioinformatics/PartialDigestion

From Metabolomics.JP
< Aritalab:Lecture | Bioinformatics(Difference between revisions)
Jump to: navigation, search
m
Line 5: Line 5:
 
この断片からもとのDNA全体を推定する問題は、以下のように定式化できます。
 
この断片からもとのDNA全体を推定する問題は、以下のように定式化できます。
  
−
: '''問題'''　: 一次元上に配置された ''n'' 個の点からなる集合 ''X'' を、その全ての要素間の距離からなる（重複を含めた）集合 ''L'' ( |''L''| = ''n''(''n''-1)/2 ) から求めよ。
+
: '''問題'''　: 一次元上に配置された ''n'' 個の点からなる集合 ''X'' を、その全ての要素間の距離からなる（重複を含めた）多重集合 ''L'' ( |''L''| = ''n'' (''n''-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 }
 
|
 
|
 
{| class="wikitable"
 
{| class="wikitable"
−
! || 0 || 2 || 5 || 10
+
! ||　0 ||　2 ||　5 || 10
 
|-
 
|-
 
! 0
 
! 0
Line 20: Line 22:
 
|-
 
|-
 
! 2
 
! 2
−
|  || || 3 || 7
+
|  || || 3 || 8
 
|-
 
|-
 
! 5  
 
! 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'' をつくることは自明。
 +
* ''V'' &ne; {} のとき
 +
帰納法の仮定から ''U'' &Theta; ''V'', ''U'' &oplus; ''V'' の作る距離集合が同じとし、''V'' に要素 ''v'' を追加する場合を考えます。点集合には ''U'' の要素を -''v'', +''v'' した点がそれぞれ追加されます。一般形として、 ''U'' に既に含まれていた要素 ''u'' ' を ''v'' ' だけシフトした点と、要素 ''u'' を ''v'' だけシフトする点との間の距離を考えましょう。シフトが正の場合の距離は以下のように、負のシフトに変形できます。
 +
: ( ''u'' ' + ''v'' ' ) - ( ''u'' + ''v'' ) = ( ''u'' ' - ''v'' ) - ( ''u'' - ''v'' ' )
 +
''U'' 中の値は、''V'' 中の値と総当りで組み合わせて点集合を形成するため、上記の対応によって生成される距離集合が同じことがわかります。上記の式は ''u'' = ''u''' の場合も成立します。これで証明が終わりました。
  
 
===アルゴリズム===
 
===アルゴリズム===
−
距離集合 ''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'' 中の最大値 ''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'' 中の最大値を求め、''x''<sub>i</sub> とできる ''i'' を見つけて配置していきます。
 +
 
  
 
もし生成されるはずの断片が ''L'' の中に見つからない場合、左右の選択が誤っていたことになります。その場合はバックトラックして、もう一方の選択を選ばなくてはなりません。
 
もし生成されるはずの断片が ''L'' の中に見つからない場合、左右の選択が誤っていたことになります。その場合はバックトラックして、もう一方の選択を選ばなくてはなりません。

Revision as of 01:21, 10 November 2010

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

問題への解が一つみつかれば、それを一次元上で平行移動してもやはり解になります。上の 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に要素を一つずつ加えていく場合を考えます。 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 中の値と総当りで組み合わせて点集合を形成するため、上記の対応によって生成される距離集合が同じことがわかります。上記の式は u = u' の場合も成立します。これで証明が終わりました。

アルゴリズム

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

  1. 式 |L| = n (n-1)/2 から点集合のサイズを決定し、X = { x1, x2, ... xn } とします。
  2. L 中の最大値 M1 を求め、一般性を失わずに x1 = 0, xn = M1 とします。L からは M1 を消去します。
  3. 次に L 中の最大値 M2 を求め、一般性を失わずに xn-1 = Mn-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=254787"
Personal tools
Namespaces

Variants
Actions
Navigation
metabolites
Toolbox