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.   je sličnost karaktera „a“i „b“. Na primer, ako bi matrica sličnosti bila

A G C T
A 10 -1 -3 -4
G -1 7 -5 -3
C -3 -5 9 0
T -4 -3 0 8

Onda bi poravnanje:

AGACTAGTTAC
CGA‒‒‒GACGT

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

 
 

Da bi pronašli poravnanje sa najvećim rezultatom, dvo dimenzioni niz ili matrica „F“ je alocirana.  . 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  . Hirsbergov algoritam ima samo podskup niza u memoriji i koristi   prostor, ali je sličan Nidlmen-Vanšovom algoritmu i jos uvek zahteva   vreme. Kako algoritam napreduje,   će biti dodeljeno optimalnom rezultatu za poravnanje prvog   karaktera u „A“ i prvog   u „B“. Belmanova jednačina je primenjena i sledi ispod:

  • Osnovno:
 
 
  • Rekurzija, bazirana na principu optimalnosti
 

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   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   i   su poravnati, Ako je Delete onda  je poravnato sa „rupom“ i ako je Insert onda je   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.  .

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

уреди
  1. ^ а б Needleman, Saul B. & Wunsch, Christian D. (1970). „A general method applicable to the search for similarities in the amino acid sequence of two proteins”. Journal of Molecular Biology. 48 (3): 443—53. PMID 5420325. doi:10.1016/0022-2836(70)90057-4.  Пронађени су сувишни параметри: |lastauthoramp= и |last-author-amp= (помоћ)
  2. ^ Sankoff D (1972). „Matching sequences under deletion/insertion constraints”. Proceedings of the National Academy of Sciences of the USA. 69 (1): 4—6. PMC 427531 . PMID 4500555. doi:10.1073/pnas.69.1.4. 
  3. ^ Vintsyuk TK (1968). „Speech discrimination by dynamic programming”. Kibernetika. 4: 81—88. 
  4. ^ Wagner RA, Fischer MJ (1974). „The string-to-string correction problem”. Journal of the ACM. 21 (1): 168—173. doi:10.1145/321796.321811. 
  5. ^ Sellers PH (1974). „On the theory and computation of evolutionary distances”. SIAM Journal on Applied Mathematics. 26 (4): 787—793. doi:10.1137/0126070.