lunes, noviembre 26, 2007

A brief sketch of a program for phylogenetics

The last week is a nice week for me, as I received a grant to begin a graduate scholarship :) As my main objective is coupled with the development of a program, and my own interest in phylogenetics, and in a lesser extent, in software engineering, i will try to show here how I think a phyligenetic-related software would be implemented.

Do not take it for granted! The software projects in which i am involved to date, are smaller and short-term, and then I usually make some (ugly) shortcuts for immediate solutions but with low flexibility to modifications. Here my sketch take into account the possibility of further refinements of each part, so it is far more modular than my small projects.
Every program is composed with two parts. The first, the more messier and the most bored part to write, is the user interface (UI). The second, is the program itself (the core). In small projects you could mix both parts without much pain, but as the program growths leaving both parts mixed makes the program difficult to maintain: you would rewrite several code parts to introduce new input formats.

Ideally you would try to make the core to be totally independent from the UI, but usually it is not possible (unless your program do noting). An effort to construct a well designed communication between the UI and the core, is always well payed in the future.

I start my design with the core, and in every moment thinking how the core would communicate with a black-box UI. In phylogenetics you have two major parts: the matrix, and the tree. Both are composed of more smaller elements. The matrix is a list of labels, usually with some coupled data (taxon-character matrix, a taxon-distribution matrix). The tree is a topology in which each vertex is associated with the matrix labels.

You could think that both the tree and the matrix are the same, after all, the tree is only an specific way to sort the terminals in the matrix (it seems that TreeFitter[1] works in that way). But there is a difference, the terminals in the matrix are unique, but you could have many tress associated with the same matrix, terminal 'a' are independent in two trees, but they could point to the same element in a matrix.
Apart from terminals, that have a fixed content, internal nodes of a tree are coupled with the same sort of data as terminals, but this is a variable content, dependent on the tree topology. So we could implement a single fixed matrix, and one (or more) variable matrix, when the tree is unused, the variable matrix can be discarded.

To communicate the core with the UI, at this moment, I prefer string streams. They could be find in standard library (although with some little spelling differences), in that way the UI always translate between formats to send to the core specific strings, for example the tree in parenthesis format, so the tree construction would not interact with files, or console input, for example.

In that way, the UI is a central of translation from console, file, command dialogs, etc., that can be implemented for different systems (e.g. Win, Linux, command line), but the core remains the same.

[1] Ronquist, F. TreeFitter, program and documentation, available on line at: http://www.ebc.uu.se/systzoo/research/treefitter/treefitter.html

jueves, noviembre 15, 2007

Now in english

All the few previous post I made for this blog were in spanish, my mother language, for now I will try to post in both english and spanish. In english because everybody know that it is the science language, I want that other people interested in systematics, biogeography and specifically cladistics could read my blog! In spanish because I never found another cladistics blog in spanish. The content of posts would not necessarily overlap, I would try to provide translations of each post, but for my own convenience, I want to post technical posts--dealing with computer programming, databasing, and 'phyloinformatics', as Page call it--in english, and philosophical and methodological in spanish. I also want to post about true bug's (Insecta: Heteroptera) phylogenetics, I think I would use english.

I also want to increase the rate of postings ;) I hope, I could post at least one time per week ;).

As you could see, I am not a good english writer, so I hope that this blog could help me to write somewhat better :).

miércoles, noviembre 07, 2007

Homología y parsimonia

Este post esta inspirado ligeramente en la discusión ke han colocado Ebach y Williams en su blog systematics & biogeography. Mi intención es mostrar como se relaciona el análisis de parsimonia (o análisis cladístico) con la homología.

Homología

El termino homología tiene una larga historia de discusiones. Yo uso un poko la definición tradicional y tomo como homologas dos estructuras ke son consideradas la misma estructura en dos organismos diferentes. Uno puede usar múltiples argumentos para decir que significa ke una estructura sea la misma: el plan de Dios, el orden del universo, el tipo primordial, o la ke yo prefiero que es por ancestría común.

Cuando digo ke dos estructuras son homologas, implica ke son la misma estructura, y que esta a sido heredada de el ancestro común de ambos organismos. La herencia implica un montón de procesos, que se hayan implícitos en la definición: especialmente genética y biología del desarrollo. Además, las estructuras, a pesar de ser las mismas no suelen ser iguales, pueden estar fuertemente modificadas, pero aún así son la misma estructura, esto implica ke hay una transformación de las homologías, así entran en juego otros factores a nuestra definición como son los procesos ke desencadenan esas diferencias, como la interacción genética y la dinámica de las poblaciones.

