Download filogenia - Departamento de Informática

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 parálogos (de una misma especie)
•Las secuencias de un set de genes ortólogos (uno por especie)
•Un set de genomas completos de bacterias
•Una tabla de características fenotípicas observadas en los fósiles de
una serie de dinosaurios
•Un set de idiomas, representados por vocablos
•...etc.
Construyendo árboles
 Un posible árbol de los
idiomas indo-europeos (Ringe,
Warnow & Taylor, 2000).
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
En los viejos tiempos la única
información era fenotípica;
hasta el día de hoy sigue
siéndolo en paleontología (¡o
en filología!).
Es una situación difícil: hay
que elegir qué conjunto de
características medir, y que
relevancia darles.
Más aún: hay rasgos
cualitativos y cuantitativos.
Construyendo árboles
Algunos errores eran
casi inevitables, como
suponerle un origen
común a los
homeotermos (aves y
mamíferos).
Pero aún así se avanzó
bastante.
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)
...Lo que no significa que con eso el
problema se vuelva trivial.
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 (i.e., los nodos internos
tienen grado 3), aunque también puede haber
“politomía” (bifurcación en más de dos ramas), por
falta de información o para simplificar.
D
Construyendo árboles
Algunos árboles son equivalentes:
Pero aún así, los árboles posibles en principio son muchos.
A
A
D
C
C
B
B
A
A
C
C
B
D
D
B
Construyendo árboles
Para n “hojas”, los
árboles sin raíz posibles
son (2n-5)!/(n-3)!2n-3.
Considerando que además
todos los criterios
usuales para escoger un
árbol crean problemas
NP-duros...
...estamos en territorio
de 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. Se les critica que con
eso pierden información. Pero en fin, c’est la vie, son
rápidos y con frecuencia no andan mal.
•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
La aproximación a usar depende principalmente del
nivel de divergencia de las secuencias. Según 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
El “outgroup” es un 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í.
•Pero además se espera que no sea demasiado lejano,
para que no agregue mucho ruido al análisis.
•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 (¡no todos!) trabajan a
partir de un alineamiento múltiple de las secuencias.
No necesariamente con el alineamiento completo: por lo
general se descartan las columnas con gaps (introducen
ruido, porque no hay buen modelo para ellos).
Con frecuencia alinear y determinar filogenia son
problemas asociados (como lo vimos en los métodos de
alineamiento progresivo que usan un “árbol guía”).
Métodos de distancia
Los métodos de distancia usan como input una
matriz de distancias; por lo general es el
resultado de un alineamiento, donde se han
despreciado las columnas con gaps.
La distancia en ese caso puede ser la proporción
de columnas en las que dos secuencias difieren.
Hay refinamientos y correcciones; los veremos
luego.
Reitero: un problema es que se pierden datos al
hacer esto de reducir el output del alineamiento a
una tabla de distancias.
Métodos de distancia
Estos métodos
reconstruyen no sólo la
topología, sino también la
longitud de las ramas.
_ A
A 0
B 4
C 6
D 10
E 10
Se asume que la distancia
entre dos hojas representa
la suma de las longitudes de
las ramas internas que las
separan.
B
4
0
4
8
8
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: mínimos cuadrados
Una opción: mínimos cuadrados.
S2
S1
a
c
b
Dado un árbol, buscamos las
longitudes de ramas que
minimicen Q =  (Dij-dij)2.
De los árboles posibles,
escogemos el que minimiza el
error cuadrático.
e
d
S3
S4
D12
D13
D14
D23
D24
D34






