Algoritmus Needleman-Wunsha

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 14. července 2016; kontroly vyžadují 10 úprav .

Needleman-Wunschův algoritmus je algoritmus pro provádění zarovnání dvou sekvencí (říkejme jim a ), který se používá v bioinformatice ke konstrukci zarovnání aminokyselinových nebo nukleotidových sekvencí. Algoritmus navrhli v roce 1970 Saul Needleman a Christian Wunsch [1] . $A$ $B$

Algoritmus Needleman-Wunsch je příkladem dynamického programování a ukázal se být prvním příkladem aplikace dynamického programování na porovnávání biologických sekvencí.

Moderní pohled

Korespondence zarovnaných znaků je dána maticí podobnosti . Zde je podobnost symbolů a . Používá se také lineární penalizace mezery , zde nazývaná . $S(a,\;b)$ $A$ $b$ $d$

Například pokud je matice podobnosti dána tabulkou

-	A	G	C	T
A	deset	-jeden	-3	-čtyři
G	-jeden	7	-5	-3
C	-3	-5	9	0
T	-čtyři	-3	0	osm

pak zarovnání:

GTTAC‒‒ G‒‒ACGT

s penalizací za mezeru bude mít následující skóre: $d = -5$

S(G,\;G)+2\krát d+S(A,\;A)+S(C,\;C)+2\krát d

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

K nalezení zarovnání s nejvyšším skóre je přiřazeno dvourozměrné pole (nebo matice ) obsahující tolik řádků, kolik je znaků v sekvenci a tolik sloupců, kolik je znaků v sekvenci . Záznam v řádku a sloupci je označen jako . Pokud tedy zarovnáme posloupnosti velikostí a , pak požadované množství paměti bude . ( Hirschbergův algoritmus počítá optimální zarovnání s použitím množství paměti, ale přibližně dvojnásobného času výpočtu. ) $F$ $A$ $B$ $i$ $j$ $F_{{ij}}$ $n$ $m$ $O(nm)$ $O(n+m)$

Během činnosti algoritmu bude hodnota nabývat hodnot optimálního odhadu pro zarovnání prvních znaků v a prvních znaků v . Potom lze Bellmanův princip optimality formulovat následovně: $F_{{ij}}$ $i=0,\;\ldots ,\;n$ $A$ $j=0,\;\ldots ,\;m$ $B$

Základ:

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

F_{{i0}}=d\cdot i

Rekurze založená na principu optimality:

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

Pseudokód algoritmu pro výpočet matice F tedy bude vypadat takto:

pro i=0 do délky (A) F(i,0) ← d*i pro j=0 do délky (B) F(0,j) ← d*j pro i=1 na délku (A) pro j = 1 na délku (B) { Shoda ← F(i-1,j-1) + S(A i , B j ) Smazat ← F(i-1, j) + d Vložte ← F(i, j-1) + d F(i,j) ← max (shoda, vložení, smazání) }

Když je matice vypočítána, její prvek dává maximální skóre ze všech možných zarovnání. Chcete-li vypočítat skutečné zarovnání, které má takové skóre, musíte začít v pravé dolní buňce a porovnat hodnoty v této buňce se třemi možnými zdroji (shoda, vložení nebo odstranění), abyste zjistili, odkud pochází. Pokud se shodují , a jsou zarovnány, pokud jsou odstraněny, zarovnány se zalomením, a pokud jsou vloženy, se zalomením, již zarovnány . (Obecně může existovat více než jedna možnost se stejnou hodnotou, která povede k alternativnímu optimálnímu zarovnání.) $F$ $F_{{ij}}$ $A_{i}$ $B_j$ $A_{i}$ $B_j$

ZarovnáníA ← "" ZarovnáníB ← "" i ← délka (A) j ← délka (B) , zatímco (i > 0 nebo j > 0) { Skóre ← F(i,j) ScoreDiag ← F(i - 1, j - 1) ScoreUp ← F(i, j - 1) ScoreLeft ← F(i - 1, j) if (Skóre == ScoreDiag + S( Ai , Bj )) { ZarovnáníA ← A i + ZarovnáníA ZarovnáníB ← B j + ZarovnáníB i ← i - 1 j ← j - 1 } else if (Skóre == SkóreLeft + d) { ZarovnáníA ← A i + ZarovnáníA ZarovnáníB ← "-" + ZarovnáníB i ← i - 1 } jinak (Skóre == Skóre + d) { ZarovnáníA ← "-" + ZarovnáníA ZarovnáníB ← B j + ZarovnáníB j ← j - 1 } } zatímco (i > 0) { ZarovnáníA ← A i + ZarovnáníA ZarovnáníB ← "-" + ZarovnáníB i ← i - 1 } zatímco (j > 0) { ZarovnáníA ← "-" + ZarovnáníA ZarovnáníB ← B j + ZarovnáníB j ← j - 1 }

