Construir un árbol filogenético — Dibujar mapas evolutivos con recursión y árboles binarios

Al finalizar este tema

Podrán crear una herramienta que analice, recorra y realice análisis por clado de árboles filogenéticos en formato Newick, combinando los árboles binarios y la recursión aprendidos en los libros de texto. Comprenderán mediante código las estructuras de datos que utilizan herramientas filogenéticas reales como MEGA o iTOL.

Este texto es un ejemplo educativo general. La inferencia real de árboles filogenéticos utiliza diversos algoritmos sofisticados como UPGMA, Neighbor-Joining, Maximum Likelihood y Bayesian.

"(((A:0.1,B:0.2):0.05,C:0.3):0.1,D:0.4);" — ¿Qué es esto?

Han analizado secuencias de 16S rRNA de 10 especies microbianas y han construido un árbol filogenético. En el archivo de resultados aparece esta cadena de caracteres.

(((Ecoli:0.05,Salmonella:0.06):0.02,Klebsiella:0.08):0.03,(Bacillus:0.15,Staph:0.14):0.10);

Este es el formato Newick. El estándar para representar árboles filogenéticos como texto. Reglas:

• El paréntesis () representa un clade (un grupo que diverge de un ancestro común).
• La coma , representa nodos hermanos.
• El número tras los dos puntos :0.05 es la distancia evolutiva hasta el padre (longitud de la rama).
• El punto y coma ; indica el final de la cadena.

Lo que debes hacer:

1. Parsing: Convertir la cadena en una estructura de datos de Python.
2. Recorrido: Enumerar las especies hoja (leaf) de cada clade.
3. Cálculo de distancia: Calcular la distancia evolutiva total entre dos especies.
4. Visualización: Mostrar el árbol como una imagen.

El enfoque real es la recursión. Dado que la cadena Newick es una estructura recursiva que contiene a sí misma como hijo, tanto el parsing como el recorrido se expresan de forma natural mediante recursión.

De la caja negra a los componentes

Componente 1: Definición del nodo del árbol

from dataclasses import dataclass, field
from typing import Optional


@dataclass
class TreeNode:
    name: Optional[str] = None
    branch_length: float = 0.0
    children: list["TreeNode"] = field(default_factory=list)

    @property
    def is_leaf(self) -> bool:
        return len(self.children) == 0

Observación clave: children es una lista del mismo tipo TreeNode. Esta estructura autorreferencial es el escenario natural para la recursión.

Componente 2: Analizador Newick (recursivo)

Al implementar el analizador manualmente, se obtiene la siguiente estructura recursiva:

class NewickParser:
    def __init__(self, s: str) -> None:
        self.s = s.rstrip(";").strip()
        self.pos = 0

    def parse(self) -> TreeNode:
        return self._parse_node()

    def _parse_node(self) -> TreeNode:
        node = TreeNode()

        if self._peek() == "(":
            self._consume("(")
            node.children.append(self._parse_node())
            while self._peek() == ",":
                self._consume(",")
                node.children.append(self._parse_node())
            self._consume(")")

        node.name = self._read_name()

        if self._peek() == ":":
            self._consume(":")
            node.branch_length = self._read_number()

        return node

    def _peek(self) -> Optional[str]:
        return self.s[self.pos] if self.pos < len(self.s) else None

    def _consume(self, expected: str) -> None:
        assert self._peek() == expected, f"Expected {expected} at pos {self.pos}"
        self.pos += 1

    def _read_name(self) -> str:
        start = self.pos
        while self.pos < len(self.s) and self.s[self.pos] not in ",():;":
            self.pos += 1
        return self.s[start:self.pos]

    def _read_number(self) -> float:
        start = self.pos
        while self.pos < len(self.s) and self.s[self.pos] not in ",():;":
            self.pos += 1
        return float(self.s[start:self.pos])

La clave es que _parse_node se llama a sí mismo de forma recursiva. La gramática recursiva de Newick se mapea directamente con una función recursiva.

Uso:

tree = NewickParser(
    "(((Ecoli:0.05,Salmonella:0.06):0.02,Klebsiella:0.08):0.03,(Bacillus:0.15,Staph:0.14):0.10);"
).parse()

Componente 3: Recorrido recursivo

Ahora recorreremos el árbol de diversas formas. Todas son recursivas.

Enumerar todas las hojas:

def get_leaves(node: TreeNode) -> list[str]:
    if node.is_leaf:
        return [node.name] if node.name else []
    result = []
    for child in node.children:
        result.extend(get_leaves(child))
    return result

Cálculo de la altura del árbol:

def tree_height(node: TreeNode) -> int:
    if node.is_leaf:
        return 0
    return 1 + max(tree_height(child) for child in node.children)

Indicado con sangría:

def pretty_print(node: TreeNode, depth: int = 0) -> None:
    label = f"{node.name or '(internal)'}"
    if node.branch_length:
        label += f" [len={node.branch_length}]"
    print("  " * depth + label)
    for child in node.children:
        pretty_print(child, depth + 1)

Salida:

(internal)
  (internal)
    (internal)
      Ecoli [len=0.05]
      Salmonella [len=0.06]
    Klebsiella [len=0.08]
  (internal)
    Bacillus [len=0.15]
    Staph [len=0.14]

Parte 4: Distancia entre dos hojas

La distancia evolutiva entre dos especies es la suma de las distancias hasta su ancestro común. Para calcular esto, primero se debe encontrar la ruta ancestral de cada hoja.