d12
d13
d14
d23
d24
d34
=
=
=
=
=
=
a
a
a
d
c
d
+
+
+
+
+
+
b
d
b
b
e
b
Para que las distancias largas no se impongan en Q,
se suele dividir cada término por Dijn, por lo general
con n=1 ó 2.
+ c
+ e
+ c
+ e
Métodos de distancia: mínimos cuadrados
Si los árboles posibles son
muchos, habrá que recorrer el
espacio de árboles, con algún
algoritmo (el problema es NP).
Por ejemplo, definiendo una
vecindad de árboles (vía
perturbaciones de algún tipo), y
aplicando hill-climbing hasta
llegar a un óptimo local: un árbol
que da menos error que todos sus
vecinos.
S2
S1
a
c
b
e
d
S3
S4
D12
D13
D14
D23
D24
D34






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: clustering
Los algoritmos de clustering generan el árbol
progresivamente, uniendo hojas en un nodo (del cual
colgarán), y luego nodos con hojas, nodos con nodos,
hasta tener un único árbol.
Difieren en la forma de definir las distancias entre
clusters, y eso a su vez depende los supuestos que
hacen, y de lo que pretenden optimizar.
Ojo: aunque sería natural pensar en la última unión
(que completa el árbol) como la raíz, eso no es
necesariamente así.
Métodos de distancia: clustering
Esquema general (se itera hasta que está listo el
árbol):
-Conectar dos nodos con un único nodo ancestral.
-Calcular distancias entre ellos y ese nuevo nodo.
[Ese es un paso que en clustering típico uno no hace]
-Actualizar la matriz de distancias:
-eliminar esos nodos que uní
-agregar el nuevo, calculando nuevas distancias
c/r al resto de las hojas o nodos
Métodos de distancia: clusteringUPGMA
UPGMA (Unweighted Pair Group Method with
Arithmetic mean):
•La distancia entre dos nodos A y B que se unen, y el
nuevo nodo N, se define como
d(A,N)=d(B,N)= d(A,B)/2
•La distancia entre dos clusters (o sea, entre cualquier
par de nodos internos) es el promedio de las distancias
entre sus miembros. De modo que al unir un nodo A del
que “cuelgan” a hojas, y otro B del que cuelgan b, la
distancia entre el nodo nuevo y un tercer nodo C será
d(C,N)= [a d(C,A) + b d(C,B) ] / [a+b]
Métodos de distancia: clusteringUPGMA
Entrega un árbol con raíz (el último nodo que agrega).
Supuesto implícitos:
•Reloj molecular (tasa de evolución constante): se asume
que todas las hojas están a la misma distancia (en
términos de mutaciones) de la raíz.
Si esto fuera cierto, además la matriz de distancias sería
ultramétrica: d(x, z) ≤ max{d(x, y), d(y, z)}
Problema:
ese supuesto, que es fuerte. Rara vez se usa UPGMA,
salvo para construir árboles “guía”, y ni eso.
Métodos de distancia: clusteringNJ
Neighbour Joining (a.k.a. NJ):
•No hace supuesto de reloj molecular.
•Entrega un árbol sin raíz.
•Busca minimizar la suma de las ramas del árbol
resultante  modelo de mínima evolución.
Métodos de distancia: clusteringNJ
C
B
b
c
a
A
Observación:
Cuando tenemos sólo 3 ramas, se pueden
calcular sus longitudes a partir de las
distancias y viceversa:
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: clusteringNJ
Empezamos con una estrella (es el peor caso!), y
vamos uniendo.
C
B
b
c
a
d
D
e
A
No conozco a,b,c,d,e, pero sí su suma:
E
d AB  a  b;
d AC  a  c;
d AD  a  d ;
d AE  a  e;
S  abcd e 
(d AB  d AC  d AD  d AE  d BC  d BD  d BE  d CD  d CE  d DE ) /( N  1)
Métodos de distancia: clusteringNJ
Ahora junto A con B.
Por un momento juntamos
en “X” todo lo que no es A
ni B, y definimos la
distancia entre A y X como
el promedio de las
distancias entre A y los
elementos de X.
Aplicando lo que dijimos
recién para el caso de tres
nodos, obtenemos a,b, y x.
C
B
b
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: clusteringNJ
Con a y b, tenemos la
distancia entre los nodos y
el nuevo nodo que los
reune:
dAN = a = ½ (dAB+dAX-dBX)
dBN = b = ½ (dAB+dBX-dAX)
C
B
b
a
A
c
N x
d
Las distancias entre el nuevo y el resto, las
sacamos suponiendo aditividad y promediando
(entre A y B):
dCN = ½ ( dCA-dAN ) + ½ (dCB-dBN)
..etc
D
e
E
X
Métodos de distancia: clusteringNJ
En general, si tengo r nodos, y uno f y g en un nuevo
nodo llamado u,
Y para el resto de los nodos k (distintos a f y g):
¿Qué nodos escogemos para unir?
Los que reduzcan más la suma de las ramas.
Al hacer las sumas antes y después (no lo haré aquí)
resulta que hay que escoger los que minimicen:
Métodos de distancia: clusteringNJ
O, escrito de otra forma. Dadas las distancias d,
calculo
1 r
uf 
d ( f , g)

