Comprensión completa del alineamiento local Smith-Waterman: la decisión de recortar los valores negativos a cero en la cuadrícula (en coreano)

Alineamiento local DP: El instante en que Smith-Waterman recorta los negativos en la cuadrícula

¿Por qué el alineamiento de secuencias en la práctica no se puede realizar solo con Needleman-Wunsch? ¿Cómo cambia completamente el problema cuando Smith-Waterman recorta los valores negativos a cero en las celdas de la matriz, y cómo el alineamiento local conduce a BLAST?

Principiante

15min

Verificado (2026-07-19)

Smith-Watermanlocal alignmentsequence alignment

¿Por qué se necesita esta parte?

En M06, dijimos que Needleman-Wunsch es un método para alinear dos secuencias de manera global contra global. Sin embargo, en la práctica, este escenario es poco común. Por ejemplo, cuando comparamos un nuevo gen descubierto (2,000 pb) con el genoma humano (3 × 10⁹ pb), una alineación global carece de sentido. Lo que queremos saber es "en qué punto del genoma se encuentra una región muy similar a este gen".

Para esto se necesita la alineación local. La respuesta es un algoritmo propuesto por Temple Smith y Michael Waterman en 1981. Sorprendentemente, se puede crear modificando solo dos líneas de Needleman-Wunsch. En esta sección analizaremos esas dos líneas.

El momento de recortar los negativos a 0 en la cuadrícula

La ecuación de recurrencia de Needleman-Wunsch era la siguiente:

F(i, j) = \max \begin{cases} F(i-1, j-1) + s(x_i, y_j) \\ F(i-1, j) - d \\ F(i, j-1) - d \end{cases}

La ecuación de recurrencia de Smith-Waterman difiere en un solo punto.

H(i, j) = \max \begin{cases} 0 \\ H(i-1, j-1) + s(x_i, y_j) \\ H(i-1, j) - d \\ H(i, j-1) - d \end{cases}

Se ha añadido 0. Además, las condiciones de frontera cambian así:

H(i, 0) = 0 (en Needleman-Wunsch era $-i \cdot d$ )
H(0, j) = 0 (en Needleman-Wunsch era $-j \cdot d$ )

Estos dos cambios alteran completamente la naturaleza del algoritmo.

¿Por qué se introduce el 0?

En Needleman-Wunsch, si el valor de una celda se vuelve negativo, la ruta que pasa por esa celda continúa con una penalización acumulada. Sin embargo, en la práctica, dos secuencias suelen ser no relacionadas hasta un punto específico donde pueden tener similitud. Para encontrar esas similitudes parciales, basta con permitir que el valor de la celda se reinicie y comience de nuevo en el momento en que se vuelve negativo. Ese es el significado de añadir 0 a max.

¿Por qué las condiciones de frontera son 0?

En Needleman-Wunsch, la alineación debía comenzar en (0, 0) y terminar en (m, n) de la cuadrícula. Es decir, se forzaba el inicio y el final de ambas secuencias. En Smith-Waterman, se puede comenzar en cualquier lugar y terminar en cualquier lugar. Por lo tanto, la primera fila y la primera columna son todas ceros. La alineación real puede comenzar en cualquier punto arbitrario de la cuadrícula.

¿Cómo encontrar la mejor alineación?

Needleman-Wunsch siempre tuvo el alineamiento óptimo en (m, n). Smith-Waterman establece que la celda con el valor máximo en toda la matriz es el punto final del alineamiento óptimo.

\text{best} = \max_{(i, j)} H(i, j)

Al realizar el traceback desde esa celda, se detiene al alcanzar un 0, porque llegar a 0 significa que lo anterior no era significativo.

Relleno manual

Rellenemos la matriz con X = AGCACACA, Y = ACACACTA, coincidencia +2, discrepancia −1 y gap −2. Si se recorta brevemente, queda X = AGCA, Y = ACAC.

	A	C	A	C
−	0	0	0	0
A	+2	0	+2	0
G	0	+1	0	+1
C	0	+2	0	+2
A	+2	0	+4	0

H(4,3) = 4 es el valor máximo en toda la matriz. Al hacer traceback desde aquí, se obtiene un alineamiento local de ACA contra ACA (3 coincidencias). La razón por la que la puntuación es 4 y no 6 es porque los valores de la matriz representan el resultado de la optimización de rutas iterativas dentro de cada celda.

Al comparar con la matriz de Needleman-Wunsch, se observa a simple vista que no hay números negativos. Las celdas en áreas irrelevantes se reinician automáticamente a 0.

Implementación completa en Python

python

def smith_waterman(x, y, match=2, mismatch=-1, gap=-2):
    m, n = len(x), len(y)
    H = [[0] * (n + 1) for _ in range(m + 1)]

    best_score = 0
    best_pos = (0, 0)

    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
            H[i][j] = max(
                0,                       # Esta es la diferencia respecto a Needleman-Wunsch
                H[i-1][j-1] + s,
                H[i-1][j]   + gap,
                H[i][j-1]   + gap,
            )
            if H[i][j] > best_score:
                best_score = H[i][j]
                best_pos = (i, j)

    return best_score, best_pos, H

