Aritalab:Lecture/Bioinformatics/PartialDigestion

Revision as of 16:34, 8 November 2010

DNAの制限酵素による切断

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

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

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

証明

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

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

アルゴリズム

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

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

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

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

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