Indexación de bases de datos de secuencias: cómo crear una herramienta para búsquedas instantáneas con 100 millones de registros

Al finalizar este tema

Podrás integrar los conceptos de índices de BD, tablas hash y búsqueda binaria aprendidos en los libros de texto para construir tu propia herramienta de indexación que encuentre elementos en tablas de variantes/secuencias de millones o cientos de millones de registros de forma instantánea y sin realizar un escaneo lineal. Comprenderás mediante código qué sucede internamente cuando se dice que "una consulta es 100 veces más rápida tras aplicar un índice a la BD".

Este artículo es un ejemplo educativo general. Se ha utilizado la consulta de tablas de variantes genómicas como tema debido a que es una tarea cotidiana en bioinformática.

"Busca esa variante en esa posición" — el problema de escanear todo cada vez

Los datos de variantes genómicas suelen presentar esta estructura de tabla: cromosoma, posición, base de referencia, base variante e información adicional.

chrom   pos       ref  alt  gene
chr1    12345     A    G    GENE_A
chr1    67890     C    T    GENE_B
chr7    55211     G    A    GENE_C
...  (de millones a cientos de millones de filas)

Aquí hay dos preguntas comunes:

1. Consulta de posición exacta: "¿Hay una variante en la posición 12345 de chr1?" — un solo punto.
2. Consulta de rango: "Dame todas las variantes entre 10000 y 20000 de chr1" — un intervalo.

Si se hace de forma simple, se recorre todo desde el principio hasta el final en cada ocasión (escaneo lineal).

def find_linear(records, chrom, pos):
    hits = []
    for r in records:
        if r["chrom"] == chrom and r["pos"] == pos:
            hits.append(r)
    return hits

Si hay 10.000 variantes, el proceso es rápido. Pero en un genoma completo, las variantes son de millones a cientos de millones. Si se escanea todo el conjunto con una sola consulta, para realizar 100 preguntas habría que recorrerlo 100 veces. Aquí es donde surge el problema: "¿Por qué esta consulta es tan lenta?".

Quien haya trabajado con bases de datos lo sabe: en estos casos, se crea un índice. Pero, ¿qué hace exactamente un índice para acelerar el proceso? En este artículo, construiremos ese índice desde cero.

Primero, veamos el producto terminado (ejecutando la caja negra)

La herramienta que crearemos escaneará la tabla una vez para crear un índice y, a partir de entonces, procesará las consultas de forma inmediata.

db = VariantIndex(records)     # construir el índice una sola vez

db.get("chr1", 12345)          # consulta exacta → inmediata
db.range("chr1", 10000, 20000) # consulta de rango → inmediata

=== Rendimiento de consulta (500 000 variantes) ===
Consulta exacta (escaneo lineal): 0.0180 s/consulta
Consulta exacta (índice hash)   : 0.0000009 s/consulta   ← unas 20 000 veces más rápido
Consulta de rango (escaneo lineal): 0.0210 s/consulta
Consulta de rango (búsqueda binaria): 0.0000254 s/consulta   ← unas 800 veces más rápido
Construcción del índice (una vez): 0.32 s

La clave es "construir una vez, consultar infinitamente rápido". Aunque se invierte un breve tiempo en crear el índice, a partir de ese momento, las consultas se vuelven extremadamente rápidas. A continuación, crearemos dos tipos de índices para alcanzar esta velocidad.

¿De qué componentes está compuesta esta herramienta? (Despiece)

Índice de variantes (VariantIndex)
   ┌──────────────────────────────────────────────┐
   │  [Entrada] cargar tabla ─── componente: E/S de archivos │ ← se proporciona listo (herramienta)
   │              │                                 │
   │      ┌───────┴────────┐                        │
   │      ▼                ▼                         │
   │  [Consulta exacta]    [Consulta de rango]         │
   │  Índice hash          Ordenación + búsqueda binaria│
   │  comp.: tabla hash    comp.: búsqueda binaria     │ ← construyes ambos ★
   │      │                │                         │
   │      └───────┬────────┘                         │
   │              ▼                                  │
   │  [Significado] esto es un índice de BD ─ comp.: índice de BD │ ← lo construyes ★
   └──────────────────────────────────────────────┘

