Algoritmul Needleman-Wunsha

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 14 iulie 2016; verificările necesită 10 modificări .

Algoritmul Needleman-Wunsch este un algoritm pentru efectuarea unei alinieri a două secvențe (să le numim și ) care este utilizat în bioinformatică pentru a construi alinieri ale secvențelor de aminoacizi sau nucleotide . Algoritmul a fost propus în 1970 de Saul Needleman și Christian Wunsch [1] . $A$ $B$

Algoritmul Needleman-Wunsch este un exemplu de programare dinamică și s-a dovedit a fi primul exemplu de aplicare a programării dinamice la compararea secvențelor biologice.

Vedere modernă

Corespondența caracterelor aliniate este dată de matricea de similaritate . Iată asemănarea simbolurilor și . Se folosește și o penalizare de decalaj liniar , numită aici . $S(a,\;b)$ $A$ $b$ $d$

De exemplu, dacă matricea de similitudine este dată de tabel

-	A	G	C	T
A	zece	-unu	-3	-patru
G	-unu	7	-5	-3
C	-3	-5	9	0
T	-patru	-3	0	opt

apoi alinierea:

GTTAC‒‒ G‒‒ACGT

cu o penalizare de distanță va avea următorul scor: $d=-5$

S(G,\;G)+2\times d+S(A,\;A)+S(C,\;C)+2\times d

=7+(2\times -5)+10+9+(2\times -5)=6.

Pentru a găsi alinierea cu cel mai mare punctaj, este atribuită o matrice bidimensională (sau matrice ) , care conține atâtea rânduri câte caractere există în secvență și atâtea coloane câte caractere există în secvență . O intrare într-un rând și coloană este notată ca . Astfel, dacă aliniem secvențele de dimensiuni și , atunci cantitatea de memorie necesară va fi . ( Algoritmul lui Hirschberg calculează alinierea optimă folosind cantitatea de memorie, dar aproximativ dublul timpului de calcul. ) $F$ $A$ $B$ $i$ $j$ $F_{{ij}}$ $n$ $m$ $O(nm)$ $O(n+m)$

În timpul funcționării algoritmului, valoarea va prelua valorile estimării optime pentru alinierea primelor caractere în și primele caractere în . Atunci principiul optimității Bellman poate fi formulat după cum urmează: $F_{{ij}}$ $i=0,\;\ldots ,\;n$ $A$ $j=0,\;\ldots ,\;m$ $B$

Bază:

F_{{0j}}=d\cdot j

F_{{i0}}=d\cdot i

Recursie bazată pe principiul optimității:

F_{{ij}}=\max(F_{{i-1,\;j-1}}+S(A_{i},\;B_{j}),\;F_{{i,\;j -1}}+d,\;F_{{i-1,\;j}}+d).

Astfel, pseudo-codul algoritmului de calcul al matricei F va arăta astfel:

pentru i=0 la lungime (A) F(i,0) ← d*i pentru j=0 la lungime (B) F(0,j) ← d*j pentru i=1 la lungime (A) pentru j = 1 la lungime (B) { Potrivire ← F(i-1,j-1) + S(A i , B j ) Ștergeți ← F(i-1, j) + d Se introduce ← F(i, j-1) + d F(i,j) ← max (Potrivire, Inserare, Ștergere) }

Când o matrice este calculată, elementul său oferă scorul maxim dintre toate aliniamentele posibile. Pentru a calcula alinierea reală care marchează astfel, trebuie să începeți din celula din dreapta jos și să comparați valorile din acea celulă cu cele trei surse posibile (potrivire, inserare sau ștergere) pentru a vedea de unde provine. Dacă se potrivesc , și sunt aliniate, dacă sunt șterse, aliniate cu o pauză și, dacă sunt inserate, cu o pauză, sunt deja aliniate . (În general, pot exista mai multe opțiuni cu aceeași valoare care vor avea ca rezultat alinieri alternative alternative.) $F$ $F_{{ij}}$ $A_{i}$ $B j$ $A_{i}$ $B j$

AliniereA ← "" AliniereaB ← „” i ← lungime (A) j ← lungime (B) în timp ce (i > 0 sau j > 0) { Scor ← F(i,j) ScoreDiag ← F(i - 1, j - 1) ScoreUp ← F(i, j - 1) ScorLeft ← F(i - 1, j) dacă (Scor == ScoreDiag + S(A i , B j )) { AliniereaA ← A i + AliniereaA AliniereaB ← B j + AliniereaB i ← i - 1 j ← j - 1 } else if (Scor == ScoreLeft + d) { AliniereaA ← A i + AliniereaA AliniereaB ← „-” + AliniereaB i ← i - 1 } în caz contrar (Scor == ScoreUp + d) { AliniereaA ← „-” + AliniereaA AliniereaB ← B j + AliniereaB j ← j - 1 } } în timp ce (i > 0) { AliniereaA ← A i + AliniereaA AliniereaB ← „-” + AliniereaB i ← i - 1 } în timp ce (j > 0) { AliniereaA ← „-” + AliniereaA AliniereaB ← B j + AliniereaB j ← j - 1 }

