Upload
others
View
7
Download
0
Embed Size (px)
Citation preview
CLADÍSTICA
Método de análisis para reconstruir filogenias
a través de la inferencia de relaciones sobre la base de
caracteres derivados (evolucionados) compartidos
¿cómo se construye un cladograma?
1. Análisis de caracteres
2. Selección de topología óptimas
en la reconstrucción filogenética
• La naturaleza tiene una estructura jerárquica
(producto de sus relaciones genealógicas)
• Esta estructura jerárquica se puede representar
mediante árboles ( = cladogramas)
• Los árboles se construyen a través del
análisis de caracteres
Axiomas C
om
ún
a t
od
os lo
s m
éto
do
s
• Parsimonia (= simplicidad)
• Máxima verosimilitud
• Métodos Bayesianos
Métodos
Probabilísticos (modelos explícitos
de evolución)
Métodos
1º Los estados de carácter se organizan en una serie de transformación que se
polariza
2º Se reconocen las sinapormorfías que se utilizan para construir el cladograma
Análisis en dos pasos o restringido
DESARROLLO HISTÓRICO: ARGUMENTACIÓN HENNIGIANA
Primeras aproximaciones cuantitativas para la evaluación de los
árboles a través de la optimización de caracteres de modo tal que
la cantidad de cambios sean mínimos
Algoritmos computarizados
Farris, J.S. (1970) Methods for computing Wagner trees
Farris, J.S. et al. (1970) A numerical approach to Phylogenetic Systematics
Fitch, W.M. (1971) Towards defining the course of evolution: minimum change for a
specific tree topology.
¿cómo se construye un cladograma?
Argumentación a posteriori de los
caracteres
- Taxones terminales: los miembros del in-group y out-group
- Se analizan juntos en una matriz
- Se obtiene un árbol sin raíz (network)
- Se enraíza el árbol resultante y en ese momento se determina la polaridad
(la raíz determina la topología del árbol)
Análisis simultaneo y no restringido
¿cómo se construye un cladograma?
A C B D
Raíz
Árboles enraizados
A C B D
Raíz
D
A C
B
Árbol no enraizado
D
A C
B
Raíz
D
A C
B
Raíz
Estos árboles muestran cinco relaciones filogenéticas distintas
entre los taxones (y todos derivan del mismos árbol no
enraizado)
La raíz determina la topología del árbol.
Árbol enraizado 3
A
3
C
B
D
Árbol enraizado 4
A
4
C
B
D
Árbol enraizado 5
A
5 C
B
D
Árbol enraizado 2
A
2
C
B
D
Árbol enraizado 1
A 1
C
B
D
A C
B D
4
3
5
2
1
Dado un conjunto de observaciones se debe evaluar la topología que represente
de forma más simple (= más parsimoniosa) las relaciones entre los taxones
Independientemente del enraizamiento
1. Se obtiene un árbol sin raíz (network)
La polaridad se establece
a posteriori del enraizamiento
2. Se enraíza el árbol resultante y luego se determina
la polaridad.
A
B
C
D
E
A C B D E
Ocurrencia
de “b”
Árbol sin raíz
Dos raíces diferentes
Polaridad de los caracteres es muy distinta pero la longitud es siempre la misma L = 7
Ocurrencia
de “b”
Árbol sin raíz
Dos raíces diferentes
Necesidad de algoritmos matemáticos
computarizados
Para n taxa el número de
árboles enraizados es:
1
2 3 !
2 1 !n
n
n
Taxa (n) Enraizados
Sin raíz
2 1 1
3 3 1
4 15 3
5 105 15
6 954 105
7 10.395 954
8 135.135 10.395
9 2.027.025 135.135
10 34.459.425 2.027.025
ESTIMACIONES FILOGENÉTICAS
Árbol de la
vida
Hillis, Zwickl, &
Gutell (2003)
Usted
esta
aquí
Cualquiera sea la naturaleza de los datos (morfológicos, moleculares)
Se debe elegir algún modelo de cambio entre estados para elegir entre hipótesis
(topologías) alternativas.
- Se debe especificar las suposiciones de cambio entre estados de un modelos
- Se aplica ese modelo para estimar la mejor topología que explique la distribución
de los caracteres entre las unidades de estudio.
Es decir: se propone la mejor topología bajo ese modelo
MÉTODOS PARA ESTIMAR FILOGENIAS
• Parsimonia
• Máxima Verosimilitud
• Bayesiano
Métodos
Probabilísticos
• Parsimonia
Método que selecciona el árbol que requiera
La menor cantidad de pasos (= sustituciones)
Elige el árbol que requiera la menor cantidad
posible de sustituciones para explicar los
datos
Los algoritmos de parsimonia son rápidos
• MODELOS DE PARSIMONIA O SIMPLICIDAD
Valoran los cambios entre estados en unidades de
“pasos” o eventos evolutivos
Búsqueda de árboles
Se debe seleccionar un criterio para comparar los árboles
(= criterio de optimalidad)
• MODELOS DE PARSIMONIA O SIMPLICIDAD
Valoran los cambios entre estados en unidades de
“pasos” o eventos evolutivos
• Wagner
• Fitch
• Dollo
• Camin-Sokal
• MODELOS DE PARSIMONIA
Se contabilizan el número de cambios entre diferentes estados de caracteres
que son necesarios para explicar los datos observados dado un determinado árbol.
La hipótesis seleccionada es la que requiere menor cantidad de cambios. Esta
“cantidad de cambio” generalmente de refiere como longitud del árbol.
Los cambios pueden estar restringidos en cuanto al “tipo” de transformación que
se adopta (e.g. ordenados vs desordenados)
0 1 2 2 1 0 0 1 2
Parsimonia de Wagner o de Farris
Las posibilidades de cambios en ambos sentidos son iguales y se suma
un paso por cada cambio
• MODELOS DE PARSIMONIA
Se contabilizan el número de cambios entre diferentes estados de caracteres
que son necesarios para explicar los datos observados dado un determinado árbol.
0 1 2 0 2 1
0 1 2
Parsimonia de Fitch
Cada paso puede derivar de otro en cualquier orden. Todas las transformaciones
tienen un costo = 1
1 2 0
2 0 1
1 0 2
2 1 0 1 2 0
1 0 2
• Caracteres pueden diferir en su costo
(contribución a la longitud del árbol)
dependiendo del tipo de cambio asignado
• Wagner (ordenado, aditivo)
0 1 2 (morfología, distinto costo)
• Fitch (desordenado, no-aditivo)
A G (morphology, molecules)
T C (igual costo para todos los cambios)
Un paso
Dos pasos
• MODELOS DE PARSIMONIA
Se contabilizan el número de cambios entre diferentes estados de caracteres
que son necesarios para explicar los datos observados dado un determinado árbol.
Parsimonia de Dollo
Bajo el modelo de parsimonia de Dollo cada estado de carácter puede ganarse
solo 1 vez. Si la distribución del carácter no concuerda, entonces debe expresarse
como reversión. Se ha propuesto este modelo para trabajar con sitios de
restricción (donde la probabilidad de pérdida es mucho más alta que la de ganancia)
• MODELOS DE PARSIMONIA
Se contabilizan el número de cambios entre diferentes estados de caracteres
que son necesarios para explicar los datos observados dado un determinado árbol.
Parsimonia de Camin-Sokal
Restringe las transformaciones de los caracteres de forma tal que una vez que
un estado se adquiere no puede ser perdido , por la tanto las homoplasias deben
expresarse como adquisiciones múltiples
Todos estos procedimientos de optimización pueden tomarse como casos especiales
de un modelo de optimización generalizada, bajo el cual se le puede asignar un
“costo” a cada transformación. Tanto en el caso de Wagner o de Fitch, los costos
son simétricos (i.e el costo del cambio de 0 –1 = costo de 1 –0)
En el caso de la opción Dollo, M es un valor arbitrario alto que se aplica
que garantiza que solo ocurran transformaciones simples sobre el cladograma
En el caso de la opción Camin-Sokal, el costo infinito de las reversiones
impiden que esos cambios no ocurran
Matrices de costos • Matrices de costos especifican los costos
de los cambios en un caracter
A C G T
A 0 5 1 5
C 5 0 5 1
G 1 5 0 5
T 5 1 5 0
a
desde
G
C T
PURINAS (Pu)
PIRIMIDINAS (Py)
transiciones
Py Py
Pu Pu
tra
nsve
rsio
ne
s
Py
Pu
A
Datos faltantes (?)
? Datos no observados
Datos no aplicables
• Los datos faltantes son ignorados durante la construcción del árbol pero pueden
llevar a varias alternativas igualmente parsimoniosas en ausencia de homoplasias
• Una matriz can gran cantidad de datos faltantes puede llevar a la obtención
de un elevado número de árboles más parsimoniosos (soluciones espurias)
• Se han propuesto distintas métricas para medir como influye el comportamiento
de los datos faltantes en la resolución de los clados
A
B C
1
Se construye un árbol para
3 taxones (= root tree)
Se adiciona un cuarto taxón (D) en cada una de las 3 posiciones
posibles
2a
A
B D
C
A
B
D C
A
B C
D
2b 2c
BÚSQUEDAS EXACTAS - - - búsqueda exhaustiva
A
B C
1
Se comienza con tres taxones
cualquiera
Se adiciona un cuarto taxón (D) en cada una de las 3 posiciones
posibles
2a
A
B D
C
A
B
D C
A
B C
D
2b 2c E
E
E E
E
BÚSQUEDAS EXACTAS - - - menos de 11 taxones
BÚSQUEDAS EXACTAS - - - Branch & Bound
Reduce el tiempo de búsqueda descartando las familias de árboles
Se usa generalmente para menos de 20 taxones
- Se calcula un primer árbol de todos los taxones mediante la aplicación
de algún método heurístico.
- La longitud de este árbol se toma como límite superior (“upper bound”)
- Se procede de igual forma que en las búsquedas exhaustivas, pero la
longitud parcial de cada árbol se compara en cada caso. Si la longitud
parcial excede al límite superior el patrón de distribución de ese
arbol de abandona.
A
B C
B1
A
B D
C
A
B C
D
B3
A1
A
B E
D
C C1.1
A
B D
E
C C1.3
A
B D
C
E C1.2
A
B
C C1.4
E D
A
B C
C1.5
E D
A
B
D C
B2
BÚSQUEDAS EXACTAS - - - Branch & Bound
BÚSQUEDAS
Exactas
Heurísticas
Algoritmos exhaustivos
Branch and Bound
Algoritmos de permutación de ramas
( “Branch swapping”)
Dependiendo del número de taxones
- Construcción de un árbol no enraizado (network), por ejemplo mediante el
algoritmo de Wagner (Kluge & Farris, 1969, Farris, 1970)
Búsquedas heurísticas
- Permutación de ramas (“branch swapping”)
-Se cuenta la longitud de los árboles permutados y se retienen en memoria
los árboles más cortos
-Se repite el procedimiento hasta que no se encuentran árboles más cortos
- Construcción de un árbol no enraizado (network), por ejemplo mediante el
algoritmo de Wagner (Kluge & Farris, 1969, Farris, 1970)
Búsquedas heurísticas
Construcción de una matriz de Manhattan de distancias absolutas
Selección y conexión de los taxones más próximos
perca celacanto x
Se busca el taxon más próximo y se lo inserta en el intervalo
1 2 3 4 5 6
perca 0 0 0 0 0 0
celacanto 1 1 0 0 0 0
salamandra 1 0 1 0 0 1
rana 1 0 1 1 0 1
salamandra
perca celacanto x
perca celacanto salamandra rana intervalo
perca 2 5 5 3
celacanto 3 3 8
salamandra 0 7
rana 7
Se calcula el valor para X como el valor de la mediana entre los tres
Taxones (o nodos) más próximos
salamandra
perca celacanto x
1 2 3 4 5 6
perca 0 0 0 0 0 0
celacanto 1 1 0 0 0 0
salamandra 1 0 1 0 0 1
rana 1 0 1 1 0 1
100000
1 2 3 4 5 6
perca 0 0 0 0 0 0
celacanto 1 1 0 0 0 0
salamandra 1 0 1 0 0 1
x 1 0 0 0 0 0
Se busca la distancia patrística menor entre todas las adiciones posibles
de todos los taxones y cada uno de los tres intervalos
perca celacanto x
salamadra
1
2
3
Se une el taxón que este mas próximo de modo tal que produzca el incremento
menor en la longitud
perca celacanto x
salamadra
rana
100000
D (rana-in1) = [D (rana-perca)+ D (rana-X)- D perca- X)]/2
Se busca la distancia patrística menor entre todas las adiciones posibles
de todos los taxones y cada uno de los tres intervalos
perca celacanto x
salamadra
1
2
3
Se une el taxón que este mas próximo de modo tal que produzca el incremento
menor en la longitud
perca celacanto x
salamadra
rana
Se busca la distancia patrística menor entre todas las adiciones posibles
de todos los taxones y cada uno de los tres intervalos
perca celacanto x
salamadra
1
2
3
Se une el taxón que este mas próximo de modo tal que produzca el incremento
menor en la longitud
perca celacanto x
salamadra
rana y 101001
100000
Árbol de Wagner es un punto de partida para aplicar otras técnicas para aplicar
algoritmos de permutación de ramas
Distintas alternativas para construir el Árbol de Wagner:
SECUENCIAS DE ADICIÓN de taxones
- Los taxones pueden incorporarse en el orden en que están en la matriz
- al azar
- de acuerdo con la distancia con respecto al grupo externo (= outgroup)
como en el ejemplo anterior
Algoritmos de PERMUTACIÓN DE RAMAS
Nearest Neighbour Interchange
Subtree Pruning and Regrafting (SPR)
Tree Bisection and Reconnection (TBR)
Algoritmos de PERMUTACIÓN DE RAMAS
Subtree Pruning and Regrafting (SPR)
Tree Bisection and Reconnection (TBR)
Nearest Neighbour Interchange (NNI)
BÚSQUEDAS HEURÍSTICAS - - - Permutación de ramas
Nearest neighbour interchange (NNI)
A
B
C D E
F
G
A
B
D C E
F
G
A
B
C D
E
F
G
Subtree pruning and regrafting (SPR)
A
B
C D E
F
G
C D E
F
G
C
D
G
B
A
E F
BÚSQUEDAS HEURÍSTICAS - - - Permutación de ramas
Se separa en un subcladograma
enraizado y se lo conecta en otra parte
del árbol
BÚSQUEDAS HEURÍSTICAS - - - Permutación de ramas
Tree bisection and reconnection (TBR)
A
B
C DE
F
G
A
B
CD
E
F
G
A
C
F
D
E
B G
El cladograma se divide en subcladogramas
sin raíz que luego se re-conectan
Búsquedas heurísticas. Permutación de ramas
Àrbol inicia T1
(e.g. Wagner)
Longitud = L1
Permutaciòn
de ramas.
Nuevo árbol
T2
Longitud L2
Reemplazar
T1 por T2
Búsquedas heurísticas. Permutación de ramas
Àrbol inicia T1
(e.g. Wagner)
Longitud = L1
Permutaciòn
de ramas.
Nuevo árbol
T2
Longitud L2 Borrar T2
Reemplazar
T1 por T2
Búsquedas heurísticas. Permutación de ramas
Àrbol inicia T1
(e.g. Wagner)
Longitud = L1
Permutaciòn
de ramas.
Guardar T2
Nuevo árbol
T2
Longitud L2 Borrar T2
Reemplazar
T1 por T2
BÚSQUEDAS HEURÍSTICAS
Problema de las islas de árboles
Islas: conjunto de árboles que están separados por una solo permutación de ramas
Problema: una vez que se encontró el árbol más corto dentro de una isla (por re-
ordenamiento de sus ramas) no se podrá llegar a las topologías que estén en otra
isla
Solución: partir de varios árboles de Wagner generados por secuencias de
adición al azar
Los algoritmos heurísticos
se pueden “trabar” en los máximos y
mínimos locales
Una solución es iniciar las búsquedas a
partir de varios árboles (eg. Wagner )
con secuencies de adición al azar
Búsqueda
del mínimo
global MÁXIMO
GLOBAL
MÍNIMO
GLOBAL
mínimo
local
máximo
local
Búsqueda
del máximo
global
MÍNIMO
GLOBAL
MÁXIMO
GLOBAL