📌 Si es la primera vez que ves estos conceptos (enlaces de acceso superior)

• Tabla Hash — El principio de los diccionarios
• Búsqueda binaria
• Índice de DB — Cómo buscar entre 100 millones de registros en 0.01 segundos

Los nuevos conceptos que crearás directamente son 3: Índice Hash, Búsqueda binaria e Índice de DB. La lectura de archivos se entrega como una herramienta ya terminada. Solo 3; dentro del límite cognitivo.

Paso 1 de la creación — Preparación de datos (proporcionado)

La parte que genera los datos para la consulta se entrega como una herramienta. En la práctica, se leen desde un archivo, pero para la práctica en el navegador, se generan como una lista.

import random

random.seed(1)
chroms = ["chr1", "chr2", "chr7"]

def make_records(n):
    recs = []
    for i in range(n):
        recs.append({
            "chrom": random.choice(chroms),
            "pos": random.randint(1, 1_000_000),
            "ref": random.choice("ACGT"),
            "alt": random.choice("ACGT"),
            "gene": f"GENE_{i % 500}",
        })
    return recs

records = make_records(50000)
assert len(records) == 50000
assert set(r["chrom"] for r in records) <= {"chr1", "chr2", "chr7"}

Este records es nuestra "tabla". Ahora lo indexaremos de dos maneras.

Paso 2 de la creación — Índice hash para consultas exactas ★ (Tabla hash)

✍️ Sección de llenado manual. Componente = Tabla hash. Objetivo: lograr que la búsqueda de "(cromosoma, posición) → variantes" sea O(1).

La clave para la consulta exacta es lo mismo que vimos en la sección de primers anterior: si lo colocas previamente en un diccionario (=tabla hash), puedes extraerlo de inmediato. Aquí, utilizaremos la tupla (cromosoma, posición) como clave.

🔎 ¿Qué es un índice hash? (Cajón — hash-table) Si colocas clave → valor en un diccionario, más tarde puedes extraer el valor de una sola vez usando esa clave (O(1)). No es necesario recorrer todo el conjunto. No hay nada más rápido para una búsqueda que busca "exactamente esta clave". Esto es el índice hash de una DB.

from collections import defaultdict

def build_hash_index(records):
    """(chrom, pos) → lista de variantes en esa posición."""
    index = defaultdict(list)
    for r in records:
        index[(r["chrom"], r["pos"])].append(r)
    return index

hash_index = build_hash_index(records)

def get_exact(hash_index, chrom, pos):
    return hash_index.get((chrom, pos), [])

# Verificación: la consulta hash debe coincidir exactamente con el escaneo lineal
sample = records[12345]
linear = find_linear(records, sample["chrom"], sample["pos"])
hashed = get_exact(hash_index, sample["chrom"], sample["pos"])
assert hashed == linear
assert len(get_exact(hash_index, "chr1", -999)) == 0     # una posición inexistente devuelve una lista vacía

find_linear(Exploración general) y get_exact(Hash) producen resultados idénticos, lo cual se ha verificado mediante un assert. La respuesta es la misma; solo difiere la velocidad. El índice hash permite realizar consultas en tiempo constante, independientemente del número de posiciones.

🤔 Prompt de autoexplicación Se utilizó la tupla (chrom, pos) como clave. ¿Qué problema surgiría si se usara solo pos como clave? (Pista: diferentes cromosomas pueden tener la misma posición. chr1:12345 y chr7:12345 son variantes distintas).

Paso 3 de creación: índice de búsqueda binaria para consultas de rango ★ (Búsqueda binaria)

✍️ Sección para completar. Componente = Búsqueda binaria. Objetivo: encontrar "todas las variantes de este intervalo" en O(log n).

El índice hash es óptimo para "esta posición exacta", pero es ineficaz para "todo lo que está entre 10000 y 20000". Dado que el hash no tiene orden, no puede agrupar rangos. Para las consultas de rango, se necesita otra herramienta: ordenación + búsqueda binaria.

La idea es la siguiente: si se ordenan las posiciones por cromosoma, se pueden encontrar inmediatamente los puntos de inicio y fin del rango mediante búsqueda binaria y, a continuación, extraer el segmento comprendido entre ellos.

