¿Por qué se necesita este capítulo?

En M07, Smith-Waterman se presentó como el algoritmo exacto para la alineación local, que requiere un tiempo de $O(mn)$. Sin embargo, las búsquedas de secuencias que encontramos en la práctica tienen esta forma:

• Consulta: un nuevo gen encontrado (~2.000 pb)
• Referencia: base de datos NCBI nr (>5 × 10¹¹ pb y en constante crecimiento)

Si se ejecuta Smith-Waterman exactamente, se requieren $2000 \times 5 \times 10^{11} = 10^{15}$ celdas. Incluso con CPUs modernas, esto tomaría varios días. Para abordar esto de manera práctica, surgió BLAST (Basic Local Alignment Search Tool). Fue publicado por Stephen Altschul y otros en 1990 y sigue siendo uno de los artículos más citados en bioinformática.

En este capítulo analizaremos las tres etapas de BLAST: semilla · extensión · significancia. Este enfoque conceptual atraviesa el capítulo actual (M10), el siguiente (M11) y herramientas que encontraremos más adelante como BWA y minimap2.

Idea — Semilla y Extensión

La intuición central de BLAST es la siguiente:

Dos secuencias verdaderamente similares deben contener necesariamente fragmentos cortos e idénticos (semillas).

Por lo tanto, BLAST funciona así:

1. Semilla: Se extraen k-meros cortos de la consulta y se buscan rápidamente en un índice las posiciones que coinciden exactamente en la base de datos de referencia.
2. Extensión: Se expande la alineación mediante Smith-Waterman alrededor de cada posición de semilla.
3. Significancia: Se reevalúa la significancia estadística de los puntajes de alineación obtenidos mediante el valor E, devolviendo solo aquellos que son significativos.

De esta manera, aunque el algoritmo de alineación en sí es Smith-Waterman exacto, el área de aplicación se limita a las cercanías de las posiciones candidatas. La carga computacional disminuye drásticamente.

Paso 1 — Determinación del tamaño de la semilla

El tamaño $k$ de los k-meros es decisivo. Si $k$ es pequeño, las semillas coinciden con demasiada frecuencia y el número de candidatos se dispara. Si $k$ es grande, podrían perderse secuencias verdaderamente similares.

• BLASTN (ADN): $k = 11$ por defecto. megaBLAST utiliza valores tan grandes como $k = 28$ (para búsquedas de alta similitud).
• BLASTP (proteína): $k = 3$ por defecto. Sin embargo, en este caso la semilla no es una coincidencia exacta, sino una coincidencia con un puntaje superior al umbral de BLOSUM62.

¿Por qué el tamaño de la semilla para BLASTP es 3? Dado que el alfabeto de aminoácidos tiene 20 tipos, hay $20^3 = 8000$ combinaciones posibles. Esto permite encontrar rápidamente las posiciones de cada combinación mediante un índice hash en la base de datos de referencia, representando un punto de equilibrio que no pierde proteínas verdaderamente similares.

Paso 2 — Expansión en dos direcciones

Desde cada semilla, se expande el alineamiento. En ambas direcciones (izquierda y derecha), se amplía la semilla mientras se observa la acumulación de la puntuación de alineamiento.

• Si la puntuación sigue aumentando, se continúa la expansión.
• Si la puntuación cae por debajo del umbral de caída (dropoff threshold), se detiene la expansión.

Lo que distingue este procedimiento del algoritmo Smith-Waterman es que se decide de manera probabilística hasta dónde expandirse. Aunque no constituye un alineamiento local exacto, en la mayoría de los casos se aproxima mucho al alineamiento óptimo real.

BLAST 1.0 (1990) solo admitía expansiones sin huecos. Desde BLAST 2.0 (1997, "gapped BLAST") se admite la expansión con huecos afines. La versión que utilizamos hoy es gapped BLAST.

Paso 3 — Two-hit frente a One-hit

Para mejorar la eficiencia, gapped BLAST utiliza el criterio two-hit.

