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. 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. 1,0 1,1 Needleman, Saul B.; and 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. doi:10.1016/0022-2836(70)90057-4. PMID 5420325. 
  2. Sankoff D (1972). „Matching sequences under deletion/insertion constraints”. Proceedings of the National Academy of Sciences of the USA 69 (1): 4—6. doi:10.1073/pnas.69.1.4. PMC 427531. PMID 4500555. 
  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.