score, pos, table = smith_waterman("AGCACACA", "ACACACTA")
print(f"Puntuación local óptima: {score}")  # 12
print(f"Punto final: {pos}")

Solo difiere de Needleman-Wunsch en una línea: se añade 0 como primer argumento de max.

Evaluar con Rosalind

Entre en LOCA de Rosalind, descargue el conjunto de datos y añada el traceback al código anterior para mostrar las secuencias alineadas. La evaluación comprueba el alineamiento propiamente dicho.

¿Por qué la alineación local conduce a BLAST?

Smith-Waterman es un algoritmo exacto, pero su tiempo O(mn) impide aplicarlo directamente a todo el genoma humano. Por eso surgieron heurísticas como BLAST (M10).

La idea de BLAST es la siguiente:

Extraer k-mers cortos como semillas (seeds) de la secuencia de consulta.
Localizar rápidamente cada semilla en el índice del genoma de referencia.
Extender con Smith-Waterman únicamente alrededor de las semillas.
Devolver solo los alineamientos estadísticamente significativos.

En otras palabras, BLAST sigue la estrategia de aplicar una versión reducida de Smith-Waterman solo donde hace falta. Su fundamento es el alineamiento local estudiado aquí; lo analizaremos con detalle en M10 y M11.

Problemas comunes en la práctica

Equilibrio entre puntuaciones de coincidencia, discrepancia y hueco: si la puntuación de coincidencia es demasiado baja o las penalizaciones por discrepancia/hueco son insuficientes, el alineamiento local se alarga sin sentido. En la práctica se ajustan según el tipo de secuencia (ADN o proteína) y la similitud esperada. BLOSUM62 (M09) es la matriz de puntuación estándar para el alineamiento local de proteínas.
Varios alineamientos locales: extraer únicamente el máximo global de la cuadrícula puede omitir otras regiones similares. En la práctica suele ser necesario ampliar el algoritmo para obtener los K mejores alineamientos no solapados.
Genomas de referencia largos: O(mn) es el límite inmediato. Incluso un genoma humano de 3 × 10⁹ pb y una consulta de 100 pb producen $3 \times 10^{11}$ celdas y requieren alrededor de un día. Por eso se utilizan BLAST y BWA.
Penalización afín de huecos: abrir un hueco y prolongarlo deben tener penalizaciones distintas para representar los eventos evolutivos reales. Se trata en M08.

Correspondencias en informática

Programación dinámica (DP): comparte el mismo armazón de DP que Needleman-Wunsch, pero la definición de subestructura óptima difiere sutilmente. La opción de "empezar de nuevo aquí" forma parte de la optimización.
Subarray máximo (algoritmo de Kadane): el algoritmo de Kadane es el modelo unidimensional de la idea de "reiniciar en 0 una suma acumulada negativa". Smith-Waterman puede entenderse como su versión bidimensional.
Divide and Conquer vs DP: Divide and Conquer divide el problema a la mitad. DP reestructura el problema como relaciones entre celdas de una cuadrícula. El punto natural donde ambos enfoques convergen es el alineamiento de secuencias.

Ramas hacia los siguientes capítulos

Siguiente capítulo (M08): Penalización de gaps afines + Hirschberg — Refinar la penalización de gaps, reducir el espacio a lineal.
Dos capítulos después (M09): BLOSUM/PAM — Justificación probabilística evolutiva de las puntuaciones de alineamiento.
Tres capítulos después (M10): BLAST — Heurística para escalar Smith-Waterman a escala genómica.
Cuatro capítulos después (M11): Valor E de BLAST — Significancia estadística del alineamiento local.

Para profundizar más

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

MIT 7.91J — Conferencias de Christopher Burge sobre Alineamiento Local y BLAST (subtítulos completos, traducción automática superior al 95%). Aborda con rigor matemático el flujo desde Needleman-Wunsch hasta Smith-Waterman y BLAST.
UCSD CSE 182 — Alineamiento Local: Smith-Waterman del profesor Pavel Pevzner. Abundante en ejemplos de cálculo manual.
Artículo original: Smith, T. F. & Waterman, M. S. (1981), Identification of common molecular subsequences, J Mol Biol 147, 195–197. Una carta breve de dos páginas.
Texto de referencia: Compau & Pevzner Bioinformatics Algorithms. Colección de problemas gratuita vinculada a Rosalind.

Resuelva los problemas de alineamiento en Rosalind como LOCA, GAFF y MULT. Se comprenderá naturalmente por qué es necesaria la penalización de gaps afines en el siguiente capítulo M08. Es necesario escribir a mano.

BioPlayground