Есть ли ошибка в описании Гусфилдом алгоритма динамического программирования для нахождения глобальных выравниваний с постоянным штрафом за пробел?

Question

Гасфилд (Алгоритмы на строках, деревьях и последовательностях, раздел 11.8.6) описывает алгоритм динамического программирования для нахождения наилучшего выравнивания между двумя последовательностями A и B в предположении, что штраф назначен промежутку длины x в одной из выровненных последовательности имеют форму R+Sx для констант R и S. В особом случае, когда S=0, есть штраф за начало промежутка, но не штраф за его удлинение. Мне кажется, что в формулах Гусфилда есть ошибка, и я надеюсь, что кто-то может помочь мне понять истинное положение дел.

Гасфилд определяет четыре функции 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

Учитывая все это в качестве предварительных, рассмотрим ситуацию, когда у нас есть две последовательности, каждая длиной одна, так что 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.

Алгоритм Гасфилда, кажется, не обрабатывает этот случай правильно.

В практических ситуациях это, вероятно, не имеет значения, потому что типичные строки имеют много совпадений, и поэтому граничные случаи не способствуют решению.

Комментарии / критика приветствуются.

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:il] по отношению к B[1:j] и пробел длиной в l (индели против A[i-l+1:i]).