View
222
Download
0
Category
Preview:
Citation preview
Unidad 6: Arboles Filogeneticos
Unidad 6: Arboles Filogeneticos
BT7412, CC5702 – BioinformaticaDiego Arroyuelo
2 de noviembre de 2010
Unidad 6: Arboles Filogeneticos
Temario (Introduction to Computational Molecular Biology – Setubal y
Meidanis – Capıtulo 6)
1. Introduccion
2. El problema de la filogenia perfecta
3. Caso de caracteres binarios
4. Caso de dos caracteres
5. Parsimonia y compatiblidad en filogenias
6. Algoritmos para matrices de distancia
7. Acuerdo entre filogenias
Unidad 6: Arboles Filogeneticos
Introduccion
Introduccion
I Todas las especies de organismos vivos terrestres llevan a caboun proceso de transformacin a lo largo de los anos
I Ese proceso se conoce con el nombre de evolucion
I Uno de los problemas centrales de la biologıa es explicar lahistoria evolucionaria de las especies actuales
I En particular, como las especies se relacionan con otras enterminos de sus ancestros comunes
I Por ejemplo, como las ballenas se relacionan con algunosmamıferos ungulados, como los hipopotamos, vacas, ciervos,etc.
Unidad 6: Arboles Filogeneticos
Introduccion
Arboles filogeneticos
I Esto se hace usando arboles: las hojas representan las especies
actuales, los nodos internos representan los ancestros hipoteticos
Unidad 6: Arboles Filogeneticos
Introduccion
Arboles filogeneticos
I El principal problema es que no hay informacion suficiente delos ancestros distantes de las especies actuales
I Y si la hubiese, no podrıamos estar 100 % seguros que un fosilen particular corresponde a una especie que es ancestro de dosespecies actuales
I Por lo tanto se infiere la historia evolucionaria de losorganismos actuales y se recrea su arbol filogenetico
I El arbol resultante no es necesariamente la verdad, es solo unahipotesis
I Usaremos el termino objeto para las unidades taxonomicassobre las que queremos reconstruir una filogenia
Unidad 6: Arboles Filogeneticos
Introduccion
Arboles filogeneticos
I Usualmente las filogenias se reconstruyen usandocomparaciones entre objetos actuales
I Podemos clasificar los datos de entrada para la reconstruccionde filogenias en dos categorıas principales
1. Caracteres discretos: numero de dedos, presencia o ausencia deun sitio de restriccion molecular, etc. Cada caracter tiene unnumero finito de estados. La entrada viene dada por unamatrız de estados de caracteres
2. Datos numericos comparativos: distancia entre objetos. Laentrada viene dada por una matrız de distancias
I Estudiaremos estos metodos en el curso
Unidad 6: Arboles Filogeneticos
El problema de la filogenia perfecta
El problema de la filogenia perfecta
I Asumiremos que los caracteres se heredan de formaindependiente del resto
I Asumiremos ademas que todos los estados observados de uncaracter dado deberıan haber evolucionado de un “estadooriginal” del ancestro comun mas cercano de los objetos deestudio
I Los caracteres que obedecen a esto se conocen comohomologos
Unidad 6: Arboles Filogeneticos
El problema de la filogenia perfecta
El problema de la filogenia perfecta
I Definimos la matrız M de estados de caracteres con n filas(objetos) y m columnas (caracteres)
I Mij denota el estado que el objeto i tiene para el caracter j
I Puede haber a lo sumo r estados para cada caracter, loscuales se denotan con numero enteros no negativos
I Una fila dada de la matrız se conoce como el vector de estadode un objeto
Unidad 6: Arboles Filogeneticos
El problema de la filogenia perfecta
El problema de la filogenia perfecta
I Ejemplo de matrız M de estados de caracteres:
Unidad 6: Arboles Filogeneticos
El problema de la filogenia perfecta
El problema de la filogenia perfecta
I Asumiremos tambien que objetos que comparten un mismoestado para un caracter dado son geneticamente mas cercanosque objetos que no lo comparten
I Sin embargo, existe la posibilidad de que dos objetoscompartan un estado pero no son geneticamente cercanos:
I por ejemplo, la presencia de alas en los murcielagos y aves
I Dicho fenomeno se conoce como convergencia o evolucionparalela
I Estos son casos muy raros en la naturaleza, asumiremos (parasimplificar los algoritmos) que no sucede, o sucede raramente
Unidad 6: Arboles Filogeneticos
El problema de la filogenia perfecta
El problema de la filogenia perfecta
I Otra dificultad tiene que ver con los diferentes estados de unmismo caracter
I Por ejemplo, asumamos que los objetos A y B evolucionaronde un ancestro comun X
I Asumiendo que A tiene c1 = 1 y B tiene c1 = 0
I ¿Que valor se le asigna al caracter c1 de X ?
I Si c1 = 0, decimos que 0 es el estado ancestral y 1 el estadoderivado
Unidad 6: Arboles Filogeneticos
El problema de la filogenia perfecta
El problema de la filogenia perfecta
I Asumamos que hemos decidido que 0 es el estado ancestral y1 el estado derivado
I Supongamos que los objetos C y D tienen un ancestro comunY 6= X
I Ademas, que el estado de c1 para Y es 1
I En este caso el objeto D representa una inversion para elcaracter c1
I Esto se puede interpretar como ganancia o perdida de alguncaracter
I Estos son tambien casos muy raros en la naturaleza,asumiremos que no suceden, o suceden raramente
Unidad 6: Arboles Filogeneticos
El problema de la filogenia perfecta
El problema de la filogenia perfecta
I Si queremos evitar los eventos de convergencia e inversiones,se requiere que el arbol T deseado cumpla con la siguientepropiedad:
Para casa estado s de cada caracter c, el conjunto detodos los nodos u (ya sean interiores u hojas) para elcual el estado de c es s deben formar un subarbol
I Una filogenia con esta propiedad se conoce como filogeniaperfecta
I Cuando un conjunto de objetos definidos por una matrız deestados de caracteres admite una filogenia perfecta, decimosque esos caracteres son compatibles
Unidad 6: Arboles Filogeneticos
El problema de la filogenia perfecta
El problema de la filogenia perfecta
I El siguiente es el problema central en la reconstruccion defilogenias basadas en matrices de estados de caracteres
Problema: Filogenia perfectaInstancia: Un conjunto O con n objetos, un conjunto C dem caracteres, cada uno con a lo sumo r estados (n,m,r sonenteros positivos)Pregunta: ¿Hay una filogenia perfecta para O?
Unidad 6: Arboles Filogeneticos
El problema de la filogenia perfecta
El problema de la filogenia perfecta
I Para la siguiente matrız existe una filogenia perfecta
Unidad 6: Arboles Filogeneticos
El problema de la filogenia perfecta
El problema de la filogenia perfecta
I ¿Existen algoritmos eficientes para encontrar filogeniasperfectas?
I ¿Cuantos arboles no enraizados diferentes existen con nnodos? (recordar que los objetos deben ser las hojas)
I Para 3 objetos hay un unico arbol
I Para 4 objetos hay 3 arboles
I Se puede probar que hay∏n
i=3(2i − 5) arboles distintos, locual crece mas rapido que n!
Construir todos los arboles tratando de encontrar alguno quesea una filogenia perfecta no es una alternativa eficiente
Unidad 6: Arboles Filogeneticos
Caso de caracteres binarios
El caso de caracteres binarios
I El caso de caracteres binarios puede ser resueltoeficientemente:
1. Caracteres ordenados: sabemos cual estado es ancestro y cuales derivado
2. Caracteres desordenados: no se especifıca el orden entre loscaracteres
I En la proxima clase veremos un algoritmo de tiempopolinomial que trabaja en dos fases (en la primera decide siexiste una filogenia perfecta, y en la segunda construye unaposible filogenia perfecta)
Recommended