Hennig XXIX – Día 4 (26 mayo 2010)

El último día de las charlas de la Willi Hennig tiene el problema que esta el día después del banquete... pero tiene también el aliciente que suele reunir las charlas de muchas de las figuras establecidas del campo :)

La primera charla le correspondió a James Carpenter quien menciono los resultados del proyecto del “árbol de la vida” de Hymenoptera, en especial de Aculeata que es la parte que le corresponde a el. La charla me pareció muy buena, pero me gusto más la discusión que siguió, en especial cuando Jim llamo la atención que usar caracteres aditivos es más conservativo que dejarlos como no aditivos!

Fuki Saito estudió la filogenia de la avispa Ropalidia, en especial el origen de sus colonias por enjambre. Por la misma onda Jun'ichi Kojima se enfoco en un grupo de avispas y de la aparción y desparición de los “ayundates” (por lo que entendí, es una especie de proto-obreras).

Albert Prieto-Márquez presento una charla sobre Hadrosauridae, esta fue la primera charla que veo sobre un grupo de dinosaurios no avianos, lo cual me pareció muy bueno desde el punto de vista de mi alegría infantil xD. Entre los puntos que más generó discusión fue el desarrollo de su análisis biogeográfico.

Después Ulf Jondelius discutió los últimos adelantos sobre la filogenia de Acoela, el grupo hermano de todos los demás bilaterales. Aunque es un grupo primordialmente estudiando mediante moléculas, consiguieron algo más de 35 caracteres morfológicos, lo cual en este grupo es realmente muy complicado.

Seguía una charla de Lauri Kaila, pero como no pudo venir, su charla la dio Maria Heikkilä. Sus resultados mostraron lo difícil que ha sido encontrar evidencia molecular para el enorme clado de mariposas Ditrysia.

Nobuhiro Minaka hablo sobre el uso de la transformación de Gromov para medir indices de diversidad.

Pablo Goloboff dio una charla que me gusto mucho (no es porque sea mi jefe xD, es más bien que he visto como desarrolla muchas de las cosas que mostró) sobre algunos de los problemas que tienen los programas que usan máxima verosimilitud a la hora de medir el apoyo.

La charla de Daniel Janies me gusto también, era sobre la dispersión geográfica de enfermedades y de como se asocian ciertos fenotipos con la expansión (outbreak) del virus y ciertas mutaciones. Eso usando su porgrama Routemap y Google earth.

Torsten Dikow menciono muchas de las cosas que ha realizado para EOL, de cierta manera, era como la continuación de lo que dio en Tucumán, ahora más sofisticado. Me gusto la discusión que siguió bien orientada a la desorganización existente en el manejo de información biológica/taxonómica.

Jyrki Mouna dio una bonita presentación sobre varios coleopteros que de alguna manera se diversificaron recientemente en los bosques finlandeses/escandinavos. Su conocimiento de la fauna y flora de esa región me impresiono bastante!

Para terminar, Steve Farris hablo sobre algunos lejendarios ataques a la parsimonia, y de su relación con algunas propuestas y discusiones recientes, fue muy entretenida.

Jyrki termino el meeting con algunas palabras como presidente.

En general me gusto mucho. Es cierto que en comparación con el meeting de Tucumán fue mucho más pequeño, pero pues me parece que el comité organizador hizo una gran labor, no solo consiguiendo precios competitivos para la estancia en Honolulu, además dio un gran apoyo a los estudiantes y en todas las recepciones hubo comida más que suficiente ;).

Además, pues la playa, el mar, y el sol no tienen precio :)

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

La wiki de TNT

Hace unos días, la wiki de TNT fue lanzada al publico. El proyecto es liderado por mi amigo Santi Catalano, Matt Yoder y Ximo Mengual. Ellos se encontraron en el Hennig meeting, en Tucumán, con la idea de proporcionar una ayuda amigable a los usuarios de TNT.

Este es el enlace: http://tnt.insectmuseum.org/

En su mayor parte, la wiki es una versión en linea de la ayuda del programa. Pero como es una wiki es posible agrandarla con muchos ejemplos y trucos.

Yo colabore con las páginas de pesado implicado: la pagina básica y un tutorial rápido. Y espero escribir algunas cosas para la sección de scripts :).

Pablo no esta directamente asociado con el proyecto. Pero, cada cierto tiempo, el revisa algo del contenido, y por supuesto, siempre a apoyado el desarrollo del sitio :).

Hay además un grupo de google de TNT: http://groups.google.com/group/tnt-tree-analysis-using-new-technology abierto a las preguntas de cualquier usuario!

El análisis de un behemot, y una wiki, esta es una gran semana para TNT :).

Por si acaso, TNT es un software gratuito para análisis filogenético a cualquier escala. Esta patrocinado por la Willi Hennig society, y puede descargarse aquí: http://www.zmuc.dk/public/phylogeny/TNT/

Filogenia de 73060 eucariotas

English version