r 2
g 1
Y escojo el par que minimiza d ( f , g )  u f  u g
Las ramas de i y j al nuevo son de largo
1 d ( f , g )  u f  u g 
2
1 d ( f , g )  u f  u g 
2
respectivamente, y la distancia entre el nodo nuevo
(“u”) y un k-ésimo nodo será
d (u, k )  1 d ( f , k )  d ( f , u )  d ( g , k )  d ( g , u ) 
2
 1 d ( f , k )  d ( g , k )  d ( f , g ) 
2
Métodos de distancia: clustering
Método de “neighbors relation”:
se basa en la observación de que
en un cuarteto,
dAB+dCD  dAD+dBC = dAC+dBD
A
B
C
D
así que, entre las tres formas de agrupar ABCD en dos
pares, debiera escoger la que da menor suma de
distancias dentro de los pares.
El método entonces: dadas N secuencias (N>4),
•considero todos los cuartetos
•en cada cuarteto evalúo eso (veo los mejores pares)
•veo que par se repitió más veces
•ese lo uno en un nuevo nodo (y recalculo como antes)
Métodos de distancia
Pese a despreciar parte de la información disponible,
los métodos de distancias son importantes.
•Son rápidos (a veces son los únicos factibles).
•Se adaptan bien a ramas de longitudes distintas
(tasas de evolución distintas en distintas partes del
árbol).
•Dependen del supuesto de la aditividad; por lo tanto,
la forma en que se calcula la distancia es vital.
Distancias
Decíamos que la forma trivial de evaluar distancia,
dado un alineamiento, sería como la fracción de
diferencias entre las dos secuencias:
p  nd / n
donde n es la cantidad de columnas del alineamiento
que estoy usando, y nd es la cantidad de columnas en
que las dos secuencias difieren.
¿Qué puede fallar con eso?
Puede haber cambios más probables que otros
(incorporar información de matrices de sustitución)
Cosas “malas” se vuelven frecuentes a mayor
distancia evolutiva.
Distancias
ACTGTAGGAATCGC
| || | |||||||
AATGAACGAATCGC
3 diferencias,
pero no debidas a
tres mutaciones...
Cuando la
distancia es
grande, estas
cosas se vuelven
más y más
frecuentes.
Distancias
“Homoplasy”: cuando los
caracteres coinciden pero por
convergencia, no porque se haya
conservado un carácter ancestral.
Se produce saturación; sólo es
posible estimarla.
La diferencia
es por
saturación
Número de diferencias
Esperado
Observado
Tiempo
Saturación:
…GCGCTTCGGC…
…GCGTTTCCGC… 2
…GCGTATTCGC… 4
…GCGCATTCGC… 5
…ACCCATACGC… 8
…TCCCATACTC…
…TCCCACACTC…
…TTGCACACTC…
…TTGCGCACTT…
Observado: 8
Real: 15
10
11
13
15
Distancias
D
D
A
A
B
C
Árbol verdadero
C
B
Árbol reconstruido
“Long branch
attraction”: la
distorsión provocada
cuando hay ramas
largas y cortas, pero
las largas “se ven”
cortas por
convergencias y retrosustituciones.
En particular, ramas
largas se “atraen”
entre sí.
(
Paréntesis: otros tipos de problemas
Problemas de otros tipos:
•Genes A y B que alguna vez fueron parálogos
(duplicados en un mismo genoma) pero en que una
especie perdió A, la otra perdió B.
•Transferencia horizontal de genes
•“Lineage sorting”: divergencia previa dentro de una
población.
Duplicación y pérdida
Transferencia horizontal
)
Lineage sorting
Distancias
Corrección de Poisson:
d   ln( 1  p )
donde p es el de antes.
Razón: si lo damos vuelta, es p=1-e-d, la probabilidad de
que haya algún evento en un lapso dado, para una tasa
de eventos d ; de ese modo estimamos la “tasa de
eventos”, o distancia evolutiva entre las secuencias.
No vuelve visible lo invisible, pero entrega una
estimación más robusta.
Distancias
En general la corrección que uno haga dependerá de la
forma en que se modele la evolución de las secuencias.
Para DNA, el modelo más simple es el de JukesCantor, que asume la misma tasa de reemplazo entre
los nucleótidos.
Si además tienen igual
frecuencia (1/4) entonces la
corrección que se deriva es
3  4 
d   ln 1  p 
4  3 
Distancias
O más en general, si no hay frecuencias iguales,
donde
p

