Needleman-Wunsha algoritmus

Az oldal jelenlegi verzióját még nem nézték át tapasztalt közreműködők, és jelentősen eltérhet a 2016. július 14-én felülvizsgált verziótól ; az ellenőrzésekhez 10 szerkesztés szükséges .

A Needleman-Wunsch algoritmus egy olyan algoritmus , amely két szekvencia (nevezzük őket és ) egymásba illesztését végrehajtó algoritmus , amelyet a bioinformatikában aminosav- vagy nukleotidszekvenciák egymáshoz igazítására használnak . Az algoritmust 1970-ben Saul Needleman és Christian Wunsch javasolta [1] . $A$ $B$

A Needleman-Wunsch algoritmus egy példa a dinamikus programozásra , és kiderült, hogy ez az első példa a dinamikus programozás biológiai szekvenciák összehasonlítására.

Modern nézet

Az igazított karakterek megfelelését a hasonlósági mátrix adja meg . Itt van a szimbólumok hasonlósága és . Lineáris résbüntetés is használatos , itt az úgynevezett . $S(a,\;b)$ $a$ $b$ $d$

Például, ha a hasonlósági mátrixot a táblázat adja meg

-	A	G	C	T
A	tíz	-egy	-3	- négy
G	-egy	7	-5	-3
C	-3	-5	9	0
T	- négy	-3	0	nyolc

majd igazítás:

GTTAC‒‒ G‒‒ACGT

résbüntetéssel a következő pontszámot kapja: $d=-5$

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

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

A legmagasabb pontszámú igazítás megtalálásához egy kétdimenziós tömb (vagy mátrix ) van hozzárendelve , amely annyi sort tartalmaz, ahány karakter van a sorozatban , és annyi oszlopot, ahány karakter van a sorozatban . A sorban és oszlopban lévő bejegyzés jelölése . Így ha a méretek és a sorozatokat egymáshoz igazítjuk , akkor a szükséges memória mennyisége . ( A Hirschberg - algoritmus a memória mennyiségével, de a számítási idő körülbelül kétszeresével számítja ki az optimális igazítást . ) $F$ $A$ $B$ $én$ $j$ $F_{{ij}}$ $n$ $m$ $O(nm)$ $O(n+m)$

Az algoritmus működése során az érték felveszi az optimális becslés értékeit az első karakterek és az első karakterek beállításához . Ekkor a Bellman optimalitás elve a következőképpen fogalmazható meg: $F_{{ij}}$ $i=0,\;\ldots ,\;n$ $A$ $j=0,\;\ldots ,\;m$ $B$

Alap:

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

F_{{i0}}=d\cdot i

Rekurzió az optimalitás elvén:

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

Így az F mátrix kiszámítására szolgáló algoritmus pszeudokódja így fog kinézni:

i =0 esetén ( A) F(i,0) ← d*i j=0 esetén ( B ) F(0,j) ← d*j i=1 esetén (A) j = 1 esetén ( B ) { Egyezés ← F(i-1,j-1) + S(A i , B j ) Törlés ← F(i-1, j) + d Beszúrás ← F(i, j-1) + d F(i,j) ← max (egyezés, beszúrás, törlés) }

A mátrix kiszámításakor az eleme a lehető legmagasabb pontszámot adja az összes lehetséges igazítás közül. Az ilyen pontszámot adó tényleges igazítás kiszámításához a jobb alsó cellában kell kezdenie, és össze kell hasonlítania a cellában lévő értékeket a három lehetséges forrással (egyeztetés, beillesztés vagy törlés), hogy megtudja, honnan származik. Ha egyező , és igazodik, ha törölve van, töréssel igazodik, és ha beszúrt, akkor töréssel, akkor már igazítva van . (Általában előfordulhat, hogy egynél több lehetőség van azonos értékkel, amely alternatív optimális igazítást eredményez.) $F$ $F_{{ij}}$ $A_{i}$ $B_j$ $A_{i}$ $B_j$

IgazításA ← "" IgazításB ← "" i ← hossz (A) j ← hossza (B) , míg (i > 0 vagy j > 0) { Pontszám ← 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 )) { IgazításA ← A i + IgazításA IgazításB ← B j + IgazításB én ← i - 1 j ← j - 1 } else if (pontszám == ScoreLeft + d) { IgazításA ← A i + IgazításA IgazításB ← "-" + IgazításB én ← i - 1 } egyébként (pontszám == ScoreUp + d) { IgazításA ← "-" + IgazításA IgazításB ← B j + IgazításB j ← j - 1 } } míg (i > 0) { IgazításA ← A i + IgazításA IgazításB ← "-" + IgazításB én ← i - 1 } míg (j > 0) { IgazításA ← "-" + IgazításA IgazításB ← B j + IgazításB j ← j - 1 }