Finalmente, el Behemot vio la luz. Nuestro paper de un análisis de parsimonia de 73060 especies de eucariotas (y 7800 caracteres mol+morf) acaba de ser puesto en linea en Cladistics [doi: 10.1111/j.1096-0031.2009.00255.x].



Pablo hizo un trabajo brutal optimizando cada cosa en las búsquedas de arboles con TNT. Y todos aquí trabajaron intensamente para poder manejar toda esa cantidad de datos!

Al principio me sorprendió la enorme exactitud de los árboles encontrados, porque el set de datos esta lleno de entradas faltantes. Además, me puse muy contento porque al incluir los datos morfológicos, aún a esta escala tan grande, los resultados fueron mejores que usando únicamente datos moleculares!

Hace uno meses, esto fue posteado en dechronization:

[Cassy Dunn] hizo un llamado convincente acerca de la necesidad de técnicas análiticas revolucionarias ahora que entramos en una era en que los alcances de la computación serán más limitantes que la disponibilidad de datos.

Yo creo que nuestro trabajo muestra exactamente lo contrario: nuestras herramientas de búsqueda son lo suficientemente buenas, pero no hay datos suficientes (el conjunto de datos más grande es SSU con 20000 especies, y solo un puñado de genes tiene más de 10000 especies).

Otra lección?.... No necesitamos los super-árboles!

Algoritmos en filogenia 0a: Campos de bits

English version

Intro

Quiero iniciar una serie de posts sobre los algoritmos usados en análisis filogenético. El motivo principal fue ver el árticulo sobre “filogenética computacional” (y los tópicos de sistemática) en wikipedia, que pues me parecen algo sesgados hacía los métodos basados en modelos, y en general los algoritmos de filogenia no están muy representados.

Hay un par de ejemplos muy buenos en i-net de algoritmos de filogenia, uno es el libro de Wheeler et al. [1], y en una vena similar, un manuscrito de DeLaet [2]. Sin embargo, los algoritmos que presentan son más bien generales, lo cual es muy bueno desde el punto de vista didáctico, pero en varios casos, alejado de lo que hacen los programas en la actualidad!

Como esas fuentes son muy buenas, espero enfocarme más en el aspecto de la implementación de los algoritmos. La idea es pasar de los más sencillos a los más complejos (en la medida en la que yo pueda comprenderlos xD).

Antes de empezar, pues quiero agradecer a Pablo Goloboff, que siempre ha estado dispuesto a discutir de algoritmos conmigo :). Por supuesto, los errores que tengan mis implementaciones son mis errores!

A medida que avance, iré posteando el código fuente en google code o sourceforge, por si desean examinarlo, requiere que sepan algo de C. El HTML tiene problemas con los símbolos mayor-que y menor-que, por los que los mostrare en estos posts como texto, en vez de usar el símbolo. Gracias a Rubén por el tip del HTML :)!

Campos de bits

Un componente básico del análisis filogenéticos son los caracteres. Asumamos que solo tenemos un carácter para cada terminal. Uno bien podría guardar cada estado en una variable, por ejemplo asignandole 0, 1, 2... según corresponda. Una idea así esta implícita en la descripción inicial del “groundpland divergence” de Wagner [3], y más o menos, en la formalización de Farris [4, ver 5]. Las operaciones entre caracteres serían operaciones de intervalos. Pero es mucho más sencillo ver a los caracteres como un conjunto de estados [4, 6]. Las operaciones entre caracteres serian operaciones de conjuntos. Esos conjuntos tienen además una característica particular: son perfectamente booleanos, es decir, un taxon tiene o no un determinado estado. Esto tiene dos consecuencias positivas: (i) podemos guardar el conjunto de estados como un campo de bits; (ii) las operaciones entre caracteres son operaciones de los campos de bits.

Las compus guardan los datos como números binarios. En un campo de bits, usamos esa particularidad para representar conjuntos de bits. Un ejemplo, aclara mejor la situación:

Estado    Representación binaria    "Número" (humano)
0        0001                        1
1        0010                        2
2        0100                        4
3        1000                        8
0, 1     0011                        3
1, 3     0101                        5

Como se ve, cada estado individual tiene su propio bit, y la combinación de estados es simplemente la unión los estados. Muchos lenguajes de programación incorporan operaciones para trabajar directamente con bits (not, and, or y xor) con lo cual la traducción de operaciones de conjuntos a operaciones de bits es directa.

En esta serie voy a utilizar un char para guardar los estados de carácter. En C, char es de 8 bits. Yo lo defino con un typedef, de manera que después es posible cambiar el número de bits en el bitfield.

#define BITS_ON_STATE 8
#define ALL_BITS_ON 255
typedef char STATES;

En este pequeño ejemplo, se leen los caractes de un taxon, desde un archivo (in), y se guardan en un array de caracteres (chars). El número de caracteres es nc, y se usan las funciones getc para leer caracteres de texto, SkipSpaces para ignorar los espacios de texto, y isdigit para reconocer si el carácter de texto es un número.

for (j = 0; j < nc; ++ j) {
error = SkipSpaces (in);
if (error != NO_ERROR) return error;
c = getc (in);
if (isdigit (c))
 chars [j] = 1 < < (c - '0');
else if ((c == '?') || (c == '-'))
 chars [j] = ALL_BITS_ON;
else return BAD_FORMAT;
}

