Szerkesztő:Iulius Aegidius/Needleman–Wunsch algoritmus
A Needleman–Wunsch algoritmus a bioinformatikában fehérje- vagy nukleotidszekvenciák illesztésére használt algoritmus. Ez volt a dinamikus programozás egyik első alkalmazása a biológiai szekvenciák összehasonlítására. Az algoritmust Saul B. Needleman és Christian D. Wunsch fejlesztette ki 1970-ben.[1] Az algoritmus lényegében egy nagy problémát (pl. a teljes szekvenciát) kisebb feladatok sorozatára bont, és a kisebb problémák megoldásait használja fel a nagyobb probléma optimális megoldására. [2] [3] A Needleman–Wunsch algoritmust még mindig széles körben használják az optimális globális igazításhoz, különösen akkor, ha a globális illesztés minősége a legfontosabb. Az algoritmus minden lehetséges illesztéshez egy pontszámot rendel, célja, hogy megtalálja az összes lehetséges illesztést, amellyel a legmagasabb pontszámot kapja.
Bevezetés
szerkesztésEz az algoritmus bármely két karakterlánchoz használható. Az alábbi útmutató két rövid DNS-szekvenciát használ példaként, az 1. ábrán látható módon:
GCATGCG GATTACA
A mátrix felépítése
szerkesztésElőször készítsünk egy üres mátrixot. A karakterláncok felírását a harmadik oszlop tetején, illetve a harmadik sor elején kezdjük 1. ábra szerint.
| G | C | A | T | G | C | G | ||
|---|---|---|---|---|---|---|---|---|
| G | ||||||||
| A | ||||||||
| T | ||||||||
| T | ||||||||
| A | ||||||||
| C | ||||||||
| A |
Pontozási rendszer kiválasztása
szerkesztésEzután definiáljuk az egyes betűpárok pontozását. A fenti példa alapján az egyik lehetséges igazítási jelölt a következő lehet:
GCATG-CG
G-ATTACA
A betűk között lehet egyezés (match), nem egyezés (mismatch), vagy hézag (gap):
- Egyezés: Az aktuális index két betűje megegyezik.
- Nem egyezés: Az aktuális index két betűje különbözik.
- Indel (inzerció vagy deléció): A legjobb illesztés során az egyik betű a másik karakterlánc hézagához igazodik.
Minden lehetséges kombinációhoz hozzá van rendelve egy pontszám, és az összes illesztés pontszámainak összege a teljes illesztés pontszámát. Különféle rendszerek léteznek a pontszámok hozzárendelésére, ezek közül a Needleman és Wunsch [1] által használt rendszer kerül bemutatásra:
- Egyezés: +1
- Nem egyezés vagy hézag: −1
A fenti példa esetében az igazítás pontszáma 0 lenne:
GCATG-CG
G-ATTACA
+−++−−+− −> 1*4 + (−1)*4 = 0
Pontozás - A mátrix kitöltése
szerkesztésA második sorban és második oszlopban 0-val kezdünk. Sorról sorra lépkedve a cellák között, kiszámítjuk az egyes cellák pontszámát. A pontszámot úgy kapjuk meg, hogy összehasonlítjuk a cella bal, felső vagy bal felső részén (átlósan) szomszédos cellák pontszámait, és hozzáadjuk a megfelelő pontszámot egyezésre, nem egyezés vagy hézag esetében. Mindhárom esetben kiszámítjuk az értékeket:
- A felső vagy a bal cellától induló útvonal egy hézag párosítást jelent, ezért vesszük a bal és a felső cella pontszámait, és adja hozzá mindegyikhez az hézag pontszámát (gap penalty).
- Az átlós útvonal egyezést/nem egyezést jelöl, ezért vesszük a bal felső átlós cella pontszámát, és a sorban és az oszlopban lévő megfelelő karakterek egyezése esetén hozzáadjuk az egyezés pontszámát, ellenkező esetben a nem egyezés pontszámát adjuk hozzá.
A cella pontszáma a három számított érték közül a legnagyobb lesz.
Mivel a második sorban nincs „felső” vagy „bal felső” cella, csak a bal oldali cella használható az egyes cellák pontszámának kiszámításához. Ezért minden jobbra eltolódáshoz −1 adható, mivel ez egy hézagot jelent. Ez azt eredményezi, hogy az első sor 0, −1, −2, −3, −4, −5, −6, −7. Ugyanez vonatkozik az első oszlopra is, mivel csak az egyes cellák felett meglévő pontszám használható. Így a kapott táblázat a következő:
| G | C | A | T | G | C | G | ||
|---|---|---|---|---|---|---|---|---|
| 0 | −1 | −2 | −3 | −4 | −5 | −6 | −7 | |
| G | −1 | |||||||
| A | −2 | |||||||
| T | −3 | |||||||
| T | −4 | |||||||
| A | −5 | |||||||
| C | −6 | |||||||
| A | −7 |
Az első eset, ahol mind a 3 irányban létező pontszámok vannak, az első betűink metszéspontja (jelen esetben G és G). A környező cellák az alábbiak:
| G | ||
|---|---|---|
| 0 | −1 | |
| G | −1 | x |
Ennek a cellának három lehetséges kimenetele van:
- Az átlós bal felső szomszéd 0 pontot kapott. A G és G párosítása egyezés, ezért hozzáadjuk az egyezés pontszámát: 0+1 = 1
- A legfelső szomszéd pontszáma –1, és onnan haladva hézagot jelent, ezért hozzáadjuk a hézag pontszámát (gap penalty: (−1) + (−1) = (−2)
- A bal oldali szomszéd esetében is hasonló módon eljárva, szintén −2-t eredményez.
A három érték közül legmagasabb pontszám az 1, így a cellába ez az érték kerül.
| G | ||
|---|---|---|
| 0 | −1 | |
| G | −1 | 1 |
Jegyezzük fel azt a cellát, amely a legmagasabb pontszámot adta a a vizsgált cellának.
A következő példában mind az X, mind az Y átlós lépése nem egyzést jelent:
| G | C | ||
|---|---|---|---|
| 0 | −1 | −2 | |
| G | −1 | 1 | x |
| A | −2 | Y |
X:
- Felül: (-2)+(-1) = (-3)
- Balra: (+1)+(−1) = (0)
- Balra fent: (-1)+(-1) = (-2)
Y:
- Felül: (1)+(−1) = (0)
- Balra: (-2)+(-1) = (-3)
- Balra fent: (-1)+(-1) = (-2)
Mind X, mind Y esetén a legmagasabb pontszám nulla:
| G | C | ||
|---|---|---|---|
| 0 | −1 | −2 | |
| G | −1 | 1 | 0 |
| A | −2 | 0 |
A legmagasabb pontszámot a szomszédos cellák közül kettőből is elérhetjük:
| T | G | |
|---|---|---|
| T | 1 | 1 |
| A | 0 | X |
- Felül: (1)+(−1) = (0)
- Balra fent: (1)+(−1) = (0)
- Balra: (0)+(-1) = (-1)
Ebben az esetben a legmagasabb pontszámot elérő összes irányt jegyezzük fel.
A táblázat ilyen módon történő kitöltése megadja az összes lehetséges illesztést pontszámát, a jobb alsó cellában lévő pontszám a legjobb illesztési pontszámot jelenti.
Visszaolvasás
szerkesztésA nyilak irányát követve jelöljük ki az útvonalat a jobb alsó sarokban lévő cellából vissza a bal felső cellába. Ebből az útvonalból a sorozat a következő szabályok szerint épül fel:
- Az átlós nyíl egyezést vagy nem egyezést jelöl, így az oszlop betűjele és a származási cella sorának betűje igazodni fog.
- A vízszintes vagy függőleges nyíl a hézagott jelöli. A függőleges nyilak egy rést ("-") illesztenek a sor betűjéhez (az "oldalsó" sorozat), a vízszintes nyilak pedig az oszlop betűjéhez (a "felső" sorozat).
- Ha több nyíl közül lehet választani, akkor ezek az illesztések elágazását jelentik. Ha két vagy több ág mind a jobb alsó és a bal felső cella közötti útvonalhoz tartozik, akkor ezek egyformán életképes illesztések. Ebben az esetben mindkét lehetséges illesztést jegyezzük fel.
A fenti szabályokat követve az 1. ábrán látható egy lehetséges illesztés lépései a következők:
G → CG → GCG → -GCG → T-GCG → AT-GCG → CAT-GCG → GCAT-GCG A → CA → ACA → TACA → TTACA → ATTACA → -ATTACA → G-ATTACA
Hivatkozások
szerkesztés- ↑ a b Needleman, Saul B. (1970). „A general method applicable to the search for similarities in the amino acid sequence of two proteins”. Journal of Molecular Biology 48 (3), 443–53. o. DOI:10.1016/0022-2836(70)90057-4. PMID 5420325. Forráshivatkozás-hiba: Érvénytelen
<ref>címke, „Needleman” nevű forráshivatkozás többször van definiálva eltérő tartalommal - ↑ bioinformatics. (Hozzáférés: 2014. szeptember 10.)
- ↑ Gagniuc, Paul A.. Algorithms in bioinformatics : theory and implementation, 1st, Hoboken, NJ: John Wiley & Sons (2021. június 4.). ISBN 978-1-119-69800-5. OCLC 1240827446