Needleman-Wunsha algoritme

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 14. juli 2016; checks kræver 10 redigeringer .

Needleman-Wunsch-algoritmen er en algoritme til at udføre en alignment af to sekvenser (lad os kalde dem og ), der bruges i bioinformatik til at konstruere alignments af aminosyre- eller nukleotidsekvenser . Algoritmen blev foreslået i 1970 af Saul Needleman og Christian Wunsch [1] . $EN$ $B$

Needleman-Wunsch-algoritmen er et eksempel på dynamisk programmering , og det viste sig at være det første eksempel på anvendelsen af dynamisk programmering til sammenligning af biologiske sekvenser.

Moderne visning

Korrespondancen af justerede tegn er givet af lighedsmatrixen . Her er ligheden mellem symboler og . En lineær gap penalty bruges også , her kaldet . $S(a,\;b)$ $-en$ $b$ $d$

For eksempel, hvis lighedsmatrixen er givet af tabellen

-	EN	G	C	T
EN	ti	-en	-3	-fire
G	-en	7	-5	-3
C	-3	-5	9	0
T	-fire	-3	0	otte

derefter justering:

GTTAC‒‒ G‒‒ACGT

med en hulstraffe vil have følgende score: $d=-5$

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

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

For at finde den højest scorende justering tildeles en todimensional matrix (eller matrix ) , der indeholder lige så mange rækker, som der er tegn i sekvensen , og så mange kolonner, som der er tegn i sekvensen . En post i en række og kolonne betegnes som . Således, hvis vi justerer sekvenserne af størrelser og , så vil den nødvendige mængde hukommelse være . ( Hirschbergs algoritme beregner den optimale justering ved hjælp af mængden af hukommelse, men omkring det dobbelte af beregningstiden. ) $F$ $EN$ $B$ $jeg$ $j$ $F_{{ij}}$ $n$ $m$ $O(nm)$ $O(n+m)$

Under driften af algoritmen vil værdien antage værdierne af det optimale estimat for at justere de første tegn i og de første tegn i . Så kan Bellman-optimalitetsprincippet formuleres som følger: $F_{{ij}}$ $i=0,\;\ldots ,\;n$ $EN$ $j=0,\;\ldots ,\;m$ $B$

Basis:

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

F_{{i0}}=d\cdot i

Rekursion baseret på princippet om optimalitet:

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

Således vil pseudokoden for algoritmen til beregning af matricen F se sådan ud:

for i=0 til længde (A) F(i,0) ← d*i for j=0 til længde (B) F(0,j) ← d*j for i=1 til længde (A) for j = 1 til længde (B) { Match ← F(i-1,j-1) + S(A i , B j ) Slet ← F(i-1, j) + d Indsæt ← F(i, j-1) + d F(i,j) ← max (Match, Insert, Delete) }

Når en matrix beregnes, giver dens element den maksimale score blandt alle mulige justeringer. For at beregne den faktiske justering, der scorer som dette, skal du starte i nederste højre celle og sammenligne værdierne i den celle med de tre mulige kilder (match, indsættelse eller sletning) for at se, hvor den kom fra. Hvis matchet , og er justeret, hvis slettet, justeret med en pause, og hvis indsat, med en pause, justeret allerede . (Generelt kan der være mere end én mulighed med samme værdi, som vil resultere i alternative optimale justeringer). $F$ $F_{{ij}}$ $A_{i}$ $B_j$ $A_{i}$ $B_j$

AlignmentA ← "" AlignmentB ← "" i ← længde (A) j ← længde (B) mens (i > 0 eller j > 0) { Score ← F(i,j) ScoreDiag ← F(i - 1, j - 1) ScoreUp ← F(i, j - 1) ScoreLeft ← F(i - 1, j) if (Score == ScoreDiag + S(A i , B j )) { AlignmentA ← A i + AlignmentA AlignmentB ← B j + AlignmentB i ← i - 1 j ← j - 1 } else if (Score == ScoreLeft + d) { AlignmentA ← A i + AlignmentA AlignmentB ← "-" + AlignmentB i ← i - 1 } ellers (Score == ScoreUp + d) { AlignmentA ← "-" + AlignmentA AlignmentB ← B j + AlignmentB j ← j - 1 } } mens (i > 0) { AlignmentA ← A i + AlignmentA AlignmentB ← "-" + AlignmentB i ← i - 1 } mens (j > 0) { AlignmentA ← "-" + AlignmentA AlignmentB ← B j + AlignmentB j ← j - 1 }

