私は配列アラインメントについて、次の質問があります。私たちは、あなたが彼らの全長にわたって整列する二つの配列を強制したいときグローバルアライメントアルゴリズムは有用であり、ローカルアライメントが領域を見つけることを知っている配列アラインメント
をまたは2つの配列間の最も高い類似性の領域を含み、そこから外側に位置合わせを構築する。
非常に長いシーケンスと小さなシーケンスのライブラリがある場合に、アライメントコストを最小限に抑えるライブラリ内の小さなシーケンスの連結を見つける最良のアルゴリズムは何ですか？
1つの単純なアプローチは、あらゆる順列を試すことです。 Sがライブラリー内の各小配列の順列のセットである場合、大きな配列をすべての配列とSに1つずつ整列させ、どの配列が最小整列コストを有するかを見ることができます。残念ながら、Sのサイズは小さなシーケンスの数が指数関数的であるため、これはCPUフレンドリではありません。
Σをアルファベット（たとえば、{A、C、G、T}）とします。 L⊆Σ*を短いライブラリシーケンスの集合とする。 L *に対する最小状態のDFA（Q、Σ、∂、q 、F）を計算する。
長いシーケンスx∈Σ*を一度に1文字ずつスキャンします。消費されたxのプレフィックスをx 'とする。すべての状態q∈Qについて、x 'と（x'）との間のレベンズ間距離の∂（q 、y）= qとなるように、すべての状態q∈Qについて、最小のcを y。 Y∈Σ*、∂（Q 、Y）= Q：| Y |空のプレフィックスεについて
は、すべての状態q∈Qのために、その Q（ε）C =分{保持します}、yとεの距離はyの長さなので、遷移グラフ上の幅優先探索を用いて初期テーブルを計算する。
x 'と文字sの表が与えられたとき、x = xの場合、yのいくつかの可能性の最小値としてc q（x）を計算します。
文字列y = yのz、sの位置合わせ。この場合のコストは、| Q |で計算できるmin q '、z：∂（q'、s z）= q（c q '（x'）+ | z |）です。幅優先検索
文字列y = y 'で、xのsを削除します。この場合のコストはc q（x '）+ 1です。
文字列yは、文字であり、tはsをtに置き換えます（またはその逆）。この場合のコストは、min q '、t：∂（q'、t）= q（c q '（x'）+1）です。終わり
、最適なアラインメントのコストが最小 Q∈F C Q（X）です。アライメントは、動的プログラムの通常の方法で再構築することができます。