任意のギャップペナルティを伴う配列アライメント

Question

私は最適な方法で2つのDNA配列をアライメントしたいと思っていますが、Lが3の倍数であればペナルティはある定数a。 Lが3の倍数でない場合、ペナルティはいくつかの定数bに対してb * Lです。

私はO（n * m）アルゴリズムを設計することになっています。ここで、nとmは最適な配列を見つけるDNA配列の長さです。しかし、これについての難しい部分は、私が拡大しているギャップの大きさを把握しなければならないということです。例えば、2つの連続したギャップがあり、さらにギャップを1つ増やした場合、スコアをL-b（L-1）で更新する必要がありますが、この状況をうまく処理するサブ問題を策定できませんでした。私は最終的なギャップの長さを「推測」するために新しいパラメータLを導入することを考えましたが、それは簡単にO（n * m）を超えます。

これらのサブ問題を効果的に策定する方法はありますか？どんな重要な観察も大いに評価されるだろう。

Answer 1

連続したギャップの意味を明確にすることはできますか？私があなたを正しく理解しているなら、あなたのシナリオの例は次のようになります： AAATTTGGGAA ---- CCCGG AAATTTCGGAA ----- GCGG しかし、両方のストランドに一致するギャップを含むことは何も成し遂げません。上記のアライメントは以下の通りです。 AAATTTGGGAACCCGG AAATTTCGGAA-GCGG ギャップペナルティは、任意の時点で1本の鎖にのみ関連している必要があります。アラインメントパラメータの変更がアラインメント出力にどのように影響するかを調べるために、biopython Pairwise2モジュール（ギャップペナルティ/ギャップ延長ペナルティを含むことができる）を調べることをお勧めします。 http://biopython.org/DIST/docs/api/Bio.pairwise2-module.html