string - 配列アラインメント

Question

配列アラインメントについて次の質問があります。

グローバル アラインメントアルゴリズムは、2 つの配列をその全長にわたって強制的にアラインさせたい場合に役立ちます。ローカル アラインメントは、2 つの配列間で類似性が最も高い領域を見つけて、そこから外側に向かってアラインメントを構築します。

非常に長い 1 つのシーケンスと小さなシーケンスのライブラリがある場合、アライメント コストを最小化するライブラリ内の小さなシーケンスの連結を見つけるための最適なアルゴリズムは何ですか?

Answer 1

∑ をアルファベットとします (例: {A, C, G, T})。L ⊆ ∑* を短いライブラリ シーケンスのセットとします。L*の最小状態 DFA (Q, ∑, ∂, q _{0 , F) を計算します。}

長いシーケンス x ∈ ∑* を一度に 1 文字スキャンします。x' を、消費された x のプレフィックスとします。すべての状態 q ∈ Q について、 x' と y の間のレーベンシュタイン距離の [∂(q ₀ , y) = q となるすべてのシーケンス y ∈ ∑*] にわたる最小 c _{q (x') を維持します。}

空の接頭辞 ε の場合、すべての状態 q ∈ Q について、c _q (ε) = min {|y|: y ∈ ∑*, ∂(q ₀ , y) = q} となります。 ε は y の長さです。遷移グラフで幅優先探索を使用して初期テーブルを計算します。

x' と文字 s の表が与えられると、x = x' s である y のいくつかの可能性の最小値としてc _{q (x) を計算します。}

1. 文字列 y = y' sz、s を並べます。この場合のコストは min _{q', z: ∂(q', sz) = q} (c _q' (x') + |z|) であり、|Q| で計算できます。幅優先検索。

2. 文字列 y = y'、x の s を削除します。この場合のコストは c _q (x') + 1 です。

3. 文字列 y = y' t ここで、t は文字で、t を s に置き換えます (またはその逆)。この場合のコストは min _{q', t: ∂(q', t) = q} (c _q' (x') + 1) です。

最後に、最適なアライメント コストは min _{q ∈ F} c _q (x) です。アラインメントは、動的プログラムの通常の方法で再構築できます。

Answer 2

単純なアプローチの 1 つは、すべての順列を試すことです。がライブラリ内の各小さなシーケンスの順列のセットである場合S、大きなシーケンスを 内のすべてのシーケンスとS1 つずつ整列させ、どれが最小の整列コストを持つかを確認できます。残念ながら、これは CPU に優しくありません。なぜなら、 のサイズSは小さなシーケンスの数で指数関数的になるからです。