d   B ln 1  
 B
B  1  f A2  f C2  f G2  fT2
Otro modelo popular es el de Kimura, que asigna
probabilidad mayor a las transiciones (CT, AG)
que a las transversiones. Como es modelo de dos
parámetros, no basta p; hay que contar las
transiciones (s) y las transversiones (v) a lo largo
del alineamiento:
1
1
d   ln 1  2s  v   ln 1  2v 
2
4
Distancias
Y hay más:
En general, de lo que se
trata es de afinar una
cadena de Markov:
A
G
C
T
Distancias
Y eso sólo considerando que todas las columnas del
alineamiento fuesen independientes.
En DNA que codifica algo, eso rara vez es cierto.
En particular en genes de proteínas, el código genético
hace neutras la mayoría de las mutaciones en la
tercera letra de cada codón (y por ende, más
A
C
G
U
probables).
A
C
G
U
0
1
2
3
16
17
18
19
32
33
34
35
48
49
50
51
AAA
AAC
AAG
AAU
CAA
CAC
CAG
CAU
GAA
GAC
GAG
GAU
UAA
UAC
UAG
UAU
K
N
K
N
Q
H
Q
H
E
D
E
D
STOP
Y
STOP
Y
4
5
6
7
20
21
22
23
36
37
38
39
52
53
54
55
ACA
ACC
ACG
ACU
CCA
CCC
CCG
CCU
GCA
GCC
GCG
GCU
UCA
UCC
UCG
UCU
T
T
T
T
P
P
P
P
A
A
A
A
S
S
S
S
8
9
10
11
24
25
26
27
40
41
42
43
56
57
58
59
AGA
AGC
AGG
AGU
CGA
CGC
CGG
CGU
GGA
GGC
GGG
GGU
UGA
UGC
UGG
UGU
R
S
R
S
R
R
R
R
G
G
G
G
STOP
C
W
C
12
13
14
15
28
29
30
31
44
45
46
47
60
61
62
63
AUA
AUC
AUG
AUU
CUA
CUC
CUG
CUU
GUA
GUC
GUG
GUU
UUA
UUC
UUG
UUU
I
I
M
I
L
L
L
L
V
V
V/M
V
L
F
L
F
Distancias
Para eso, se consideran valores distintos según
posición, o bien se usan matrices de sustitución
codóncodón.
A propósito: dijimos que para hacer alineamientos, se
usa de preferencia la secuencia de proteína (aún
cuando conozcamos el DNA que la codifica).
Para hacer filogenia, suele convenir usar el DNA
codificador, sobre todo entre proteínas muy cercanas
evolutivamente (las mutaciones neutrales dan
información!).
Distancias
Si se usan proteínas para el análisis filogenético, hay
varios tipos de correcciones:
•Tipo Jukes-Cantor
•Usando matrices de sustitución (PAM)
...y con diversas reglas “empíricas”, que da el
expertise, para ver qué correcciones usar según la
situación concreta.
NO nos meteremos en eso.
Máxima parsimonia
Máxima parsimonia, o mínima evolución:
buscamos el árbol, coherente con los datos, que
requiera el mínimo de eventos evolutivos.
•Es el método más intuitivo, simple y general, pero sólo
se porta bien con pocos datos (es caro) y cercanos
(poca distancia evolutiva).
•Se consideran los “caracteres” de a uno. Digamos, las
columnas del alineamiento. Pero también podría ser un
cambio de orden de genes en un genoma, un rasgo
morfológico, o hasta un hábito de apareamiento de las
especies. Whatever.
Máxima parsimonia
•Para un árbol dado (sin raíz) y un carácter 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
•Algunas posiciones no son informativas: para el
conjunto de letras de la derecha (A,A,C,G), cualquier
árbol arroja la misma cantidad mínima de cambios.
•Si no permiten
discriminar entre árboles,
no nos interesan. Para ser
informativa, una columna
del alineamiento tiene que
tener al menos dos letras
que estén al menos dos
veces.
A
A
A
A
A
G
G
G
G
C
A
A
A
C
T
G
C
C
T
T
*
T
T
T
T
G
G
C
C
*
G
A
G
A
C
A
G
C
A
A
A
A
Máxima parsimonia
La parte barata: evaluar puntaje
C
T
T
G
T, score 0
T
C
T, score 1
G
CT, score 1
A
T
C
G
A
T
T
T
T
T
C
T
T
T
A
G
TGA, score 3
A
Máxima parsimonia
La parte barata: evaluar puntaje
•Colgamos el árbol de algún nodo interior (cualquiera).
•Cada hoja tiene una letra; en los nodos internos voy
poniendo un conjunto de letras, según lo que tengan los
nodos que cuelgan de él:
Si no tienen letras en
común, pongo su unión.
Si tienen letras en
común, pongo la
intersección.
Máxima parsimonia
La parte barata: evaluar puntaje
•Ahora escojo una letra de cada conjunto:
•En la raíz escojo una
cualquiera
•En el resto, escojo la
letra del padre si es que
la tengo, y si no, una
cualquiera.
•Ahora evalúo la cantidad
de cambios.
C
A
C
C
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, menos
de 20): branch & bound.
•De ahí para arriba, heurísticas. Por lo general se
parte de varios posibles árboles, y se recorre el
paisaje de posibles topologías, haciendo hill climbing o
simulated annealing. Se requiere definir 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.
Es O(n3N) [n secuencias de largo N], pero se puede
bajar a O(n2N).
Se puede usar como punto de partida de heurísticas,
probando distintos órdenes de agregado.
•Existe otro algoritmo (tb. polinomial) que garantiza una 2aproximación; usa MST (min. árbol recubridor).
Máxima parsimonia
Transformaciones de árboles más usadas:
Nearest Neighbor Interchange (NNI):
•Para cada arista interior, pruebo las otras dos formas
de armar el cuarteto centrado en ella.
El tamaño de la vecindad es lineal en el número de hojas.
Máxima parsimonia
Transformaciones de árboles más usadas:
•Subtree Pruning Regrafting (SPR): separo cada
posible subárbol, y veo todas las formas posibles de
agregarlo.
Separo el subárbol
1-2 y lo re-enchufo
El tamaño de la vecindad es ahora cuadrático.
Máxima parsimonia
Transformaciones de árboles más usadas:
•Tree-Bisection-Reconnection (TBR): se corta el árbol
en dos (de cada manera posible), y se reconectan las
partes de todas las maneras posibles.
Si se puede
O(n3), se suele
preferir TBR
El tamaño de la vecindad es ahora cúbico.
Máxima parsimonia
Branch & Bound
•El “Branch” se hace agregando progresivamente hojas
(y se crean “branches” nuevas según los lugares en que
las puedo agregar).
A
A
D
C
E
B
D
A
C
E
B
D
C
B
E
Máxima parsimonia
Branch & Bound
•El “Bound” se
aprovecha de que el
score, al agregar
más hojas, sólo
puede empeorar.
Máxima parsimonia
Branch & Bound
•En este caso se parte juntando las secuencias más
distintas, para tener mejores cotas y descartar más
rápido partes del espacio de búsqueda.
•Uso un árbol “bueno” obtenido por otro método (por
ejemplo, el algoritmo glotón, o el que 2-aproxima, o
eso + hill climbing) para tener cota superior.
•Si al agregar alguna rama tengo un valor peor,
descarto esa opción.
Máxima parsimonia
Gracias de MP:
•Es fácil poner ponderaciones distintas a los
caracteres, si se piensa que uno es más fundamental o
más confiable que otro.
•Se puede exigir un orden a los cambios (esto es útil
sobre todo con información del tipo “cola
corta/mediana/larga”). Se les llama “caracteres de
Wagner”.
•Provee secuencias ancestrales.
Máxima parsimonia
Problemas:
•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: susceptible a
“long branch attraction”, y agregar datos no ayuda.
Máxima parsimonia
Paréntesis a próposito de ponderaciones distintas.
El índice de consistencia para un carácter dado un
árbol, es el cuociente entre la cantidad mínima de
cambios que el carácter requiere (o sea, la que tendría
en un árbol escogido sólo para él), y la cantidad mínima
en el árbol dado. Digamos, mi/ai.
Para un árbol, el CI será mi/ ai, y se le considera un
índice (discutible) de homoplasia.
Una idea que algunos aplican y otros rechazan: hacer
MP varias veces (hasta converger), ponderando los
caracteres por su CI de la iteración anterior.
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 (branch & bound no se le da bien).
•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 antes.
Para cada árbol, determina longitud óptima de las
ramas, y con eso y el modelo de evolución, calcula L.
Máxima verosimilitud
La probabilidad de sustituciones considera tiempo
continuo. Por lo tanto, un proceso de Markov continuo.
Qv
e
 P(v)