def find_path_to_leaf(node: TreeNode, target: str) -> Optional[list[TreeNode]]:
    if node.is_leaf:
        return [node] if node.name == target else None

    for child in node.children:
        subpath = find_path_to_leaf(child, target)
        if subpath is not None:
            return [node] + subpath

    return None


def evolutionary_distance(root: TreeNode, leaf_a: str, leaf_b: str) -> float:
    path_a = find_path_to_leaf(root, leaf_a)
    path_b = find_path_to_leaf(root, leaf_b)

    if path_a is None or path_b is None:
        raise ValueError("Leaf not found")

    # Encontrar ancestro común (el último nodo compartido en la ruta)
    lca_idx = 0
    while lca_idx < min(len(path_a), len(path_b)) and path_a[lca_idx] is path_b[lca_idx]:
        lca_idx += 1
    lca_idx -= 1

    # Suma de las longitudes de rama de los nodos después del LCA en cada ruta
    distance = sum(node.branch_length for node in path_a[lca_idx + 1:])
    distance += sum(node.branch_length for node in path_b[lca_idx + 1:])

    return distance


d = evolutionary_distance(tree, "Ecoli", "Bacillus")
print(f"Ecoli ↔ Bacillus: {d}")
# 0.02 + 0.05 (ruta Ecoli) + 0.10 + 0.15 (ruta Bacillus) + 0.03 (LCA) = 0.35

Desvanecimiento — Los dos espacios en blanco que deben completar

Espacio en blanco 1: Estadísticas de clados

Calcule el número de hojas y la longitud media de las ramas bajo un clado (nodo interno) específico.

def clade_stats(node: TreeNode) -> dict:
    """
    Devuelve: {
        "leaf_count": número de hojas debajo,,
        "total_branch_length": suma de todas las longitudes de rama debajo,,
        "mean_branch_length": promedio
    }
    """
    if node.is_leaf:
        # TODO: valor predeterminado cuando es un nodo hoja
        pass

    # TODO: obtener estadísticas de cada hijo mediante llamadas recursivas y combinarlas
    pass

Pista: si es una hoja, {"leaf_count": 1, "total_branch_length": node.branch_length, ...}. Los nodos internos suman los resultados de sus hijos.

Espacio en blanco 2: Extracción de un subárbol mediante un filtro de nombres de hojas

Se crea un árbol reducido conservando solo las hojas de interés.

def prune_tree(node: TreeNode, keep_leaves: set[str]) -> Optional[TreeNode]:
    """
    Devuelve un árbol contraído que solo incluye las hojas en keep_leaves.
    Se eliminan los nodos internos innecesarios, pero se fusionan las longitudes de rama.
    """
    if node.is_leaf:
        # TODO: devolver la hoja si está en keep_leaves, de lo contrario None
        pass

    # TODO: podar recursivamente los hijos, mantener solo los que no son None
    # Si no hay hijos, devolver None; si hay uno, devolver ese hijo (sumando branch_length)
    pass

Pista: Si solo queda un hijo, este nodo interno es innecesario; devuelve la suma del branch_length de este nodo al branch_length del hijo.

Reflexión — Diferencias con las herramientas filogenéticas reales

Algoritmos de inferencia filogenética: Lo que han manejado es analizar y procesar un árbol ya construido. Construir un árbol filogenético desde cero a partir de secuencias es un problema distinto. Existen métodos como UPGMA (el más simple), Neighbor-Joining (complejidad intermedia), Maximum Likelihood (RAxML, IQ-TREE) y Bayesianos (MrBayes, BEAST).

Árboles no binarios: El formato Newick puede no ser binario; un nodo puede tener tres o más hijos (polotomía). Su analizador ya maneente este caso.

Valores de bootstrap: Los árboles reales muestran el soporte de bootstrap (0–100) en cada nodo interno. En Newick, esto suele escribirse en la posición del nombre del nodo interno; su _read_name captura esto.

Visualización: En la práctica se utilizan ETE Toolkit, Biopython Phylo e iTOL para dibujar árboles. También es posible dibujar árboles radiales y ortogonales simples con matplotlib.

Extensión de anotaciones: En la práctica se usan formatos Nexus (filogenia + secuencias + metadatos) o phyloXML (basado en XML). Su analizador Newick maneja el formato mínimo.

Proyecto de extensión

1. Visualización: Dibujar su árbol en forma de dendrograma ortogonal usando matplotlib. Mostrar los nombres de las hojas y las longitudes de las ramas.

2. Filtrado por bootstrap: Contraer mediante poda (pruning) los nodos internos con bajo soporte de bootstrap.

3. Implementación de UPGMA: Construir un árbol desde cero a partir de una matriz de distancias mediante UPGMA. Reutilizar la estructura de datos TreeNode que han creado.

4. Integración con Biopython: Realizar la lectura y escritura de archivos mediante el módulo Phylo de Biopython y aplicar sus funciones de análisis.

Mapa de componentes de este capítulo

• [F] Árbol de búsqueda binaria (extensión): Estructura de autorreferencia TreeNode. Un árbol general donde los nodos pueden tener múltiples hijos.
• [F] Recursión: El análisis, el recorrido y el cálculo de distancias se implementan todos mediante recursión. Comparación entre recursión e iteración.
• [W] E/S de archivos: Lectura de archivos Newick, etc. (proporcionado en el script completo).

[F] = Implementado por ustedes mismos / [W] = Proporcionado como código completo.