De las secuencias al árbol evolutivo

Una vez creado el MSA, el siguiente paso es el árbol filogenético (phylogenetic tree). Representa las relaciones evolutivas entre especies o genes mediante un árbol binario. A partir de este único árbol se derivan innumerables análisis, como el orden de la especiación, la estimación de ancestros comunes y la medición de la velocidad evolutiva.

Los algoritmos de árboles filogenéticos se dividen principalmente en tres ramas:

• Basados en la distancia (este episodio, M26): Construyen el árbol utilizando una matriz de distancias entre secuencias. Son rápidos e intuitivos.
• Parsimonia (M27): El árbol que requiere el menor número de cambios en los datos observados.
• Máxima verosimilitud (M28): El árbol que maximiza la probabilidad de los datos observados.

En este episodio, derivaremos manualmente los dos representantes basados en la distancia, UPGMA y NJ, y los implementaremos en Python.

Creación de la matriz de distancias

Se calcula la distancia entre pares de secuencias en el MSA. Lo más simple es la p-distance: la proporción de columnas en el alineamiento donde los caracteres son diferentes.

p_{ij} = \frac{\text{número de columnas con desajuste}}{\text{número total de columnas}}

En la práctica, esto se extiende a distancias evolutivas aplicando, por ejemplo, la corrección de Jukes-Cantor. Esto corrige estadísticamente la posibilidad de que hayan ocurrido múltiples sustituciones.

d_{JC}(p) = -\frac{3}{4} \ln\left(1 - \frac{4p}{3}\right)

Para la derivación de este episodio, usaremos la p-distance tal cual por conveniencia. Ejemplo con 4 especies.

UPGMA — El enfoque más simple

UPGMA (Unweighted Pair Group Method with Arithmetic mean) es un caso especial de agrupamiento jerárquico (average linkage).

Algoritmo:

1. Encontrar el par con la distancia más pequeña en la matriz de distancias.
2. Fusionar ese par en un solo clúster.
3. Calcular la distancia entre el nuevo clúster y los nodos restantes (promedio de las distancias de los dos nodos originales).
4. Repetir hasta que solo quede un nodo.

Derivación manual con el ejemplo anterior.

Paso 1: Distancia mínima = d(A,B) = 5. Fusionar A y B. La longitud de la rama (branch length) hasta el nodo fusionado = 5/2 = 2.5.

Paso 2: Recalcular la distancia entre el nuevo clúster (AB) y los restantes.

d((AB), C) = \frac{d(A,C) + d(B,C)}{2} = \frac{9 + 10}{2} = 9.5

d((AB), D) = \frac{9 + 10}{2} = 9.5

Nueva matriz de distancias:

Paso 3: Distancia mínima = d(C,D) = 8. Fusión de C y D. Longitud de la rama = 8/2 = 4.

Paso 4: Fusión de (CD) y (AB).

d((AB), (CD)) = \frac{d((AB),C) + d((AB),D)}{2} = \frac{9.5 + 9.5}{2} = 9.5

Longitud de la rama = 9,5/2 - 4 = 0,75 (se resta la profundidad del subárbol C·D, que es 4).

Árbol resultante (incluyendo longitudes de ramas):

┌── A (2.5)
     ┌─┤
(AB) │ └── B (2.5)
─────┤
(CD) │ ┌── C (4)
     └─┤
       └── D (4)

El supuesto crítico de UPGMA: el reloj molecular

UPGMA asume la existencia de un reloj molecular. Que todas las ramas hayan transcurrido el mismo tiempo desde la raíz implica que todas las hojas se encuentran a la misma distancia de la raíz (árbol ultramétrico).

Este supuesto suele violarse. Algunos linajes evolucionan a mayor velocidad, mientras que otros lo hacen más despacio. Si no se cumple el reloj molecular, UPGMA dibuja incorrectamente la topología del árbol.

NJ: un enfoque que abandona el reloj molecular

El método Neighbor Joining de Saitou & Nei(MBE 1987) abandona el supuesto del reloj molecular. Las longitudes de las ramas pueden variar entre las hojas. En su lugar, el criterio para seleccionar los pares a fusionar es más sofisticado.