Solo se inicia la expansión si se encuentran dos semillas cercanas (por ejemplo, dentro de los primeros 40 pb) en la misma diagonal.

Es decir, generalmente se ignoran los casos en los que una sola semilla coincide por casualidad. Dado que es más probable que las secuencias similares presenten varias semillas adyacentes, este filtro elimina la mayoría de las coincidencias fortuitas.

Esta idea se repite posteriormente en BWA y minimap2. La idea fundamental del enfoque seed-and-extend consiste en utilizar "varias coincidencias exactas cortas como señal".

Creación de una versión reducida de BLAST con Python

Aunque no es posible reproducir el BLAST real en 100 líneas, podemos crear una versión reducida para comprender sus principios.

from collections import defaultdict

def build_kmer_index(reference: str, k: int) -> dict[str, list[int]]:
    """Índice de k-mer → lista de posiciones en la secuencia de referencia."""
    index = defaultdict(list)
    for i in range(len(reference) - k + 1):
        index[reference[i:i+k]].append(i)
    return index

def mini_blast(query: str, reference: str, k: int = 11, extend: int = 20) -> list[dict]:
    """BLAST reducido — localiza coincidencias de semillas y las extiende a ambos lados."""
    index = build_kmer_index(reference, k)
    hits = []
    for q_pos in range(len(query) - k + 1):
        seed = query[q_pos:q_pos+k]
        for r_pos in index.get(seed, []):
            # Extender a ambos lados (simplificado; BLAST real usa un umbral de dropoff)
            left = max(0, min(q_pos, r_pos) - extend)
            right = min(len(query), q_pos + k + extend)
            q_seg = query[q_pos - (min(q_pos, r_pos) - left):right]
            r_seg = reference[r_pos - (min(q_pos, r_pos) - left):
                              r_pos + k + (right - q_pos - k)]
            matches = sum(a == b for a, b in zip(q_seg, r_seg))
            hits.append({
                "q_pos": q_pos, "r_pos": r_pos,
                "identity": matches / max(len(q_seg), 1),
                "length": len(q_seg),
            })
    return hits

# Uso
reference = "AAAAGGCCTTGGCCAATTGGCCTTAAAA"
query = "GGCCTT"
for hit in mini_blast(query, reference, k=6, extend=5):
    print(hit)

Esta versión reducida difiere del BLAST real en varios aspectos:

• No incluye la expansión de semillas vecinas de BLASTP.
• No utiliza el filtro de dos impactos (two-hit).
• No calcula la estadística del valor E, que se tratará en la siguiente unidad.
• No utiliza huecos afines.
• Mantiene el índice en memoria, mientras que BLAST real utiliza archivos mapeados en disco.

Sin embargo, conserva la idea central: encontrar una semilla mediante el índice y extender únicamente alrededor de ella.

Práctica con NCBI BLAST en la web

La práctica más sencilla utiliza la interfaz web de NCBI BLAST.

1. Abra NCBI BLAST y elija blastn o blastp.
2. Pegue una secuencia de interés, por ejemplo un fragmento de 200 bp de la CDS humana de BRCA1.
3. Seleccione la base de datos nr o refseq_rna.
4. Ejecute la búsqueda; los alineamientos aparecerán en segundos o minutos.

Elementos que debe observar en el resultado:

• Score: puntuación del alineamiento, suma de cocientes de log-verosimilitud de BLOSUM62.
• E-value: significación estadística, tratada en la siguiente unidad.
• Identity: proporción de coincidencias.
• Alignment: representación visual del alineamiento.

Conviene reinterpretar cada puntuación de hit como la suma de cocientes de log-verosimilitud de BLOSUM62, tal como se explicó en M09.

Limitaciones de BLAST y herramientas posteriores

BLAST fue diseñado para la escala genómica de la década de 1990. Para el volumen actual de lecturas cortas de Illumina y lecturas largas de Nanopore o PacBio han aparecido herramientas nuevas.