🔎 ¿Qué es la búsqueda binaria? (Drawer — binary-search) Consiste en dividir sucesivamente por la mitad los datos ordenados hasta encontrar el elemento. Incluso con 1 millón de elementos, se completa en aproximadamente 20 pasos (log₂ 1.000.000 ≈ 20). Es similar a buscar una palabra en un diccionario abriendo por la mitad para decidir si continuar en la parte anterior o posterior. La biblioteca estándar de Python bisect se encarga de esto.

import bisect

def build_range_index(records):
    """Ordena las posiciones por cromosoma. (array de pos ordenado y registros correspondientes)"""
    by_chrom = defaultdict(list)
    for r in records:
        by_chrom[r["chrom"]].append(r)
    index = {}
    for chrom, recs in by_chrom.items():
        recs.sort(key=lambda r: r["pos"])          # ordenar por posición (una vez al construir)
        positions = [r["pos"] for r in recs]
        index[chrom] = (positions, recs)
    return index

range_index = build_range_index(records)

def get_range(range_index, chrom, start, end):
    if chrom not in range_index:
        return []
    positions, recs = range_index[chrom]
    lo = bisect.bisect_left(positions, start)       # posición donde se insertaría start (O(log n))
    hi = bisect.bisect_right(positions, end)        # posición posterior a end
    return recs[lo:hi]                              # extraer de una vez el segmento intermedio

# Verificación: el rango binario debe coincidir con el filtro lineal (cantidad y contenido)
def range_linear(records, chrom, start, end):
    return [r for r in records if r["chrom"] == chrom and start <= r["pos"] <= end]

bs = get_range(range_index, "chr1", 100000, 200000)
lin = range_linear(records, "chr1", 100000, 200000)
assert len(bs) == len(lin)
assert sorted(r["pos"] for r in bs) == sorted(r["pos"] for r in lin)
# Comprobar límites inclusivos: deben incluirse start y end (combinación bisect_left/right)
assert all(100000 <= r["pos"] <= 200000 for r in bs)

bisect_left/bisect_right La combinación es clave. Con estos dos, se encuentran los índices de los extremos del rango en O(log n) y se obtiene todo el segmento intermedio mediante recs[lo:hi]. Mientras que un filtro lineal recorre todo el conjunto, la búsqueda binaria identifica el intervalo en pocos pasos, como si se desplegara un índice.

🤔 Pregunta para la autoexplicación ¿Por qué se usó bisect_left en el punto inicial y bisect_right en el punto final? Si se usara bisect_left para ambos, ¿la variante ubicada exactamente en la misma posición que end se incluiría o se excluiría del resultado? (Una sola condición de límite puede cambiar el resultado).

Unificar las piezas: clase de índice completa

Agrupa ambos índices en una única herramienta. Esto es, en esencia, un índice de base de datos en miniatura.

class VariantIndex:
    def __init__(self, records):
        self.records = records
        self.hash_index = build_hash_index(records)     # para consultas exactas
        self.range_index = build_range_index(records)   # para consultas de rango

    def get(self, chrom, pos):
        return get_exact(self.hash_index, chrom, pos)

    def range(self, chrom, start, end):
        return get_range(self.range_index, chrom, start, end)

db = VariantIndex(records)

# Ambas consultas deben coincidir con los resultados del escaneo lineal
s = records[999]
assert db.get(s["chrom"], s["pos"]) == find_linear(records, s["chrom"], s["pos"])
assert len(db.range("chr2", 0, 1_000_000)) == len(range_linear(records, "chr2", 0, 1_000_000))

🔎 Entonces, ¿qué es un índice de DB? (Draweer — db-index) Al aplicar CREATE INDEX a la DB, esta realiza exactamente la misma tarea que acabamos de crear. Para búsquedas exactas, crea un índice hash; para búsquedas por rango, una estructura ordenada (B-tree, el pariente de la búsqueda binaria). Decir que "el índice lo hizo 100 veces más rápido" significa que el escaneo completo se transformó en una búsqueda hash o binaria. Acaban de implementar directamente el funcionamiento interno de esa magia.

Análisis profundo del rendimiento — ¿Por qué es tan rápido?

import time

records = make_records(200000)
db = VariantIndex(records)
targets = [(r["chrom"], r["pos"]) for r in random.sample(records, 200)]

