4 de mayo de 2008
Algoritmos de solucion de matrices filogeneticas
¿Cuales son los algoritmos matemáticos que utilizan los software cladisticos para resolver las matrices? Mi pregunta se basa en el hecho de que mientras en la TN es perfectamente conocible que las matrices son resueltas a través de índices de similitud o de distancias y no pueden consignarse signos como ? y - para denotar que no se conoce o no es evaluable el caracter, en el caso de las matrices resueltas a traves de software filogeneticos estos signos son perfectamente admisibles y evaluables, lo cual he supuesto debe ser interpretado de alguna forma por el algoritmo empleado en la solucion. Hasta el presente no he podido encontrar los algoritmos que se utilizan en la solución de las matrices filogenéticas en los diferentes progrmas como POY,TNT, HENNIG, Mc CLADE y otos tantos.
Suscribirse a:
Enviar comentarios (Atom)
Hola!
ResponderEliminarLos programas que nombras (como TNT, Hennig86, o POY) son programas cladísticos están basados en parsimonia, un método que busca optimar directamente los caracteres sin recurrir a una matriz de distancias.
Así en realidad, los caracteres no conocidos (los '?' y '-') son ignorados en el análisis. Desde un punto de vista más técnico, cada entrada de la matriz de datos es guardada como un campo de bits, con los bits encendidos si el estado esta presente en el taxon. Por ejemplo si tienes un taxon A que tenga el estado '0' esta sera su representación en bits (para una variable de 8 bits): 0000 0001, si el taxon B tiene un 0 y un 1, entonces es 0000 0011, y así. Cuando hay un interrogante o un no aplicable, todos los bits se encienden: 1111 1111.
Para calcular la longitud, entonces se hace una operación a nivel de bits. Primero se hace un AND (es decir una intersección). Para nuestro caso A (AND) B = 0000 0001. En caso de que el conjunto de intersección sea vacío, uno realiza un OR (una unión), y suma un paso. Como vez, si uno hace una intersección con un interrogante, el conjunto de estados no cambia, la intersección siempre produce algún valor. Tampoco se usaron distancias.
Los algoritmos y cosas las puedes encontrar en journals como systematic biology y cladistics. He aquí una pequeniisma lista de algunos papers que pueden ser bien útiles:
**Farris, J.S. 1970. Systematic Zoology 19: 83-92 [Descripción básica de la optimación de caracteres].
**Fitch, W.M. 1971. Systematic Zoology 20: 406-416 [Generalización del algoritmo de Farris].
**Goloboff, P.A. 1996. Cladistics 12: 199-220 [Atajos y algoritmos para hacer optimaciones rápidas].
**Goloboff, P.A. 1998. Cladistics 14: 229-237 [Métodos usando transformaciones de Sankoff].
Estos dos textos en línea tienen descripciones bien completas con pseudo-código de muchos de los algoritmos:
http://www.plantsystematics.org/publications/jdelaet/algora.pdf
http://research.amnh.org/scicomp/pdfs/wheeler/Wheeler_etal2006b.pdf
Saludos!
Salvador
Hola Salva. Gracias por tu comentario, las referencias y los links. Realmente todo me resulta de gran utilidad y me colabora en el entendimiento de estos procesos.
ResponderEliminarNo obstante quisiera ir sobre un aspecto que me resulto interesante. Tu dices que los programas cladisticos mencionados por mi estan basados en parsimonia y yo entiendo que utilizan esta durante el proceso de calculo. Si mi entender es correcto mi duda es la siguiente. Yo entiendo por parsimonia el criterio que selecciona la solucion que implica menor cantidad de pasos, energia, esfuerzo o alguna otra unidad. O sea que si un problema presenta diferentes soluciones con las cuales se obtiene el mismo resultado, bajo el principio de parsimonia la solucion, en este caso hipotesis, que sera seleccionada, es aquella que implique menor candidad de pasos. Esto mismo basicamente dice el principio de Occan's razor si no me equivoco. Si estos programas utilizan el principio de parsimonia en el proceso, podria llamar a esto "parsimonia a priori"? Si se utiliza esta "parsimonia a priori" es de suponer que la hipotesis o arbol obtenido dbe ser el arbol mas parsimonioso "per se"? Si lo anterior se cumple, porque estos programas ofrecen resultados multiples o sea, mas de un arbol o hipotesis, por lo cual debe ser aplicado nuevamente el principio de parsimonia para seleccionar aquel que en menor cantidad de pasos lleve a la solucion, algo asi como "parsimonia a posteriori"? No es esto una doble aplicacion del principio?
Te agradeceria un comentario al respecto.
Una vez mas gracias y exitos
Enrique Rubio
Hola Enrique
ResponderEliminarLo que minimizan los programas de parsimonia es, en general, es el costo de transformaciones, como todos los caracteres informativos se transforman al menos una vez, eso es equivalente a minimizar la cantidad de homoplasia. Para mi, la mejor forma lógica de entender la minimización de la homplasia, la da Farris en 1983: minimizar hipótesis ad hoc.
En los programas uno puede pensar que la parsimonia se usa 'a dos niveles', en el primero es como se optiman los caracteres, es decir en la asignación de estados en los nodos. Esto suele ser independiente de que se utilicen pesaje de caracteres por ejemplo, pero depende de las transformaciones entre estados. Lo usual es que las transformaciones entre estados sean iguales, pero en principio, podemos utilizar diversos costos de transformación entre caracteres.
El otro uso, es para escoger entre arboles, en este caso, se suman los costos de todas las asignaciones y ese es el costo de un árbol. En realidad, los dos niveles en este caso son diferentes aspectos de los mismo, uno selecciona el árbol que minimice el total de asignaciones!
Ahora bien, el principio no te cuida de la ambigüedad de los datos! Es por eso que puedes tener muchos arboles con el mismo costo, en ese caso no tienes la posibilidad de seleccionar entre un árbol u otro, es por eso que para algunos conjuntos de datos producen una igual cantidad de árboles igualmente parsimoniosos. De ese grupo de arboles no tenemos una opción lógica para preferir uno sobre el otro, por eso no hay nada similar a lo que llamas “parsimonia a posteriori”. Muchas personas usan cosas como pesaje sucesivo para escoger un árbol, pero esa aplicación es errónea, en realidad pesaje sucesivo no implica que te reduzca el número de árboles, y en principio si uno es usuario de pesaje sucesivo debería hacerlo incluso si solo obtiene un árbol!
Saludos,
Salvador
Pd. Notaras que use 'costo' y no longitud, eso es porque si tienes matrices de transformación, pesos a priori, o algún tipo de pesado implícito, el costo no es equivalente con la longitud.