Történelmi megjegyzések

Needleman és Wunsch kifejezetten leírta az algoritmusukat arra az esetre, amikor csak a karakterek egyezését vagy eltérését értékelik ki, de a hiányt ( ) nem. Az eredeti publikáció [1] 1970-ből egy rekurziót javasol $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})\}.

A megfelelő dinamikus programozási algoritmus kiszámításához köbidő szükséges. A cikk arra is rámutat, hogy a rekurzió bármely résbüntetés-képlethez adaptálható:

A hézagbüntetés – az egyes hézagokból levont szám – úgy is felfogható, hogy megakadályozza a rések megjelenését az igazításban. A résbüntetés mértéke függhet a rés méretétől és/vagy irányától. [o. 444]

Ugyanerre a problémára (nincs hézagbüntetés) egy gyorsabb kvadratikus idejű dinamikus programozási algoritmust először David Sankoff javasolt [2] 1972-ben. Egy hasonló idő-kvadratikus algoritmust 1968-ban T. K. Vintsyuk [3] fedezett fel a beszéd feldolgozására. dinamikus skála előkiemelés) és Robert A. Wagner és Michael J. Fisher [4] 1974-ben a húrillesztésért.

Needleman és Wunsch a hasonlóság maximalizálásával fogalmazta meg problémáját. Egy másik lehetőség a V. Levenshtein által javasolt szekvenciák közötti szerkesztési távolság minimalizálása , azonban kimutatták [5] , hogy ez a két probléma egyenértékű.

A modern terminológiában Needleman-Wunsch egy kvadratikus idősorrend-illesztési algoritmusra utal lineáris vagy affin résbüntetésre.

Lásd még

Jegyzetek

↑ 1 2 Needleman, Saul B.; és Wunsch, Christian D. Egy általános módszer, amely alkalmazható két fehérje aminosav-szekvenciájának hasonlóságainak keresésére // Journal of Molecular Biology : folyóirat. - 1970. - 1. évf. 48 , sz. 3 . - P. 443-453 . - doi : 10.1016/0022-2836(70)90057-4 . — PMID 5420325 .
↑ Sankoff, D. Egyező szekvenciák törlés alatt / beillesztési megszorítások // Proceedings of the National Academy of Sciences of the United States of America : Journal. - 1972. - 1. évf. 69 , sz. 1 . - P. 4-6 .
↑ Vintsyuk, TK Beszéddiszkrimináció dinamikus programozással (neopr.) // Kibernetika. - 1968. - T. 4 . - S. 81-88 .
↑ Wagner, RA és Fischer, MJ The string-to-string korrekciós probléma // Journal of the ACM : Journal. - 1974. - 1. évf. 21 . - 168-173 . o . - doi : 10.1145/321796.321811 .
↑ Sellers, PH Az evolúciós távolságok elméletéről és számításáról // SIAM Journal on Applied Mathematics : folyóirat. - 1974. - 1. évf. 26 , sz. 4 . - P. 787-793 .

Linkek

Needleman-Wunsch algoritmus mint Rubin kód
A Needleman-Wunsch algoritmus Java implementációja
BABA - egy kisalkalmazás (forrással), amely vizuálisan magyarázza az algoritmust.
Az NW világos magyarázata és alkalmazásai a szekvencia-illesztésre
Sequence Alignment Techniques at Technology Blog

Húrok
Karakterlánc hasonlósági mértékek	Távolság Damerau és Loewenstein között Levenshtein távolság Hamming távolság Jaro-Winkler hasonlóságok
Substring keresés	Boyer-Moore algoritmus Boyer-Moore-Horspool algoritmus Knuth-Morris-Pratt algoritmus Rabin-Karp algoritmus előtag funkció Z-függvény Algoritmus Aho - Korasik
palindromák	palindromfa Menedzser algoritmusa
Sorozat-igazítás	Needleman-Wunsha algoritmus Smith-Waterman algoritmus
Utótag szerkezetek	Utótag tömb Utótag automata utótag fa előtag fa
Egyéb	elemzése Mintaillesztés A legnagyobb közös sorozat Legnagyobb közös részkarakterlánc

Szótárak és enciklopédiák	Britannica (online)