Блог

Гусфилд (Алгоритмы для строк, деревьев и последовательностей, раздел 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 = ppppppp … p и B = qqqqq …q с p и q разными. Выравнивание, которое полностью отделяет A от B:

 A-
-B
  

должно оцениваться как -2R (оно имеет два разрыва), и поэтому это выравнивание в конечном итоге является оптимальным при условии, что w (p, q)<0.

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

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

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

Да, два уравнения на самом деле неверны. Они должны быть

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-длинный разрыв (индексы против [i-l 1:i]).