Нидлмен-Ваншов алгоритам

Нидлмен-Ванш алгоритам извршава глобално поравњање две секвенце (“А” I “Б”). Обично се користи у биофарматици за поравнање секвенци протеина или нуклеотида. Алгоритам су објавили 1970године Саул Б. Неедлеман и Цхристиан D. Wунсцх. . Нидлмен-Ванш алгоритам је пример динамичког програмирања, и то је прва примена динамичког програмирања на поредјење биолошких секвенци.

Модерна презентација

Резултати за поравнате карактере су одређени матрицом сличности. $S(a,b)$ је сличност карактера „а“и „б“. На пример, ако би матрица сличности била

	А	Г	C	Т
А	10	-1	-3	-4
Г	-1	7	-5	-3
C	-3	-5	9	0
Т	-4	-3	0	8

Онда би поравнање:

AGACTAGTTAC
CGA‒‒‒GACGT

са казненим јазом од -5, имало следећи резултат

$S(A,C)+S(G,G)+S(A,A)+(3\times d)+S(G,G)+S(T,A)+S(T,C)+S(A,G)+S(C,T)$

$=-3+7+10-(3\times 5)+7+-4+0+-1+0=1$

Да би пронашли поравнање са највећим резултатом, дво димензиони низ или матрица „Ф“ је алоцирана. $F_{ij}$. Постоји једна колона за сваки карактер у секвенци „А“, и један ред за сваки карактер у секвенци „Б“. Ако бисмо поравнавали секвенце величине „н“ и „м“, количина меморије коришцена је $O(nm)$. Хирсбергов алгоритам има само подскуп низа у меморији и користи $\Theta (\min\{n,m\})$ простор, али је сличан Нидлмен-Ваншовом алгоритму и јос увек захтева $O(nm)$ време. Како алгоритам напредује, $F_{ij}$ ће бити додељено оптималном резултату за поравнање првог $i=0,\dotsc ,n$ карактера у „А“ и првог $j=0,\dotsc ,m$ у „Б“. Белманова једначина је примењена и следи испод:

• Основно:

$F_{0j}=d*j$

$F_{i0}=d*i$

• Рекурзија, базирана на принципу оптималности

$F_{ij}=\max(F_{i-1,j-1}+S(A_{i},B_{j}),\;F_{i,j-1}+d,\;F_{i-1,j}+d)$

Псеудо код за алгоритам за израчунавање Ф матрице изгледа овако:

for i=0 to length(A)
  F(i,0) ← d*i
for j=0 to length(B)
  F(0,j) ← d*j
for i=1 to length(A)
  for j=1 to length(B)
  {
    Match ← F(i-1,j-1) + S(Ai, Bj)
    Delete ← F(i-1, j) + d
    Insert ← F(i, j-1) + d
    F(i,j) ← max(Match, Insert, Delete)
  }

Када је Ф матрица израчуната, унос $F_{nm}$ даје максимални резултат између свих могућих поравнања. За израчунавање поравнања који заправо даје овакав резултат, поцињемо од доње десне целије и поредимо вредност са три могућа извора (Матцх, Инсерт и Делете изнад) да видимо одакле долази. Ако је Матцх, онда $A_{i}$ и $B_{j}$ су поравнати, Ако је Делете онда $A_{i}$је поравнато са „рупом“ и ако је Инсерт онда је $B_{j}$ поравната са „рупом“ (генерално, висе од једног избора може имати исту вредност водеци алтернативним оптималним поравнањима.)

AlignmentA ← ""
AlignmentB ← ""
i ← length(A)
j ← length(B)
while (i > 0 or j > 0)
{
  if (i > 0 and j > 0 and F(i,j) == F(i-1,j-1) + S(Ai, Bj))
  {
    AlignmentA ← Ai + AlignmentA
    AlignmentB ← Bj + AlignmentB
    i ← i - 1
    j ← j - 1
  }
  else if (i > 0 and F(i,j) == F(i-1,j) + d)
  {
    AlignmentA ← Ai + AlignmentA
    AlignmentB ← "-" + AlignmentB
    i ← i - 1
  }
  else (j > 0 and F(i,j) == F(i,j-1) + d)
  {
    AlignmentA ← "-" + AlignmentA
    AlignmentB ← Bj + AlignmentB
    j ← j - 1
  }
}

Историјске белеске

Нидлмен и Ванш су описали свој алгоритам експлицитно за случај када поравнања имају казну према неускладјености, и када јаз нема казну (д=0). Оригинална публикација из 1970 препоруцује рекурзију. $F_{ij}=\max _{h<i,k<j}\{F_{h,j-1}+S(A_{i},B_{j}),F_{i-1,k}+S(A_{i},B_{j})\}$.

Казнени фактор, број одузет за сваки јаз који је направљен, мозе се оценити као баријера за дозвољавање јаза. Казнени фактор може бити функција величине и/или правац јаза.

Бољи алгоритам динамичког програмирања са квадратним временом извршавања истог проблема(нема казненог јаза) био је први пут објављен у од Дејвида Санкофа 1972 године.

Слични квадратни алгоритми били су осмисљени независно Т. К. Винтсyук 1968 године за обраду говора. ("тиме wарпинг"), и Роберт А. Wагнер иМицхаел Ј. Фисцхер 1974године за поклапање стринга.

Нидлмен и Ванш су формулисали проблем као максимизацију сличности. Друга могућност за минимизацију је Левенштајново растојање измедју секвенци које је представио Владимир Левенсхтеин. Петер Х. Селлерс је показао у 1974године да су ова два проблема еквивалентна.