Historické poznámky

Needleman a Wunsch výslovně popsali svůj algoritmus pro případ, kdy se hodnotí pouze shoda nebo neshoda znaků, ale ne mezera ( ). Původní publikace [1] z roku 1970 navrhuje rekurzi $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})\}.

Odpovídající algoritmus dynamického programování vyžaduje krychlový čas k výpočtu. Článek také poukazuje na to, že rekurzi lze přizpůsobit jakémukoli vzorci pro penalizaci mezery:

Pokutu za mezeru - číslo odečtené pro každou mezeru - lze považovat za zabránění výskytu mezer ve vyrovnání. Velikost penalizace mezery může být funkcí velikosti a/nebo směru mezery. [str. 444]

Rychlejší kvadratický algoritmus dynamického programování pro stejný problém (bez penalizace za mezeru) poprvé navrhl [2] David Sankoff v roce 1972. Podobný časově kvadratický algoritmus nezávisle objevil T. K. Vintsyuk [3] v roce 1968 pro zpracování řeči ( dynamická stupnice pre-emphasis) a Robert A. Wagner a Michael J. Fisher [4] v roce 1974 pro párování strun.

Needleman a Wunsch formulovali svůj problém z hlediska maximalizace podobnosti. Další možností je minimalizovat editační vzdálenost mezi sekvencemi navrženou V. Levenshteinem , nicméně se ukázalo [5] , že tyto dva problémy jsou ekvivalentní.

V moderní terminologii Needleman-Wunsch odkazuje na kvadratický algoritmus zarovnání časové sekvence pro lineární nebo afinní mezeru.

Viz také

Poznámky

↑ 1 2 Needleman, Saul B.; a Wunsch, Christian D. Obecná metoda použitelná pro hledání podobností v aminokyselinové sekvenci dvou proteinů // Journal of Molecular Biology : deník. - 1970. - Sv. 48 , č. 3 . - str. 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. - Sv. 69 , č. 1 . - str. 4-6 .
↑ Vintsyuk, TK Diskriminace řeči dynamickým programováním (neopr.) // Kibernetika. - 1968. - T. 4 . - S. 81-88 .
↑ Wagner, RA a Fischer, MJ Problém korekce mezi řetězci // Journal of the ACM : journal. - 1974. - Sv. 21 . - S. 168-173 . - doi : 10.1145/321796.321811 .
↑ Sellers, PH O teorii a počítání evolučních vzdáleností // SIAM Journal on Applied Mathematics : deník. - 1974. - Sv. 26 , č. 4 . - str. 787-793 .

Odkazy

Algoritmus Needleman-Wunsch jako Ruby kód
Java implementace Needleman-Wunschova algoritmu
BABA - applet (se zdrojem), který vizuálně vysvětluje algoritmus.
Jasné vysvětlení NW a jeho aplikací pro sekvenční zarovnání
Techniky zarovnání sekvencí na technologickém blogu

Struny
Míry podobnosti řetězců	Vzdálenost Damerau - Loewenstein Levenshteinská vzdálenost Hammingova vzdálenost Podobnost Jaro-Winkler
Hledání podřetězců	Boyer-Mooreův algoritmus Algoritmus Boyer-Moore-Horspool Knuth-Morris-Prattův algoritmus Rabin-Karpův algoritmus funkce předpony Z-funkce Algoritmus Aho - Korasik
palindromy	palindromový strom Manažerův algoritmus
Sekvenční zarovnání	Algoritmus Needleman-Wunsha Smith-Watermanův algoritmus
Struktury přípon	Pole přípon Přípona automat příponový strom předponový strom
jiný	rozebrat Shoda vzorů Největší společná podsekvence Největší společný podřetězec

Slovníky a encyklopedie	Britannica (online)