Algoritmo de Hirschberg

En informática , el algoritmo de Hirschberg , llamado así por su inventor, Dan Hirschberg , es un algoritmo de programación dinámica que encuentra la alineación de secuencia óptima entre dos cadenas . La optimalidad se mide con la distancia de Levenshtein , definida como la suma de los costos de inserciones, reemplazos, eliminaciones y acciones nulas necesarias para cambiar una cadena en otra. El algoritmo de Hirschberg se describe simplemente como una versión más eficiente en términos de espacio del algoritmo Needleman-Wunsch que utiliza divide y vencerás . ^[1] El algoritmo de Hirschberg se usa comúnmente en biología computacional para encontrar alineaciones globales máximas de secuencias de ADN y proteínas .

El algoritmo de Hirschberg es un algoritmo de aplicación general para el alineamiento óptimo de secuencias. BLAST y FASTA son heurísticas subóptimas . Si y son cadenas, donde y , el algoritmo de Needleman-Wunsch encuentra un alineamiento óptimo en el tiempo, usando el espacio. El algoritmo de Hirschberg es una modificación inteligente del algoritmo de Needleman-Wunsch, que todavía lleva tiempo, pero solo necesita espacio y es mucho más rápido en la práctica. ^[2] Una aplicación del algoritmo es encontrar alineamientos de secuencias de ADN o proteínas. También es una forma eficiente en términos de espacio de calcular la subsecuencia común más larga entre dos conjuntos de datos, como con la herramienta de diferencias comunes . ${\estilo de visualización X}$${\estilo de visualización Y}$${\displaystyle \operatorname {longitud} (X)=n}$${\displaystyle \operatorname {longitud} (Y)=m}$${\displaystyle O(nm)}$${\displaystyle O(nm)}$${\displaystyle O(nm)}$${\displaystyle O(\min\{n,m\})}$

El algoritmo de Hirschberg se puede derivar del algoritmo de Needleman-Wunsch observando que: ^[3]

1. se puede calcular la puntuación de alineación óptima almacenando únicamente la fila actual y la anterior de la matriz de puntuación de Needleman-Wunsch;
2. si es la alineación óptima de , y es una partición arbitraria de , existe una partición de tal que .${\displaystyle (Z,W)=\operatorname {NW} (X,Y)}$${\estilo de visualización (X,Y)}$${\displaystyle X=X^{l}+X^{r}}$${\estilo de visualización X}$${\displaystyle Y^{l}+Y^{r}}$${\estilo de visualización Y}$${\displaystyle \nombreoperador {NW} (X,Y)=\nombreoperador {NW} (X^{l},Y^{l})+\nombreoperador {NW} (X^{r},Y^{r})}$

$Estilo de visualización X_{i}}$denota el i -ésimo carácter de , donde . denota una subcadena de tamaño , que va desde el i -ésimo hasta el j -ésimo carácter de . es la versión invertida de . ${\estilo de visualización X}$${\displaystyle 1\leqslant i\leqslant \operatorname {length} (X)}$${\displaystyle X_{i:j}}$${\displaystyle j-i+1}$${\displaystyle X}$${\displaystyle \operatorname {rev} (X)}$${\displaystyle X}$

${\displaystyle X}$y son secuencias que se deben alinear. Sea un carácter de , y un carácter de . Suponemos que , y son funciones de valor entero bien definidas. Estas funciones representan el costo de eliminar , insertar y reemplazar con , respectivamente. ${\displaystyle Y}$${\displaystyle x}$${\displaystyle X}$${\displaystyle y}$${\displaystyle Y}$${\displaystyle \operatorname {Del} (x)}$${\displaystyle \operatorname {Ins} (y)}$${\displaystyle \operatorname {Sub} (x,y)}$${\displaystyle x}$${\displaystyle y}$${\displaystyle x}$${\displaystyle y}$

Definimos , que devuelve la última línea de la matriz de puntuación de Needleman–Wunsch : ${\displaystyle \operatorname {NWScore} (X,Y)}$${\displaystyle \mathrm {Score} (i,j)}$

