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. . 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 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 od Dejvida Sankofa 1972 godine.
Slični kvadratni algoritmi bili su osmisljeni nezavisno T. K. Vintsyuk 1968 godine za obradu govora. ("time warping"), i Robert A. Wagner iMichael J. Fischer 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 1974godine da su ova dva problema ekvivalentna.
Reference
Категорија:Алгоритми поравнавања секвенци Категорија:Динамичко програмирање