Por qué es necesario este capítulo

El BLAST de M10 · M11 utilizó un índice k-mer basado en hash. Es rápido, pero tiene dos limitaciones.

1. k es fijo: Se debe definir k al crear el índice. Si se desea un k diferente, hay que volver a crearlo.
2. El manejo de coincidencias parciales es torpe: Encuentra bien las coincidencias exactas, pero la búsqueda de diversas combinaciones de sufijos y prefijos no es natural.

El árbol de sufijos (suffix tree) y el arreglo de sufijos (suffix array) superan estas limitaciones. Se pueden encontrar patrones de longitud arbitraria en tiempo O(m) (m = longitud del patrón). Esto es independiente del tamaño del genoma de referencia. En este capítulo, abordaremos los principios y las diferencias de estas dos estructuras de datos. Una vez establecido este capítulo, el BWT · FM-index de M14～M15 se seguirá de forma natural.

¿Qué es un sufijo (Suffix)?

La cadena T = BANANA$ tiene los siguientes sufijos, donde $ es el marcador de final.

0: BANANA$
1: ANANA$
2: NANA$
3: ANA$
4: NA$
5: A$
6: $

En total, hay 7 (longitud + 1). Indica en qué posición de la cadena comienza cada sufijo.

Árbol de sufijos: inserción de todos los sufijos en un árbol

Un árbol de sufijos es una estructura de datos que agrupa los sufijos anteriores en un único árbol para su almacenamiento. Cada ruta corresponde a un sufijo.

BANANA$
       /
      /       A
[root]--- NA$
      \    NANA$
       \
        $

Propiedades clave:

• Número de hojas = número de sufijos = longitud de la cadena + 1
• Cada hoja almacena la posición inicial en la cadena original
• El prefijo común de dos sufijos comparte el mismo camino

Gracias a esta estructura, es posible:

• Verificar si el patrón P existe en T: recorriendo desde la raíz del árbol hasta O(m) tiempo.
• Contar cuántas veces aparece P: basta con contar las hojas debajo del nodo alcanzado.
• Encontrar la subsecuencia repetida más larga: se reduce al problema del ancestro común más cercano (LCA) entre dos hojas.
• Encontrar la subsecuencia común de dos cadenas: combinando dos árboles de sufijos.

Algoritmo de Ukkonen — construcción del árbol en O(n) tiempo

Construir un árbol de sufijos de forma ingenua toma O(n^2), pero Esko Ukkonen publicó en 1995 un algoritmo de tiempo lineal O(n). El principio se basa en un truco llamado enlace de sufijo (suffix link). Los detalles son complejos, por lo que aquí solo se registran los conceptos.

• Agregar los sufijos uno por uno al árbol.
• Reutilizar las partes que coinciden con sufijos ya existentes.
• Saltar a la siguiente posición de inserción mediante el enlace de sufijo.

Los detalles están rigurosamente organizados en el Capítulo 6 del libro Algorithms on Strings, Trees, and Sequences de Dan Gusfield (1997).

Implementación (simplificada) de un árbol de sufijos en Python

Veamos una implementación ingenua O(n^2) con fines educativos.

class SuffixTreeNode:
    def __init__(self):
        self.children = {}
        self.suffix_indices = []

class SuffixTree:
    def __init__(self, text: str):
        self.text = text + "$"
        self.root = SuffixTreeNode()
        for i in range(len(self.text)):
            self._insert(self.text[i:], i)

    def _insert(self, suffix: str, index: int):
        node = self.root
        for c in suffix:
            if c not in node.children:
                node.children[c] = SuffixTreeNode()
            node = node.children[c]
        node.suffix_indices.append(index)

    def search(self, pattern: str) -> list[int]:
        node = self.root
        for c in pattern:
            if c not in node.children:
                return []
            node = node.children[c]
        # Recopilar los índices de todas las hojas bajo este nodo
        result = []
        self._collect_indices(node, result)
        return sorted(result)

    def _collect_indices(self, node, result):
        result.extend(node.suffix_indices)
        for child in node.children.values():
            self._collect_indices(child, result)

# Uso
tree = SuffixTree("BANANA")
print(tree.search("ANA"))  # [1, 3]

ANA que aparece en las posiciones 1 y 3 de BANANA se encuentra en el tiempo O(m).

Matriz de sufijos: una versión comprimida del árbol de sufijos

Los árboles de sufijos son potentes, pero tienen el inconveniente de que consumen mucha memoria. Aproximadamente 20n bytes (20 bytes por carácter). Para el genoma humano, esto serían 60 GB.

Una matriz de sufijos es mucho más pequeña. Es una matriz de enteros que contiene las posiciones de inicio de cada sufijo, ordenadas alfabéticamente. Para el genoma humano, esto serían aproximadamente 4n bytes, es decir, 12 GB.

La matriz de sufijos de BANANA$:

Ordenar lexicográficamente las posiciones iniciales de los sufijos:
$        → 6
A$       → 5
ANA$     → 3
ANANA$   → 1
BANANA$  → 0
NA$      → 4
NANA$    → 2

Array de sufijos: SA = [6, 5, 3, 1, 0, 4, 2]

