3

Gusfield（关于字符串、树和序列的算法，第 11.8.6 节）描述了一种动态规划算法，用于在两个序列 A 和 B 之间找到最佳比对，假设惩罚分配给一个比对中长度为 x 的间隙对于常数 R 和 S，序列的形式为 R+Sx。在 S=0 的特殊情况下，开始一个间隙会受到惩罚，但延长它不会受到惩罚。在我看来，Gusfield 的公式中存在错误，我希望有人能帮助我了解真实情况。

Gusfield 定义了四个函数 V(i,j)、G(i,j)、E(i,j) 和 F(i,j)，具有以下属性：

  • V(i,j) 是前缀 A[1..i] 和 B[1..j] 对齐的最佳分数。
  • 在 B[j] 与 A 中的间隙配对的条件下，E(i,j) 是这些前缀对齐的最佳可能分数。
  • 在 A[i] 与 B 中的间隙配对的条件下，F(i,j) 是这些前缀对齐的最佳可能分数。
  • G(i,j) 是 A[i] 与 B[j] 配对的最佳可能分数。

i 和 j 大于或等于 1 的递归是：

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 的序列的情况，因此 A=p 和 B=q。在这种情况下，只有三种可能的对齐方式：

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（它有两个间隙），因此假设 w(p,q)<0，这种对齐最终是最优的。

Gusfield 的算法似乎不能正确处理这种情况。

在实际情况下，这可能无关紧要，因为典型的字符串有很多匹配项，因此边界情况对解决方案没有贡献。

欢迎评论/批评。

4

1 回答 1

1

是的，其中两个等式实际上是不正确的。他们应该是

F(i,j)=max(F(i,j-1),V(i,j-1)-R] E(i,j)=max(E(i-1,j),V(i-1,j)-R]

由于在 A[i] 与 B 中的间隙配对的条件下，E(i,j) 是这些前缀对齐的最佳可能分数，因此对齐由 A[1:il] 与 B 的最佳对齐组成[1:j] 和一个 l 长的间隙（插入缺失与 A[i-l+1:i] 相对）。

于 2014-06-23T07:43:15.930 回答