La navaja de Occam y los árboles filogenéticos

Aunque la distancia métrica (M26) es el valor predeterminado en la práctica, existe un enfoque estadísticamente más riguroso. La parsimonia plantea la siguiente pregunta:

De entre todos los árboles que pueden explicar el Alineamiento Múltiple de Secuencias (MSA) observado, ¿cuál es el árbol que requiere el menor número de cambios?

La navaja de Occam. Es una intuición estadística basada en la idea de que la evolución se explica con mayor probabilidad mediante el mínimo número de cambios. En esta sección, derivaremos a mano los dos algoritmos clásicos de la parsimonia: Fitch y Sankoff. Se trata de un apartado sobre principios estadísticos previos al paso al método de máxima verosimilitud M28.

Parsimonia pequeña frente a parsimonia grande

El problema de la parsimonia se divide en dos categorías:

Parsimonia pequeña (Small parsimony): Dada una topología de árbol fija, calcular el número mínimo de cambios necesario para explicar el MSA observado sobre ese árbol. Se resuelve en tiempo polinómico.

Parsimonia grande (Large parsimonia): Buscar entre todas las posibles topologías de árbol aquella que minimiza el número de cambios. Es un problema NP-completo.

En esta sección nos centraremos en la parsimonia pequeña. La parsimonia grande se resuelve mediante búsquedas heurísticas (como branch-and-bound, hill climbing, etc.), pero cada iteración de dichos métodos requiere calcular la parsimonia pequeña. La parsimonia pequeña constituye el esqueleto de la parsimonia.

Algoritmo de Fitch — Estados binarios · Costes uniformes

Es la forma más sencilla de parsimonia. Se aplica cuando el coste de cambio entre cualquier par de estados es siempre 1 (transición = transversión = ...).

Algoritmo (recorrido postorden del árbol):

1. Hoja: almacenar el carácter observado como conjunto {X}
2. Nodo interno: calcular la intersección de los conjuntos de sus dos hijos
   • Si la intersección no está vacía → usar la intersección, manteniendo el número de cambios sin alterar
   • Si la intersección está vacía → usar la unión, incrementando el número de cambios en +1
3. Repetir hasta alcanzar la raíz. Si el conjunto en la raíz tiene más de un elemento, existen múltiples estados ancestrales óptimos

Derivación manual — 4 especies (A, B, C, D), caracteres observados (T, A, T, A), topología del árbol ((A,B),(C,D)):

root
      /    \
    N1      N2
   /  \    /  \
  A    B  C    D
  T    A  T    A

Recorrido postorden:

• N1 = {T} ∩ {A} = ∅ → unión {T, A}, número de mutaciones +1
• N2 = {T} ∩ {A} = ∅ → unión {T, A}, número de mutaciones +1
• root = {T,A} ∩ {T,A} = {T, A} → intersección, número de mutaciones sin cambios

Número total de mutaciones = 2.

Bajo esta topología del árbol, el mínimo de mutaciones que explica la observación (T, A, T, A) es 2. Intentemos también otra topología del árbol ((A,C),(B,D)):

root
      /    \
    N1      N2
   /  \    /  \
  A    C  B    D
  T    T  A    A

• N1 = {T} ∩ {T} = {T} → número de mutaciones 0
• N2 = {A} ∩ {A} = {A} → número de mutaciones 0
• root = {T} ∩ {A} = ∅ → unión {T,A}, número de mutaciones +1

Número total de mutaciones = 1. Esta topología es mejor. La parsimonia se utiliza así para evaluar la propia topología del árbol.

Segunda pasada de Fitch — Asignación real de ancestros desde la raíz hacia abajo

Después de determinar el estado de la raíz (si hay múltiples conjuntos, elegir uno arbitrariamente), descendemos para determinar el estado óptimo de cada nodo interno.

• Si el estado del padre actual está incluido en el conjunto del hijo → usarlo tal cual
• Si no está incluido → elegir cualquier estado del conjunto del hijo