La forma de hacerlo con Python es sorprendentemente sencilla.

def suffix_array(text: str) -> list[int]:
    text = text + "$"
    n = len(text)
    return sorted(range(n), key=lambda i: text[i:])

# Uso
sa = suffix_array("BANANA")
print(sa)  # [6, 5, 3, 1, 0, 4, 2]

Esta implementación simple basada en ordenamiento tiene un tiempo de $O(n^2 \log n)$. Las herramientas reales utilizan algoritmos de tiempo O(n) como SA-IS y DC3.

Búsqueda con el arreglo de sufijos

Dado que el arreglo de sufijos está ordenado, es posible encontrar patrones mediante búsqueda binaria.

def sa_search(text: str, sa: list[int], pattern: str) -> list[int]:
    text_with_end = text + "$"
    n = len(text_with_end)
    m = len(pattern)

    # Buscar la primera coincidencia mediante búsqueda binaria
    lo, hi = 0, n
    while lo < hi:
        mid = (lo + hi) // 2
        if text_with_end[sa[mid]:sa[mid]+m] < pattern:
            lo = mid + 1
        else:
            hi = mid
    left = lo

    # Buscar la última coincidencia mediante búsqueda binaria
    lo, hi = 0, n
    while lo < hi:
        mid = (lo + hi) // 2
        if text_with_end[sa[mid]:sa[mid]+m] <= pattern:
            lo = mid + 1
        else:
            hi = mid
    right = lo

    return sorted(sa[left:right])

# Uso
text = "BANANA"
sa = suffix_array(text)
print(sa_search(text, sa, "ANA"))  # [1, 3]

La complejidad temporal es $O(m \log n)$. Es algo más lento que el árbol, pero utiliza mucha menos memoria.

Intercambios entre árbol de sufijos y matriz de sufijos

En la práctica suele preferirse el array de sufijos: el ahorro de memoria compensa la pequeña pérdida de velocidad de búsqueda.

Práctica con Rosalind

El problema SUFF de Rosalind permite practicar la construcción de un array de sufijos. Puede resolverse en 3–5 líneas de Python.

Problemas comunes en la práctica

• Carácter de fin $: debe utilizarse un carácter especial ausente de la cadena original, normalmente $ o \0. Sin él, el árbol de sufijos puede colapsar parcialmente.
• Repeticiones largas: en genomas ricos en secuencias repetitivas, el tamaño real del árbol o array puede superar la estimación teórica, especialmente en telómeros y centrómeros humanos.
• Tamaño del alfabeto: el ADN tiene 4–5 símbolos y un factor de ramificación pequeño; las proteínas tienen 20 y el texto Unicode muchos más.
• Disco frente a memoria: cuando el genoma de referencia es grande, el array de sufijos debe almacenarse en disco y utilizarse mediante mmap, como hacen BWA y Bowtie.

Correspondencias con la informática

• Estructura en árbol: el árbol de sufijos es un caso especial de trie, una estructura clásica de la teoría de cadenas.
• Búsqueda binaria: el array de sufijos se consulta mediante búsqueda binaria, aplicando el principio básico de búsqueda logarítmica sobre datos ordenados.
• Afinidad con la caché: es una razón importante por la que los arrays de sufijos superan a los árboles en la práctica; la jerarquía de caché de las CPU modernas influye en la elección del algoritmo.
• Compresión: BWT, tratado en la siguiente unidad, y FM-index almacenan el array de sufijos en forma comprimida, reduciendo aún más la memoria mediante la combinación de teoría de la información y estructuras de datos.

Continuación en el próximo artículo

• Siguiente unidad (M14): Burrows–Wheeler Transform, pariente del array de sufijos que combina compresión y búsqueda.
• Unidad M15: FM-index, estructura de mapeo ultrarrápida que combina BWT con operaciones rank/select y constituye el núcleo de BWA y Bowtie2.
• Unidad M16: minimap2 y minimizers, diseño de índices para lecturas largas.
• Unidad S03: práctica con BWA-MEM, aplicación real de las estructuras construidas aquí.

Si quieres profundizar más

El siguiente texto es una narración autorreconstruida por BPD. Profundización a continuación.

• UC Berkeley CS176 — Curso de la profesora Yun Song sobre Suffix Trees and Arrays (subtítulos completos). Detalle exhaustivo de los algoritmos Ukkonen y SA-IS.
• Artículo original: Ukkonen, E. (1995), On-line construction of suffix trees, Algorithmica 14, 249–260. La fuente original de la construcción lineal de árboles de sufijos.
• Artículo original: Manber, U. & Myers, G. (1993), Suffix arrays: A new method for on-line string searches, SIAM J Comput 22, 935–948. El origen de los arreglos de sufijos.
• Libro de texto de referencia: Gusfield, D. Algorithms on Strings, Trees, and Sequences (1997). Texto clásico fundamental.
• Herramienta de referencia: sais-py (implementación SA-IS para Python). Útil cuando se necesita un arreglo de sufijos en la práctica.

Resuelva problemas de búsqueda de cadenas como SUFF, LREP y REVP en Rosalind. En el próximo capítulo M14, comprenderá naturalmente por qué BWT es un primo lejano de los arreglos de sufijos.