La definición de la matriz Q es el corazón de NJ.

Q(i, j) = (n - 2) \cdot d(i, j) - \sum_{k} d(i, k) - \sum_{k} d(j, k)

n es el número de nodos restantes; los dos últimos términos son la suma total de distancias de cada nodo. Se fusiona el par con el valor Q más bajo.

¿Por qué la matriz Q? Si dos nodos i y j están evolutivamente cercanos, la "distancia total al resto del mundo" de cada uno será similar, y estos valores se cancelarán en Q, permitiendo centrarse puramente en la distancia pareada. Mientras que UPGMA simplemente elegía la distancia mínima, NJ elige la fusión óptima considerando el contexto circundante.

Se aplica el mismo ejemplo paso a paso.

Cálculo de Q:

• Σ_k d(A,k) = 5 + 9 + 9 = 23
• Σ_k d(B,k) = 5 + 10 + 10 = 25
• Σ_k d(C,k) = 9 + 10 + 8 = 27
• Σ_k d(D,k) = 9 + 10 + 8 = 27

n = 4. Entonces.

Q(A,B) = 2 \times 5 - 23 - 25 = 10 - 48 = -38 Q(A,C) = 2 \times 9 - 23 - 27 = 18 - 50 = -32 Q(A,D) = 2 \times 9 - 23 - 27 = 18 - 50 = -32 Q(B,C) = 2 \times 10 - 25 - 27 = 20 - 52 = -32 Q(B,D) = 2 \times 10 - 25 - 27 = 20 - 52 = -32 Q(C,D) = 2 \times 8 - 27 - 27 = 16 - 54 = -38

Q mínimo = -38 (empate: A-B y C-D). La primera fusión es A-B o C-D. En la práctica, estos empates son frecuentes en NJ y pueden alterar sutilmente la topología del árbol resultante.

El cálculo de las longitudes de las ramas es más sofisticado.

L(A) = \frac{d(A,B)}{2} + \frac{\sum_k d(A,k) - \sum_k d(B,k)}{2(n-2)} = \frac{5}{2} + \frac{23 - 25}{4} = 2.5 - 0.5 = 2 L(B) = d(A,B) - L(A) = 5 - 2 = 3

En UPGMA, las dos ramas eran simétricas (2,5; 2,5), mientras que en NJ fueron asimétricas (2; 3). Esto se interpreta como una evolución ligeramente más rápida de B en comparación con A.

Implementación de NJ en Python (~40 líneas)

def neighbor_joining(D, labels):
    """Algoritmo NJ. D es la matriz de distancias (lista de listas) y labels son los nombres de los nodos."""
    tree = []
    n = len(labels)
    nodes = list(range(n))
    dist = [row[:] for row in D]
    next_id = n

    while len(nodes) > 2:
        m = len(nodes)
        # Calcular la matriz Q
        total = [sum(dist[i][k] for k in range(m)) for i in range(m)]
        Q = [[0]*m for _ in range(m)]
        for i in range(m):
            for j in range(m):
                if i != j:
                    Q[i][j] = (m-2) * dist[i][j] - total[i] - total[j]

        # Par con Q mínima
        min_val, mi, mj = float('inf'), 0, 1
        for i in range(m):
            for j in range(i+1, m):
                if Q[i][j] < min_val:
                    min_val, mi, mj = Q[i][j], i, j

        # branch length
        L_i = dist[mi][mj]/2 + (total[mi] - total[mj]) / (2*(m-2))
        L_j = dist[mi][mj] - L_i
        tree.append((labels[nodes[mi]], next_id, L_i))
        tree.append((labels[nodes[mj]], next_id, L_j))
        labels.append(f"N{next_id}")

        # Nueva matriz de distancias
        new_dist = []
        for k in range(m):
            if k in (mi, mj):
                continue
            row = []
            for l in range(m):
                if l in (mi, mj):
                    continue
                row.append(dist[k][l])
            # Distancia al nuevo nodo
            new_d = (dist[k][mi] + dist[k][mj] - dist[mi][mj]) / 2
            row.append(new_d)
            new_dist.append(row)
        last_row = [(dist[mi][k] + dist[mj][k] - dist[mi][mj])/2
                    for k in range(m) if k not in (mi, mj)] + [0]
        new_dist.append(last_row)

        dist = new_dist
        nodes = [nodes[k] for k in range(m) if k not in (mi, mj)] + [next_id]
        next_id += 1

    # Unir los dos nodos restantes
    if len(nodes) == 2:
        tree.append((labels[nodes[0]], labels[nodes[1]], dist[0][1]))
    return tree