Al finalizar la segunda pasada, se asignan caracteres ancestrales a todos los nodos internos y se muestran las mutaciones reales en cada rama.

Algoritmo de Sankoff — Costos asimétricos

En Fitch, el costo de todas las mutaciones era 1. En la realidad, las transiciones (purina→purina, pirimidina→pirimidina) ocurren con mucha más frecuencia que las transversiones (purina↔pirimidina). También existen diferencias de costos entre aminoácidos según su similitud química.

Matriz de costos c(x, y) = costo de mutación del estado x al estado y.

Ejemplo (diferenciación transición/transversión en ADN):

A↔G y C↔T son transiciones (costo 1), el resto son transversiones (costo 2).

Algoritmo de Sankoff (recorrido postorden del árbol):

Si la hoja muestra el carácter x, entonces S(x) = 0, y para los demás estados S(y) = ∞.

Para cada nodo interno, el costo mínimo para cada estado x:

S_{\text{node}}(x) = \sum_{\text{child}} \min_{y} [c(x, y) + S_{\text{child}}(y)]

Para cada hijo, se suma el "mínimo de (costo de transición + costo del subárbol del hijo) al ir a cualquier estado y de ese hijo".

El valor min_x S_root(x) en la raíz es la puntuación total de parsimonia.

Derivación de costos de Sankoff (ejemplo breve)

Árbol (A=A, B=G), con la matriz de costos anterior.

Hoja A: S_A = [0, ∞, ∞, ∞] (A=0, resto ∞) Hoja B: S_B = [∞, ∞, 0, ∞] (G=0, resto ∞)

Para el estado raíz x = A:

• hijo A: min_y [c(A,y) + S_A(y)] = c(A,A) + 0 = 0
• hijo B: min_y [c(A,y) + S_B(y)] = c(A,G) + 0 = 1
• S_root(A) = 0 + 1 = 1

Cuando el estado raíz x = G:

• hijo A: min_y [c(G,y) + S_A(y)] = c(G,A) + 0 = 1
• hijo B: min_y [c(G,y) + S_B(y)] = c(G,G) + 0 = 0
• S_root(G) = 1 + 0 = 1

Cuando el estado raíz x = C:

• hijo A: c(C,A) + 0 = 2
• hijo B: c(C,G) + 0 = 2
• S_root(C) = 4

De manera similar, cuando x = T, S_root(T) = 4.

min S_root = 1 (A o G). El costo de parsimonia mínimo necesario para las observaciones (A, G) es 1. Esto lleva a la conclusión de que hay una única transición. Esta es la respuesta según el algoritmo de Sankoff.

Implementación de Fitch en Python

class Node:
    def __init__(self, name=None, left=None, right=None):
        self.name, self.left, self.right = name, left, right
        self.state, self.set = None, None

def fitch_up(node, chars):
    """Calcula conjuntos de estados mediante recorrido postorden. chars = {leaf_name: char}."""
    if node.left is None and node.right is None:
        node.set = {chars[node.name]}
        return 0
    left = fitch_up(node.left, chars)
    right = fitch_up(node.right, chars)
    intersect = node.left.set & node.right.set
    if intersect:
        node.set = intersect
        return left + right
    else:
        node.set = node.left.set | node.right.set
        return left + right + 1

def fitch_down(node, parent_state=None):
    """Determina estados ancestrales mediante recorrido preorden."""
    if parent_state is not None and parent_state in node.set:
        node.state = parent_state
    else:
        node.state = next(iter(node.set))
    if node.left:
        fitch_down(node.left, node.state)
    if node.right:
        fitch_down(node.right, node.state)

# Ejemplo: ((A,B),(C,D))
A = Node("A"); B = Node("B"); C = Node("C"); D = Node("D")
N1 = Node(left=A, right=B); N2 = Node(left=C, right=D)
root = Node(left=N1, right=N2)

