string - Gusfield 对动态规划算法的描述是否有错误，该算法用于寻找具有恒定空位惩罚的全局比对？

Question

Gusfield(关于字符串、树和序列的算法，第 11.8.6 节)描述了一种动态规划算法，用于在假设将惩罚分配给长度为 x 的间隙的情况下，找到两个序列 A 和 B 之间的最佳对齐方式对于常量 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]。
• E(i,j) 是这些前缀对齐的最佳得分 在 B[j] 与 A 中的空位配对的条件下。
• F(i,j) 是这些前缀对齐的最佳得分 在 A[i] 与 B 中的缺口配对的条件下。
• 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 的算法似乎无法正确处理这种情况。

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

欢迎评论/批评。

Answer 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]

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