Download Construyendo árboles - Departamento de Informática USM

V
Filogenia
Andrés Moreira
Departamento de Informática UTFSM
Construyendo á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 á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 árboles
Algunos errores eran
casi inevitables, como
suponerle un origen
común a los
vertebrados de sangre
caliente.
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.
Construyendo árboles
Algunas gracias de la información genotípica:
•Discreta
•Abundante (muchos bits por objeto)
•La mayoría de las mutaciones son neutrales
se acumula variación “gratis”
es poco probable la convergencia (similaridad
sin homología real)
Construyendo árboles
Lo que hay que construir es un árbol:
E
A
C
•Puede ser con raíz o sin raíz.
B
•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.
D
Construyendo árboles
•La # de árboles posibles
crece muy rápido.
•Todos los criterios usuales
para escoger un árbol dan
problema NP-duros...
 heurísticas
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
Construyendo á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 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 aproximaciones
Según David Mount:
Datos
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.
Outgroup
“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 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 distancia
•Usan una matriz de
distancias (por lo general
sacada de un alineamiento).
_ A
A 0
B 4
C 6
D 10
E 10
•Pierden datos.
B
4
0
4
8
8
•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.
C D E
6 10 10
4 8 8
0 6 6
6 0 4
6 4 0
D
C
A
B
E
Métodos de distancia: supuesto aditivo
S1
S2
S3
S4
S1
S2
-
D12 D13 D14
-
S3
S4
S2
S1
a
b
D23 D24
-
D34
d
-
S3
e
S4
Distancia en el árbol
Distancia observada
D12
D13
Objetivo: D14
D23
D24
D34
c






d12
d13
d14
d23
d24
d34
=
=
=
=
=
=
a
a
a
d
c
d
+
+
+
+
+
+
b
d
b
b
e
b
+ c
+ e
+ c
+ e
Métodos de distancia: Neighbour Joining
C
B
b
c
a
A
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) ]
Métodos de distancia: Neighbour Joining
C
B
b
c
a
d
D
Empezamos con una
estrella (es el peor caso!),
y vamos uniendo.
C
e
B
A
b
E
•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.
a
A
c
x
d
D
e
E
X
d AX  (d AC  d AD  d AE ) / 3;
d BX  (d BC  d BD  d BE ) / 3;
a  b  d AB ; a  x  d AX ; b  x  d BX .
Métodos de distancia: Neighbour Joining
dAN = a = ½ (dAB+dAX-dBX)
Para las distancias entre el
nuevo y el resto, suponemos
aditividad y promediamos lo
que dan A y B:
dBN = b = ½ (dAB+dBX-dAX)
C
B
b
a
dCN = ½(dCA-dAN) + ½(dCB-dBN)
...etc
A
c
x
d
D
e
E
•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.
X
Mé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
Distancias
Forma trivial de evaluar distancia:
p  nd / n
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: d   ln( 1  p)
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 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 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
A
A
G
A
A
G
A
C
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 parsimonia
•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.
G
G
A
G
G
G
G
C
A
A
A
C
T
G
C
C
T
T
*
T
T
T
T
G
G
C
C
*
A
C
A
G
C
A
A
A
A
A
A
A
A
A
Má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 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 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 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 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 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 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 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 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
log L(T / datos )  log P(datos / T )   log P(columna i / T )
i 1
Má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 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 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í
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.
Significatividad
¿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.
1
2
3
4
5
6
7
8
A
G
A
G
C
A
T
T
T
B
G
C
G
C
A
T
C
T
C
G
C
A
C
C
T
C
T
D
G
C
A
C
C
T
T
T
1
2
3
4
5
6
7
8
A
G
G
A
A
T
T
T
T
B
G
G
C
A
T
C
C
T
C
G
A
C
C
T
C
C
T
D
G
A
C
C
T
T
T
T
Significatividad
Significatividad
Hacemos un árbol de
consenso.
ORFP MG01127.1
NCU01640.1
70
Le asociamos a los nodos
interiores el % de veces
que aparecieron (con los
mismos hijos) en los
árboles del bootstrap.
100
ORFP YDL020C
Scastellii
80
95
Skluyeri
orf6.4920.prot
100
AN0709.2
H.
Á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 CloteBackofen.
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.
Ejemplos de usos del análisis filogenético
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.
1985: caso resuelto,
con datos
moleculares.
Ejemplos de
usos del
análisis
filogenético
Inferencia
de función a
partir de
filogenia
Ejemplos de usos del análisis filogenético
Concordancia entre especies: pistas para el diseño de
estrategias de conservación.
Ejemplos de usos del análisis filogené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 filogenético
P: paciente
V: víctima
LA: otros pacientes
seropositivos de la zona
Caso resuelto.
Acusado  culpable!
Todos los detalles sórdidos:
Molecular evidence of HIV-1 transmission
in a criminal case
M. Metzker et al, PNAS (2002)
doi : 10.1073/pnas.222522599
Desafí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á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 Genetics
Vol. 30: 371-403 (1996)
doi : 10.1146/annurev.genet.30.1.371