En un análisis cladístico no hay una preocupación directa por todos esos fenómenos asociados a la homología. Esos procesos son más de interés de otras ramas de la biología como la evolución, le biología del desarrollo, la genética, la biología molecular, la genética de poblaciones, la ecología, etc. pero ke no sean de interés no implica ke sean ignorables: en la definición de caracteres (homologos) para el análisis cladístico muchos de esos factores entran en consideración para dar limite a los caracteres y como codificarlos.

Desafortunadamente, el ke el 'proceso' no sea preocupación de la cladística a llevado a la errónea idea ke es irrelevante en la definición de los caracteres. Así los cladístas de patrón (como Nelson, Platnick, o más recientemente Pleijel y Brower) consideran ke la cladística esta totalmente libre de todo pensamiento evolutivo, pero todo lo contrario: el usar caracteres homologos implica ke estamos trabajando en un marco ke esta basado en el origen por ancestría común, por lo tanto todos los estados de un carácter--y no solo los apomorficos--son la misma estructura.

Pero no solo eso, la implicación evolutiva es enorme para muchos caracteres, en especial si tenemos un buen conocimiento para el carácter, por lo ke la idea de Kluge (e.g. 2003) de ke solo es necesario 'descendencia con modificación' es también errada. Al introducir herencia y evolución, muchas más cosas se encuentran embebidas en la definición de cada carácter. Claro esta, eso depende de cada carácter, en muchas situaciones solamente tenemos un conocimiento morfológico del carácter, con lo ke lo único ke podemos asumir es la simple 'descendencia con modificación', pero en muchos grupos (como los vertebrados), el conocimiento ke se tiene sobre los caracteres es mucho más amplio, incluyendo por ejemplo un buen conocimiento del desarrollo de la estructura.

Parsimonia: algoritmo

El algoritmo básico de parsimonia es bastante sencillo. Si keremos establecer el estado de carácter presente en un nodo A, cuyos descendientes son B y C, y de los cuales ya sabemos su estado de carácter, el estado de A es la intersección de los estados de B y C, si esa intersección es un conjunto vacío entonces el estado es la unión de los estados B y C. Esta unión implica ke ha habido un cambio (lo ke es llamado un paso). Optimizar los estados es un poko más complicado, pero esas operaciones son lo básico del algoritmo.

Asignación de estados con el algoritmo de parsimonia: (A) y (B) el estado del nodo ancestro 'x' es igual a la intersección del estado de los descendientes 'y', 'z', en este caso, blanco; (C) 'y' y 'z' no comparten ningún estado, por lo tanto el estado asignado a 'x' es la unión de los estados de los descendientes.

Es fácil notar ke el algoritmo es 'independiente' de los datos tomados, uno puede tomar cualkier clase de 'carácter' (en ciencias de computadores este problema es conocido como el problema del coloreado, y los 'caracteres' son colores en un mapa) y cualkier clase de terminales de análisis. Esa es una característica propia de los métodos formalizados como algoritmos. Dado esas circunstancias es necesario proveer una justificación del uso de un algoritmo particular para cada problema.

En cladística la justificación para el uso de parsimonia viene dada por el concepto de homología.

Parsimonia: análisis cladístico

Dado el concepto evolutivo de homología, su unión con el concepto algoritmico de parsimonia es directo. Si decimos ke un carácter, cualquiera ke sea su estado, es el mismo en dos organismos ke comparten un ancestro común, eso implica ke ese carácter es heredado del ancestro común, por lo tanto el ancestro común debe tener ese carácter.

Si además ambos organismos comparten la misma expresión del carácter, es decir su mismo estado, entonces ese mismo estado se encuentra en su ancestro común, si por el contrario ambos organismos tienen diferentes expresiones del carácter, el ancestro común tiene el carácter, pero no sabemos ke expresión pueda tener, por lo ke asumimos ke tiene alguno de los dos estados, y damos por hecho, ke si en realidad ambos organismos comparten ese carácter, debió haber ocurrido una transformación.

Como se puede ver, esa es exactamente la misma descripción del algoritmo de parsimonia. En cladística el algoritmo esta justificado pues los caracteres usados son tomados como homologos. En ese contexto el algoritmo maximiza nuestras proposiciones de homología al minimizar las transformaciones: de esa forma se asegura ke la mayor cantidad de organismos con el mismo estados de carácter kedan contiguos. Esto es minimización de hipótesis ad hoc de homoplasia (Farris, 1983).

Parsimonia y los tests de homología

Es una idea común entre los cladístas el argumentar ke parsimonia es un test de homología: la congruencia. Yo estoy en desacuerdo, pues como he argumentado akí la base de la parsimonia es asumir de plano ke las entradas para un carácter son homologas. Para mi los tests de homología son una condición previa del análisis cladístico.

