¿Por qué es necesaria esta sección

En M06 y M07, el alineamiento aplicó una penalización constante por cada hueco. -d representaba la puntuación por hueco. Sin embargo, desde una perspectiva evolutiva, esto no es preciso. Cuando ocurre una inserción dentro de un gen, la probabilidad del evento inicial de la inserción y la de que la inserción continúe son completamente diferentes. Es común que un único evento de inserción introduzca 30 pb de golpe, mientras que es mucho menos frecuente que ocurran dos inserciones separadas de 15 pb cada una en posiciones distintas.

Lo que refleja esto es la penalización de huecos afín (affine gap penalty). Además, se examina el algoritmo de Hirschberg, que reduce la complejidad espacial del algoritmo de O(mn) a O(n). Ambas ideas están presentes en las herramientas de alineamiento actuales (como EMBOSS needle, stretcher, minimap2, etc.).

Huecos afines — dos penalizaciones diferentes

Se define la penalización para una longitud de hueco de k de la siguiente manera:

• a: Penalización de apertura de hueco (gap opening penalty) — se aplica una vez cuando comienza el hueco
• b: Penalización de extensión de hueco (gap extension penalty) — se aplica cada vez que el hueco se alarga

Por ejemplo, si a = 10 y b = 1, la penalización para un hueco de longitud 5 es -(10 + 5) = -15. Aunque es mayor que la penalización constante (por ejemplo, $-2 \cdot 5 = -10$), la penalización para una longitud de 20 es -(10 + 20) = -30, lo cual es menor que la penalización constante de -40. Es decir, un solo hueco largo resulta más económico que varios huecos cortos.

¿Por qué esto es evolutivamente correcto? Porque es común que un único evento de inserción/deleción mueva varios nucleótidos de golpe, mientras que la probabilidad de que ocurran pequeñas inserciones separadas en múltiples lugares es baja.

Programación dinámica de 3 estados — cómo representar los huecos afines en la cuadrícula

La cuadrícula única de Needleman-Wunsch no puede expresar fácilmente los huecos afines, ya que es necesario rastrear si "esta celda está dentro de un hueco" o si "el hueco acaba de comenzar".

La solución consiste en crear tres cuadrículas.

• M(i, j): Puntuación óptima alcanzada mediante coincidencia/desajuste en la posición (i, j)
• I_x(i, j): Puntuación óptima del estado con un hueco abierto en X en la posición (i, j)
• I_y(i, j): Puntuación óptima del estado con un hueco abierto en Y en la posición (i, j)

Las tres cuadrículas se referencian entre sí y se rellenan conjuntamente.

Cada una de las tres cuadrículas toma O(mn) tiempo, por lo que el tiempo total sigue siendo O(mn). Aunque el espacio se triplica, al ser un factor constante, la complejidad espacial sigue siendo O(mn).

Implementación en Python

def affine_alignment(x, y, match=1, mismatch=-1, a=2, b=1):
    NEG_INF = float("-inf")
    m, n = len(x), len(y)
    M  = [[NEG_INF] * (n + 1) for _ in range(m + 1)]
    Ix = [[NEG_INF] * (n + 1) for _ in range(m + 1)]
    Iy = [[NEG_INF] * (n + 1) for _ in range(m + 1)]

    M[0][0] = 0
    for i in range(1, m + 1):
        Ix[i][0] = -a - b * i
    for j in range(1, n + 1):
        Iy[0][j] = -a - b * j

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            s = match if x[i-1] == y[j-1] else mismatch
            M[i][j] = max(
                M[i-1][j-1]  + s,
                Ix[i-1][j-1] + s,
                Iy[i-1][j-1] + s,
            )
            Ix[i][j] = max(
                M[i-1][j] - a - b,
                Ix[i-1][j] - b,
            )
            Iy[i][j] = max(
                M[i][j-1] - a - b,
                Iy[i][j-1] - b,
            )

    return max(M[m][n], Ix[m][n], Iy[m][n])

Esta función permite resolver el problema GAFF de Rosalind. Si se añade el traceback, también puede recuperarse el alineamiento real.

Hirschberg: un truco ingenioso para reducir el espacio a BP083P0000

Veamos ahora un problema distinto. Los algoritmos anteriores almacenaban la cuadrícula completa de O(mn). Para secuencias del tamaño del genoma humano se necesitarían $3 \times 10^9 \times 3 \times 10^9 = 9 \times 10^{18}$ bytes, algo completamente inviable.

La idea que Daniel Hirschberg propuso en 1975 es la siguiente: para calcular la puntuación solo hace falta una fila de la cuadrícula. Como cada fila utiliza únicamente los valores de la fila anterior, las filas antiguas pueden descartarse. Así, el espacio se reduce a O(n).

El problema era que, para reconstruir el alineamiento, parecía necesario conservar toda la cuadrícula. Hirschberg resolvió este obstáculo mediante divide y vencerás.

La idea de Hirschberg

