Algoritmo di Hirschberg

L'algoritmo di Hirschberg, dal nome del suo creatore, Dan Hirschberg, è un algoritmo di programmazione dinamica che trova l'allineamento ottimale della sequenza tra due stringhe. L'ottimalità si misura con la distanza di Levenshtein, definita come la somma dei costi di inserimenti, sostituzioni, eliminazioni e azioni nulle necessarie per cambiare una stringa nell'altra. L'algoritmo di Hirschberg è semplicemente descritto come una versione più efficiente in termini di spazio dell'algoritmo Needleman-Wunsch che utilizza divide et impera. L'algoritmo di Hirschberg è comunemente usato nella biologia computazionale per trovare il numero massimo di allineamenti globali di DNA e sequenze proteiche.

Concetti di base

L'algoritmo di Hirschberg è un algoritmo generalmente applicabile per l'allineamento ottimale della sequenza. BLAST e FASTA sono euristiche non ottimali. Se x ed y sono stringhe,dove la lunghezza (x) = n e lunghezza (y) = m, l'algoritmo di Needleman-Wunsch constata un allineamento ottimale O (nm) tempo, utilizzando O (nm) spazio. L'algoritmo di Hirschberg è una modifica intelligente dell'algoritmo di Needleman–Wunsch, che richiede ancora tempo O(nm), ma necessita solo di O(min{n, m}) spazio ed è molto più veloce in pratica. Un'applicazione dell'algoritmo è trovare allineamenti di sequenze di DNA o sequenze proteiche. È anche un modo efficiente in termini di spazio per calcolare la massima sottosequenza comune tra due insiemi di dati, ad esempio con lo strumento diff comune.

L'algoritmo di Hirschberg può essere derivato dall'algoritmo di Needleman-Wunsch osservando che:

1. si può calcolare il punteggio di allineamento ottimale memorizzando solo la riga corrente e precedente della matrice del punteggio di Needleman–Wunsch;
2. Se $(Z,W)=\operatorname {NW} (X,Y)$ è l'allineamento ottimale di $(X,Y)$, e $X=X^{l}+X^{r}$ è una partizione arbitraria di $X$, esiste una partizione $Y^{l}+Y^{r}$ di $Y$ tale che $\operatorname {NW} (X,Y)=\operatorname {NW} (X^{l},Y^{l})+\operatorname {NW} (X^{r},Y^{r})$.

Descrizione dell'algoritmo

$X_{i}$ indica l'i -esimo carattere di $X$, dove $1\leqslant i\leqslant \operatorname {length} (X)$ . $X_{i:j}$ denota una sottostringa di dimensione $j-i+1$, dove i limiti vanno dal I -esimo al carattere j -esimo di $X$. $\operatorname {rev} (X)$ è la versione invertita di $X$.

Se $X$ e $Y$ sono sequenze da allineare. $x$ è un elemento da $X$, e $y$ è un elemento della sequenza $Y$. Assumendo che $\operatorname {Del} (x)$, $\operatorname {Ins} (y)$ e $\operatorname {Sub} (x,y)$ sono funzioni a valori interi ben definite. Queste funzioni rappresentano il costo dell'eliminazione $x$, inserendo $y$, e la sostituzione $x$ con $y$, rispettivamente.

Definiamo $\operatorname {NWScore} (X,Y)$, lo score che restituisce l'ultima riga della matrice del punteggio di Needleman–Wunsch $\mathrm {Score} (i,j)$:

funzione NWScore(X, Y)
  Punteggio(0, 0) = 0 // 2 * (lunghezza(Y) + 1) matrice
  per j = 1 alla lunghezza(Y)
    Punteggio(0, j) = Punteggio(0, j - 1) + Ins(Y j )
  for i = 1 to length(X) // Init array
    Punteggio(1, 0) = Punteggio(0, 0) + Canc(X i )
    per j = 1 alla lunghezza(Y)
      scoreSub = Punteggio(0, j - 1) + Sub(X i, Y j )
      scoreDel = Punteggio(0, j) + Del(X i )
      scoreIns = Punteggio(1, j - 1) + Ins(Y j )
      Score(1, j) = max(scoreSub, scoreDel, scoreIns)
    fine
    // Copia il punteggio[1] in punteggio[0]
    Punteggio(0, :) = Punteggio(1, :)
  fine
  per j = 0 alla lunghezza(Y)
    Ultima riga(j) = Punteggio(1, j)
  restituisce LastLine

Da notare che in qualsiasi momento $\operatorname {NWScore}$ richiede solo le due righe più recenti della matrice del punteggio. Così, $\operatorname {NWScore}$ è implementato in $O(\min\{\operatorname {length} (X),\operatorname {length} (Y)\})$ spazio.

L'algoritmo di Hirschberg segue:

funzione Hirschberg(X, Y)
  Z = ""
  W = ""
  se lunghezza(X) == 0
    per i = 1 alla lunghezza(Y)
      Z = Z + '-'
      W = W + Y io
    fine
  altrimenti se lunghezza(Y) == 0
    per i = 1 alla lunghezza(X)
      Z = Z + X io
      W = W + '-'
    fine
  altrimenti se lunghezza(X) == 1 o lunghezza(Y) == 1
    (Z, W) = NeedlemanWunsch(X, Y)
  altro
    xlen = lunghezza(X)
    xmid = lunghezza(X) / 2
    ylen = lunghezza(Y)

    PunteggioL = NWScore(X 1:xmid, Y)
    PunteggioR = NWScore(rev(X xmid+1:xlen ), rev(Y))
    ymid = arg max PunteggioL + rev(PunteggioR)

    (Z,W) = Hirschberg(X 1:xmid, y 1:ymid ) + Hirschberg(X xmid+1:xlen, Y ymid+1:ylen )
  fine
  ritorno (Z, W)

Nel contesto dell'osservazione (2), supponiamo che $X^{l}+X^{r}$ è una partizione di $X$. Indice $\mathrm {ymid}$ è calcolato in modo tale che $Y^{l}=Y_{1:\mathrm {ymid} }$ e $Y^{r}=Y_{\mathrm {ymid} +1:\operatorname {length} (Y)}$.

Esempio

Supponendo che

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

L'allineamento ottimale è dato da

W = AGTACGCA
 Z = --TATGC-

In effetti, questo può essere verificato tornando indietro sulla sua matrice di Needleman-Wunsch corrispondente:

TATGC
   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

Iniziando con la chiamata di livello superiore a $\operatorname {Hirschberg} ({\text{AGTACGCA}},{\text{TATGC}})$, che divide a metà il primo argomento: $X={\text{AGTA}}+{\text{CGCA}}$. La chiamata a $\operatorname {NWScore} ({\text{AGTA}},Y)$ produce la seguente matrice:

TATGC
  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

Allo stesso modo, $\operatorname {NWScore} (\operatorname {rev} ({\text{CGCA}}),\operatorname {rev} (Y))$ genera la seguente matrice:

CGTAT
  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

Le loro ultime righe (dopo aver invertito quest'ultima) e la loro somma sono rispettivamente

PunteggioL = [ -8 -4 0 -2 -1 -3 ]
 rev(PunteggioR) = [ -3 -1 1 0 -4 -8 ]
 Somma = [-11 -5 1 -2 -5 -11]

Il massimo (mostrato in grassetto) appare a ymid = 2, producendo la partizione $Y={\text{TA}}+{\text{TGC}}$.

L'intera ricorsione di Hirschberg (che omettiamo per brevità) produce il seguente albero:

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

Le foglie dell'albero contengono l'allineamento ottimale.

Voci correlate

• Massima sottosequenza comune