Hirschbergův algoritmus - Hirschbergs algorithm - Wikipedia

v počítačová věda, Hirschbergův algoritmus, pojmenoval podle jeho vynálezce, Dan Hirschberg, je dynamické programování algoritmus který najde optimální zarovnání sekvence mezi dvěma struny. Optimalita se měří pomocí Levenshteinova vzdálenost, definovaný jako součet nákladů na vložení, nahrazení, odstranění a nulové akce potřebné ke změně jednoho řetězce na druhý. Hirschbergův algoritmus je jednoduše popsán jako vesmírně efektivnější verze Algoritmus Needleman – Wunsch který používá rozděl a panuj.^[1] Hirschbergův algoritmus se běžně používá v výpočetní biologie najít maximální globální vyrovnání DNA a protein sekvence.

Informace o algoritmu

Hirschbergův algoritmus je obecně použitelný algoritmus pro optimální zarovnání sekvence. VÝBUCH a FASTA jsou neoptimální heuristika. Li X a y jsou řetězce, kde délka (X) = n a délka (y) = m, Needleman-Wunschův algoritmus najde optimální zarovnání v Ó (nm) čas pomocí O (nm) prostor. Hirschbergův algoritmus je chytrá modifikace algoritmu Needleman-Wunsch, který stále trvá O (nm) čas, ale potřebuje pouze O (min {n,m}) prostor a v praxi je mnohem rychlejší.^[2]Jednou z aplikací tohoto algoritmu je hledání sekvenčních srovnání DNA nebo proteinových sekvencí. Je to také prostorově efektivní způsob výpočtu nejdelší společná posloupnost mezi dvěma soubory dat, jako je tomu u společného rozdíl nářadí.

Algoritmus Hirschberg lze odvodit z Needleman-Wunschova algoritmu pozorováním, že:^[3]

1. lze vypočítat optimální skóre zarovnání pouze uložením aktuální a předchozí řady matice skóre Needleman-Wunsch;
2. -li ${ displaystyle (Z, W) = operatorname {NW} (X, Y)}$ je optimální zarovnání ${ displaystyle (X, Y)}$, a ${ displaystyle X = X ^ {l} + X ^ {r}}$ je libovolný oddíl ${ displaystyle X}$, existuje oddíl ${ displaystyle Y ^ {l} + Y ^ {r}}$ z ${ displaystyle Y}$ takhle ${ displaystyle operatorname {NW} (X, Y) = operatorname {NW} (X ^ {l}, Y ^ {l}) + operatorname {NW} (X ^ {r}, Y ^ {r} )}$.

Popis algoritmu

${ displaystyle X_ {i}}$ označuje i-tý znak ${ displaystyle X}$, kde ${ displaystyle 1 leqslant i leqslant operatorname {délka} (X)}$. ${ displaystyle X_ {i: j}}$ označuje podřetězec velikosti ${ displaystyle j-i + 1}$, od i-tého do j-tého znaku ${ displaystyle X}$. ${ displaystyle operatorname {rev} (X)}$ je obrácená verze ${ displaystyle X}$.

${ displaystyle X}$ a ${ displaystyle Y}$ jsou sekvence, které mají být zarovnány. Nechat ${ displaystyle x}$ být postavou z ${ displaystyle X}$, a ${ displaystyle y}$ být postavou z ${ displaystyle Y}$. To předpokládáme ${ displaystyle operatorname {Del} (x)}$, ${ displaystyle operatorname {Ins} (y)}$ a ${ displaystyle operatorname {Sub} (x, y)}$ jsou dobře definované funkce s celočíselnou hodnotou. Tyto funkce představují náklady na odstranění ${ displaystyle x}$, vkládání ${ displaystyle y}$a nahrazení ${ displaystyle x}$ s ${ displaystyle y}$, resp.

Definujeme ${ displaystyle operatorname {NWScore} (X, Y)}$, který vrací poslední řádek matice skóre Needleman-Wunsch ${ displaystyle mathrm {skóre} (i, j)}$:

funkce Pole NWScore (X, Y) (0,0) = 0 // 2 * (délka (Y) + 1) pro j = 1 na délka (Y) skóre (0, j) = skóre (0, j - 1) + vstupy (Yj)    pro i = 1 na length (X) // Init array Score (1,0) = Score (0, 0) + Del (Xi)        pro j = 1 na délka (Y) skóre Sub = skóre (0, j - 1) + Sub (Xi, Yj) scoreDel = Skóre (0, j) + Del (Xi) scoreIns = skóre (1, j - 1) + vstupy (rj) Skóre (1, j) = max (scoreSub, scoreDel, scoreIns) konec        // Kopírování skóre [1] do skóre [0] Skóre (0, :) = skóre (1, :) konec    pro j = 0 na délka (Y) LastLine (j) = skóre (1, j) vrátit se LastLine

