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. S(a, b) 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

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

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

  • Osnovno:
F_{0j} = d*j
F_{i0} = d*i
  • Rekurzija, bazirana na principu optimalnosti
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 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 A_i i B_j su poravnati, Ako je Delete onda A_ije poravnato sa „rupom“ i ako je Insert onda je 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. 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[уреди]

  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.