Por qué es necesario esto

La Transformada de Burrows-Wheeler (BWT) fue inventada en 1994 por David Wheeler y Michael Burrows para la compresión de datos. Su aplicación inicial fue el programa de compresión bzip2. Parecía no tener relación con la búsqueda de secuencias.

Sin embargo, a finales de la década de 2000, la BWT cambió las reglas del juego en el alineamiento genómico. BWA (2009) y Bowtie (2009) demostraron un rendimiento capaz de alinear cientos de miles de lecturas cortas en el genoma humano por segundo utilizando el FM-index basado en BWT. Casi todos los pipelines de alineamiento de lecturas cortas que utilizamos hoy en día se basan en esta estructura de datos.

En este episodio, derivemos manualmente los principios de la BWT: la ordenación cíclica y la transformación inversa. El FM-index del siguiente episodio (M15) será una continuación natural.

Paso 1 — Rotación y ordenación

Comencemos con la cadena T = BANANA$. El símbolo $ es un marcador de fin (un carácter especial no presente en el original).

Cree todas las rotaciones. Repita el proceso de mover el carácter del extremo izquierdo al extremo derecho.

BANANA$
ANANA$B
NANA$BA
ANA$BAN
NA$BANA
A$BANAN
$BANANA

Se ordena alfabéticamente.

$BANANA
A$BANAN
ANA$BAN
ANANA$B
BANANA$
NA$BANA
NANA$BA

El último columna de estas rotaciones ordenadas es lo que se conoce como la BWT.

$BANANA → A
A$BANAN → N
ANA$BAN → N
ANANA$B → B
BANANA$ → $
NA$BANA → A
NANA$BA → A

BWT(T) = "ANNB$AA"

Por qué esto es bueno para la compresión

Al observar ANNB$AA, vemos que los mismos caracteres tienden a aparecer consecutivamente: NN, AA. Está más agrupada que la cadena original BANANA$.

Esto no es casualidad. La última columna de las rotaciones ordenadas tiende a presentar caracteres repetidos agrupados. Esto se debe a que, cuando el arreglo de sufijos se ordena alfabéticamente, los sufijos que comparten el mismo prefijo se agrupan, y sus caracteres inmediatamente anteriores (es decir, la última columna) también suelen ser iguales con frecuencia.

Cuando los caracteres están agrupados, la compresión mediante Move-to-Front + Huffman · Arithmetic Coding es mucho más eficiente. Este es el principio de bzip2.

Propiedad sorprendente — La BWT es reversible

Esta es la verdadera magia de la BWT como estructura de datos. Con solo la BWT, se puede restaurar completamente la cadena original.

Procedimiento de inversión:

1. Ordenar alfabéticamente los caracteres de la BWT produce la primera columna de las rotaciones ordenadas. ANNB$AA → orden lexicográfico → $AAABNN (primera columna).
2. Etiquetar cada carácter con "qué número de repetición es esta posición" para distinguir caracteres idénticos.
3. LF-mapping: El i-ésimo carácter de la última columna y el i-ésimo carácter de la primera columna son adyacentes en la cadena original (uno precede al otro).
4. Al repetir el LF-mapping, se puede extraer la cadena original.

En Python, se vería así:

def bwt(text: str) -> str:
    text = text + "$"
    n = len(text)
    rotations = [text[i:] + text[:i] for i in range(n)]
    rotations.sort()
    return "".join(row[-1] for row in rotations)

def inverse_bwt(bwt_str: str) -> str:
    n = len(bwt_str)
    # Etiquetar cada carácter con su número de repetición
    last = list(bwt_str)
    first = sorted(bwt_str)

    # Construir el mapeo LF
    # Para cada carácter, indicar qué aparición ocupa en la primera columna
    from collections import defaultdict
    count = defaultdict(int)
    last_tagged = []
    for c in last:
        last_tagged.append((c, count[c]))
        count[c] += 1

    count = defaultdict(int)
    first_tagged = []
    for c in first:
        first_tagged.append((c, count[c]))
        count[c] += 1

    # Reconstruir la cadena original
    lf_map = {c: i for i, c in enumerate(last_tagged)}
    result = []
    i = last_tagged.index(("$", 0))
    for _ in range(n):
        result.append(first_tagged[i][0])
        i = lf_map[first_tagged[i]]
    return "".join(result).rstrip("$")

# Uso
original = "BANANA"
transformed = bwt(original)
print(f"BWT: {transformed}")  # ANNB$AA
recovered = inverse_bwt(transformed)
print(f"Recuperada: {recovered}")  # BANANA