• BWA-MEM (2013): estándar para alinear lecturas cortas; combina seed-and-extend y FM-index. Unidades M14–M15.
• Bowtie2 (2012): contemporáneo de BWA; combina FM-index y alineamiento local.
• minimap2 (2018): estándar para lecturas largas; utiliza semillas minimizer y huecos afines de dos piezas. Unidad M16.
• DIAMOND (2015): alternativa a BLAST para búsquedas de proteínas a gran escala; su índice optimizado puede ser más de cien veces más rápido. Unidad M17.

Todas estas herramientas heredaron el enfoque seed-and-extend de BLAST. BLAST fue el origen de esa idea.

Trampas comunes en la práctica

• Filtro de baja complejidad: BLAST activa por defecto el enmascaramiento de baja complejidad con DUST o SEG. Si se desactiva, por ejemplo con -dust no, las secuencias repetitivas pueden contaminar los resultados.
• Tamaño de la base de datos y valor E: el valor E es proporcional al tamaño de la base consultada. Por eso difiere entre nr, que es amplia, y RefSeq, que prioriza registros de alta calidad. Se explicará con detalle en la siguiente unidad.
• Ajuste de word_size: Con la opción -word_size es posible ajustar el tamaño de la semilla. Para búsquedas de secuencias con baja similitud, utilice valores pequeños (por ejemplo, 7); para secuencias muy similares, utilice valores grandes (por ejemplo, 28).
• Local vs remoto: La web de BLAST de NCBI puede ser lenta dependiendo del tráfico. Si necesita realizar búsquedas masivas a diario, ejecute BLAST+ en local mediante la CLI (se aborda en M12). Esto reduce la carga del servidor y mejora la reproducibilidad.

Mapeo con Ciencias de la Computación

• Índices basados en hash: La relación k-mer → lista de posiciones es exactamente una tabla hash. Tal como se aprende en CS.
• Seed-and-extend: Es el ejemplo típico de "filtro aproximado rápido + extensión precisa". Comparte la misma estructura fundamental que el reconocimiento facial, la búsqueda de documentos y la búsqueda de código.
• Filtrado estocástico: El criterio de dos aciertos es un filtro estocástico diseñado para reducir los falsos positivos. Pertenece a la misma familia que Bloom filters, MinHash y locality-sensitive hashing.

Ramas hacia el siguiente capítulo

• Siguiente capítulo (M11): Estadística del E-value de BLAST — Cómo convertir puntuaciones de alineamiento en probabilidades.
• Dos capítulos después (M12): Servidor local BLAST+ — Construcción de BLAST local con su propia base de datos.
• Tres capítulos después (M13): Sufixos y arrays — Refinamiento del índice de BLAST.
• Cinco capítulos después (M15): FM-index — La estructura de datos subyacente en BWA y Bowtie2.

Para profundizar más

El texto principal es una narrativa reconstruida por BPD. Para un estudio más profundo, consulte las siguientes referencias:

• Harvard STAT115 — Lección 3 del curso de la profesora Xiaole Shirley Liu: Deep Dive en el Algoritmo BLAST (con subtítulos completos y excelente traducción automática). Cubre exhaustivamente seed, extend y estadística.
• Artículo original: Altschul, S. F. et al. (1990), Basic Local Alignment Search Tool, J Mol Biol 215, 403–410. El padre fundacional de BLAST.
• Artículo original: Altschul, S. F. et al. (1997), Gapped BLAST and PSI-BLAST, Nucleic Acids Res 25, 3389–3402. El padre fundacional de Gapped BLAST.
• Manual de NCBI — The BLAST Sequence Analysis Tool. La referencia definitiva para el ajuste práctico de parámetros.
• Texto de referencia: Durbin et al. Biological Sequence Analysis, Capítulo 4.

En la web de NCBI BLAST, busquemos la secuencia de interés y utilicemos los resultados como preparación para el próximo capítulo M11, donde exploraremos cómo se calculan la puntuación (Score) y el valor E. ¡Mover las manos es lo que convierte las estadísticas del próximo capítulo en conocimiento vivo!