En la operación chars [j] = 1 < < (c – '0') se resta el valor ASCII de '0' (30) al valor ASCII guardado en c (es un número, va de 30 a 39). El valor de esa resta lo usamos para correr los bits de 1. Así por ejemplo, si se lee un '0', la operación seria:

chars [j] = 1 < < (30 – 30)
chars [j] = 1 < < 0
    [0000 0001 < < 0 = 0000 0001]
chars [j] = 1

Si leemos un 5

chars [j] = 1 < < (35 – 30)
chars [j] = 1 < < 5
     [0000 0001 < < 5 = 0010 0000]
chars [j] = 32

Corrimos el 1 cinco bits a la izquierda.

Observen que los no aplicables o desconocidos, se codifican con todos los bits encendidos.

Esto funciona bastante bien para caracteres no aditivos. Para caracteres aditivos, es posible "recodificarlos" como varios caracteres binarios [7][8], una vez recodificados es posible utilizarlos como si fueran caracteres no aditivos independientes.

Hay formas más sofisticas de usar los campos de bits, uniendo varios caracteres en una sola variable (por ejemplo, en una variable de 32 bits, se pueden usar 8 caracteres de 4 bits, como nucleotidos) [8][9]. Ese empaquetado permite una evaluación muchisimo más rápida de los caracteres durante las búsquedas, puesto que en cada operación se pueden revisar simultáneamente varios caracteres.

Referencias
[1] Wheeler, W. et al. 2006. Dynamic homology and phylogenetic systematics: a unified approach using POY. American Mus. of Natural History, published in cooperation with NASA. online: http://research.amnh.org/scicomp/pdfs/wheeler/Wheeler_etal2006b.pdf
[2] DeLaet, J. 2005. Pseudocode for some tree search algorithms in phylogenetics. Manuscrito online: http://www.plantsystematics.org/publications/jdelaet./algora.pdf
[3] Wagner, W.H. 1961. Problems in the classification of ferns. En: Recent advances in botany. Toronto Univ. Press. pp. 841-844.
[4] Farris, J.S. 1970. Methods for computing Wagner trees. Syst. Zool. 19: 83-92.
[5] Goloboff, P.A. et al. 2006. Continuos characters analyzed as such. Cladistics 22: 589-601. doi: 10.1111/j.1096-0031.2006.00122.x
[6] Fitch, W.M. 1971. Toward defining the course of evolution: minimum change for a specific tree topology. Syst. Zool. 20: 406-416.
[7] Farris, J.S. et al. 1970. A numerical approach to phylogenetic systematics. Syst. Zool. 19: 172-189.
[8] Moilanen, A. 1999. Searching for most parsimonious trees with simulated evolutionary optimization. Cladistics 15: 39-50. doi: 10.1111/j.1096-0031.1999.tb00393.x
[9] Goloboff, P.A. 2002. Optimization of polytomies: state and parallel set operations. Mol Phyl. Evol. 22: 269-275. doi: 10.1006/mpev.2001.1049

Core coding

En estos días, algunas de las ideas que tengo de mi proyecto, no están saliendo como yo quería, así que me he dedicado a la programación de algunos detalles computacionales... como el asunto, aunque muy relacionado con computadoras, pero poco con cladística (aparte claro, de ser parte de mi proy xD).. lo deje en mi blog personal :P.

English version:

How can Java (and several other languages) programmers live without pointers?

Muy buena noticia sobre TNT

En estos momentos no estoy en la ciudad, así que no puedo escribir posts muy largos :'(... pero no podia dejar pasar esta gran noticia sobre TNT. La Willy Hennig Society a tomado la financiación y apoyo a TNT (un programa de Pablo Goloboff, Steve Farris y Kevin Nixon), así que a partir de ahora el programa es gratuito! Solo hay que cumplir algunas condiciones muy simples: uso personal, y citar el programa--y como no la financiación por partde de la WHS--al publicar resultados.

En caso de que no lo sepan, TNT es el programa más rápido para análisis filogenético de parsimonia, que implementa muchos de los más recientes y eficientes algoritmos de búsqueda [1, 2], y un excelente y poderoso lenguaje de macros/scripts. Si ustedes realizan análisis cladísticos/filogenéticos, este es el programa ideal.

Yo adoro el editor de caracteres! Es muy fácil de usar, y mucho más intuitivo que WinClada, NDE o Mesquite (sip! Es mucho mejor que el de Mesquite!).

Pueden descargarlo aquí: http://www.zmuc.dk/public/phylogeny/TNT/
lean la licencia y a disfrútenlo :)

Cuando regrese a Bogotá completare las citas ;)

[1] Nixon, K.C. 1999. The parsimony ratchet a new method for rapid parsimony analysis. Cladistics 15: 407-414.
[2] Goloboff, P. A. 1999. Analyzing large data sets in reasonable times: solutions for composite optima. Cladistics 15: 415-428.