La razón por la que esta transformación inversa es posible es que la primera y la última columna de la rotación ordenada son adyacentes en el original. Más precisamente, el carácter que sigue al de la última columna en la misma posición es el de la primera columna.

La elegancia del mapeo LF

El mapeo LF (LF-mapping) es el concepto central de esta conveniencia. Es la abreviatura de Last-to-First mapping.

Definición: ¿En qué posición de la primera columna se encuentra el mismo carácter que en la posición i-ésima de la última columna, y ambos corresponden a la misma posición en el original?

Respuesta: Si el carácter c en la posición i-ésima de la última columna es la j-ésima repetición de c en dicha columna, entonces también la j-ésima repetición de c en la primera columna corresponde a la misma posición en el original.

Esta hermosa propiedad permite no solo la reconstrucción del original, sino también encontrar patrones arbitrarios con extrema velocidad en el índice FM de la próxima sección.

Relación con el sufijo array

El BWT es, de hecho, una representación transformada del sufijo array.

• Sufijo array (SA): posiciones de inicio de los sufijos ordenados.
• BWT: el carácter inmediatamente anterior a cada sufijo ordenado.

Matemáticamente, esto se expresa como:

BWT[i] = T[SA[i] - 1] \quad \text{(si SA[i] = 0, se usa } T[n-1] \text{)}

Es decir, la BWT extrae el carácter inmediatamente anterior a cada posición inicial del array de sufijos.

Práctica con Rosalind

En BWT de Rosalind puede resolver un ejercicio que pide calcular la BWT. Basta con la función bwt anterior.

Trampas comunes en la práctica

• Necesidad del marcador de fin: sin $, no hay forma de distinguir la cadena original entre las rotaciones ordenadas y la transformación inversa falla. Debe usarse un carácter especial que no aparezca en el original.
• Tamaño del alfabeto: en cadenas con alfabetos grandes (por ejemplo, Unicode), aumenta el tamaño del mapeo LF. Es muy eficiente para el ADN, cuyo alfabeto tiene entre cuatro y cinco caracteres.
• Implementación real de la ordenación por rotaciones: el código Python anterior es didáctico y cuesta $O(n^2 \log n)$. BWA construye en la práctica el array de sufijos con SA-IS en O(n) y deriva después la BWT en O(n).
• Almacenamiento en disco: la BWT del genoma humano ocupa aproximadamente 3 GB, un tamaño similar al original. BWA la comprime, la guarda en disco y la utiliza mediante mmap.

Mapeo de CS

• Ordenación por rotaciones (rotation sorting): es un ejemplo clásico del punto donde se solapan la compresión y la búsqueda.
• Move-to-Front · Huffman · codificación aritmética: el pipeline de compresión de bzip2 sigue BWT → MTF → Huffman → resultado.
• Mapeo LF: es una identidad elegante de la teoría de estructuras de datos. Sin esta propiedad, la BWT sería tan solo una transformación de compresión.
• Dualidad entre compresión e indexación: la observación de que una representación fácil de comprimir también favorece la búsqueda está vinculada a principios fundamentales de la teoría de la información.

Ramificaciones para los próximos artículos

• Próximo artículo (M15): FM-index — una estructura de datos para mapeo ultrarrápido completada con BWT + Rank/Select.
• Dos artículos más adelante (M16): minimap2 · minimizadores — el índice de la era de las lecturas largas.
• Nueve artículos más adelante (S03): BWA-MEM en la práctica — aplicación real de la estructura de datos que acabamos de construir.
• Dieciséis artículos más adelante (S22 · S23): ensamblaje — la BWT también se aplica al ensamblaje.

Si desea profundizar

El texto principal es una exposición reconstruida por BPD. Para profundizar, consulte los recursos siguientes.

• MIT 7.91J — conferencia BWT and Read Mapping del profesor David Gifford (con subtítulos completos y buena traducción automática). Trata conjuntamente la estructura de datos de la BWT y sus aplicaciones de compresión.
• CMU 02-510 — Ben Langmead (creador de Bowtie) imparte Data Structures for Genome Indexing (con subtítulos completos y excelente traducción automática). Explica con gran claridad el BWT y el FM-index.
• Artículo original: Burrows, M. & Wheeler, D. (1994), A block-sorting lossless data compression algorithm, Technical Report 124 del Digital Systems Research Center. El origen del BWT.
• Artículo original: Ferragina, P. & Manzini, G. (2000), Opportunistic data structures with applications, FOCS. El origen del FM-index.
• Herramienta de referencia: bzip2 código fuente. Implementación práctica de la aplicación de compresión del BWT.

Resolvamos los problemas BWT y SUFF en Rosalind. En el siguiente capítulo, M15, se comprenderá por qué el FM-index es una extensión natural del BWT.