3

最小のサブシーケンス長の制約でシーケンスアラインメントを実装するにはどうすればよいですか。たとえば、これらの入力の最小サブシーケンス長を3とします。Smith-Watermanを使用すると、次のような出力が得られます。

ATACGGACC
||    |||
ATCATAACC

しかし、代わりに私は以下のようにする必要があります。

---ATACGGACC
   |||   |||
ATCATA---ACC

このための既知のアルゴリズムはありますか、それともアプローチを知っていますか？

前もって感謝します。

4

2 に答える 2

3

スミス-ウォーターマンがどのように機能するかを見てください。2つのシーケンス（長さNのS1、長さMのS2）があり、NxM行列（Aと呼びましょう）を作成します。ここで、A（i、j）は「S1[1..i]とS2の最良のスコアアラインメントです。 [1..j]。」これを行うには、最後の要素に基づいてA（i、j）を取得する方法についての繰り返しを記述します-A（i、j）は

A(i-1, j-1) + match/mismatch score
A(i,j-1) + indel score
A(i-1,j) + indel score

これが基本的な考え方です。あなたはそれを少し微調整する必要があるかもしれません。

あなたが求めていることをするために、あなたは2つの行列を必要とします。A（i、j）を「一致で終わるS1[1..i]とS2[1..j]の最高スコアの配置」とし、B（i、j）を「S1[の最高スコアの配置」とします。 1..i]とS2[1..j]はインデルで終わります。」

簡単なので、Bから始めましょう。B（i、j）は最高です

A(i,j-1) + indel score
A(i-1,j) + indel score
B(i,j-1) + indel score
B(i-1,j) + indel score

そしてA（i、j）は最高です 

A(i-1, j-1) + match/mismatch score
B(i-3, j-3) + match/mismatch score for the three
于 2013-01-13T05:13:29.033 に答える
1

アルゴリズムは、すべての可能なサブシーケンスの2Dテーブルを効果的に返します。実際のサブシーケンスを追加するという追加の作業を行う必要がありますが、これは明らかにあなたが行っていることです。アラインメント（バック）トラッキング中に、アドミッションチェックを行うことができます。

if(subsequence.length() > 2)
     results.add(subsequence);

私が述べたように行きたくない場合は、実際のサブシーケンスを取得するために使用しているコードを表示してもよろしいですか？編集する場所を表示できるかもしれません。

于 2013-01-12T17:24:18.523 に答える