sequence-alignment - ギャップペナルティ関数を使用したグローバルアライメント

Question

次の問題で私を助けることができる体はありますか?!

パラメーター k について、2 つの文字列間のグローバル アラインメントを計算します。ただし、アラインメントに含まれるギャップ (連続するインデルのブロック) は最大で k 個であるという制約に従います。

Answer 1

これは、シーケンス アラインメントに対する標準の動的計画法アプローチの拡張として処理できるはずです。問題は、さまざまな量のギャップを使用してそこに到達できた可能性があるため、マトリックス内の特定のセルに到達する方法が複数あることです。その結果、そこに到達するために特定の数のギャップを使用した場合に、各セルで得られる最高のスコアを追跡する必要があります。

これは、アフィン ペナルティを実装するときにギャップの長さを追跡するために使用されるのと同じ直感を使用することで実現できます。つまり、k + 1 行列を追跡することです。動的計画法のアルゴリズムは、0 番目の行列から開始します。このマトリックスは、ギャップを挿入することなく、グリッド内の任意のポイントで得られる最高のスコアを表します。マトリックス 0 から「x にギャップを追加」または「y にギャップを追加」のいずれかを選択すると、結果のスコアがマトリックス 1 に記録されます。マトリックス 1 からギャップを追加すると、マトリックス 2 に移動します。マトリックス k にいる場合、ギャップを追加することはできません。トレースバックの開始点は、スコアが最も高い右下隅になります。