Q: matriz de tasa de sustitución
v: tiempo transcurrido
P: probabilidad de la sustitución, en un tiempo v
 3
 
Q
 

 


 
 3

 

 3
 



 3 


 
1  3
 

1

3




P(1)  
 

1  3
 





1

3



Se pide que la cadena de Markov sea reversible.
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 en cualquier parte
(da lo mismo dónde  ahí entra la
condición de reversibilidad).
Máxima verosimilitud
•Hay que considerar
todas las posibles
letras en (5) y (6).
•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
De otro ejemplo: para secuencias
y el árbol
y el modelo
A: ccat
B: ccgt
C: gcat
Máxima verosimilitud
Se obtiene L(1) como
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.
Cuartetos
Ya mencionamos, cuando estábamos en los métodos
de distancias, un método con cuartetos.
No es el único. Hay hartos.
Razón:
•Los cuartetos son fáciles.
•La topología de un árbol induce topología para
cualquier cuarteto de hojas.
Cuartetos
Pero además:
•Si conocieramos la topología correcta para todos los
cuartetos, se puede reconstruir la topología del
árbol completo.
Problema:
Idea natural: resolver para los cuartetos, y tratar
de compatibilizar.
Cuartetos
Quartet puzzling:
•Hacer ML para todos los cuartetos posibles.
•Aleatorizar el orden de las hojas.
•Partir del cuarteto de las primeras cuatro. Agregar
la quinta de la manera más compatible presente. Y
luego la que sigue. Etc. [No veremos el detalle].
•Hacer eso muchas veces, para distintos órdenes de
las hojas.
•Construir un árbol de consenso mayoritario.
Árbol de consenso
¿Árbol de consenso?
Siguiendo a Clote & Backofen:
•1, 2 y 3 determinan la topología del árbol.
•Dado un árbol común y corriente, definimos sus
etiquetas recursivamente: en las hojas, la hoja. Hacia
arriba, la unión.
Árbol de consenso
Dado un conjunto de árboles T1, T2, ..., TN, hacemos sus
n-árboles, y definimos el n-árbol de consenso:
Son los nodos cuya etiqueta está presente en al
menos el 50% de los árboles.
•Resulta que es un n-árbol. Ergo, determina topología.
+ A veces se usa un umbral >50%.
+ Otra forma de verlo es que un clado es apoyado por al
menos ese porcentaje de árboles.
+ El árbol de consenso suele no ser binario.
Métodos bayesianos
Es una aproximación (o mejor dicho, un grupo de
aproximaciones) más recientes.
•Se asume una distribución a priori sobre los
árboles (que suele generar polémica).
Implícitamente, ML asumía un a priori uniforme.
•Por lo general se samplea la distribución a
posteriori mediante Markov Chain Monte Carlo :
se genera un proceso markoviano cuya distribución
estacionaria debiera coincidir con la a posteriori.
Métodos bayesianos
•El MCMC hace un paseo (vía transformaciones) por el
paisaje de árboles.
•El paseo es sesgado (no 100% dirigido) hacia los
mejores puntajes.
Métodos bayesianos
•Tomo un árbol inicial T. Calculo P(D|T) como en ML.
•Propongo un T’ (vía transformación). Calculo P(D|T’).
•Calculo el cuociente de aceptación:
Cuociente de
verosim.
Cuociente
de a prioris
Cuociente de
proposición de
árboles
P( D T ') P(T ' ) P(T T ')


P( D T ) P(T ) P(T ' T )
•Será la probabilidad de pasar a T’ (si es >1, paso seguro).
Métodos bayesianos
•Considero las probabilidades a posteriori.
•Hago árbol de consenso (ponderando por las prob.).
•Da probabilidad a posteriori para los distintos
clados.
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 el á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.
Jackknife: parecido,
pero sampleamos k<n
columnas, sin reemplazo.
Significatividad
Para Jacckife, se recomienda
tomar entre el 50% y el 37%
(en realidad, e-1) de las
columnas.
Los puntajes de apoyo suelen
ser J50 < BS < J37, pero
similares en todo caso (BS más
cerca de J50 para secuencias
más lejanas, más cerca de J37
para secuencias más parecidas).
Lo más común: BS.
Muchas revistas exigen
que el árbol vaya
acompañado por valores
de bootstrap.
Significatividad
Otras ideas:
•Permutar las letras dentro de cada columna del
alineamiento, y generar árboles a partir de esos
datos randomizados. ¿Dónde queda nuestro árbol
dentro de la distribución?
•“Decay analysis”: se evalúa, para un clado, la
diferencia entre el puntaje del mejor árbol que
incluye ese conjunto como un clado, y el mejor
puntaje de los árboles que no lo hacen (que es
decir, incluyen otras “hojas” entremedio). Es el
“Decay Index” o “Bremer support”.
Test de Kishino-Hasegawa
Dados dos árboles, las diferencias entre ellos, ¿son
atribuibles al margen de error de los datos
disponibles?
•El test de K-H (el más usado, pero no es el único)
funciona bajo el supuesto de caracteres i.i.d..
•Dado un carácter, calculamos la diferencia entre
su parsimonia, o su likelihood, para cada árbol.
•Si las diferencias fueran aleatorias, debería
haber la misma cantidad de caracteres
favoreciendo un árbol o el otro.
Bajo hipótesis nula,
la media debiera
ser cero, y la
distribución,
normal.
Caracteres a favor
del árbol A
Media esperada
Test de Kishino-Hasegawa
Caracteres a favor
del árbol B
0
Distribución de diferencias en pasos/likelihood por caracter
De lo observado calculamos desviación
estándar. Si la media queda a más de 2 de 0,
se rechaza hipótesis nula, y de los dos árboles,
el de mejor score se declara
significativamente mejor que el otro.
Test de Kishino-Hasegawa
Ochromonas
SSUrDNA de
ciliados
Symbiodinium
Prorocentrum
Sarcocystis
Theileria
Plagiopyla n
Plagiopyla f
Trimyema c
Trimyema s
Cyclidium p
Cyclidium g
Cyclidium l
Glaucoma
Colpodinium
Tetrahymena
Paramecium
Opisthonecta
Colpoda
Dasytrichia
Entodinium
Spathidium
Loxophylum
Homalozoon
Metopus c
Metopus p
Stylonychia
Onychodromous
Oxytrichia
Loxodes
Tracheloraphis
Spirostomum
Gruberia
Blepharisma
Ciliados anaeróbicos con hidrogenosomas
Discophrya
Trithigmostoma
Resultó este árbol.
¿Habrá otro con menos
apariciones de
hidrogenosomas, que no
sea significativamente
peor?
Test de Kishino-Hasegawa
Ochromonas
Symbiodinium
Prorocentrum
Sarcocystis
Theileria
Plagiopyla n
Plagiopyla f
Trimyema c
Trimyema s
Cyclidium p
Cyclidium g
Cyclidium l
Dasytrichia
Entodinium
Loxophylum
Homalozoon
Spathidium
Metopus c
Metopus p
Loxodes
Tracheloraphis
Spirostomum
Gruberia
Blepharisma
Discophrya
Trithigmostoma
Stylonychia
Onychodromous
Oxytrichia
Colpoda
Paramecium
Glaucoma
Colpodinium
Tetrahymena
Opisthonecta
Ochromonas
Symbiodinium
Prorocentrum
Sarcocystis
Theileria
Plagiopyla n
Plagiopyla f
Trimyema c
Trimyema s
Cyclidium p
Metopus c
Metopus p
Dasytrichia
Entodinium
Cyclidium g
Cyclidium l
Loxophylum
Spathidium
Homalozoon
Loxodes
Tracheloraphis
Spirostomum
Gruberia
Blepharisma
Discophrya
Trithigmostoma
Stylonychia
Onychodromous
Oxytrichia
Colpoda
Paramecium
Glaucoma
Colpodinium
Tetrahymena
Opisthonecta
Dos restricciones topológicas
Se hizo MP con
restricción en la
cantidad de orígenes,
obligando a que pares
de ramas rojas
quedanse juntas.
Se comparó el árbol
resultante con el de la
página anterior.
Test de Kishino-Hasegawa
Los árboles con 1 ó 2 orígenes fueron todos
significativamente peores.
Así que hay
buenas razones
para suponer al
menos 3
orígenes
independientes
de los
hidrogenosomas
en los ciliados.
No.
Origins
4
4
3
3
3
3
3
3
2
2
2
2
2
2
2
1
Constraint
tree
ML
MP
(cp,pt)
(cp,rc)
(cp,m)
(pt,rc)
(pt,m)
(rc,m)
(pt,cp,rc)
(pt,rc,m)
(pt,cp,m)
(cp,rc,m)
(pt,cp)(rc,m)
(pt,m)(rc,cp)
(pt,rc)(cp,m)
(pt,cp,m,rc)
Extra
Steps
+10
+13
+113
+47
+96
+22
+63
+123
+100
+40
+124
+77
+131
+140
+131
Difference
and SD
-13  18
-21  22
-337  40
-147  36
-279  38
-68  29
-190  34
-432  40
-353  43
-140  37
-466  49
-222  39
-442  48
-414  50
-515  49
Significantly
worse?
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Ejemplos de usos del análisis filogenético
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 pandas gigantes: 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
Opsina: los pigmentos
visuales que nos permiten
distinguir colores.
Origen común de los
pigmentos, para
vertebrados e
invertebrados.
Duplicación y
especialización, varias
veces en distintas ramas.
Ejemplos de usos del análisis filogenético
El verde del humano es más cercano al rojo humano (y al rojo
de la gallina) que al verde de la gallina. ¿Qué pasa ahí?
Ejemplos de usos del análisis filogenético
Es producto de una duplicación que se produjo en los
monos del viejo mundo, y permitió la especialización.
La diferencia son sólo 3 aminoácidos!
En monos del nuevo mundo, verde/rojo son alelos distintos
del mismo gen. Tienen visión dicromática.
El gen va en el cromosoma X; eso permite que algunas
hembras de monos del nuevo mundo tengan visión tricromática.
En humanos, subsiste el daltonismo. Tal vez por motivos
evolutivos.
Ejemplos de usos del análisis filogenético
La hipótesis “out of Africa” del origen del hombre:
•Origen común alrededor de 200.000 años atrás.
•No seríamos descendientes de Neanderthals.
•Los humanos modernos habrían reemplazado a las
otras poblaciones que encontraron en su camino
(H. erectus, Neanderthal, y otros).
Se contrapone a la idea de: un origen común hace 2
millones de años atrás, aparición de
características modernas en continentes distintos,
y mezcla generalizada.
Ejemplos de usos del análisis filogenético
Ejemplos de usos del análisis filogenético
Hoy en día “out of Africa” se considera
prácticamente un hecho.
Ejemplos de usos del análisis filogenético
DNA mitocondrial
Cromosoma Y
Africa
...y otras evidencias. Incluyendo... Piojos!
Ejemplos de usos del análisis filogenético
Hoy en día “out of Africa” se considera
prácticamente un hecho.
Pero:
-Al parecer hubo dos “oleadas” (al menos)
-Sí hubo algún nivel (menor) de cruce con
Neanderthal, y algunos genes actuales los sacamos
de ahí.
Estudios filogenéticos con mtDNA (DNA
mitocondrial) rescatado de Neanderthals.
http://www.actionbioscience.org/evolution/johanson.html
http://johnhawks.net/weblog/topics/modern_human_origins/multiregional_
vs_out_of_africa.html
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
•Los capítulos en los libros de Mount y de Clote no
están malos...
...pero son 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