Esos test pueden venir de muchas formas, bien sea basado en argumentos de morfología (usualmente llamada 'similitud'), posición anatómica, organización estructural, ontogenía, genética, en la mayor parte de los casos muchas de esas pruebas son conjuntas--por lo ke definir un carácter marca una fuerte carga teórica--es despues de haber examinado todas esas alternativas ke podemos tener un buen carácter. Es por eso ke una homoplasía es una hipótesis ad hoc: la homoplasia en el carácter solo esta justificada en relación con el cladograma.
Por supuesto, es necesario recurrir a la revisión de caracteres, y ciertamente es bueno revisar los caracteres homoplasicos, pero es igualmente valioso examinar todos los caracteres por igual. Es posible ke tengamos alguna duda acerca de como codificar caracteres, debido a su complejidad o porke son muy poko conocidos, en estos casos puede ser posible utilizar como apoyo el resultado ke producen diferentes tipos de codificación (esa es la alternativa ke usa Ramírez, en prensa, y en molecular Wheeler, 1996). Pero debo llamar la atención sobre eso: la codificación no esta 'avalada' por el cladograma, pues el argumento ke se utiliza para defender esa codificación es el mismo usado para la homoplasia: solo se justifica en relación con el cladograma, por lo tanto la codificación tiene un fuerte elemento ad hoc. Para esos casos yo preferiría ke se utilizara un eskema de pesado como el de Neff (1986): dado ke conocemos poko del carácter, tanto ke tenemos nuestras dudas para codificarlo, es mejor ke tenga un peso más bajo ke el de caracteres ke conocemos mejor.

**
Adicional: una especulación histórica

En este ensayo yo presente las ideas de homología y parsimonia por separado y luego las fusione. Lo hice así porke considero ke da claridad a la discusión. Sin embargo, históricamente el desarrollo fue muy entrelazado desde el inicio. Leyendo a Wagner (1961, desde el lado algoritmico) y a Hennig (1968, desde el lado lógico) es claro como ambas ideas son intercambiables desde el inicio. Ambas visiones kedaron integradas muy bien en Farris et al. 1970, ke a pesar de ser un intento de axiomatización, contiene ideas (para mi muy estimulantes) ke coinciden con muchos de los puntos expuestos akí. Así desde el inicio las ideas del análisis cladístico y de parsimonia estuvieron juntas.

Wagner, Hennig y Farris desarrollaron sus ideas desde un contexto de la morfología. Dayoff (1969) también experimento con varios algoritmos para secuencias moleculares, donde al menos por ahora, las ideas de homología son en muchos casos diferentes a el concepto de morfología, en su época (mediados de los 60s), no se exactamente ke pensaran de homología los moleculares, pero era claro ke ellos no creían ke dos bases (en el caso de Dayoff, dos aminoacidos) iguales en dos organismos implicaba un origen común, la idea de mutaciones constantes precluyo la idea. Es interesante ver ke Dayoff no pudo encontrar una forma adecuada de asignar estados en los ancestros.

Referencias
Dayoff, M.O. (1969) Computer analysis of protein evolution. Sci. Amer. 221: 87-95.
Farris, J.S. (1983) The logical basis of phylogenetic systematics. En: Platnick, N., Funk, V.A. (Eds.), Advances in cladistics, vol. 2. Columbia, New York. Pp. 7-36.
Farris, J.S., Kluge, A.G., Eckardt, M.J. (1970) A numerical approach to phylogenetic systematics. Syst. Zool. 19: 172-189.
Hennig, W. (1968) Elementos de una sistemática filogenética. Eudeba, Buenos Aires.
Kluge, A.G. (2003) On deduction of species relationships: a précis. Cladistics 19: 233-239.
Neff, N.A. (1986) A rational basis for a priori character weighting. Syst. Zool. 35: 110-123.
Ramírez, M.J. (2007) Homology as a parsimony problem: a dynamic homology approach for morgological data. Cladistics 23:xx-xx.
Wagner, W.H. (1961) Problems in the classification of ferns. En: Recent advances in botany, vol. 1 Univ. Toronto, Toronto. Pp. 841-844.
Wheeler, W.C. (1996) Optimization alignment: the end of multiple sequence alignment in phylogenetics? Cladistics 12: 1-9.

jueves, noviembre 01, 2007

Pasando a BPR3

Ayer me entere ke existe una iniciativa, BPR3, blogs sobre investigación revisada por pares, y muy contento con esa idea me voy a poner a modificar mis post previos :), y realizar los futuros dentro de esa iniciativa :D

Pueden ver lo ke dice la gente de BPR3 en su blog oficial: bpr3.org
Y aquí pueden leer un poco sobre lo ke pienso de esa idea (en mi blog personal).