Análisis filogenético de grandes matrices de datos

GOLOBOFF, PABLO

Quilmes

Congreso; 1er Congreso Argentino de Bioinformática y Biología Computacional; 2010

Asociacion Argentina de Bioinformatica y Biologia Computacional

   Se discutirán varios aspectos computacionales del programa TNT [1,2], el programa de análisisfilogenético por parsimonia más eficiente y plataforma para muchísimos tipos de comparacionesfilogenéticas (con unos 140 comandos y un intérprete de scripts). TNT es un proyecto iniciadoen 1998, hoy con cerca de 100.000 líneas de código C, que cuenta con unas 500 citas.   El análisis filogenético consiste en seleccionar árboles de acuerdo a una función objetiva (quepermite asignar un score a cada árbol posible); bajo parsimonia, los árboles son evaluados deacuerdo a sus requerimientos de homoplasia (i.e. cantidad mínima de originacionesindependientes de características similares). Esto involucra una serie de problemascomputacionales interesantes, el más obvio de los cuales es el de maximizar la eficiencia con laque se puede evaluar esta función objetiva en un gran número de árboles. Se presentan variosatajos computacionales para búsquedas de árboles en TNT; los más interesantes son varios atajos(algunos nuevos, otros ya descritos) que combinados permiten evaluar árboles durante branch-swapping en un tiempo que (para data sets reales) decrece con el número de hojas (=taxa) delárbol. Así, el branch-swapping de tipo TBR para T taxa explora una vecindad cuyo tamaño creceentre T2.5 y T3, pero el tiempo necesario para completar el proceso crece con T2 o menos. De estemodo, para el data set de 73,000 taxa x 10,000 caracteres de [3], el tiempo utilizado para evaluar(=calcular el número de pasos) cada reacomodamiento es de ca. 7.5x10-9 seg; en el data set de[4], de 218,000 taxa x 1300 caracters, el tiempo es 3.2x10-11 seg.   Otros aspectos del programa que debieron mejorarse al comenzar a experimentar con data setsrealmente grandes involucraron varios algoritmos para trabajar con aspectos de la topología delos árboles, que ocupan tiempos o cantidades de memoria negligibles en data sets de unos pocosmiles de taxa, pero bastante importantes para decenas o cientos de miles. Un ejemplo es elmanejo de comparaciones de grupos entre árboles (para calcular consensos, y para comparacionesentre árboles durante ciertas estrategias de búsquedas); los algoritmos usuales (e.g. [5]) sonrápidos pero necesitan enormes cantidades de memoria. Nuevos algoritmos usan tiempossimilares, pero cantidades insignificantes de memoria. Otro ejemplo interesante es el métodousado para trabajar bajo "constraints positivos" en TNT, con el cual los árboles que violan losconstraints no son nunca generados ni evaluados, permitiendo acelerar considerablemente elproceso de búsqueda (en otros programas, como PAUP*, la velocidad de branch-swapping bajoconstraints es semejante a la velocidad sin constraints).