chars = {"A": "T", "B": "A", "C": "T", "D": "A"}
score = fitch_up(root, chars)
fitch_down(root)

print(f"Puntuación de parsimonia: {score}")
print(f"root state: {root.state}, N1: {N1.state}, N2: {N2.state}")

Al ejecutarlo, la puntuación de parsimonia es 2, estado del ancestro T o A. Las 40 líneas son el núcleo de la parsimonia.

La trampa de la parsimonia — Long branch attraction

Una trampa práctica famosa de la parsimonia. Dos ramas muy largas tienden a agruparse entre sí aunque no estén relacionadas. Esto se debe a que, si en las dos ramas largas se acumulan accidentalmente mutaciones en la misma dirección, la parsimonia las interpreta como una señal de "ancestro común".

Para evitar esta trampa, es mejor el enfoque de máxima verosimilitud. Se tratará en el siguiente episodio M28. La máxima verosimilitud define explícitamente un modelo evolutivo, lo que reduce probabilísticamente la evaluación de coincidencias accidentales.

Small parsimony vs Large parsimony

• Small: O(N × K²) (Sankoff) o O(N × K) (Fitch). K es el número de estados, N es el tamaño del árbol.
• Large: NP-completo. Requiere búsqueda heurística. Branch-and-bound, hill climbing.

Las herramientas prácticas MEGA y PAUP resuelven la parsimonia grande mediante heurística. Dado que cada iteración es una parsimonia pequeña, el algoritmo de este episodio es el corazón de todas las herramientas de parsimonia.

Mapeo CS — La esencia de la DP en árboles

El concepto de DP en árboles de DryBench se reproduce exactamente aquí.

• Recorrido postorden = agregación de información desde las hojas hacia la raíz.
• Cada nodo = la subsolución óptima de su subárbol.
• Recorrido preorden = propagación de la decisión óptima desde la raíz hacia las hojas.

Este patrón aparece en otros lugares: árboles binarios de búsqueda óptimos, multiplicación de cadenas de matrices, diseño de árboles DOM de HTML e incluso análisis de árboles de dominadores en la forma SSA de un compilador. Combinar las soluciones óptimas de los subárboles para obtener el óptimo global: este mismo esquema se redescubre en diversos dominios.

Evaluación en Rosalind

Rosalind FSNK — Problema de parsimonia pequeña. Aplicación directa del algoritmo de Fitch. Si se añade el análisis del árbol según las especificaciones del problema al código anterior, se aprobará.

Ramificaciones hacia el siguiente episodio

• Próximo episodio (M28): Máxima verosimilitud — IQ-TREE, RAxML — Maximiza la verosimilitud estadística en lugar de la parsimonia. Evita el Long branch attraction.
• Después de Assembly (M29): Teoría de la coalescencia — Perspectiva de reversión temporal en genética de poblaciones.
• Último episodio (M30): Modelo de Wright-Fisher — Modelo probabilístico generacional.

Si deseas profundizar más

• Fitch (1971), Hacia la definición del curso de la evolución: cambio mínimo para una topología de árbol específica, Syst Zool — El artículo original de Fitch.
• Sankoff (1975), Árboles de mutación mínimos de secuencias, SIAM J Appl Math — El artículo original de Sankoff. Costos enteros asimétricos.
• Felsenstein (1978), Casos en los que los métodos de parsimonia o compatibilidad serán positivamente engañosos, Syst Zool — El artículo que estableció la trampa de atracción de ramas largas.
• UC Berkeley BIDS — Lecciones de parsimonia del profesor Yun S. Song.
• Compau & Pevzner Bioinformatics Algorithms Capítulo 7 — Derivación detallada de la parsimonia pequeña.

Veamos en qué datos la parsimonia y la máxima verosimilitud producen respuestas diferentes, ejecutando el mismo Alineamiento Múltiple de Secuencias (MSA) en MEGA con ambos métodos para compararlos. Esto completa esta intuición.