# Ejemplo anterior
D = [[0, 5, 9, 9],
     [5, 0, 10, 10],
     [9, 10, 0, 8],
     [9, 10, 8, 0]]
labels = ['A', 'B', 'C', 'D']
tree = neighbor_joining(D, labels[:])
for edge in tree:
    print(edge)

La ejecución produce el mismo resultado que la derivación manual anterior. NJ cabe en unas 40 líneas. El principio del algoritmo de árboles no es especialmente difícil; en la práctica, la validación estadística mediante bootstrap y selección de modelos tiene mucho más peso.

Resumen: UPGMA vs. NJ

NJ es la opción predeterminada si no existe una razón específica para elegir otra. Utilice UPGMA solo cuando desee imponer explícitamente el supuesto de reloj molecular.

Complejidad

Ambos algoritmos tienen complejidad O(N³), donde N es el número de nodos. Cientos de secuencias pueden procesarse en segundos; para miles o decenas de miles se necesitan variantes rápidas de NJ, como RapidNJ.

Bootstrapping: evaluación de la confianza

¿Hasta qué punto es fiable cada rama del árbol filogenético? El remuestreo bootstrap es la herramienta estándar.

1. Muestrear con reemplazo las columnas del MSA para crear un nuevo alineamiento.
2. Construir un árbol nuevo a partir de ese MSA.
3. Repetir el proceso entre 100 y 1000 veces.
4. Indicar el porcentaje de árboles bootstrap que respalda cada rama.

Un valor bootstrap de al menos 70–80 suele considerarse razonablemente fiable. Por debajo de ese intervalo, los datos no sustentan suficientemente la topología de la rama.

Mapeo CS: fusión de árboles voraz

La estructura es la misma que la del clustering jerárquico de DryBench.

• UPGMA = clustering jerárquico con enlace promedio.
• NJ = fusión ponderada basada en Q, con una función de enlace más sofisticada.
• Ambos enfoques realizan una fusión voraz de abajo arriba.

Este patrón aparece también en el clustering jerárquico de ciencia de datos, el método de Ward utilizado para inicialización y hasta en decisiones de inlining de funciones de un compilador. Extraer una estructura de árbol a partir de información de distancias es un patrón habitual del análisis de datos.

Obtener una puntuación en Rosalind

El problema Rosalind NJ proporciona una matriz de distancias y el número de nodos y solicita un árbol NJ. Basta convertir el resultado tree del código anterior al formato Newick.

Continuación en el siguiente artículo

• Siguiente unidad (M27): parsimonia — Fitch y Sankoff; evalúa el árbol mediante el número mínimo de cambios requerido por el MSA observado.
• Unidad M28: máxima verosimilitud — IQ-TREE y RAxML; maximiza la verosimilitud del árbol mediante un modelo estadístico.
• Herramientas prácticas: MEGA, FastTree, IQ-TREE — las herramientas estándar actuales para árboles filogenéticos

Si desea profundizar más

• Saitou & Nei (1987), The neighbor-joining method: a new method for reconstructing phylogenetic trees, MBE — El artículo original sobre NJ.
• Felsenstein Inferring Phylogenies — El texto estándar sobre algoritmos de árboles filogenéticos.
• UC Berkeley BIDS — Clase de filogenia del profesor Yun S. Song (con subtítulos completos).
• Compau & Pevzner Bioinformatics Algorithms Capítulo 7 — Tutorial de NJ integrado con Rosalind.

Construya un árbol filogenético para una familia de proteínas real (por ejemplo, hemoglobina) utilizando MEGA o FastTree. Comparar el método de vecino-unión (NJ) con el árbol de máxima verosimilitud profundizará considerablemente su intuición práctica.