Needleman-Wunsha algoritm

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 14 juli 2016; kontroller kräver 10 redigeringar .

Needleman-Wunsch-algoritmen är en algoritm för att utföra en anpassning av två sekvenser (låt oss kalla dem och ) som används inom bioinformatik för att konstruera anpassningar av aminosyra- eller nukleotidsekvenser . Algoritmen föreslogs 1970 av Saul Needleman och Christian Wunsch [1] . $A$ $B$

Needleman-Wunsch-algoritmen är ett exempel på dynamisk programmering , och det visade sig vara det första exemplet på tillämpningen av dynamisk programmering för jämförelse av biologiska sekvenser.

Modern vy

Överensstämmelsen mellan justerade tecken ges av likhetsmatrisen . Här är likheten mellan symboler och . En linjär gap penalty används också , här kallad . $S(a,\;b)$ $a$ $b$ $d$

Till exempel, om likhetsmatrisen ges av tabellen

-	A	G	C	T
A	tio	-ett	-3	-fyra
G	-ett	7	-5	-3
C	-3	-5	9	0
T	-fyra	-3	0	åtta

sedan justering:

GTTAC‒‒ G‒‒ACGT

med ett gap straff kommer att ha följande poäng: $d=-5$

S(G,\;G)+2\ gånger d+S(A,\;A)+S(C,\;C)+2\ gånger d

=7+(2\ gånger -5)+10+9+(2\ gånger -5)=6.

För att hitta den högst poänggivande justeringen tilldelas en tvådimensionell matris (eller matris ) som innehåller lika många rader som det finns tecken i sekvensen och lika många kolumner som det finns tecken i sekvensen . En post i en rad och kolumn betecknas som . Således, om vi anpassar sekvenserna av storlekar och , kommer mängden minne som krävs att vara . ( Hirschbergs algoritm beräknar den optimala justeringen med hjälp av mängden minne men ungefär dubbelt så lång tid. ) $F$ $A$ $B$ $i$ $j$ $F_{{ij}}$ $n$ $m$ $På M)$ $O(n+m)$

Under driften av algoritmen kommer värdet att anta värdena för den optimala uppskattningen för att justera de första tecknen i och de första tecknen i . Då kan Bellmans optimalitetsprincip formuleras på följande sätt: $F_{{ij}}$ $i=0,\;\ldots ,\;n$ $A$ $j=0,\;\ldots ,\;m$ $B$

Grund:

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

F_{{i0}}=d\cdot i

Rekursion baserad på principen 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 kommer pseudokoden för algoritmen för beräkning av matrisen F att se ut så här:

för i=0 till längd (A) F(i,0) ← d*i för j=0 till längd (B) F(0,j) ← d*j för i=1 till längd (A) för j = 1 till längd (B) { Matcha ← F(i-1,j-1) + S(A i , B j ) Ta bort ← F(i-1, j) + d Infoga ← F(i, j-1) + d F(i,j) ← max (matcha, infoga, ta bort) }

När en matris beräknas ger dess element maximal poäng bland alla möjliga justeringar. För att beräkna den faktiska justeringen som ger poäng så här måste du börja i den nedre högra cellen och jämföra värdena i den cellen med de tre möjliga källorna (matchning, infogning eller radering) för att se var den kom ifrån. Om matchade , och är justerade, om de tas bort, justerade med en brytning, och om de infogas, med en brytning, justerade redan . (I allmänhet kan det finnas mer än ett alternativ med samma värde som kommer att resultera i alternativa optimala justeringar.) $F$ $F_{{ij}}$ $A_{i}$ $B_j$ $A_{i}$ $B_j$

AlignmentA ← "" AlignmentB ← "" i ← längd (A) j ← längd (B) medan (i > 0 eller j > 0) { Betyg ← F(i,j) ScoreDiag ← F(i - 1, j - 1) ScoreUp ← F(i, j - 1) ScoreLeft ← F(i - 1, j) if (Poäng == ScoreDiag + S(A i , B j )) { AlignmentA ← A i + AlignmentA AlignmentB ← B j + AlignmentB i ← i - 1 j ← j - 1 } annat om (Poäng == Poäng Vänster + d) { AlignmentA ← A i + AlignmentA AlignmentB ← "-" + AlignmentB i ← i - 1 } annars (Poäng == ScoreUp + d) { AlignmentA ← "-" + AlignmentA AlignmentB ← B j + AlignmentB j ← j - 1 } } medan (i > 0) { AlignmentA ← A i + AlignmentA AlignmentB ← "-" + AlignmentB i ← i - 1 } medan (j > 0) { AlignmentA ← "-" + AlignmentA AlignmentB ← B j + AlignmentB j ← j - 1 }

