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

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

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

Резултати за поравнате карактере су одређени матрицом сличности. $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(A_i, B_j)
    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(A_i, B_j))
  {
    AlignmentA ← A_i + AlignmentA
    AlignmentB ← B_j + AlignmentB
    i ← i - 1
    j ← j - 1
  }
  else if (i > 0 and F(i,j) == F(i-1,j) + d)
  {
    AlignmentA ← A_i + AlignmentA
    AlignmentB ← "-" + AlignmentB
    i ← i - 1
  }
  else (j > 0 and F(i,j) == F(i,j-1) + d)
  {
    AlignmentA ← "-" + AlignmentA
    AlignmentB ← B_j + AlignmentB
    j ← j - 1
  }
}

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

Нидлмен и Ванш су описали свој алгоритам експлицитно за случај када поравнања имају казну према неускладјености, и када јаз нема казну (д=0). Оригинална публикација^[1] из 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})\}$ .

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

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

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

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

Референце

^ ^а ^б Неедлеман, Саул Б. & Wунсцх, Цхристиан D. (1970). „А генерал метход апплицабле то тхе сеарцх фор симиларитиес ин тхе амино ацид сеqуенце оф тwо протеинс”. Јоурнал оф Молецулар Биологy. 48 (3): 443—53. ПМИД 5420325. дои:10.1016/0022-2836(70)90057-4. Пронађени су сувишни параметри: |ластаутхорамп= и |ласт-аутхор-амп= (помоћ)
^ Санкофф D (1972). „Матцхинг сеqуенцес ундер делетион/инсертион цонстраинтс”. Процеедингс оф тхе Натионал Ацадемy оф Сциенцес оф тхе УСА. 69 (1): 4—6. ПМЦ 427531  . ПМИД 4500555. дои:10.1073/пнас.69.1.4.
^ Винтсyук ТК (1968). „Спеецх дисцриминатион бy дyнамиц программинг”. Кибернетика. 4: 81—88.
^ Wагнер РА, Фисцхер МЈ (1974). „Тхе стринг-то-стринг цоррецтион проблем”. Јоурнал оф тхе АЦМ. 21 (1): 168—173. дои:10.1145/321796.321811.
^ Селлерс ПХ (1974). „Он тхе тхеорy анд цомпутатион оф еволутионарy дистанцес”. СИАМ Јоурнал он Апплиед Матхематицс. 26 (4): 787—793. дои:10.1137/0126070.

[Needleman-1] а ^б Неедлеман, Саул Б. & Wунсцх, Цхристиан D. (1970). „А генерал метход апплицабле то тхе сеарцх фор симиларитиес ин тхе амино ацид сеqуенце оф тwо протеинс”. Јоурнал оф Молецулар Биологy. 48 (3): 443—53. ПМИД 5420325. дои:10.1016/0022-2836(70)90057-4. Пронађени су сувишни параметри: |ластаутхорамп= и |ласт-аутхор-амп= (помоћ)

[Sankoff-2] Санкофф D (1972). „Матцхинг сеqуенцес ундер делетион/инсертион цонстраинтс”. Процеедингс оф тхе Натионал Ацадемy оф Сциенцес оф тхе УСА. 69 (1): 4—6. ПМЦ 427531  . ПМИД 4500555. дои:10.1073/пнас.69.1.4.

[Vintsyuk-3] Винтсyук ТК (1968). „Спеецх дисцриминатион бy дyнамиц программинг”. Кибернетика. 4: 81—88.

[WagnerFischer-4] Wагнер РА, Фисцхер МЈ (1974). „Тхе стринг-то-стринг цоррецтион проблем”. Јоурнал оф тхе АЦМ. 21 (1): 168—173. дои:10.1145/321796.321811.

[Sellers-5] Селлерс ПХ (1974). „Он тхе тхеорy анд цомпутатион оф еволутионарy дистанцес”. СИАМ Јоурнал он Апплиед Матхематицс. 26 (4): 787—793. дои:10.1137/0126070.

[1]

[2]

[3]

[4]

[5]