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] .
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í.
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á .
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‒‒ACGTs penalizací za mezeru bude mít následující skóre:
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. )
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ě:
Základ: Rekurze založená na principu optimality: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í.)
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 }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
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.
Struny | |
---|---|
Míry podobnosti řetězců | |
Hledání podřetězců | |
palindromy | |
Sekvenční zarovnání | |
Struktury přípon | |
jiný |
Slovníky a encyklopedie |
---|