3

Gusfield (Algorithms on Strings, Trees, and Sequences, Section 11.8.6) は、2 つのシーケンス A と B の間の最適なアラインメントを見つけるための動的計画法アルゴリズムについて説明しています。シーケンスは、定数 R および S に対して R+Sx の形式です。S=0 の特殊なケースでは、ギャップを開始することにはペナルティがありますが、それを長くすることにはペナルティはありません。ガスフィールドの式には誤りがあるように思われます。誰かが私に本当の状況を理解するのを手伝ってくれることを願っています.

Gusfield は、次のプロパティを持つ 4 つの関数 V(i,j)、G(i,j)、E(i,j)、および F(i,j) を定義します。

  • V(i,j) は、プレフィックス A[1..i] と B[1..j] のアラインメントで可能な最高のスコアです。
  • E(i,j) は、B[j] が A のギャップに対してペアになっているという条件の下で、これらの接頭辞のアラインメントの可能な最高のスコアです。
  • F(i,j) は、A[i] が B のギャップに対してペアになっているという条件の下で、これらの接頭辞のアラインメントの可能な最高のスコアです。
  • G(i,j) は、A[i] と B[j] をペアにするアラインメントの可能な最高のスコアです。

1 以上の i と j の再帰は次のとおりです。

V(i,j)=max[E(i,j),F(i,j),G(i,j)]
G(i,j)=V(i,j)+w(A[i],B[j]) where w is the score for a match/mismatch.
E(i,j)=max(E(i,j-1),V(i,j-1)-R]
F(i,j)=max(F(i-1,j),V(i-1,j)-R]

最後に、境界条件は次のように与えられます。

V(i,0)=E(i,0)=-R
V(0,j)=F(0,j)=-R

準備として、それぞれ長さが 1 のシーケンスが 2 つあり、A=p および B=q である状況を考えてみましょう。この状況で可能なアラインメントは 3 つだけです。

p    p-    -p
q    -q    q-

これらには、それぞれ w(p,q)、-2R、-2R のスコアがあります。特に、E(0,1)=F(1,0)=-2R とする必要があります。ただし、反復により、E(0,1) と F(1,0) は両方とも -R 以上になります。

境界条件のこのエラーは結果をもたらします。たとえば、A=pppppp...p および B=qqqq...q で、p と q が異なるとします。A を B から完全に離す配置:

A-
-B

スコアは -2R (ギャップが 2 つある) であるため、w(p,q)<0 と仮定すると、このアライメントは最終的に最適になります。

Gusfield のアルゴリズムは、このケースを正しく処理していないようです。

実際の状況では、これはおそらく問題ではありません。典型的な文字列には多くの一致があり、境界ケースは解決に寄与しないためです。

コメント/批評を歓迎します。

4

1 に答える 1