Všimněte si, že kdykoli ${ displaystyle operatorname {NWScore}}$ vyžaduje pouze dva poslední řádky matice skóre. Tím pádem, ${ displaystyle operatorname {NWScore}}$ je implementováno v ${ displaystyle O ( operatorname {min} { operatorname {délka} (X), operatorname {délka} (Y) })}$ prostor

Následuje Hirschbergův algoritmus:

funkce Hirschberg (X, Y) Z = "" W = "" -li délka (X) == 0 pro i = 1 na délka (Y) Z = Z + '-' W = W + Yi        konec    jinak pokud délka (Y) == 0 pro i = 1 na délka (X) Z = Z + Xi            W = W + '-' konec    jinak pokud délka (X) == 1 nebo délka (Y) == 1 (Z, W) = NeedlemanWunsch (X, Y) jiný        xlen = délka (X) xmid = délka (X) / 2 ylen = délka (Y) skóre L = NWScore (X1: xmid, Y) Skóre R = NWScore (rev (Xxmid + 1: xlen), rev (Y)) ymid = arg max ScoreL + rev (ScoreR) (Z, W) = Hirschberg (X1: xmid, y1: ymid) + Hirschberg (Xxmid + 1: xlen, Yymid + 1: ylen)    konec    vrátit se (Z, W)

V kontextu Pozorování (2) předpokládejme, že ${ displaystyle X ^ {l} + X ^ {r}}$ je oddíl ${ displaystyle X}$. Index ${ displaystyle mathrm {ymid}}$ je vypočítán tak, že ${ displaystyle Y ^ {l} = Y_ {1: mathrm {ymid}}}$ a ${ displaystyle Y ^ {r} = Y _ { mathrm {ymid} +1: operatorname {délka} (Y)}}$.

Příklad

Nechat

${ displaystyle { begin {aligned} X & = mathrm {AGTACGCA}, Y & = mathrm {TATGC}, operatorname {Del} (x) & = - 2, operatorname {Ins} ( y) & = - 2, operatorname {Sub} (x, y) & = { begin {cases} +2, & { mbox {if}} x = y - 1, & { mbox {if}} x neq y. end {cases}} end {aligned}}}$

Optimální zarovnání je dáno vztahem

 W = AGTACGCA Z = --TATGC-

To lze skutečně ověřit zpětným sledováním odpovídající matice Needleman-Wunsch:

         T A T G C     0  -2  -4  -6  -8 -10 A  -2  -1   0  -2  -4  -6 G  -4  -3  -2  -1   0  -2 T  -6  -2  -4   0  -2  -1 A  -8  -4   0  -2  -1  -3 C -10  -6  -2  -1  -3   1 G -12  -8  -4  -3   1  -1 C -14 -10  -6  -5  -1   3 A -16 -12  -8  -7  -3   1

Jeden začíná hovorem na nejvyšší úrovni ${ displaystyle operatorname {Hirschberg} ( mathrm {AGTACGCA}, mathrm {TATGC})}$, který rozděluje první argument na polovinu: ${ displaystyle X = mathrm {AGTA} + mathrm {CGCA}}$. Volání na ${ displaystyle operatorname {NWScore} ( mathrm {AGTA}, Y)}$ vytvoří následující matici:

        T A T G C    0  -2  -4  -6  -8 -10 A -2  -1   0  -2  -4  -6 G -4  -3  -2  -1   0  -2 T -6  -2  -4   0  -2  -1 A -8  -4   0  -2  -1  -3

Rovněž, ${ displaystyle operatorname {NWScore} ( operatorname {rev} ( mathrm {CGCA}), operatorname {rev} (Y))}$ generuje následující matici:

       C G T A T    0 -2  -4  -6  -8 -10 A -2 -1  -3  -5  -4  -6 C -4  0  -2  -4  -6  -5 G -6 -2   2   0  -2  -4 C -8 -4   0   1  -1  -3

Jejich poslední řádky (po jejich obrácení) jsou součtem těchto řádků

 Skóre L = [-8 -4 0 -2 -1 -3] rev (ScoreR) = [-3-1 1 0 -4 -8] Součet = [-11 -5 1 -2 -5 -11]

Maximum (zobrazené tučně) se zobrazí na {{{1}}}, produkující oddíl ${ displaystyle Y = mathrm {TA} + mathrm {TGC}}$.

Celá Hirschbergova rekurze (kterou pro stručnost vynecháme) vytváří následující strom:

               (AGTACGCA, TATGC) /  (AGTA, TA) (CGCA, TGC) /  /  (AG,) (TA, TA) (CG, TG) (CA, C) /  /  (T, T) ( A, A) (C, T) (G, G) 

Listy stromu obsahují optimální zarovnání.

Viz také

• Nejdelší společná posloupnost

Reference