1. Divida la secuencia X por la mitad: X = X_1 X_2.
2. Calcule las puntuaciones hacia delante de todos los alineamientos parciales de X_1 contra Y, conservando solo la última fila: tiempo $O(m/2 \cdot n)$ y espacio O(n).
3. Calcule las puntuaciones hacia atrás de todos los alineamientos parciales de las secuencias invertidas de X_2 y Y, también conservando solo la última fila: tiempo $O(m/2 \cdot n)$ y espacio O(n).
4. Combine los resultados: encuentre el punto j^* de Y donde su suma sea máxima. Ese j^* es el punto exacto que separa X_1 de X_2 en el alineamiento óptimo.
5. Aplique la misma operación recursivamente a X_1 contra Y[0:j^*] y a X_2 contra Y[j^*:n].

El tiempo es $O(mn) + O(mn/2) + O(mn/4) + \cdots = O(mn)$; el total sigue siendo O(mn), aunque el factor constante se duplica. El espacio es O(n).

¿Por qué funciona?

La idea clave es que el alineamiento óptimo debe atravesar el límite entre X_1 y X_2 en algún punto de Y. Si conocemos ese punto, el problema se divide en dos problemas menores, que pueden volver a dividirse con el mismo procedimiento.

Dónde se utilizan las penalizaciones de huecos afines y Hirschberg en la práctica

• EMBOSS needle: utiliza por defecto penalizaciones afines de huecos, mediante las opciones -gapopen y -gapextend.
• BLAST: utiliza huecos afines en el alineamiento con huecos (gapped BLAST).
• minimap2 (M16): Utiliza una penalización de piezas dobles afín (affine two-piece) que extiende la penalización de huecos afines para manejar grandes indels en lecturas largas.
• BWA-SW: Aplica la idea de alineación de espacio lineal de Hirschberg en la fase de extensión del alineamiento de BWA.

Trampas prácticas frecuentes

• Ajuste de parámetros de hueco: El tamaño relativo entre a y b influye significativamente en los resultados. Para alineación de proteínas, por convención se usan a = 10, b = 1 (al usar BLOSUM62). Para alineación de ADN, varía según el tipo de secuencia.
• Diferencia entre afín y constante: En la alineación de secuencias cortas, la diferencia entre ambas penalizaciones puede ser mínima. La diferencia se vuelve evidente en secuencias de más de 100 pb y evolutivamente distantes.
• Sobrecarga constante de Hirschberg: Teóricamente el tiempo es igual, pero en la práctica es aproximadamente el doble de lento. Úsela solo cuando el espacio sea realmente el cuello de botella. Para secuencias cortas, más bien resulta perjudicial.
• Extensión a alineaciones múltiples: Los huecos afines son muy importantes en la alineación múltiple de secuencias (MSA, M25). Al alinear especies distantes, sin huecos afines se obtienen resultados incorrectos.

Mapeo de CS

• DP de múltiples estados: El hueco afín expande el espacio de estados de uno a tres. Esta idea se repite en diversos problemas de CS como optimización de rutas de automóviles, IA para juegos y predicción de series temporales.
• Divide y vencerás + DP: Hirschberg es uno de los primeros casos que combina divide y vencerás con DP. También se introduce en el capítulo de algoritmos de ordenación del libro de texto CLRS.
• Compensación espacio-tiempo: Esta compensación, que utiliza un poco más de tiempo para reducir significativamente el espacio, es uno de los principios centrales de la informática. El mismo principio opera en compresión, diseño de cachés e indexación de bases de datos.

Ramas hacia el siguiente capítulo

• Siguiente capítulo (M09): BLOSUM/PAM — Justificación probabilística evolutiva de las puntuaciones de alineamiento. Base para el ajuste de parámetros del hueco afín.
• Dos capítulos después (M10): BLAST — gapped BLAST que incorpora huecos afines.
• Seis capítulos después (M14 · M15): BWT · FM-index — Extensión del alineamiento a escala genómica.
• Ocho capítulos después (M16): minimap2 — Aplicación práctica de la penalización de piezas dobles afín.

Para profundizar más

El texto principal es una narración reconstruida por BPD. Para profundizar, consulte lo siguiente:

• UC Berkeley CS176 — Conferencia del profesor Yun Song sobre Alineamiento de Secuencias con Penalizaciones de Huecos Afines (con subtítulos completos). Aborda en detalle la inducción de DP de 3 estados.
• Artículo original: Hirschberg, D. S. (1975), A linear space algorithm for computing maximal common subsequences, Comm ACM 18, 341–343. Tradición de la informática.
• Artículo original: Gotoh, O. (1982), An improved algorithm for matching biological sequences, J Mol Biol 162, 705–708. Origen de la programación dinámica de 3 estados con brechas afines.
• Libro de referencia: Durbin et al. Biological Sequence Analysis Capítulo 2. El texto clásico sobre alineamiento de secuencias.
• Herramienta de referencia: Biopython (Bio.pairwise2.align.globalds) — En la práctica, con esta función basta. Ahora mismo lo hemos implementado manualmente para comprender los principios subyacentes.

Resuelva los problemas GAFF · MULT · GCON en Rosalind. Esto le permitirá comprender por qué los bloques BLOSUM/PAM de la siguiente sección M09 están compuestos por números específicos.