Historiske bemærkninger

Needleman og Wunsch beskrev eksplicit deres algoritme for det tilfælde, hvor kun karaktermatch eller mismatch evalueres, men ikke gap ( ). Den originale publikation [1] fra 1970 foreslår en rekursion $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})\}.

Den tilsvarende dynamiske programmeringsalgoritme kræver kubiktid at beregne. Artiklen påpeger også, at rekursionen kan tilpasses til enhver form for gap penalty:

Gab-straffen - tallet fratrukket for hvert mellemrum - kan opfattes som at forhindre huller i at opstå i justeringen. Størrelsen af mellemrummet kan være en funktion af størrelsen og/eller retningen af mellemrummet. [s. 444]

En hurtigere kvadratisk-tids-dynamisk programmeringsalgoritme for det samme problem (ingen gap penalty) blev først foreslået [2] af David Sankoff i 1972. En lignende tid-kvadratisk algoritme blev uafhængigt opdaget af T.K. Vintsyuk [3] i 1968 til behandling af tale ( dynamisk skala præ-emphasis) og af Robert A. Wagner og Michael J. Fisher [4] i 1974 for strengmatchning.

Needleman og Wunsch formulerede deres problem i forhold til at maksimere ligheden. En anden mulighed er at minimere redigeringsafstanden mellem sekvenser foreslået af V. Levenshtein , men det blev vist [5] at disse to problemer er ækvivalente.

I moderne terminologi refererer Needleman-Wunsch til en kvadratisk tidssekvensjusteringsalgoritme for en lineær eller affin gap straf.

Se også

Noter

↑ 1 2 Needleman, Saul B.; og Wunsch, Christian D. En generel metode, der kan anvendes til at søge efter ligheder i aminosyresekvensen af to proteiner // Journal of Molecular Biology : journal. - 1970. - Bd. 48 , nr. 3 . - S. 443-453 . - doi : 10.1016/0022-2836(70)90057-4 . — PMID 5420325 .
↑ Sankoff, D. Matchende sekvenser under sletning / indsættelsesbegrænsninger // Proceedings of the National Academy of Sciences of the United States of America : journal. - 1972. - Bd. 69 , nr. 1 . - S. 4-6 .
↑ Vintsyuk, TK Talediskrimination ved dynamisk programmering (neopr.) // Kibernetika. - 1968. - T. 4 . - S. 81-88 .
↑ Wagner, RA og Fischer, MJ The string-to-string correction problem // Journal of the ACM : journal. - 1974. - Bd. 21 . - S. 168-173 . - doi : 10.1145/321796.321811 .
↑ Sellers, PH Om teorien og beregningen af evolutionære afstande // SIAM Journal on Applied Mathematics : journal. - 1974. - Bd. 26 , nr. 4 . - s. 787-793 .

Links

Needleman-Wunsch Algoritme som Ruby Code
Java-implementering af Needleman-Wunsch-algoritmen
BABA - en applet (med kilde), som visuelt forklarer algoritmen.
En klar forklaring af NW og dens anvendelser til sekvensjustering
Sequence Alignment Techniques på Technology Blog

Strenge
String lighedsmål	Afstand fra Damerau til Loewenstein Levenshtein afstand Hammerafstand Jaro-Winkler lighed
Understrengssøgning	Boyer-Moore algoritme Boyer-Moore-Horspool algoritme Knuth-Morris-Pratt algoritme Rabin-Karp algoritme præfiks funktion Z-funktion Algoritme Aho - Korasik
palindromer	palindrom træ Manakers algoritme
Sekvensjustering	Needleman-Wunsha algoritme Smith-Waterman algoritme
Suffiksstrukturer	Suffiks array Suffiks automat suffiks træ præfiks træ
Andet	parsing Mønster matchende Største fælles efterfølger Største fælles understreng

Ordbøger og encyklopædier	Britannica (online)