Algoritmos en filogenia 0b: Árboles

English version

Otro de los componentes básicos de un programa de análisis filogenético son los árboles. Los árboles pueden ser el resultado del análisis (como en los programas de análisis cladístico), o pueden ser parte de los datos usados (como en los programas de análisis biogeográfico).

Los árboles, son además, una de las estructuras de datos más conocidas y usadas en programación. En programación un árbol es una colección de elementos (nodos), los nodos están relacionados entre sí por un "parentesco" que les impone una jerarquía. El parentesco es una relación de pares: un nodo es el ancestro y el otro es el descendiente. Un nodo puede tener un número indefinido de descendientes, más como máximo solo puede tener un ancestro.

En general, en filogenía se llama nodo, únicamente a los elementos que poseen descendientes, y hojas o terminales, a los elementos sin descendientes (en ciencias de computadores se utiliza más nodo interno y nodo terminal o nodo hoja, aquí yo sigo la notación de ciencias de computadores, y utilizo nodos cuando me refiero a todos los elementos del árbol).

Un árbol tiene como máximo un nodo raíz, que es un nodo interno sin ancestro. A diferencia de los árboles más abstractos de ciencias de computadores, los únicos elementos con datos incluidos por el usuario son los terminales (que entran vía la matriz de datos). Los datos guardados por los nodos internos son inferidos mediante algún algoritmo.

Existen varias formas de representar un árbol. Para mi, la más natural es usando estructuras y apuntadores. He aquí un nodo básico

typedef struct tagPHYLONODE PHYLONODE;

struct tagPHYLONODE {
PHYLONODE* anc;
PHYLONODE* left;
PHYLONODE* right;
STATES* recons;
};

Esta estructura es el nodo de un árbol binario, es decir, que cada nodo interno tiene dos descendientes, los apuntadores left, y right, que como pueden notar apuntan a elementos del tipo PHYLONODE. anc es el puntero a el ancestro. En esta estructura el nodo raíz tiene a anc como NULL (es decir que no apunta a ningún elemento), y los nodos terminales tienen left y right como NULL. recons es un arreglo con los caracteres (en forma de campo de bits).

Yo suelo guardar la información del terminal (extraída de la matriz de datos) en una estructura aparte, por ejemplo

typedef struct tagTERMINAL TERMINAL;
struct tagTERMINAL {
char name [32];
STATES* chars;
};

E incluyo un apuntador a TERMINAL como parte de PHYLONODE

struct tagPHYLONODE {
... //Otros campos aquí
TERMINAL* term;
};

Si es un nodo interno, term es NULL.

Una de las ventajas de los árboles es que un subárbol tiene las mismas propiedades de un árbol, por lo que los algoritmos recursivos son muy naturales al trabajarlos con árboles. Aún así, yo prefiero tener siempre una estructura que guarda el árbol

typedef struct tagPHYLOTREE PHYLOTREE;
struct tagPHYLOTREE {
unsigned numNodes;
PHYLONODE* root;
PHYLONODE* nodeArray;
DATAMATRIX* matrix;
};

En esta estructura se guarda un puntero al nodo raíz (root), un array con los nodos del árbol (nodeArray), un apuntador a la matriz de datos (matrix) y el número de nodos.

Esta aproximación tiene la ventaja de que uno bien puede tener varios conjuntos de árboles de forma independiente, por ejemplo, cada árbol con su propio id, o nombre, que no es una característica del nodo raíz, sino del conjunto completo de los nodos.

Aparte de las estructuras es posible guardar los árboles como arrays coordinados. Esta opción, por ejemplo, es usada en [1] para el código que aparece en los ejemplos, y también es la manera de manejar los árboles en el lenguaje de macros de TNT (que no maneja estructuras). La declaración de los arreglos coordinados es más sencilla

int* anc;
int* left;
int* right;
STATES** chars;

En este caso anc, left y right son arreglos dinámicos (por eso están declarados como apuntadores, pero se pueden tratar como arrays), y en vez de contener un apuntador, contienen un numero que es el índice del array. Como es un arreglo coordinado, todos los elementos con el mismo índice son parte del mismo nodo. Así, por ejemplo anc [17] = 20; dice que el ancestro del nodo 17, es el nodo 20. En este caso left [20] o right [20] debe ser igual a 17. chars [20] contiene los estados asignados al nodo 20. Si revisan las entradas sobre árboles en wikipedia (en especial las entradas sobre heaps) notaran que esa es la manera con la que tratan los árboles.

Para mi, lo malo de esa aproximación, es que requiere un control más fuerte sobre el mantenimiento de la información (cabe anotar que en el lenguaje de macros TNT, TNT mantiene todo por nosotros, así que eso no es ningún problema!). En mi propia experiencia, yo trabaje en reconciliación de árboles, y trabajaba con alguien que no sabia manejar apuntadores. Así que trate de hacer la implementación con arreglos coordinados. pero en árboles reconciliados no siempre sabemos cuantos nodos nuevos va a tener el árbol, por lo que mantener el código con los arreglos coordinados se hizo bien problemático.

Lo que muestra esa experiencia, no es que una alternativa es mejor que la otra, solo que a veces, la naturaleza del problema puede complicar la forma de resolverlo, y que además algunos estilos de programación se dan mejor que otros, según quien este haciendo el código ;). De aquí en adelante en otros posts, yo voy a usar estructuras.

Para tener algo de código y resaltar la recursividad de los árboles he aquí una función que guarda un árbol en formato parentética (como Hennig86, NONA y TNT)

#include < stdio.h >

void PrintTree (FILE* out, PHYLOTREE* tree) {
fprintf (out, "tread \'Simple tree output\'\n");
PrintNode (out, tree - > root)
fprintf (out, ";\np/;");
}

void PrintNode (FILE* out, PHYLONODE* node) {

if (node - > term != NULL) {
fprinf ("%s ", node - > term - > name);
return;
}
fprintf (out, "(");
PrintNode (out, node - > left);
PrintNode (out, node- > right);
fprintf (out, ") ");
}

Estas funciones usas las operaciones IO estándar. La función PrintTree coloca la cabecera de un archivo de árboles para Hennig86/NONA/TNT. Y llama a PrintNode. PrintNode chequea si el nodo actual es un terminal, si es así escribe el nombre del terminal, de lo contrario, como en un nodo interno, imprime los paréntesis y llama recirsivamente a PrintNode en cada uno de sus descendientes.

Me parece que Mike Keesey escribió un post sobre árboles bajo programación orientada a objetos, pero no pude encontrarlo, esta es la alternativa más parecida :P

Referencias
[1] Goloboff, P. A. 1997. Self weighted optimization: tree searches and character state reconstruction under implied transformation costs. Cladistics 13: 225-245. doi: 10.1111/j.1096-0031.1997.tb00317.x

Post anteriores en Algoritmos en filogenia
0a. Campos de bits