función NWScore(X, Y)
    Puntuación(0, 0) = 0 // 2 * (longitud(Y) + 1) matriz
    para j = 1 hasta longitud(Y)
        Puntuación(0, j) = Puntuación(0, j - 1) + Ins(Y j )
     para i = 1 hasta longitud(X) // Matriz de inicialización
        Puntuación(1, 0) = Puntuación(0, 0) + Del(X i )
         para j = 1 hasta longitud(Y)
            puntuaciónSub = Puntuación(0, j - 1) + Sub(X i , Y j )
            puntuaciónDel = Puntuación(0, j) + Del(X i )
            puntuaciónIns = Puntuación(1, j - 1) + Ins(Y j )
            Puntuación(1, j) = máx.(puntuaciónSub, puntuaciónDel, puntuaciónIns)
        fin
        // Copiar Score[1] a Score[0]
        Puntuación(0, :) = Puntuación(1, :)
    fin 
    para j = 0 a longitud(Y)
        Última línea(j) = Puntuación(1, j)
    Devolver LastLine

Tenga en cuenta que, en cualquier momento, solo se requieren las dos filas más recientes de la matriz de puntaje. Por lo tanto, se implementa en el espacio. ${\displaystyle \operatorname {NWScore} }$${\displaystyle \operatorname {NWScore} }$${\displaystyle O(\min\{\operatorname {length} (X),\operatorname {length} (Y)\})}$

El algoritmo de Hirschberg es el siguiente:

función Hirschberg(X, Y)
    Z = ""
    W = ""
    si longitud(X) == 0
         para i = 1 a longitud(Y)
            Z = Z + '-'
            W = W + Y i 
        fin 
    de lo contrario si longitud(Y) == 0
         para i = 1 hasta longitud(X)
            Z = Z + Xi
            W = W + '-'
        fin 
    de lo contrario si longitud(X) == 1 o longitud(Y) == 1
        (Z, W) = NeedlemanWunsch(X, Y)
    demás
        xlen = longitud(X)
        xmid = longitud(X) / 2
        ylen = longitud(Y)

        PuntuaciónL = NWScore(X 1:xmid , Y)
        PuntuaciónR = NWScore(rev(X xmid+1:xlen ), rev(Y))
        ymid = arg max PuntuaciónL + rev(PuntuaciónR)

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

En el contexto de la observación (2), supongamos que es una partición de . El índice se calcula de manera que y . ${\displaystyle X^{l}+X^{r}}$${\displaystyle X}$${\displaystyle \mathrm {ymid} }$${\displaystyle Y^{l}=Y_{1:\mathrm {ymid} }}$${\displaystyle Y^{r}=Y_{\mathrm {ymid} +1:\operatorname {length} (Y)}}$

Dejar

${\displaystyle {\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}}}$

La alineación óptima viene dada por

W = AGTACGCA
 Z = --TATGC-

De hecho, esto se puede verificar retrocediendo hasta su matriz Needleman-Wunsch correspondiente:

         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

Se comienza con la llamada de nivel superior a , que divide el primer argumento a la mitad: . La llamada a produce la siguiente matriz: ${\displaystyle \operatorname {Hirschberg} ({\text{AGTACGCA}},{\text{TATGC}})}$${\displaystyle X={\text{AGTA}}+{\text{CGCA}}}$${\displaystyle \operatorname {NWScore} ({\text{AGTA}},Y)}$

        TAGCC
    0 -2 -4 -6 -8 -10
 Un -2 -1 0 -2 -4 -6
  Sol -4 -3 -2 -1 0 -2
  T -6 -2 -4 0 -2 -1
  Un -8 -4 0 -2 -1 -3

De igual forma, genera la siguiente matriz: ${\displaystyle \operatorname {NWScore} (\operatorname {rev} ({\text{CGCA}}),\operatorname {rev} (Y))}$

       CGTA
    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

Sus últimas líneas (después de invertir la última) y la suma de las mismas son respectivamente

PuntuaciónL = [ -8 -4 0 -2 -1 -3 ]
 rev(PuntuaciónR) = [ -3 -1 1 0 -4 -8 ]
 Suma = [-11 -5   1 -2 -5 -11]

El máximo (mostrado en negrita) aparece en ymid = 2, produciendo la partición . ${\displaystyle Y={\text{TA}}+{\text{TGC}}}$

La recursión completa de Hirschberg (que omitimos por brevedad) produce el siguiente árbol:

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

Las hojas del árbol contienen la alineación óptima.

• Subsecuencia común más larga