Repositorio Institucional de Documentos

Proyecto Fin de Carrera Ingenier´ıa Inform´atica Curso 2009/2010 An´alisis te´orico-pr´actico de m´etodos de inferencia filogen´etica basados en selecci´on de modelos y m´etodos de super´arboles Autor: Jorge ´ Alvarez Jarreta Bajo la direcci´on de: Roberto Blanco Mart´ınez Elvira Mayordomo C´amara Departamento de Inform´atica e Ingenier´ıa de Sistemas ´ Area de Lenguajes de Sistemas Inform´aticos Centro Polit´ecnico Superior Universidad de Zaragoza Septiembre de 2010 An´alisis te´orico-pr´actico de m´etodos de inferencia filogen´etica basados en selecci´on de modelos y m´etodos de super´arboles RESUMEN Este proyecto fin de carrera tiene como objetivo principal el desarrollo de un sistema de inferencia filogen´etica a partir de secuencias de ADN, utilizando m´etodos de selecci´on de modelos evolutivos y de construcci´on de super´arboles. La filogen´etica es la ciencia que trata de establecer la relaci´on evolutiva real entre individuos o especies. Los modelos evolutivos son modelos matem´aticos que intentan explicar de la forma m´as fiel posible la evoluci´on real de los datos a tratar, generando para ello ´arboles filogen´eticos, en los cuales se refleja dicha relaci´on. Los m´etodos de construcci´on de super´arboles crean estas estructuras a partir de varios ´arboles filogen´eticos cuyas hojas poseen cierto nivel de solapamiento. En la actualidad existen importantes barreras de coste computacional que limitan de forma pr´actica tanto la realizaci´on de filogenias extensivas (muchos de los m´etodos habituales s´olo han sido realmente probados con cientos de secuencias) como la consideraci´on de modelos evolutivos m´as generales, interesantes y explicativos que el modelo uniforme (estos modelos s´olo se han utilizado hasta ahora en tama˜nos de problema muy reducidos). Las novedades que aporta el proyecto tienen dos vertientes principales: por un lado el desarrollo e implementaci´on de nuevos algoritmos para la construcci´on de super´arboles, y por el otro el desarrollo de un sistema de inferencia filogen´etica que concentra varios m´etodos sobre an´alisis de secuencias y estudio de filogenias que no se hab´ıan unido hasta el momento. Especial menci´on requiere la utilizaci´on de flujos de trabajo para la construcci´on de este sistema, pues nunca hab´ıan sido aplicados en este tipo de herramientas. El trabajo desarrollado ha exigido una intensa fase de formaci´on debido a la novedad de los temas biol´ogicos a tratar. De forma entrelazada a esta formaci´on se ha estudiado, dise˜nado e implementado el sistema mencionado, incorporando como fase final aquellos m´etodos de super´arboles que mejores prestaciones ofrec´ıan. Debido a la utilizaci´on de los flujos de trabajo y a la elevada carga computacional que genera el sistema, la selecci´on del marco tecnol´ogico en el que se ha desarrollado ha requerido especial atenci´on. Los resultados tanto del sistema dise˜nado como de los m´etodos de super´arboles estudiados han sido excelentes en las pruebas realizadas (incluso las realizadas con datos mucho mayores que los que hasta ahora manejaban otro tipo de aplicaciones bioinform´aticas), lo que se ha considerado como un rotundo ´exito. I Agradecimientos El final de este largo camino. Qui´en me lo iba a decir. Me gustar´ıa agradec´erselo a mucha gente, y seguramente todos ellos lo sepan, as´ı que pido perd´on por si me dejo a alguien en el tintero, estas cosas nunca se me han dado bien. En primer lugar quiero agradec´erselo a mis dos directores, Roberto y Elvira, que me han aguantado y ayudado siempre que me ha hecho falta. Adem´as, a Jos´e Manuel, Goyo y Nacho, quienes han estado ah´ı apoy´andome e interes´andose por c´omo iba mi proyecto. Esas reuniones del grupo de bioinform´atica dudo que se me olviden nunca. Pasando al plano personal, en primer lugar quiero agradec´erselo a mis padres, quienes con su esfuerzo y duro trabajo durante su vida me han costeado los estudios, y me han aguantado en rabietas y malas notas. Por supuesto, toda mi familia tambi´en ha estado ah´ı, unos m´as que otros, pero no es momento para se˜nalar a nadie. Gracias a todos por estar ah´ı. No me gustar´ıa terminar estas l´ıneas sin agradec´erselo a mis amigos, entre ellos a Fronti y Antonio, los mejores entre los mejores, que empezaron conmigo, y aunque un poco rezagados, siguen por ah´ı queriendo andar a mi lado. Y las ´ultimas l´ıneas las reservo para la persona m´as especial de todas. S´ı, Laura, me refiero a ti. Sabes lo mucho que te quiero y que sin ti no habr´ıa llegado aqu´ı nunca. Eres lo mejor de todo y a quien m´as quiero agradecerle (y dedicarle) todo lo bueno en mi vida. De coraz´on os digo, gracias. III ´ Indice general 1. Introducci´on 1 1.1. Contexto del proyecto . . . . . . . . . . . . . . . . . . . . . . 1 1.2. Objetivos ............................. 1 1.3. Metodolog´ıa y herramientas . . . . . . . . . . . . . . . . . . . 2 1.4. Software.............................. 3 1.5. Entorno tecnol´ogico . . . . . . . . . . . . . . . . . . . . . . . 4 1.6. Estructura de la memoria . . . . . . . . . . . . . . . . . . . . 4 2. Glosario biol´ogico 6 3. Sistema de inferencia filogen´etica mediante flujos de trabajo y selecci´on de modelos 8 3.1. Estadodelarte .......................... 8 3.2. Dise˜no............................... 9 3.3. Marco tecnol´ogico . . . . . . . . . . . . . . . . . . . . . . . . 13 3.4. Implementaci´on.......................... 16 3.5. Pruebas .............................. 19 3.6. Resultados............................. 20 4. Super´arboles 22 4.1. Estadodelarte .......................... 22 4.2. Super´arbol simple . . . . . . . . . . . . . . . . . . . . . . . . 22 4.2.1. Definici´on......................... 22 4.2.2. Implementaci´on . . . . . . . . . . . . . . . . . . . . . . 23 4.2.3. Pruebas realizadas . . . . . . . . . . . . . . . . . . . . 23 4.3. Super´arbol de corte m´ınimo . . . . . . . . . . . . . . . . . . . 23 4.3.1. Definici´on......................... 23 4.3.2. Implementaci´on . . . . . . . . . . . . . . . . . . . . . . 24 4.3.3. Pruebas realizadas . . . . . . . . . . . . . . . . . . . . 25 5. Conclusiones 26 5.1. Trabajo realizado . . . . . . . . . . . . . . . . . . . . . . . . . 26 5.2. Con vistas al futuro . . . . . . . . . . . . . . . . . . . . . . . 27 5.3. De lo profesional a lo personal . . . . . . . . . . . . . . . . . . 27 Bibliograf´ıa 29 IV ´ Indice de figuras 3.1. Dise˜no del primer m´odulo del sistema . . . . . . . . . . . . . 10 3.2. Dise˜no del segundo m´odulo del sistema . . . . . . . . . . . . . 11 3.3. Dise˜no del tercer m´odulo del sistema . . . . . . . . . . . . . . 12 3.4. Implementaci´on del primer m´odulo del sistema . . . . . . . . 17 3.5. Implementaci´on del segundo m´odulo del sistema . . . . . . . 17 3.6. Implementaci´on del tercer m´odulo del sistema . . . . . . . . . 18 V 1 Introducci´on 1.1 Contexto del proyecto El proyecto de fin de carrera que se ha realizado prosigue el trabajo de varios proyectos fin de carrera de a˜nos anteriores, en concreto los proyectos de Pablo Urcola [27], Roberto Blanco [5] e Iv´an Dar´ıo Traveso [26]. Se ha desarrollado en el Departamento de Inform´atica e Ingenier´ıa de Sistemas de la Universidad de Zaragoza, dentro del ´ambito de la bioinform´atica [15], en un grupo de investigaci´on formado por los dos directores de este proyecto y otros miembros del departamento. Pasar´e a formar parte del mismo oficialmente una vez haya finalizado este proyecto, aunque ya me sienta como un miembro m´as. Respecto al contexto biol´ogico del proyecto, la construcci´on de filogenias permite estudiar la relaci´on evolutiva entre organismos de la misma o de distintas especies. En el caso concreto de este proyecto, se ha trabajado con el ADN mitocondrial humano, ya que, entre otras cosas, su estudio filogen´etico permite detectar enfermedades raras y, muchas de ellas, asociadas a muerte prematura del individuo. La detecci´on de estas enfermedades se basa en la locaci´on de su ADN en el ´arbol de ADN mitocondrial humano [20]. 1.2 Objetivos Una vez situados en el contexto de este proyecto, es hora de pasar a describir los objetivos que lo han guiado. La investigaci´on se ha centrado en la construcci´on de filogenias completas o ´arboles filogen´eticos para casos de grandes cantidades de datos, tomando como unidad de trabajo la secuencia de ADN mitocondrial humano, como se ven´ıa haciendo en los proyectos mencionados en la secci´on anterior. Cabe destacar que con el trabajo realizado se ofrecen nuevas v´ıas de investigaci´on, tratando temas hasta ahora poco o nada utilizados en bioinform´atica. El proyecto consta de tres objetivos fundamentales: introducci´on y formaci´on, creaci´on de un sistema de inferencia filogen´etica basado en flujos de trabajo y selecci´on de modelos, y estudio y desarrollo de algoritmos para la construcci´on de super´arboles. 1 1.3. METODOLOG´ IA Y HERRAMIENTAS El primero de los objetivos queda inherente a todo proyecto, pues suele ser necesaria una peque˜na fase de formaci´on para adquirir los conocimientos necesarios para afrontarlo. El problema adicional es que no existe formaci´on en estas tem´aticas durante la carrera, por lo cual ha sido necesario un esfuerzo a˜nadido desde el comienzo. Pr´acticamente este objetivo se ha mantenido durante todo el proyecto, con una ligera variaci´on: al principio fue m´as guiada por los directores del proyecto y, hacia el final, se me dio libertad para profundizar en aquellos temas que creyese convenientes para desempe˜nar mi trabajo, teniendo que buscar la bibliograf´ıa necesaria por mi mismo. El segundo consiste en abordar problemas de inferencia filogen´etica basados en problemas de selecci´on de modelos evolutivos [17]. La selecci´on de modelos consiste en la evaluaci´on de un conjunto de modelos evolutivos te´oricos respecto a un alineamiento de secuencias dado, y bajo alguna metodolog´ıa (m´axima verosimilitud, criterios de informaci´on,) obtener alg´un valor num´erico que permita decidir qu´e modelo se ajusta mejor a dicho alineamiento. En otras palabras, qu´e modelo evolutivo explica m´as fielmente la relaci´on entre las secuencias. Adem´as, se ha realizado un estudio del impacto de esta nueva metodolog´ıa en casos reales con grandes cantidades de datos. Fundamentalmente se ha estudiado la influencia del particionado de datos (divisi´on en grupos m´as peque˜nos de secuencias y con un menor n´umero de nucle´otidos o amino´acidos, seg´un se trate de ADN o prote´ınas) en relaci´on al coste temporal para la obtenci´on de los resultados deseados. Para el c´omputo eficiente de estos problemas se ha aprovechado el paralelismo inherente mediante una estructuraci´on en flujos de trabajo [9] que permite la gesti´on autom´atica de trabajos y un m´aximo aprovechamiento de los recursos disponibles. El ´ultimo objetivo tiene como base el estudio de los algoritmos existentes que permiten combinar varios ´arboles filogen´eticos compatibles entre s´ı en un super´arbol que los aglutine [21], con la firme intenci´on de encontrar alguno que lo consiga de forma exacta y con coste polin´omico [22, 14]. Como se puede ver en proyectos anteriores [26], no existen actualmente soluciones satisfactorias en este aspecto, al menos p´ublicamente, por lo que se ha optado por desarrollar soluciones aceptables a este problema. Aunque este punto podr´ıa quedar incluido como parte de los objetivos del del sistema de inferencia filogen´etica, debido a su peso e importancia en el proyecto se ha considerado oportuno plantearlo como un objetivo m´as del mismo en vez de envolverlo dentro del anterior. 1.3 Metodolog´ıa y herramientas Como ya se ha comentado, la carencia de formaci´on en contextos biol´ogicos ha requerido un esfuerzo m´as intenso, tanto en dedicaci´on como en tiempo de adquisici´on de conocimientos. De forma espec´ıfica, se ha profundizado 2 3.2. DISE˜ NO estudio de costes temporales realizado a la herramienta jModelTest. Adem´as, estas herramientas trabajan ´unicamente con los alineamientos, no haciendo otra cosa que evaluar los modelos evolutivos. Por tanto, su valor o utilidad queda muy limitado por estas caracter´ısticas. Por ello, se vio la necesidad de crear una herramienta que realizase una verdadera inferencia filogen´etica de un conjunto de secuencias, con unos costes temporales razonables. Para realizar una inferencia filogen´etica que se pueda considerar v´alida, son necesarios varios elementos que han de estar presentes a lo largo del proceso. El primero y principal es el evaluar y seleccionar el modelo evolutivo adecuado para cada conjunto de datos, como resulta ya obvio tras lo que se ha comentado, unas l´ıneas m´as arriba. Pero tambi´en hay que tener en cuenta que los datos pueden contener errores, debido a que es posible que las lecturas en el laboratorio contengan alg´un tipo de margen de error o posibles huecos, limitaci´on de la propia tecnolog´ıa actual. Por ello es necesario acompa˜nar la selecci´on de modelos de un estudio estad´ıstico que permita asegurar que el modelo seleccionado es el adecuado. Para ello es necesario generar muestras con ligeras diferencias a nivel de los amino´acidos en las secuencias iniciales que permitan asegurar que la selecci´on es correcta. Por otro lado, que se seleccione un modelo evolutivo para un alineamiento concreto, implica que se puede construir un ´arbol filogen´etico de dicho alineamiento, que es lo que queremos obtener finalmente. Para ello ser´a necesario utilizar alg´un m´etodo que permita obtener un ´unico ´arbol a partir de todos los que se obtengan a partir de las muestras generadas. Como elementos a˜nadidos, adem´as, como objetivos a˜nadidos, se ha querido construir un sistema que trabaje con grupos m´as peque˜nos de secuencias, y alineamientos con un menos n´umero de ellas. Para ello, de los datos iniciales se realizar´a una primera divisi´on por haplogrupos y una segunda divisi´on por genes, permitiendo as´ı que distintos modelos evolutivos puedan explicar la filogenia de distintos genes, para diferentes haplogrupos. Debido a que la divisi´on por haplogrupos es una divisi´on especial, como se ha explicado en el cap´ıtulo Fundamentos, ser´a necesaria una reconstrucci´on del ´arbol filogen´etico final mediante alg´un m´etodo de super´arboles. 3.2 Dise˜no Una vez especificadas todas las necesidades y objetivos del sistema, se ha procedido a la realizaci´on del dise˜no del mismo. Como idea inicial para realizar una mejora en el rendimiento, se puede ver f´acilmente que la evaluaci´on de cada modelo es un proceso independiente, lo que sugiere que podr´ıa ser factible la paralelizaci´on de estas tareas, aumentando as´ı el rendimiento del sistema. De este punto surge la idea de la utilizaci´on de flujos de trabajo como base para la construcci´on del sistema. De esta forma, todas las tareas quedan separadas y marcadas, pudiendo 9 3.2. DISE˜ NO as´ı detectarse todos aquellos procesos del sistema cuya ejecuci´on es independiente entre s´ı, permitiendo as´ı su paralelizaci´on [28, 7, 11, 13]. El sistema se ha construido bajo la idea de caja negra. Para aquellas personas que desconozcan el concepto, la idea de la caja negra es desarrollar m´odulos independientes, de forma que trabajen sin tener conocimiento de las dem´as partes del sistema a las que est´an conectados. Para poder manejarlos solamente es necesario conocer qu´e datos se les ha de proporcionar y qu´e salida se obtendr´a. Aunque se explicar´a con m´as detalles en el siguiente apartado, a la hora de poder realizar un dise˜no factible y real del sistema, una vez identificadas las necesidades b´asicas, se ha seleccionado el software que se va a utilizar para poder satisfacer dichas necesidades. Se ha escogido la aplicaci´on Phyml para la evaluaci´on de cada modelo, al igual que hace jModelTest, y las herramientas seqboot y consense del paquete Phylip para la generaci´on de muestras y la aplicaci´on del m´etodo de consenso. La justificaci´on del uso de estas dos herramientas se explicar´a tambi´en en el siguiente apartado. A continuaci´on se van a ir mostrando las distintas partes que conforman el sistema y una detallada explicaci´on de cada una de ellas. Figura 3.1: Primer componente del sistema. Realiza la selecci´on de modelo evolutivo, generaci´on y re-evaluaci´on de los muestreos y aplicaci´on del m´etodo de consenso para unificar los ´arboles filogen´eticos resultantes. En la figura 3.1 se puede ver la caja m´as elemental del sistema. Antes de continuar indicar que todas las cajas se han construido de forma que puedan operar independientemente, es decir, que este m´odulo per se puede servir perfectamente como herramienta software, si solo se desea realizar una selecci´on de modelo del alineamiento dado. Al igual suceder´a con el resto. Siguiendo con la explicaci´on, en dicha figura puede verse que como entrada ´unicamente es necesario proporcionar el alineamiento deseado, y se obtendr´an dos salidas: los valores de la evaluaci´on de todos los modelos para 10 3.2. DISE˜ NO el alineamiento proporcionado como entrada y el ´arbol filogen´etico obtenido mediante consenso. A continuaci´on se va a analizar las operaciones internas que se realizar´an dentro de este primer m´odulo. Como se puede ver, todos los modelos pueden realizarse de forma paralela, ya que ´unicamente necesitan como entrada el mismo fichero, pero no tienen c´alculos dependientes entre s´ı. Adem´as, la generaci´on de las muestras tampoco requiere ning´un elemento que exija la finalizaci´on de los modelos, por lo que tambi´en puede ser ejecutada de forma paralela. Una vez finalizada esta primera etapa, ser´a necesario recopilar la informaci´on de cada modelo para as´ı poder seleccionar el mejor, por lo que ser´a necesario esperar a todos y cada uno de ellos. Dado adem´as que lo siguiente es probar el modelo seleccionado sobre las muestras, tambi´en ser´a necesario esperar a que finalice la tarea de generaci´on de las mismas. Una vez se tiene todo, se pasar´a a la evaluaci´on del modelo en las muestras. Como resultado de la evaluaci´on, Phyml genera un fichero con el ´arbol filogen´etico para cada muestra bajo ese modelo, por lo que solo resta, una vez obtenidos todos los ´arboles, aplicar el m´etodo de consenso para obtener el ´arbol filogen´etico resultante. La aplicaci´on de ´arbol de consenso frente a otras posibles metodolog´ıas se justifica por la necesidad de agrupar los ´arboles de muestra obtenidos en uno solo, pudiendo medir su fiabilidad. Este m´etodo es aplicable debido a que todos los ´arboles a agrupar poseen el mismo conjunto de secuencias u hojas y, de entra las opciones, este m´etodo ofrece las caracter´ısticas buscadas con una complejidad m´ınima. Figura 3.2: Segundo componente del sistema. Realiza la divisi´on de las secuencias del alineamiento por columnas, aplica la selecci´on de modelos a cada alineamiento resultante, y calcula finalmente el ´arbol de consenso para el conjunto de resultados. En la figura 3.2 se puede ver la segunda caja negra del sistema. Como se puede apreciar, el rect´angulo con bordes redondeados con nombre Selecci´on de Modelo hace referencia al primer m´odulo, ya comentado. Por tanto, este m´odulo no solo permite su extracci´on del sistema para funcionar de manera 11 3.2. DISE˜ NO independiente, si no que se podr´ıa extraer el m´odulo de selecci´on de modelos e introducir otro que requiriese las mismas entradas y generase las mismas salidas, en busca de otro tipo de resultados. Centr´andonos en el contenido de este paquete, ser´a necesario proporcionar el alineamiento deseado as´ı como los puntos de corte, correspondientes a posiciones de amino´acidos de las secuencias. Dado que el alineamiento se puede considerar una matriz, estos puntos representar´ıan grupos de columnas que permanecer´an unidos, lo que, si se dan los puntos de corte adecuados, supondr´a una divisi´on de las secuencias en genes o grupos de genes, seg´un los intereses del usuario final. Como resultado de nuevo se obtendr´a el ´arbol de consenso para el alineamiento completo. Adentr´andonos en la estructura de la segunda caja, podemos ver que inicialmente ser´a necesario realizar los cortes indicados por el usuario, generando los distintos ficheros con alineamientos con las mismas secuencias, pero con un menor n´umero de amino´acidos. Una vez se ha finalizado la selecci´on del modelo para todos los alineamientos, se aplicar´a el m´etodo de consenso para obtener el ´arbol filogen´etico del alineamiento inicial. De nuevo puede observarse que la selecci´on de modelo para cada divisi´on es independiente, lo que permitir´a su paralelizaci´on. El uso del m´etodo de ´arbol de consenso se basa en las mismas ideas comentadas para el caso anterior. Figura 3.3: Tercera y ´ultima componente del sistema. Realiza la divisi´on de las secuencias del alineamiento por filas, aplica el tratamiento por columnas a cada alineamiento resultante, y obtiene finalmente el ´arbol de consenso para el conjunto de resultados. En la figura 3.3 se pueden destacar las mismas caracter´ısticas que en la componente anterior, solo que en este caso el rect´angulo de esquinas redondeadas con nombre Divisi´on en columnas se refiere a la segunda caja. Al igual que suced´ıa antes, este m´odulo interior puede ser substituido por otro o, por ejemplo, quiz´a resultase interesante eliminar el m´odulo dos e incluir directamente en este punto el primer m´odulo. Aunque esta idea y otras semejantes quedan fuera de los objetivos y prop´ositos de este proyecto. 12 3.3. MARCO TECNOL´ OGICO En cuanto a los par´ametros de entrada y salida de este componente, es necesario proveer de un alineamiento a tratar, como en los casos anteriores, adem´as de un ´arbol base para la construcci´on del super´arbol, en caso de que la metodolog´ıa para realizar este paso as´ı lo requiera. Como salida se obtendr´a el ´arbol filogen´etico resultante de aplicar el m´etodo de super´arbol a los ´arboles parciales obtenidos del m´odulo dos. Internamente este m´odulo se encarga de dividir en grupos de secuencias, disminuyendo as´ı la cantidad de secuencias en los alineamientos resultantes. Si la divisi´on en grupos se realiza bajo un criterio biol´ogico, seguramente la divisi´on se realice por haplogrupos, debido a su importancia y relevancia en un estudio de estas caracter´ısticas. Una vez obtenidos los distintos alineamientos se utilizar´an como entrada para el m´odulo dos. De nuevo, gracias a la independencia de este proceso, se permite la paralelizaci´on de estas tareas. Finalmente, una vez obtenidos todos los ´arboles filogen´eticos resultantes, se obtendr´a el super´arbol final aplicando una metodolog´ıa adecuada para ello. El uso de este tipo de m´etodos en vez del consenso como en los casos anteriores se justifica con el hecho de que cada ´arbol obtenido posee un conjunto de hojas distintas, siendo adem´as, en principio, conjuntos disjuntos. Como ya se ha comentado en la Introducci´on, se ha considerado que esta fase del sistema tiene suficiente relevancia como para ir en una secci´on aparte. 3.3 Marco tecnol´ogico A continuaci´on se va a proceder a explicar las decisiones tomadas respecto al marco tecnol´ogico que tendr´a como consecuencia la justificaci´on y explicaci´on de la implementaci´on realizada. Para que el lector pueda hacerse una idea de las necesidades del sistema, se van a realizar a continuaci´on una serie de c´alculos de lo que supone en coste, tanto del n´umero de tareas independientes como temporal, la ejecuci´on del sistema dise˜nado. Imaginemos, en primer lugar, que se va a trabajar con los 88 modelos que incluye la aplicaci´on jModelTest en su versi´on 0.1. A continuaci´on introducimos como entrada un alineamiento de 100 secuencias de ADNmt, donde el n´umero de amino´acidos de las secuencias es poco relevante, debido a que tiene un efecto m´ınimo en el coste temporal y no afecta al n´umero de tareas del sistema (tampoco lo hace el n´umero de secuencias). En el ap´endice C se adjuntan detalles de costes temporales de los distintos puntos del sistema respecto al n´umero de secuencias y de amino´acidos de los alineamientos. Haciendo una divisi´on sencilla tanto por filas como por columnas, por ejemplo, realizando 2 grupos en cada fase, se tiene que en el momento de la evaluaci´on de modelos de evoluci´on se podr´ıan ejecutar 2 x 2 x 89 = 356 tareas a la vez. Si suponemos que cada alineamiento formado tras la primera fase contiene aproximadamente la mitad de las secuencias (50), el coste temporal medio de evaluar cada modelo ser´ıa de aproximadamente 13 3.3. MARCO TECNOL´ OGICO un minuto, lo que hace que, de ejecutarse todas las tareas de forma secuencial, tardar´ıa 6 horas en completarse la evaluaci´on de todos los modelos. Y luego faltar´ıa la fase de la evaluaci´on de los muestreos, que si suponemos que se realizan 10 muestreos a partir del alineamiento inicial, esta nueva fase tendr´ıa 2 x 2 x 10 = 40 tareas, que a 1 minuto por cada una de ellas, supondr´ıa un incremento de 40 minutos. Es decir, redondeando, casi 7 horas en realizar el estudio completo del alineamiento inicial. Hay que tener en cuenta que el coste temporal de esta ´ultima fase es dif´ıcil de predecir debido a que depender´a del modelo seleccionado en la fase de evaluaci´on, y el rango de tiempos, como se ha podido ver en el ap´endice C, es muy amplio. Ahora se va a mostrar qu´e sucede cuando estos valores toman dimensiones reales. El objetivo principal de este proyecto es trabajar con grandes cantidades de datos, por lo que la prueba principal, que se detalla en el apartado Resultados, ten´ıa como entrada un alineamiento con 4925 secuencias de 16707 nucle´otidos (la longitud completa del ADNmt), y se realizaba una primera divisi´on en los 26 haplogrupos actualmente reconocidos y en la segunda fase la divisi´on era en los 38 genes identificados en las secuencias de ADNmt. El n´umero de modelos ha sido el mismo que en el ejemplo anterior, aunque cabe la posibilidad de que sea ampliado en un futuro, si apareciesen nuevos modelos v´alidos. As´ı pues, en la fase de evaluaci´on de los modelos evolutivos tendremos 26 x 38 x 89 = 87932 tareas simult´aneamente, lo que, a unos 2 minutos de media por evaluaci´on, supone aproximadamente 122 d´ıas un tratamiento secuencial de esta fase. Adem´as, como se explicar´a m´as adelante en este mismo apartado, es necesario un n´umero de muestras entre 100 y 1000 para que los resultados puedan considerarse v´alidos desde un punto de vista estad´ıstico, por lo que, tomando el n´umero menos de este rango, se tendr´an 98800 tareas en la fase de evaluaci´on de las muestras. Suponiendo el mismo coste temporal promedio por cada una de ellas, secuencialmente tardar´ıa 137 d´ıas en completarse. As´ı pues, el sistema completo, tratado de forma secuencial, tardar´ıa 259 d´ıas en completarse (sin tener en cuenta el coste de los puntos intermedios, que en algunos casos puede resultar no despreciable). El lector puede hacerse una idea ahora de por qu´e la paralelizaci´on es tan importante a la hora de poder llevar a cabo una implementaci´on viable y, sobre todo, ´util del sistema. Se ha llevado a cabo un estudio sobre el hardware o equipos que se podr´ıan utilizar para llevar a cabo la implementaci´on del sistema. Debido a los requisitos de paralelizaci´on, ahora ya innegables, se evaluaron tres posibles opciones: procesadores con varios n´ucleos, hardware de alto rendimiento en computaci´on como los Tesla de Nvidia y clusters [4]. Los procesadores de varios n´ucleos (conocidos en ingl´es como multi-core processors) permiten la ejecuci´on de m´ultiples threads o hilos en cada n´ucleo, facilitando as´ı la ejecuci´on muchos procesos simult´aneamente. Aunque en principio el n´umero de hilos no es limitado, actualmente el n´umero de n´ucleos por procesador no es muy elevado, y dado el alto coste computacional que se requiere pa- 14 3.3. MARCO TECNOL´ OGICO ra la evaluaci´on de algunos modelos evolutivos (sobre todo si el n´umero de secuencias a evaluar es elevado) no permiten un gran n´umero de tareas ejecut´andose de forma simult´anea. En cuanto al hardware espec´ıfico para este tipo de sistemas, fue descartado por dos motivos principales: si coste elevado, dado que no se dispon´ıa de acceso a ninguno ya instalado, y la necesidad de hacer una gesti´on muy detallada de las tareas debido a las dependencias, como se ha podido ver en la fase de dise˜no. La elecci´on de usar un cluster fue, aparte de por haber descartado las otras opciones, porque se dispon´ıa de acceso a uno. En concreto, como ya se ha comentado anteriormente, se tuvo acceso a Hermes, un cluster que posee el Instituto de Investigaci´on en Ingenier´ıa de Arag´on y al que se concedi´o acceso para poder trabajar con ´el. Una vez decidido el entorno en el que se iba a trabajar, se vio que en Hermes se encontraba instalado el sistema Condor [3, 8], un software que ofrece un framework para entornos de alta productividad computacional. Debido a la gran cantidad de tareas a ejecutar en el sistema, se ha visto conveniente la utilizaci´on de este entorno para realizar la implementaci´on del mismo. Adem´as, en la versi´on instalada se incluye el meta-scheduler DAGMan (de las siglas en ingl´es Directed Acyclic Graph Manager). Este meta-scheduler de Condor permite manejar las dependencias entre trabajos a un mayor nivel que el propio scheduler de Condor. Adem´as, para indicar dichas dependencias es necesario ´unicamente reflejarlas en un grafo dirigido ac´ıclico, con una traducci´on casi inmediata a nivel de implementaci´on. Los flujos de trabajo descritos en la fase de dise˜no pueden verse como grafos dirigidos ac´ıclicos, donde se muestran todas las tareas y sus dependencias. Por tanto, el hecho de que esta tecnolog´ıa estuviese instalada en Hermes hizo que el trabajo resultase m´as c´omodo y potente, dado que la implementaci´on era b´asicamente traducir el dise˜no realizado. Adem´as, DAGMan posee la propiedad de que tareas en el grafo puedan ser a su vez nuevos grafos, lo que hace que se pueda mantener de forma ´ıntegra las estructuras en caja negra dise˜nadas. Una vez establecido todo el entorno en el que se iba a desarrollar el sistema, era necesario establecer el lenguaje de programaci´on a emplear as´ı como las aplicaciones a utilizar para ciertas partes del dise˜no. Desde un principio se opt´o por seleccionar un lenguaje de script de entre los existentes debido a la flexibilidad que estos ofrecen. El hecho de ser interpretados compensa con creces el incremento en coste temporal en el que incurren, y dada la naturaleza de las tareas a implementar, este incremento se puede marcar de despreciable frente a otras tareas puramente de c´alculo. Las tareas a implementar con el lenguaje seleccionado ser´an b´asicamente interconectoras entre distintas fases del sistema o de mantenimiento y recopilaci´on de la informaci´on que se va generando, por lo que se ha considerado esta decisi´on como adecuada. Adem´as, algunos de los lenguajes que pertenecen a este grupo contienen librer´ıas de alto nivel que facilitan el trabajo con 15 3.4. IMPLEMENTACI´ ON elementos biol´ogicos, lo que facilitaba a´un m´as su implementaci´on, adem´as de que requer´ıa de un menor n´umero de pruebas. El lenguaje seleccionado finalmente ha sido Python debido a una cuesti´on meramente pragm´atica: el tiempo necesario invertir en su aprendizaje era mucho menor para mi debido a que hab´ıa trabajado anteriormente con ´el, y la componente te´orico del proyecto ya era suficientemente grande de por s´ı como para aumentarla de forma innecesaria. Aparte de la utilizaci´on de Phyml para la evaluaci´on de los modelos evolutivos, se encontr´o el paquete software Phylip que conten´ıa aplicaciones para varias necesidades biol´ogicas. En concreto, y para este proyecto, se han usado las aplicaciones seqboot y consense de dicho paquete, en su versi´on 3.69. Consense es una aplicaci´on que, dado un fichero con los ´arboles a los que aplicar este m´etodo, se obtiene el ´arbol de consenso de los mismos. Como se ha comentado en la fase de dise˜no, es necesario que todos los ´arboles posean las mismas hojas para poderlo aplicar correctamente. Seqboot, por su parte, no genera realmente muestreos como tal, sino que utiliza una t´ecnica conocida en ingl´es como bootstrap, que se podr´ıa traducir como automuestreo. La idea es generar muestras de forma estad´ıstica sin tener conocimiento del tipo de distribuci´on que han de seguir, permitiendo aun as´ı hacer un estudio estad´ıstico admisible. Si la evaluaci´on de los modelos resulta adecuada para el 95 % de los casos, el modelo seleccionado se considerar´a valido. Seg´un nos indica la documentaci´on de Phylip, para que el sistema tenga validez estad´ıstica se aconseja realizar entre 100 y 1000 bootstraps. 3.4 Implementaci´on Como se ha comentado en el apartado anterior, las tareas que era necesario implementar han sido desarrolladas bajo el lenguaje de programaci´on Python. Gracias a la modularidad que Python ofrece, ha sido posible crear los ficheros de cada parte del sistema bajo la misma idea de caja negra que se lleva mencionando a lo largo de esta secci´on. Muchos de los ficheros creados tienen como objetivo la generaci´on de todos los ficheros DAGMan y Condor necesarios para el correcto funcionamiento de cada una de las cajas. Otros, los menos, han sido dise˜nados como scripts pre y post a tareas Condor o como tareas de generaci´on o nexo de resultados necesarios para proseguir el trabajo del sistema. En la figura 3.4, figura 3.5 y figura 3.6 se encuentran los esquemas a nivel de implementaci´on de los dise˜nos desarrollados anteriormente. La idea de la primera caja es ofrecer b´asicamente 3 funcionalidades al usuario: un diccionario con todos los modelos que se desean probar (que puede ser modificado para comprobar menos modelos u otros distintos no 16 3.4. IMPLEMENTACI´ ON Figura 3.4: Primer componente del sistema. Realiza la selecci´on de modelo evolutivo, generaci´on y re-evaluaci´on de los muestreos y aplicaci´on del m´etodo de consenso para unificar los ´arboles filogen´eticos resultantes. Figura 3.5: Segundo componente del sistema. Realiza la divisi´on de las secuencias del alineamiento por columnas, aplica la selecci´on de modelos a cada alineamiento resultante, y calcula finalmente el ´arbol de consenso para el conjunto de resultados. contemplados), una funci´on que genera todos los ficheros Condor y DAGMan necesarios para el buen funcionamiento del primer m´odulo y la posibilidad de la ejecuci´on a modo de script del fichero principal de forma que adem´as de generar todos los ficheros lance la ejecuci´on del fichero DAGMan principal. Para las otras dos cajas la funcionalidad es semejante, solo que eliminando, como es obvio, el diccionario con los modelos evolutivos que se comprobar´an (de nuevo se puede ver como se ha mantenido en todo momento la estructura de caja negra en cada m´odulo). En la generaci´on de ficheros se crea un directorio aparte con un identificador del m´odulo que permite as´ı no mezclar los ficheros fuente del m´odulo con los creados, tanto antes de ejecutar el sistema como conforme se van generando ficheros durante su ejecuci´on, 17 3.4. IMPLEMENTACI´ ON Figura 3.6: Tercera y ´ultima componente del sistema. Realiza la divisi´on de las secuencias del alineamiento por filas, aplica el tratamiento por columnas a cada alineamiento resultante, y obtiene finalmente el ´arbol de consenso para el conjunto de resultados. temporales y finales. Se ha a˜nadido a todo el sistema una opci´on de debugging que implica que todos los ficheros temporales que se generen no sean borrados, permitiendo as´ı que se pueda verificar la trazabilidad de los resultados que se han ido obteniendo. Aunque el objetivo de esta funcionalidad era ´unicamente para verificar los resultados en la fase de pruebas, se ha cre´ıdo conveniente dejarla de cara al usuario, no con el objetivo de verificaci´on de los resultados, si no por si requiere tambi´en la informaci´on almacenada en los resultados parciales para su investigaci´on o trabajo. Adentr´andonos un poco m´as en la implementaci´on, se puede observar que se ha tenido especial cuidado a la hora de generar el nombre de todas las tareas y ficheros, debido a la necesidad de que ´estos sean ´unicos dentro del proceso de ejecuci´on de Condor. Todos los ficheros tienen como prefijo el nombre del fichero donde se encuentra el alineamiento con el que se va a trabajar, seguido de un c´odigo alfanum´erico, que indica el tipo de fichero y el n´umero (´unico) del mismo. As´ı, en todo momento puede verse el tipo de fichero y el n´umero asegura su singularidad. Por ejemplo, el fichero con nombre alignment l002.phy indica que se trata de un link soft al fichero alignment.phy, que es el fichero con el alineamiento proporcionado como entrada. En el apartado Manual de usuario se encuentra el significado de todos los prefijos y extensiones de los ficheros que se podr´an encontrar durante la ejecuci´on del sistema. Este hecho ha requerido que el c´odigo fuente de las aplicaciones seqboot y consense del paquete Phylip haya sido modificado ligeramente para que los ficheros generados contengan ya su prefijo apropiado. Con esta peque˜na modificaci´on se permite que el sistema pueda ser lanzado dos o m´as veces, siempre y cuando el fichero de alineamiento tenga un nombre distinto para cada ejecuci´on. Otro de los grandes problemas a los que ha sido necesario enfrentarse para poder desarrollar el sistema es el problema de la concurrencia. Aunque 18 4.3. SUPER´ ARBOL DE CORTE M´ INIMO Para facilitar el trabajo los nodos son numerados mediante un identificador ´unico de forma autom´atica en cada ´arbol. Se ha incluido la implementaci´on de los TADs descritos en el ap´endice F. 4.3.3. Pruebas realizadas Se han realizado varias pruebas con distinto nivel de solapamiento entre ´arboles para comprobar el comportamiento del m´etodo, observando que los resultados obtenidos fuesen correctos. Debido a que distintos m´etodos de super´arboles no tienen por qu´e dar el mismo resultado para las mismas entradas, ha sido necesario realizar pruebas con datos suficientemente peque˜nos como para poder aplicar el algoritmo de forma manual. En el ap´endice G se incluyen los ´arboles utilizados para todas las pruebas realizadas as´ı como los resultados obtenidos. La primera prueba consisti´o en pasar como par´ametros de entrada tres ´arboles con una estructura similar, aunque con ligeras variaciones, y con el mismo conjunto de hojas. La segunda ten´ıa de nuevo tres ´arboles de entrada, y al igual que pasaba con la prueba anterior, todos ten´ıan una estructura similar aunque con variaciones en algunas ramas. Los conjuntos de hojas ten´ıan un solapamiento muy alto, aunque todos ten´ıan alguna hoja distinta a las de los dem´as. La tercera prueba probaba el comportamiento del m´etodo en caso de que los ´arboles poseyeran la misma estructura pero no existiese solapamiento alguno entre las hojas. La cuarta y ´ultima prueba consisti´o en probar qu´e suced´ıa si se pasaba como par´ametros de entrada dos ´arboles completamente diferentes en su estructura y con sin solapamiento entre sus hojas. Una vez completadas todas las pruebas y comprobado que el resultado era correcto, se dio por terminada la implementaci´on de este m´etodo. 25 5 Conclusiones 5.1 Trabajo realizado El trabajo realizado supone una nueva aportaci´on a la filogenia computacional extensiva, con ´enfasis en el caso mitocondrial humano. Se han cumplido de forma satisfactoria todos los objetivos que se plantearon inicialmente y otros que han ido surgiendo a lo largo del desarrollo del trabajo. Como es l´ogico, en todo proyecto surgen dificultades y problemas que han de solucionarse. Y este caso no ha sido una excepci´on. Uno de los primeros problemas al que hubo que enfrentarse fue el comprender el algoritmo de construcci´on de super´arboles de corte m´ınimo y su funcionamiento. El algoritmo no estaba desarrollado en lenguaje matem´atico, por lo que el lenguaje natural en algunos momentos permit´ıa dobles interpretaciones, o no profundizaba lo suficiente en algunos conceptos, estructuras e ideas, lo que hizo necesario buscar bibliograf´ıa relacionada con este m´etodo para conseguir comprenderlo en su totalidad. Una vez superado este problema, surgi´o el siguiente. Fue necesario conseguir desarrollar estructuras de datos ´optimas para el m´etodo en cuesti´on. El sentido de ´optimas no se refiere tanto al ahorro de memoria como al intento de alcanzar el mejor coste computacional posible de las operaciones que se requer´ıan. Dentro de todos los problemas relacionados con la creaci´on del sistema, cabe destacar los problemas relacionados con el trabajo con el cluster Hermes. Con problemas no pretendo referirme en ningun momento a criticas sobre su montaje o la labor de gesti´on de los administradores. Hermes nunca hab´ıa sido probado con sistemas organizados mediante DAGMans, y mucho menos mediante DAGMans anidados, por lo que fue necesaria una colaboraci´on conjunta con los administradores para solucionar problemas como cancelaci´on de tareas o errores de ejecuci´on debido a la carga que el sistema generaba en el cluster. Aunque se pens´o inicialmente en cambiar el dise˜no intentando eliminar la anidaci´on (lo que habr´ıa sido desastroso pues toda la metodolog´ıa de flujos de trabajo resultar´ıa inservible) se encontr´o al final la soluci´on calibrando par´ametros adicionales para gesti´on de trabajos del scheduler de Condor. 26 5.2. CON VISTAS AL FUTURO 5.2 Con vistas al futuro La magnitud del sistema que se deseaba desarrollar en ´ultimo t´ermino estaba totalmente fuera de las limitaciones de un proyecto fin de carrera, por lo que, aunque se han cumplido y con creces todos los objetivos que se plantearon al inicio del mismo, ha quedado a´un mucho trabajo por hacer. Como mejoras a lo que ya se encuentra incluido dentro del sistema ser´a necesario mejorar el software Phyml, pues se ha detectado en las pruebas que no contempla los casos triviales (alineamientos con una o dos secuencias) lo que provoca que los ficheros de salida no tengan la estructura esperada y se produzca un fallo en la ejecuci´on del sistema de dificil captura y soluci´on ad-hoc. Fue realmente una sorpresa encontrar un software que no contemplase casos triviales tan sencillos de tratar. Otra mejora a realizar tiene que ver con la divisi´on en grupos o haplogrupos. Es obvio que se desea crear una herramienta robusta adem´as de potente, por lo que es necesario contemplar la posibilidad de que un grupo no tuviese ninguna correspondencia con las secuencias del alineamiento, dej´andolo vac´ıo. Aparentemente esto puede parecer un problema insignificante, pero no hemos de olvidar que esta informaci´on s´olo se tiene cuando el sistema ya se est´a ejecutando y los ficheros ya han sido creados, por lo que no se puede revertir la configuraci´on preestablecida. Como partes a a˜nadir, el deseo final es que el sistema disponga de todos los elementos necesarios para que un usuario, simplemente indicando el tipo de secuencias que desea y la cantidad de las mismas, se recoja dicha informaci´on de GenBank u otra base de datos de la misma categor´ıa, realice un alineamiento de las secuencias recogidas y finalmente realice un estudio filogen´etico de las mismas. Se ha pretendido dejar claro (y espero que se haya conseguido) a lo largo de la memoria que el trabajo realizado en este proyecto tiene muchos aspectos de innovaci´on, lo que ha abierto nuevos caminos en la investigaci´on bioinform´atica. Actualmente estamos finalizando un art´ıculo con vistas a su pronta publicaci´on y ya hay otros en el tintero esperando a cobrar forma. 5.3 De lo profesional a lo personal Profesionalmente, aunque quede mal que yo lo diga, he de hacer una valoraci´on muy positiva del trabajo que he realizado. No me refiero con esto a haber logrado cumplir todos los objetivos del proyecto, que tambi´en me llena de satisfacci´on, sino al haber conseguido comprender e implementar el algoritmo de construcci´on de super´arboles de corte m´ınimo (que me supuso m´as de un quebradero de cabeza) y el desarrollar un sistema realmente funcional y eficiente que pueda servir como herramienta de trabajo a otros investigadores. Supongo que lo que m´as me ha llenado, profesionalmente hablando, es el conseguir superar los retos y aprender mucho, tanto de biolog´ıa como de 27 5.3. DE LO PROFESIONAL A LO PERSONAL inform´atica, por el camino. Por otro lado, parte de este proyecto ha estado pr´oximo a lo que ser´ıa un trabajo de investigaci´on en temas de filogen´etica, como la fase de formaci´on y b´usqueda de bibliograf´ıa o la redacci´on de parte de un art´ıculo, lo que ha hecho que me entusiasme por este trabajo y desee continuar mi formaci´on cursando el m´aster del departamento y realizando una tesis doctoral. Desde que estaba en tercero de carrera he querido adentrarme en estos temas, y he de agradecer a mis dos directores el haberme brindado la oportunidad de poder realizar este proyecto, que tanto me ha aportado, profesional y personalmente. Entrando es aspectos m´as personales, me he sentido muy c´omodo y acogido en el grupo de bioinform´atica, pues me han hecho sentir como uno m´as de ellos, permiti´endome colaborar de forma activa en las reuniones y tratando mis sugerencias e ideas con el mismo valor que las de los dem´as integrantes del grupo. 28 Bibliograf´ıa [1] http://atgc.lirmm.fr/phyml/. Web site del software Phyml. [2] http://evolution.genetics.washington.edu/phylip.html. Web site del paquete Phylip. [3] http://www.cs.wisc.edu/condor/manual/. Web site del manual de Condor. [4] Ilkay Altintas, Chad Berkley, Efrat Jaeger, Matthew Jones, Bertran Lud¨ascher, and Steve Mock. Kepler: an extensible system for design and execution of scientific workflows. In Proceedings of the 16th International Conference on Scientific and Statistical Database Management, 2004. [5] Roberto Blanco. Definici´on y prototipo de herramienta de an´alisis filogen´etico para el ADN mitocondrial humano. Master’s thesis, Centro Polit´ecnico Superior, Universidad de Zaragoza, 2008. [6] Roberto Blanco and Elvira Mayordomo. ZARAMIT: a system for the evolutionary study of human mitochondrial DNA. In IWANN 2009, Part II, volume 5518 of Lecture Notes in Computer Science, pages 1139– 1142, 2009. [7] Peter Couvares, Tevfik Kosar, Alain Roy, Jeff Weber, and Kent Wenger. Workflows for e-Science, chapter Workflow management in Condor, pages 357–375. Springer, 2006. [8] Ewa Deelman, James Blythe, Yolanda Gil, Carl Kesselman, Gaurang Mehta, Karan Vahi, Kent Blackburn, Albert Lazzarini, Adam Arbree, Richard Cavanaugh, and Scott Koranda. Mapping abstract complex workflows onto grid environments. Journal of Grid Computing, V1(1):25–39, 2003. [9] Diimitrios Georgakopoulos, Mark Hornick, and Amit Sheth. An overview of workflow management: from process modeling to workflow automation infrastructure. Distributed and Parallel Databases, 3(2):119– 153, 1995. [10] Corinna Herrnstadt, Joanna L. Elson, Eoin Fahy, Gwen Preston, Douglass M. Turnbull, Christen Anderson, Soumitra S. Ghosh, Jerrold M. Olefsky, M. Flint Beal, Robert E. Davis, and Neil Howell. Reducedmedian-network analysis of complete mitochondrial DNA coding-region sequences for the major African, Asian, and European haplogroups. American Journal of Human Genetics, 70(5):1152–1171, 2002. 29 BIBLIOGRAF´ IA [11] Bertram Lud¨ascher, Ilkay Altintas, Chad Berkley, Dan Higgins, Efrat Jaeger, Matthew Jones, Edward A. Lee, Jing Tao, and Yang Zhao. Scientific workflow management and the Kepler system. Concurrency and Computation: Practice and Experience, 18(10):1039–1065, 2006. [12] Wayne P. Maddison. Gene trees in species trees. Systems Biology, 46(3):523–536, 1997. [13] Timothy M. McPhillips. Pipelined scientific workflows for inferring evolutionary relationships. Technical report, National Diversity Discovery Project, 2005. [14] Roderic D. M. Page. Modified mincut supertrees. In Proceedings of the Second International Workshop on Algorithms in Bioinformatics, volume 2452 of Lecture Notes in Computer Science, pages 537–552, 2002. [15] Andrzej Polanski and Marek Kimmel. Bioinformatics. Springer, 2007. [16] David Posada. jModelTest: phylogenetic model averaging. Molecular Biology and Evolution, 25(7):1253–1256, 2008. [17] David Posada and Keith A. Crandall. Selecting models of nucleotide substitution: An application to human immunodeficiency virus 1 (hiv- 1). Molecular Biology and Evolution, 18:897–906, 2001. [18] David Posada and Keith A. Crandall. Selecting the best-fit model of nucleotide substitution. Systematic Biology, 50(4):580–601, 2001. [19] Martin B. Richards, Vincent A. Macaulay, Hans-J¨urgen Bandelt, and Bryan C. Sykes. Phylogeography of mitochondrial DNA in western Europe. Annals of Human Genetics, 62(3):241–260, 1998. [20] Eduardo Ruiz-Pesini, Dan Mishmar, Martin Brandon, Vincent Procaccio, and Douglas C. Wallace. Effects of purifying and adaptive selection on regional variation in human mtdna. Science, 303:223–226, 2004. [21] Michael J. Sanderson, Andy Purvis, and Chris Henze. Phylogenetic supertrees: assembling the trees of life. Trends in Ecology and Evolution, 13(3):105–109, 1998. [22] Charles Semple and Mike Steel. A supertree method for rooted trees. Discrete Applied Mathematics, 105:147–158, 2000. [23] Mike Steel. The complexity of reconstructing trees from qualitative characters and subtrees. Journal of Classification, 9(1):91–116, 1992. 30 BIBLIOGRAF´ IA [24] Mike Steel, Andreas W. M. Dress, and Sebastian B¨ocker. Simple but fundamental limitations on supertree and consensus tree methods. Systematic Biology, 49(2):363–368, 2000. [25] Antonio Torroni, Alessandro Achilli, Vincent Macaulay, Martin Richards, and Hans-J¨urgen Bandelt. Harvesting the fruit of the human mtDNA tree. Trends in Genetics, 22(6):339–345, 2006. [26] Iv´an D. Traveso. Desarrollo e implementaci´on de un entorno de an´alisis filogen´etico basado en la clasificaci´on de haplogrupos mitocondriales y m´etodos de super´arboles. Master’s thesis, Centro Polit´ecnico Superior, Universidad de Zaragoza, 2009. [27] Pablo Urcola. Algoritmos de compresi´on para secuencias biol´ogicas y su aplicaci´on en ´arboles filog´enicos construidos a partir de adn mitocondrial. Master’s thesis, Universidad de Zaragoza, 2006. [28] W. M. P. van der Aalst. The application of Petri nets to workflow management. The Journal of Circuits, Systems and Computers, 8(1):21–66, 1998. 31