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(A_i, B_j)
    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_{i}$ je 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(A_i, B_j))
  {
    AlignmentA ← A_i + AlignmentA
    AlignmentB ← B_j + AlignmentB
    i ← i - 1
    j ← j - 1
  }
  else if (i > 0 and F(i,j) == F(i-1,j) + d)
  {
    AlignmentA ← A_i + AlignmentA
    AlignmentB ← "-" + AlignmentB
    i ← i - 1
  }
  else (j > 0 and F(i,j) == F(i,j-1) + d)
  {
    AlignmentA ← "-" + AlignmentA
    AlignmentB ← B_j + 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

^ ^а ^б 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= (помоћ)
^ 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.
^ Vintsyuk TK (1968). „Speech discrimination by dynamic programming”. Kibernetika. 4: 81—88.
^ Wagner RA, Fischer MJ (1974). „The string-to-string correction problem”. Journal of the ACM. 21 (1): 168—173. doi:10.1145/321796.321811.
^ Sellers PH (1974). „On the theory and computation of evolutionary distances”. SIAM Journal on Applied Mathematics. 26 (4): 787—793. doi:10.1137/0126070.

[Needleman-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= (помоћ)

[Sankoff-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.

[Vintsyuk-3] Vintsyuk TK (1968). „Speech discrimination by dynamic programming”. Kibernetika. 4: 81—88.

[WagnerFischer-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.

[Sellers-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.

[1]

[2]

[3]

[4]

[5]