# Consulta exacta: lineal frente a hash
t0 = time.time()
for c, p in targets: find_linear(records, c, p)
linear_time = time.time() - t0

t0 = time.time()
for c, p in targets: db.get(c, p)
hash_time = time.time() - t0

print(f"200 consultas exactas — lineal: {linear_time:.4f} s")
print(f"200 consultas exactas — hash  : {hash_time:.6f} s")
assert hash_time < linear_time

Los números varían según la máquina, pero la lógica es siempre la misma. La búsqueda lineal se vuelve más lenta a medida que los datos crecen (O(n)), mientras que la búsqueda hash permanece constante (O(1)). El tiempo invertido en la construcción del índice (O(n) una sola vez) se amortiza rápidamente a medida que se realizan más consultas. En sistemas con un alto volumen de consultas, el índice es la opción ganadora.

Otros caminos (Reflexión multipasos)

• Bases de datos reales (SQLite/PostgreSQL): En la práctica, la base de datos hace lo que nosotros hemos implementado manualmente. CREATE INDEX ... ON variants(chrom, pos) Una sola línea es suficiente. Cuándo nuestro método es mejor: cuando necesitamos entender y depurar exactamente qué está haciendo el índice. Si usamos la base de datos solo como una caja negra, no podremos identificar por qué es lenta.
• Árbol de intervalos (Interval Tree): Si las variantes no son "puntos" sino "intervalos" (por ejemplo, CNV, regiones génicas), un árbol de intervalos es mejor que la búsqueda binaria. Compromiso (Trade-off): complejidad de implementación ↔ rendimiento en consultas de superposición de intervalos.
• Memoria vs. disco: Nuestro índice reside completamente en la RAM. Si los datos superan la capacidad de la RAM, se requieren índices basados en disco (B-tree en disco). Las bases de datos reales se encargan de esto.

Clave: "Para búsquedas exactas, hash; para búsquedas de rango, ordenación + búsqueda binaria". Este principio no cambia, ya sea que lo implementemos manualmente o usemos una base de datos. La habilidad reside en elegir el índice según la forma de la consulta.

Siguiente paso (Enlaces de salida)

• Por qué el hash es O(1) y cómo se resuelven las colisiones → Tabla hash
• Estructuras de árbol, la familia de la búsqueda binaria → Árbol de búsqueda binaria
• Conexión con el eliminador de duplicados creado anteriormente → Aplicación: Eliminador de duplicados de primers

Inténtalo tú mismo (Problemas independientes)

1. Índice de nombres de genes: Agrega un índice hash para realizar una búsqueda exacta usando gene en lugar de pos. ("Dame todas las variantes de GENE_42")
2. Condiciones múltiples: Encuentra las variantes que estén "entre 10000 y 20000 en chr1" y cuyo "alt sea 'G'" utilizando un índice de rango + filtro.
3. Costo de construcción vs. índice: Mediante un experimento, encuentra el punto de equilibrio con el escaneo lineal para determinar cuántas consultas deben realizarse para que el costo de construcción del índice se amortice.
4. Desafío: Implementa un método para mantener bisect.insort sin tener que reordenar el índice de rango cada vez que se añaden nuevas variantes en tiempo real.

Resumen

Hemos conquistado el problema de "encontrar lo que buscamos en tablas de gran tamaño" utilizando dos tipos de índices.

• La tabla hash permite realizar búsquedas exactas en O(1). (Búsqueda por punto)
• La búsqueda binaria permite realizar consultas de rango en posiciones ordenadas con una complejidad de O(log n). (Consulta de intervalos)
• Los índices de DB nos muestran que esto es precisamente lo que la DB hace internamente. (Integración de principios)

CREATE INDEX Si esta línea te ha parecido magia, ahora podrás ver qué hay dentro. No es magia, sino simplemente un mapa que el hash y la búsqueda binaria (aprendidos en los libros de texto) han preparado de antemano junto a los datos.

Este texto es un ejemplo educativo general. En la práctica, se añaden índices multicolumna, almacenamiento basado en disco, concurrencia, entre otros. La versión detallada puede ser construida por ustedes sobre esta estructura o delegada a una DB verificada.