Nidlmen-Vanšov algoritam

Nidlmen-Vanš algoritam izvršava globalno poravnjanje dve sekvence (“A” I “B”). Obično se koristi u biofarmatici za poravnanje sekvenci proteina ili nukleotida. Algoritam su objavili 1970godine Saul B. Needleman i Christian D. Wunsch. .^[1] Nidlmen-Vanš algoritam je primer dinamičkog programiranja, i to je prva primena dinamičkog programiranja na poredjenje bioloških sekvenci.

Moderna prezentacija

Rezultati za poravnate karaktere su određeni matricom sličnosti. ${\displaystyle S(a,b)}$ je sličnost karaktera „a“i „b“. Na primer, ako bi matrica sličnosti bila

Onda bi poravnanje:

AGACTAGTTAC
CGA‒‒‒GACGT

sa kaznenim jazom od -5, imalo sledeći rezultat

${\displaystyle 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)}$

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

Da bi pronašli poravnanje sa najvećim rezultatom, dvo dimenzioni niz ili matrica „F“ je alocirana. ${\displaystyle F_{ij}}$. Postoji jedna kolona za svaki karakter u sekvenci „A“, i jedan red za svaki karakter u sekvenci „B“. Ako bismo poravnavali sekvence veličine „n“ i „m“, količina memorije korišcena je ${\displaystyle O(nm)}$. Hirsbergov algoritam ima samo podskup niza u memoriji i koristi ${\displaystyle \Theta (\min\{n,m\})}$ prostor, ali je sličan Nidlmen-Vanšovom algoritmu i jos uvek zahteva ${\displaystyle O(nm)}$ vreme. Kako algoritam napreduje, ${\displaystyle F_{ij}}$ će biti dodeljeno optimalnom rezultatu za poravnanje prvog ${\displaystyle i=0,\dotsc ,n}$ karaktera u „A“ i prvog ${\displaystyle j=0,\dotsc ,m}$ u „B“. Belmanova jednačina je primenjena i sledi ispod:

• Osnovno:

${\displaystyle F_{0j}=d*j}$

${\displaystyle F_{i0}=d*i}$

• Rekurzija, bazirana na principu optimalnosti

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

Pseudo kod za algoritam za izračunavanje F matrice izgleda ovako:

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)
  }

Kada je F matrica izračunata, unos ${\displaystyle F_{nm}}$ daje maksimalni rezultat između svih mogućih poravnanja. Za izračunavanje poravnanja koji zapravo daje ovakav rezultat, pocinjemo od donje desne celije i poredimo vrednost sa tri moguća izvora (Match, Insert i Delete iznad) da vidimo odakle dolazi. Ako je Match, onda ${\displaystyle A_{i}}$ i ${\displaystyle B_{j}}$ su poravnati, Ako je Delete onda ${\displaystyle A_{i}}$je poravnato sa „rupom“ i ako je Insert onda je ${\displaystyle B_{j}}$ poravnata sa „rupom“ (generalno, vise od jednog izbora može imati istu vrednost vodeci alternativnim optimalnim poravnanjima.)

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
  }
}

Istorijske beleske

Nidlmen i Vanš su opisali svoj algoritam eksplicitno za slučaj kada poravnanja imaju kaznu prema neuskladjenosti, i kada jaz nema kaznu (d=0). Originalna publikacija^[1] iz 1970 preporucuje rekurziju. ${\displaystyle 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})\}}$.

Kazneni faktor, broj oduzet za svaki jaz koji je napravljen, moze se oceniti kao barijera za dozvoljavanje jaza. Kazneni faktor može biti funkcija veličine i/ili pravac jaza.

Bolji algoritam dinamičkog programiranja sa kvadratnim vremenom izvršavanja istog problema(nema kaznenog jaza) bio je prvi put objavljen u^[2] od Dejvida Sankofa 1972 godine.

Slični kvadratni algoritmi bili su osmisljeni nezavisno T. K. Vintsyuk^[3] 1968 godine za obradu govora. ("time warping"), i Robert A. Wagner iMichael J. Fischer^[4] 1974godine za poklapanje stringa.

Nidlmen i Vanš su formulisali problem kao maksimizaciju sličnosti. Druga mogućnost za minimizaciju je Levenštajnovo rastojanje izmedju sekvenci koje je predstavio Vladimir Levenshtein. Peter H. Sellers je pokazao u^[5] 1974godine da su ova dva problema ekvivalentna.

Reference