Historiska anmärkningar

Needleman och Wunsch beskrev uttryckligen sin algoritm för det fall där endast teckenmatchning eller felmatchning utvärderas, men inte gap ( ). Den ursprungliga publikationen [1] från 1970 föreslå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 motsvarande dynamiska programmeringsalgoritmen kräver kubiktid för att beräkna. Artikeln påpekar också att rekursionen kan anpassas till valfri form för gapstraff:

Spaltstraffet - siffran som subtraheras för varje mellanrum - kan ses som att förhindra luckor från att uppstå i linjen. Storleken på gapstraffet kan vara en funktion av gapets storlek och/eller riktning. [s. 444]

En snabbare kvadratisk-tid dynamisk programmeringsalgoritm för samma problem (ingen gap penalty) föreslogs först [2] av David Sankoff 1972. En liknande tidskvadratisk algoritm upptäcktes oberoende av T.K. Vintsyuk [3] 1968 för bearbetning av tal ( dynamisk skala pre-emphasis) och av Robert A. Wagner och Michael J. Fisher [4] 1974 för strängmatchning.

Needleman och Wunsch formulerade sitt problem i termer av att maximera likheten. En annan möjlighet är att minimera redigeringsavståndet mellan sekvenser som föreslagits av V. Levenshtein , men det visades [5] att dessa två problem är likvärdiga.

I modern terminologi hänvisar Needleman-Wunsch till en kvadratisk tidssekvensjusteringsalgoritm för en linjär eller affin gap penalty.

Se även

Anteckningar

↑ 1 2 Needleman, Saul B.; och Wunsch, Christian D. En allmän metod tillämpbar för sökandet efter likheter i aminosyrasekvensen för två proteiner // Journal of Molecular Biology : journal. - 1970. - Vol. 48 , nr. 3 . - S. 443-453 . - doi : 10.1016/0022-2836(70)90057-4 . — PMID 5420325 .
↑ Sankoff, D. Matchande sekvenser under radering / infogningsbegränsningar // Proceedings of the National Academy of Sciences of the United States of America : journal. - 1972. - Vol. 69 , nr. 1 . - S. 4-6 .
↑ Vintsyuk, TK Taldiskriminering genom dynamisk programmering (neopr.) // Kibernetika. - 1968. - T. 4 . - S. 81-88 .
↑ Wagner, RA och Fischer, MJ The string-to-string correction problem // Journal of the ACM : journal. - 1974. - Vol. 21 . - S. 168-173 . - doi : 10.1145/321796.321811 .
↑ Sellers, PH Om teorin och beräkningen av evolutionära avstånd // SIAM Journal on Applied Mathematics : journal. - 1974. - Vol. 26 , nr. 4 . - s. 787-793 .

Länkar

Needleman-Wunsch Algoritm som Ruby Code
Java-implementering av Needleman-Wunsch-algoritmen
BABA - en applet (med källa) som visuellt förklarar algoritmen.
En tydlig förklaring av NW och dess tillämpningar för sekvensanpassning
Sequence Alignment Techniques på Technology Blog

Strängar
Stränglikhetsmått	Avstånd från Damerau till Loewenstein Levenshtein avstånd Hamming avstånd Jaro-Winkler likheter
Sök efter delsträng	Boyer-Moore algoritm Boyer-Moore-Horspool-algoritm Knuth-Morris-Pratt-algoritm Rabin-Karps algoritm prefixfunktion Z-funktion Algoritm Aho - Korasik
palindromer	palindromträd Manakers algoritm
Sekvensjustering	Needleman-Wunsha algoritm Smith-Waterman algoritm
Suffixstrukturer	Suffix array Suffix automat suffixträd prefixträd
Övrig	analysera Mönstermatchning Största vanliga följden Största gemensamma delsträngen

Ordböcker och uppslagsverk	Britannica (online)