Гасфилд (Алгоритмы для строк, деревьев и последовательностей, раздел 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.
Алгоритм Гасфилда, похоже, неправильно обрабатывает этот случай.
В практических ситуациях это, вероятно, не имеет значения, потому что типичные строки имеют много совпадений, поэтому граничные случаи не влияют на решение.
Комментарии/критика приветствуются.
