View
225
Download
0
Category
Preview:
Citation preview
VFilogenia
VFilogenia
Andrés MoreiraDepartamento de Informática UTFSM
Construyendo árbolesConstruyendo árbolesConstruyendo árbolesConstruyendo árboles
El objetivo del análisis filogenético es construir un árbol que refleje las relaciones evolutivas (a partir de un origen que se supone común) de un conjunto de objetos sobre los que se tienen datos.
Los objetos pueden ser:
•Las secuencias de un set de genes homólogos•Un set de genomas completos de bacterias•Una tabla de características observadas en fósiles de dinosaurios•Un set de idiomas, representados por vocablos•...etc.
Construyendo árbolesConstruyendo árbolesConstruyendo árbolesConstruyendo árboles
Un posible árbol de los idiomas indo-europeos.
El estudio de filogenia de idiomas es anterior a Darwin. De hecho, fue una inspiración para el pensamiento evolucionista.
Post-Darwin, se aplicó la lógica de esos estudios a la clasificación de Lineo (en la que se reconoció una aproximación a la filogenia).
Construyendo árbolesConstruyendo árbolesConstruyendo árbolesConstruyendo árboles
Por suerte hoy en día podemos usar, en la mayoría de los problemas de interés, información genotípica: secuencias de DNA, RNA, o proteínas.
Algunos errores eran casi inevitables, como suponerle un origen común a los vertebrados de sangre caliente.
Construyendo árbolesConstruyendo árbolesConstruyendo árbolesConstruyendo árboles
Algunas gracias de la información genotípica:
•Discreta
•Abundante (muchos bits por objeto)
•La mayoría de las mutaciones son neutralesse acumula variación “gratis”es poco probable la convergencia (similaridad sin homología real)
Construyendo árbolesConstruyendo árbolesConstruyendo árbolesConstruyendo árboles
Lo que hay que construir es un árbol:
•Puede ser con raíz o sin raíz.
•A veces la longitud de las aristas es relevante, y refleja distancia evolutiva.
•Por lo general es binario, aunque puede haber “politomía” por falta de información o para simplificar.
A
B
C
D
E
Construyendo árbolesConstruyendo árbolesConstruyendo árbolesConstruyendo árboles
hojas árboles
3 1
4 3
5 15
6 105
7 945
8 10,395
9 135,135
10 2,027,025
11 34,459,425
12 654,729,075
13 13,749,310,575
14 316,234,143,225
15 7,905,853,580,625
•La # de árboles posibles crece muy rápido.
•Todos los criterios usuales para escoger un árbol dan problema NP-duros...
heurísticas
Construyendo árbolesConstruyendo árbolesConstruyendo árbolesConstruyendo árboles
Existen muchos softwares de filogenia computacional:
Pero hay menos asociación algoritmo-software que en, digamos, MSA. De hecho los principales paquetes ofrecen todas las aproximaciones principales. Así que hablaremos en términos de esas.
Principales aproximacionesPrincipales aproximacionesPrincipales aproximacionesPrincipales aproximaciones
Principales aproximaciones:
•Métodos de distancias: trabajan sólo con una matriz de distancias entre los objetos.
•Máxima parsimonia: se intenta minimizar la cantidad de cambios evolutivos implicados por el árbol.
•Maxima verosimilitud: se incluye algún modelo de evolución, y de acuerdo con él –y los datos– se busca el árbol más probable.
Principales aproximacionesPrincipales aproximacionesPrincipales aproximacionesPrincipales aproximaciones
Según David Mount:
DatosDatosDatosDatos
Para resolver filogenia de especies, la información preferida dependerá del nivel de separación:
•Para comparar primates es útil la mitocondria, porque acumula mutaciones rápido.
•Para resolver las profundidades del árbol de la vida se usa RNA ribosomal, porque cambia lento.
•RNA ribosomal: fuerte conservación debido a estructura 2d, 3d, y a lo esencial de la molécula.
•Nótese que el árbol de los tres dominios es sin raíz ; eso se debe a que no hay outgroup posible.
OutgroupOutgroupOutgroupOutgroup
“Outgroup” : método para ponerle raíz a los árboles:
•Escogemos algo que sea con certeza pariente más lejano de los objetos en estudio, que ellos entre sí.
•No demasiado lejano, para no agregar mucho ruido.
•Una vez hecho el árbol, lo enraizamos en la rama que va hacia el outgroup.Otra forma de enraizar un árbol es
agregar la hipótesis del “reloj molecular”: suponer tasa de mutación constante.
Filogenia y MSAFilogenia y MSAFilogenia y MSAFilogenia y MSA
•La mayoría de los métodos trabajan a partir de un alineamiento múltiple.
•Por lo general se descartan las columnas con gaps.
•Con frecuencia se alterna entre filogenia y alineamiento, usando uno como input del otro.
Métodos de distanciaMétodos de distanciaMétodos de distanciaMétodos de distancia
•Usan una matriz de distancias (por lo general sacada de un alineamiento).
•Pierden datos.
•Reconstruyen la topología, y la longitud de las ramas.
Supuesto: la distancia entre dos hojas es igual a la suma de las longitudes del camino entre ellas.
E
A
B
C
D
_ A B C D EA 0 4 6 10 10B 4 0 4 8 8C 6 4 0 6 6D 10 8 6 0 4E 10 8 6 4 0
Métodos de distancia: supuesto Métodos de distancia: supuesto aditivoaditivo
Métodos de distancia: supuesto Métodos de distancia: supuesto aditivoaditivo
S1 S2 S3 S4
S1 - D12 D13 D14
S2 - D23 D24
S3 - D34
S4 -Distancia observada
S1
S3
S2
S4
a
b
c
d e
Distancia en el árbol
D12 d12 = a + b + cD13 d13 = a + dD14 d14 = a + b + eD23 d23 = d + b + cD24 d24 = c + eD34 d34 = d + b + e
Objetivo:
Métodos de distancia: Métodos de distancia: Neighbour Neighbour JoiningJoining
Métodos de distancia: Métodos de distancia: Neighbour Neighbour JoiningJoining
NJ: El método de distancia más popular. Idea:
Cuando tenemos sólo 3 ramas, se puede resolver:
d(A,B)=a+b d(A,C)=a+c d(B,C)=b+c
a = ½ [ d(A,B) + d(A,C) - d(B,C) ]b = ½ [ d(A,B) - d(A,C) + d(B,C) ]c = ½ [ -d(A,B) +d(A,C) + d(B,C) ]
A
BC
a
b c
A
BC
D
E
a
b c
d
e
.;;
;3/)(
;3/)(
BXAXAB
BEBDBCBX
AEADACAX
dxbdxadba
dddd
dddd
X
•Unimos A y B a un nuevo nodo.•Juntamos en “X” todo lo demás.•Definimos dAX como el promedio de las distancias entre A y los elementos de X.•Ahora aplicamos el caso de tres nodos, a los nodos a, b y X.
x
Métodos de distancia: Métodos de distancia: Neighbour Neighbour JoiningJoining
Métodos de distancia: Métodos de distancia: Neighbour Neighbour JoiningJoining
A
BC
D
E
a
b c
de
Empezamos con una estrella (es el peor caso!), y vamos uniendo.
dAN = a = ½ (dAB+dAX-dBX) dBN = b = ½ (dAB+dBX-dAX)Para las distancias entre el nuevo y el resto, suponemos aditividad y promediamos lo que dan A y B:
dCN = ½(dCA-dAN) + ½(dCB-dBN)...etc
Métodos de distancia: Métodos de distancia: Neighbour Neighbour JoiningJoining
Métodos de distancia: Métodos de distancia: Neighbour Neighbour JoiningJoining
A
BC
D
E
a
b c
d
e
X
x
•Se aplica esa idea repetidamente.•Para escoger cuáles unir, se aplica una estrategia glotona, que escoge los que reduzcan más la suma de las ramas.
Métodos de distanciaMétodos de distanciaMétodos de distanciaMétodos de distancia
Más detalles, y otros métodos de distancia: en ppt full.
Ventajas de los métodos de distancia:
•Son rápidos•Se adaptan bien a ramas de longitudes distintas
Desventajas:
•Pierden información•Dependen del supuesto de la aditividad la forma en que se calcula la distancia es vital
DistanciasDistanciasDistanciasDistancias
Forma trivial de evaluar distancia: nnp d /
n : # de columnas que uso del alineamiento nd : # de columnas en que las dos secuencias son
¿Qué puede fallar con eso?
Puede haber cambios más probables que otros (incorporar información de matrices de sustitución)
Si ha pasado mucho tiempo, algunos sitios van a haber mutado más de una vez.
Se introducen correcciones.La más simple, de Poisson: )1ln( pd
En general la corrección depende un asumir un modelo de evolución de la secuencia (como una matriz PAM).
Es toda una ciencia; no veremos más.
Máxima parsimoniaMáxima parsimoniaMáxima parsimoniaMáxima parsimonia
Máxima parsimonia, o mínima evolución: Busca el árbol, coherente con los datos, que requiere menos eventos evolutivos.
•Es el método más intuitivo, simple y general•Pero: se porta bien con pocos datos (es caro) y cercanos (poca distancia evolutiva).
•Se consideran los “caracteres” de a uno.
•“Caracter”: columna del alineamiento, o rasgo morfológico, o cualquier atributo en realidad.
Máxima parsimoniaMáxima parsimoniaMáxima parsimoniaMáxima parsimonia
•Para un árbol dado (sin raíz) y un caracter dado, evaluamos la cantidad mínima de cambios que sea coherente con ese esquema.
G A
G
C
A
A
A A
G
A
A
A
•Evaluar eso es barato (polinomial).
•Para el conjunto de caracteres disponibles, sumamos los valores, y eso le da un score al árbol.
Máxima parsimoniaMáxima parsimoniaMáxima parsimoniaMáxima parsimonia
G
C
G A
A
A
A
G
A
A
C
A
•Hay posiciones que no permiten discriminar entre árboles, no interesan.
•Para ser informativa, una columna del alineamiento tiene que tener al menos dos letras que estén al menos dos veces.A A G A C T G
A G C C C T GA G A T T T CA G A G T T C * *
Máxima parsimoniaMáxima parsimoniaMáxima parsimoniaMáxima parsimonia
La parte difícil (lo NP-duro!) es encontrar el árbol que minimice la suma de los scores.
•Si son pocas hojas, se hace exhaustivo.
•Si son más, pero tampoco taaantas (digamos, < 20): branch & bound.
•De ahí para arriba, heurísticas. Se parte de varios posibles árboles, y se recorre haciendo simulated annealing o hill climbing. Se usa un set de árboles “vecinos” de un árbol dado, vía alguna transformación.
Máxima parsimoniaMáxima parsimoniaMáxima parsimoniaMáxima parsimonia
Un algoritmo glotón:
•Parto con un árbol de tres hojas.•Voy agregando hojas de a una.•Al agregar una hoja, escojo la forma de hacerlo que aumente menos el score.
Se puede hacer en O(n2N) [n secuencias, de largo N],
Se puede usar como punto de partida de heurísticas, probando distintos órdenes de agregado.
Máxima parsimoniaMáxima parsimoniaMáxima parsimoniaMáxima parsimonia
Un ejemplo de transformación de árbol, Nearest Neighbor Interchange (NNI):
Para cada arista interior, pruebo las otras dos formas de armar el cuarteto centrado en ella.
Hay otras dos transformaciones frecuentes; ver ppt full.
Máxima parsimoniaMáxima parsimoniaMáxima parsimoniaMáxima parsimonia
Ventajas de MP:
•Es fácil de aplicar a datos no genómicos.
•Es fácil poner ponderaciones distintas a los caracteres.
•Se puede exigir un orden a los cambios (ej., “cola corta/mediana/larga”).
•Provee secuencias ancestrales.
Máxima parsimoniaMáxima parsimoniaMáxima parsimoniaMáxima parsimonia
Desventajas:
•Lento.
•No usa toda la información (sólo sitios informativos).
•No da información sobre la longitud de las ramas.
•No hay corrección para mutaciones múltiples; no hay modelo de evolución asociado.
•No es estadísticamente consistente: tiene sesgos en que agregar datos no ayuda.
Máxima verosimilitudMáxima verosimilitudMáxima verosimilitudMáxima verosimilitud
Máxima verosimilitud (ML, por max. likelihood) combina la idea de MP con los modelos de evolución de caracteres (Jukes-Cantor, etc.).
•También usa heurísticas para recorrer los árboles posibles.
•Es aún más lento que MP.
•Pero como permite tasas de evolución distintas por rama, e incorporar distancia evolutiva entre caracteres (Jukes-Cantor, PAMs, etc), es más general y robusto. Y usa mejor los datos.
Máxima verosimilitudMáxima verosimilitudMáxima verosimilitudMáxima verosimilitud
Lo que cambia respecto a MP, es lo que le evaluamos a cada árbol candidato.
En MP: queremos el árbol con menos evolución.En ML: queremos el árbol más probable.
ML evalúa la verosimilitud L (probabilidad relativa) del árbol, y busca maximizarla.
¿Cómo la evalúa?
L(árbol) Probabilidad( datos / árbol )
Máxima verosimilitudMáxima verosimilitudMáxima verosimilitudMáxima verosimilitud
Usa un modelo de evolución:
•Probabilidades de sustituciones•Frecuencias de caracteres (en “background”)
Lo desconocido:
•El árbol•La longitud de las ramas
Los árboles, los recorre como en MP.
Para cada árbol, determina longitud óptima de las ramas, y con eso y el modelo de evolución, calcula L.
Máxima verosimilitudMáxima verosimilitudMáxima verosimilitudMáxima verosimilitud
Al igual que en MP, se asume independencia entre las distintas posiciones del alineamiento.
Por lo tanto, P(datos/árbol) se calcula como el producto de P(columna/árbol), sobre todas las columnas.
(O más bien, como se juntan números muy chicos, se toman los logs y se suman).
N
i
TiPTPTL1
)/columna(log)/datos(log)datos/(log
Máxima verosimilitudMáxima verosimilitudMáxima verosimilitudMáxima verosimilitud
Evaluemos L(j), dado un árbol y suponiendo que conocemos las longitudes de las ramas.
¿Cuál es la probabilidad de que ese árbol genere la columna j?
•Enraizamos el árbol
•Hay que considerar todas las posibles letras en (5) y (6).
Máxima verosimilitudMáxima verosimilitudMáxima verosimilitudMáxima verosimilitud
•Para cada caso, el modelo y la longitud de las ramas me dan, en cada rama, una probabilidad.
•Las multiplico y tengo la de ese caso.
•Sumo las de todos los casos, y tengo la probabilidad de los datos, dada esa topología, ese modelo y esas longitudes.
Máxima verosimilitudMáxima verosimilitudMáxima verosimilitudMáxima verosimilitud
Eso, suponiendo que conozco las longitudes de las ramas.
Lo que se hace es escoger (con métodos de optimización numérica, tipo Newton-Raphson) las longitudes que maximizan L.
Eso es ML clásico (Felsenstein). Existen variantes.
PHYML (Guindon & Bascuel, 2003) es muy popular, y alterna entre modificar ramas y modificar la topología del árbol; es un tipo de algoritmo EM.
Hasta aquíHasta aquíHasta aquíHasta aquí
Métodos de distancias (digamos, NJ)
Máxima parsimonia(MP)
Máxima verosimilitud(ML)
Usa sólo distancias Usa sólo caracteres “informativos”
Usa todos los datos
Minimiza suma de ramas Minimiza eventos evolutivos
Maximiza la verosimilitud del árbol, dado un modelo de evolución.
Rápido Lento Muy lento
Asume aditividad, y además es heurístico.
Falla con ramas largas o muy disímiles
Depende harto del modelo de evolución que se use.
Bueno para árboles tentativos, y solución casi inevitable cuando hay muchas hojas.
Mejor opción cuando sus supuestos se aplican y hay pocas (<20) hojas
Bueno para conjuntos de muy pocas secuencias. O para evaluar y/o iterar sobre un árbol generado por otro algoritmo.
SignificatividadSignificatividadSignificatividadSignificatividad
¿Qué confianza podemos tener en un árbol filogenético?
Lo que se suele hacer es bootstrapear: •Resamplear (con reemplazo) las columnas del alineamiento, obteniendo así un nuevo alineamiento•Calcular un árbol a partir de ese alineamiento.•Hacer eso unas 100 ó 1000 veces.
TTTCCACGD
TCTCCACGC
TCTACGCGB
TTTACGAGA
87654321
TTTTCCAGD
TCCTCCAGC
TCCTACGGB
TTTTAAGGA
87654321
SignificatividadSignificatividadSignificatividadSignificatividad
SignificatividadSignificatividadSignificatividadSignificatividad
Hacemos un árbol de consenso.
Le asociamos a los nodos interiores el % de veces que aparecieron (con los mismos hijos) en los árboles del bootstrap.
ORFP MG01127.1
NCU01640.1
ORFP YDL020C
Scastellii
Skluyeri
orf6.4920.prot
AN0709.2
H.
100
95
100
80
70
Árbol de consensoÁrbol de consensoÁrbol de consensoÁrbol de consenso
Es una forma de combinar un conjunto de árboles, en un único árbol.
Idea: si un clado está apoyado por una mayoría de los árboles, entonces el clado se incluye en el árbol de consenso. Combinando los distintos clados, se define el árbol completo, o casi (puede no quedar binario).
Detalles técnicos: en ppt full o en libro de Clote-Backofen.
Muchas revistas exigen que los árboles filogenéticos vayan acompañado por valores de bootstrap.
Qué pasó ahí?Las plantas quedan agrupadas con las bacterias!Explicación: adquirieron el gen por transferencia horizontal desde sus cloroplastos.
Durante un siglo hubo discusión sobre qué eran los osos pandas: parecen osos, pero no hibernan. En algunos rasgos, se parecen más a los mapaches.
Ejemplos de usos del análisis Ejemplos de usos del análisis filogenéticofilogenético
Ejemplos de usos del análisis Ejemplos de usos del análisis filogenéticofilogenético
1985: caso resuelto, con datos moleculares.
Inferencia de función a partir de filogenia
Ejemplos Ejemplos de usos de usos
del del análisis análisis
filogenéticfilogenéticoo
Ejemplos Ejemplos de usos de usos
del del análisis análisis
filogenéticfilogenéticoo
Concordancia entre especies: pistas para el diseño de estrategias de conservación.
Ejemplos de usos del análisis Ejemplos de usos del análisis filogenéticofilogenético
Ejemplos de usos del análisis Ejemplos de usos del análisis filogenéticofilogenético
Lafayette, Louisiana, 1994.
•Una mujer acusó a su ex-amante (un gastroenterólogo) de haberle inyectado sangre con SIDA.
•Había registro de que en esa fecha el acusado sacó sangre a un paciente seropositivo.
•La defensa alegó coincidencia.
El virus del SIDA (HIV) es altamente variable. De hecho, su juego contra el sistema inmune es evolutivo. Se usaron dos genes del HIV, y tres métodos de reconstrucción filogenética.
Ejemplos de usos del análisis Ejemplos de usos del análisis filogenéticofilogenético
Ejemplos de usos del análisis Ejemplos de usos del análisis filogenéticofilogenético
P: pacienteV: víctimaLA: otros pacientes seropositivos de la zona
Caso resuelto. Acusado culpable!
Todos los detalles sórdidos:Molecular evidence of HIV-1 transmission in a criminal caseM. Metzker et al, PNAS (2002)doi : 10.1073/pnas.222522599
Ejemplos de usos del análisis Ejemplos de usos del análisis filogenéticofilogenético
Ejemplos de usos del análisis Ejemplos de usos del análisis filogenéticofilogenético
Desafíos actualesDesafíos actualesDesafíos actualesDesafíos actuales
Sólo algunos de los principales:
•Tradicionalmente se ha trabajado con pocos genes en muchas especies, o muchos genes en pocas especies. Crecientemente, son muchos en muchas.
•Transferencia horizontal de genes: ahí no sirven los árboles, hay que pensar en redes.
•Filogenia de genomas completos: importa el contenido de genes, y el orden en que están.
Para saber másPara saber másPara saber másPara saber más
•El Ppt full.
•Los capítulos en los libros de Mount y de Clote...pese a ser incompletos; de hecho, casi no tienen intersección.
•Un review muy completo y bueno aunque un poco viejo:
PHYLOGENETIC ANALYSIS IN MOLECULAR EVOLUTIONARY GENETICS Masatoshi Nei Annual Review of GeneticsVol. 30: 371-403 (1996) doi : 10.1146/annurev.genet.30.1.371
Recommended