Observații istorice

Needleman și Wunsch și-au descris în mod explicit algoritmul pentru cazul în care este evaluată doar potrivirea sau nepotrivirea caracterelor, dar nu și decalajul ( ). Publicația originală [1] din 1970 propune o recursivitate $d=0$

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})\}.

Algoritmul de programare dinamică corespunzător necesită timp cub pentru a calcula. Articolul subliniază, de asemenea, că recursiunea poate fi adaptată la orice formulă de penalizare de decalaj:

Penalizarea decalajului - numărul scăzut pentru fiecare decalaj - poate fi considerată ca împiedicând apariția golurilor în aliniere. Valoarea penalizării decalajului poate fi în funcție de dimensiunea și/sau direcția decalajului. [p. 444]

Un algoritm de programare dinamică în timp patratic mai rapid pentru aceeași problemă (fără penalizare de decalaj) a fost propus pentru prima dată [2] de David Sankoff în 1972. Un algoritm timp-quadratic similar a fost descoperit independent de T.K. Vintsyuk [3] în 1968 pentru procesarea vorbirii ( dynamic scale pre-accent) și de Robert A. Wagner și Michael J. Fisher [4] în 1974 pentru potrivirea șirurilor.

Needleman și Wunsch și-au formulat problema în termeni de maximizare a similitudinii. O altă posibilitate este de a minimiza distanța de editare dintre secvențele propuse de V. Levenshtein , cu toate acestea, s-a arătat [5] că aceste două probleme sunt echivalente.

În terminologia modernă, Needleman-Wunsch se referă la un algoritm de aliniere a secvenței de timp pătratice pentru o penalizare a decalajului liniar sau afin.

Vezi și

Note

↑ 1 2 Needleman, Saul B.; și Wunsch, Christian D. O metodă generală aplicabilă la căutarea asemănărilor în secvența de aminoacizi a două proteine // Journal of Molecular Biology : jurnal. - 1970. - Vol. 48 , nr. 3 . - P. 443-453 . - doi : 10.1016/0022-2836(70)90057-4 . — PMID 5420325 .
↑ Sankoff, D. Matching sequences under deletion / insertion constraints // Proceedings of the National Academy of Sciences of the United States of America : journal. - 1972. - Vol. 69 , nr. 1 . - P. 4-6 .
↑ Vintsyuk, TK Discriminarea vorbirii prin programare dinamică (neopr.) // Kibernetika. - 1968. - T. 4 . - S. 81-88 .
↑ Wagner, RA și Fischer, MJ The string-to-string correction problem // Journal of the ACM : journal. - 1974. - Vol. 21 . - P. 168-173 . - doi : 10.1145/321796.321811 .
↑ Sellers, PH Despre teoria și calculul distanțelor evolutive // SIAM Journal on Applied Mathematics : jurnal. - 1974. - Vol. 26 , nr. 4 . - P. 787-793 .

Link -uri

Algoritmul Needleman-Wunsch ca cod Ruby
Implementarea Java a algoritmului Needleman-Wunsch
BABA - un applet (cu sursă) care explică vizual algoritmul.
O explicație clară a NW și a aplicațiilor sale la alinierea secvenței
Tehnici de aliniere a secvenței la Blogul de tehnologie

Siruri de caractere
Măsuri de similitudine a șirurilor	Distanța de la Damerau la Loewenstein Distanța Levenshtein Distanța de Hamming Asemănarea Jaro-Winkler
Căutare subșir	Algoritmul Boyer-Moore Algoritmul Boyer-Moore-Horspool Algoritmul Knuth-Morris-Pratt Algoritmul Rabin-Karp funcția de prefix Funcția Z Algoritmul Aho - Korasik
palindromuri	arbore palindrom Algoritmul lui Manaker
Alinierea secvenței	Algoritmul Needleman-Wunsha Algoritmul Smith-Waterman
Structuri de sufix	Matrice de sufixe Sufix automat arbore de sufix arbore de prefix
Alte	analizare Potrivire de model Cea mai mare succesiune comună Cel mai mare subșir comun

Dicționare și enciclopedii	Britannica (online)