Download MAXIMA PARSIMONIA

- Inferir una filogenia es un proceso de estimación. Se hace la “mejor
estimación” de una historia evolutiva con base en la información parcial
o incompleta que representan los datos disponibles
- Debido a que se pueden postular diferentes escenarios evolutivos con
los datos evaluados, es necesario contar con un criterio definido para
seleccionar uno o más árboles preferidos de entre las múltiples
hipótesis que se pueden producir
MAXIMA PARSIMONIA
EN LA INFERENCIA FILOGENÉTICA
DE SECUENCIAS DE ADN
CEAMISH - UAEM
Máxima Parsimonia
Tree 3
C
A
B
A
B
B
D
C
D
D
C
-El definir un criterio óptimo al comparar filogenias alternativas,
permite decidir cuál es la mejor (o si varias de ellas son igualmente
buenas)
Francisco X. González-Cózatl
@2007González-Cózatl
Tree 2
Tree 1
A
1
- En un contexto general, el criterio de Parsimonia significa simplicidad
o economía
- Metodológicamente, este principio postula la elección de la hipótesis
más sencilla entre varias hipótesis concurrentes
@2007González-Cózatl
Máxima Parsimonia
2
- A diferencia de los métodos de distancias, bajo el criterio de
parsimonia (y ML – BI) los datos a evaluar corresponden a cada posición
o sitio en la secuencia de nucleótidos o aminoácidos = DATOS
DISCRETOS (vs. datos continuos)
MP, ML, BI
- Aplicado a la Sistemática Filogenética el criterio de parsimonia
conduce a la elección del cladograma o árbol filogenético que explica la
filogenia de un grupo con el menor número de cambios evolutivos
Distancias
- La primera mención de la aplicación del
criterio de Parsimonia en filogenia fue
realizada por Edwards y Cavalli-Sforza en
1963; el árbol evolutivo preferido debe ser
aquel que involucre “la cantidad mínima neta
de evolución”
@2007González-Cózatl
Máxima Parsimonia
3
- Aunque en muchas ocasiones, el criterio de distancias genera
resultados iguales a los de MP, este último método permite identificar
que sitios (caracteres) están contribuyendo a la topología de la
filogenia y a la longitud de las ramas
@2007González-Cózatl
Máxima Parsimonia
4
- La premisa básica en Parsimonia es que los taxa que comparten una
característica (similitud), lo hacen porque heredaron esa característica
de un ancestro común = HOMOLOGÍA
- Cuando este supuesto no se cumple, esta similitud se explican por
eventos como reversión, convergencia o paralelismo, que en conjunto se
agrupan bajo el término = HOMOPLASIA
@2007González-Cózatl
Máxima Parsimonia
5
@2007González-Cózatl
Máxima Parsimonia
6
1
- Para cada sitio, se busca reconstruir la evolución del mismo en un
árbol, con la condicionante de recurrir al menor número de cambios
1
2
3
4
A
A
G
G
T
T
C
C
A
C
A
C
T
G
G
G
-Este proceso se repite para otros posibles árboles
T
T
T
T
1
2
3
4
A
A
G
G
T
T
C
C
A
C
A
C
T
G
G
G
T
T
T
T
Tree 2
Tree 1
Tree 3
1
3
1
2
1
2
2
4
3
4
4
3
Site 1
@2007González-Cózatl
Máxima Parsimonia
7
@2007González-Cózatl
Máxima Parsimonia
8
-Como se observa, los sitios 4 y 5 tienen el mismo número de pasos para
los tres árboles y por los tanto no discriminan entre estas tres
alternativas.
- Entonces, bajo el criterio de parsimonia se pueden reconocer sitios o
caracteres que SI contribuyen a decidir cual sería el árbol óptimo (de
menor número de pasos), mientras que otros NO son útiles para este
fin
1
2
3
4
- Evidentemente, aquellos sitios que no son variables (constantes), como
el 5, no son informativos en parsimonia y no se incluyen en un análisis
A
A
G
G
T
T
C
C
A
C
A
C
T
G
G
G
T
T
T
T
Tree 2
Tree 1
Tree 3
1
3
1
2
1
2
2
4
3
4
4
3
- De los caracteres variables, aquellos en los que solo una secuencia o
taxón es diferente (4), tampoco son informativos porque la variación en
ese sitio siempre puede ser explicada con el mismo número de pasos en
cualquier árbol
- Solo los sitios en donde más de dos secuencias tienen en mismo
estado (1, 2, 3) son considerados filogenéticamente informativos
1
2
3
4
@2007González-Cózatl
Máxima Parsimonia
9
1
A
A
G
G
2
T
T
C
C
3
A
C
A
C
@2007González-Cózatl
4
T
G
G
G
5
T
T
T
T
Máxima Parsimonia
10
- Parsimonia no pesada o sin pesos (unweighted MP)
- Aunque existen distintas variantes de métodos en Parsimonia, en
general pueden ser divididas en dos grupos:
- Dentro de este grupo, el método o algoritmo más común es el de
Fitch (1971) que asume un paso al cambio entre cualquier estado
-Parsimonia no pesada o sin pesos (unweighted MP)
-Se asume que sustituciones de nucleótidos
o aminoácidos ocurren en todas direcciones
con la misma (o casi la misma) probabilidad
-Parsimonia pesada (weighted MP)
- Este algoritmo permite contabilizar el número de cambios en un
árbol bifurcado o binario con datos de secuencias, en las cuales
cualquiera de las cuatro bases (A, C, G, T) puede cambiar hacia
cualquier otra
-Se asume que algunas sustituciones (e.g.
transiciones) ocurren más frecuentemente
que otras (e.g. transversiones), y en
consecuencia, resulta razonable asignar
diferente peso a los distintos tipos o
eventos de sustituciones
@2007González-Cózatl
Máxima Parsimonia
11
@2007González-Cózatl
Máxima Parsimonia
12
2
-Algoritmo de Fitch
-Algoritmo de Fitch
- Se inicia considerando que cada uno los estados en los nodos
terminales corresponde a los nucleótidos observados en la
secuencia, con una longitud acumulada de cero
W
X
Y
Z
G
A
C
C
G
T
G
G
A
T
A
G
-En cada nodo interno, los estados ancestrales corresponderán a la
intersección de los estados de los nodos descendientes. La
longitud acumulada será la suma de los nodos descendientes
-Si la intersección de los estados de los nodos descendientes esta
vacía, entonces el estado del nodo ancestral es la unión de dichos
estados. La longitud acumulada será la suma de los nodos
descendientes más uno (+ 1)
C
C
T
C
- Para calcular los estados de los nodos internos (1,2,3) se siguen
dos reglas simples:
@2007González-Cózatl
Máxima Parsimonia
13
-Parsimonia pesada (weighted MP)
@2007González-Cózatl
-Pesando el carácter
- En genes que codifican para una proteína, los nucleótidos de
los cada una de las posiciones del codón evolucionan a distintas
tasas de cambio:
-Por lo tanto, resulta razonable asignar un peso diferencial a los
diferentes sitios de la secuencia (carácter) o distintos tipos de
sustitución (estado del carácter) en función de su posible
aportación en la inferencia filogenética
2A
LENTA
-En cualquier caso, el objetivo es dar un mayor peso a los cambios
que son raros, los cuales son menos probables que sean
homoplásicos (particularmente cuando las tazas de cambio son
altas) y por lo tanto, más probables que reflejen la historia
filogenética
Máxima Parsimonia
14
-Parsimonia pesada (weighted MP)
-Considerando que algunos tipos de sustituciones son más
frecuentes que otros, o que algunos sitios evolucionan más
rápidamente que otros, la asignación del mismo costo a todos los
cambios podría resultar en árboles poco confiables
@2007González-Cózatl
Máxima Parsimonia
15
-Parsimonia pesada (weighted MP)
1A
3A
RÁPIDA
TASA EVOLUCIÓN
2A
1A
3A
MENOR
MAYOR
PESO
@2007González-Cózatl
Máxima Parsimonia
16
-Parsimonia pesada (weighted MP)
-Pesando el estado del carácter
-Pesando el estado del carácter
- Considerando que los transiciones por lo general ocurren más
frecuentemente que las trasversiones, resulta conveniente
darle mayor peso a estas últimas
- Los esquemas de pesos pueden implementarse de manera
empírica, probando distintas opciones ó en función del modelo
evolutivo que mejor se ajuste a los datos de secuencias
- Esto se puede implementar construyendo una matriz de
costos ó de pasos
- Un caso extremo de parsimonia pesada representa la
“Parsimonia de transversión” en donde las transiciones no son
consideradas en el análisis
Pars. Transv.
A
C
G
T
@2007González-Cózatl
Máxima Parsimonia
17
A
0
1
0
1
C
1
0
1
0
G
0
1
0
1
T
1
0
1
0
@2007González-Cózatl
5:1
A
C
G
T
A
0
5
1
5
C
5
0
5
1
G
1
5
0
5
10 : 1
T
5
1
5
0
Máxima Parsimonia
A
C
G
T
A C G T
0 10 1 10
10 0 10 1
1 10 0 10
10 1 10 0
18
3
-Parsimonia pesada (weighted MP)
-Métodos de búsqueda de árboles óptimos
- En cualquier caso, la estrategia de pesos que se implemente
deberá estar en función del grado de divergencia entre las
secuencias que se están analizando
- Aunque el criterio de Máxima Parsimonia nos permite aceptar
como la mejor hipótesis el árbol con el menor número de cambios
evolutivos, en la práctica, el reto es encontrar ese árbol entre los
múltiples árboles posibles que se pueden generar con los datos
- Cuando los niveles de divergencia son bajos, es posible que,
incluso, los métodos de parsimonia sin pesos funcionen
adecuadamente y se pueda obtener la filogenia correcta
-Incluso con solo pocas secuencias o taxa, se puede producir un
número importante de árboles
-Exclusión de información como 3as. posiciones o transiciones
puede tener implicaciones en la pérdida de información para
recuperar relaciones entre secuencias poco divergentes
@2007González-Cózatl
Máxima Parsimonia
-El número de posibles árboles se incrementa de manera factorial
con cada nueva secuencia o taxon
19
-Métodos de búsqueda de árboles óptimos
@2007González-Cózatl
Máxima Parsimonia
20
-Métodos de búsqueda de árboles óptimos
-Número de posibles árboles binarios sin raíz (Nu)
Nu = A (2i-5)
T
i =3
(2·3-5) (2·4-5) (2·5-5)... (2·T-5)
-Número de posibles árboles binarios con raíz (Nr)
Nr = A (2i-3)
T
i =2
(2·2-3) (2·3-3) (2·4-3)... (2·T-3)
@2007González-Cózatl
Máxima Parsimonia
21
-Métodos de búsqueda de árboles óptimos
-Métodos heurísticos (aproximados)
-Se intenta encontrar soluciones óptimas, pero no hay garantía
de hallarlas (en este caso el árbol óptimo). No obstante, se
reduce el tiempo de análisis cuando se evalúan datos con un
gran número de taxa
- Adición secuencial (Stepwise addition)
- Permutación de ramas (Branch swapping)
- Descomposición de estrella (Star decomposition)
Máxima Parsimonia
Máxima Parsimonia
22
-Métodos de búsqueda de árboles óptimos
-Algoritmos exactos
-Se garantiza que se encontrará el árbol ó árboles óptimos,
pero puede requerirse una gran cantidad de tiempo de cómputo
- Búsqueda exhaustiva
- Búsqueda “branch and bound”
@2007González-Cózatl
@2007González-Cózatl
23
-Búsqueda Exahustiva
- Cuando el número de secuencias o taxa no es muy grande
(‹ 10), es posible calcular la longitud de todos los posible
árboles y determinar cuál es el más parsimonioso
- El procedimiento para generar todos los árboles posible sin
raíz es el siguiente
@2007González-Cózatl
Máxima Parsimonia
24
4
-Métodos de búsqueda de árboles óptimos
-Métodos de búsqueda de árboles óptimos
-Búsqueda Branch and Bound
- Este algoritmo opera al evaluar implícitamente todos los
árboles posibles, pero evitando rutas, en la búsqueda de
árboles, en donde se determina que no conducirán a árboles
óptimos
-Búsqueda
Exahustiva
- En la práctica solo se evalúan aquellos árboles que no exceden
un determinado valor, que es establecido como límite superior
- Este límite superior representa el valor de longitud o
probabilidad de cualquiera de los posibles árboles que se
pueden generar con las secuencias o taxa analizados
-Útil para evaluar hasta 25 secuencias o taxa
@2007González-Cózatl
Máxima Parsimonia
25
-Métodos de búsqueda de árboles óptimos
@2007González-Cózatl
Máxima Parsimonia
26
-Métodos de búsqueda de árboles óptimos
-Búsqueda Branch and Bound
- Este método genera los árboles de forma similar a la
búsqueda exhaustiva, pero cada vez que se adiciona una nueva
secuencia o taxón en una de las ramas del árbol en construcción
se calcula el valor del mismo (longitud o probabilidad)
- Si este valor no excede el límite superior establecido, se
continua adicionando nuevas secuencias o taxa
-Búsqueda
Branch and
Bound
- Cuando el valor de un árbol incompleto (no incluye todas las
secuencias) supera el límite superior se detiene la búsqueda en
esa ruta
- Si el valor de un árbol completo es mejor que límite superior,
se convierte en el nuevo límite de referencia
@2007González-Cózatl
Máxima Parsimonia
27
-Métodos de búsqueda de árboles óptimos
Máxima Parsimonia
28
-Métodos de búsqueda de árboles óptimos
-Búsquedas aproximadas
-Búsquedas aproximadas
- En función de que cada uno de los métodos heurísticos por si
mismos no garantizan encontrar la solución óptima, varios
programas (PAUP y otros) utilizan un sistema de dos fases para
realizar búsquedas aproximadas
- En una primera etapa, un árbol inicial es generado usando un
algoritmo que construye este de adicionando secuencias o taxa
de forma secuencial (Stepwise addition)
-En una segunda fase, el árbol obtenido es sometido a una serie
de rearreglos o permutaciones de ramas (Branch swapping) con
los que se intenta mejorar su valor. El proceso continua hasta
que ya no es posible encontrar una mejor solución
@2007González-Cózatl
@2007González-Cózatl
Máxima Parsimonia
29
- En general los búsquedas heurísticas son referidas como un
proceso de escalada o ascenso a la cima (Hill-climbing).
-Dependiendo del sitio en donde se inicie el ascenso se podrá
llegar o no a la cima más alta en una zona montañosa
- En filogenia, la cima más alta
corresponde al árbol óptimo,
es decir el más parsimonioso ó
el más probable
@2007González-Cózatl
Máxima Parsimonia
30
5
-Métodos de búsqueda de árboles óptimos
-Métodos de búsqueda de árboles óptimos
-Adición secuencial (stepwise addition)
- Este algoritmo funciona de forma similar al proceso seguido
en las búsquedas Exahustiva y de Branch and Bound, pero
difiere en que cada vez que se adiciona una nueva secuencia o
taxón se calcula el valor de los árboles generados y únicamente
se continua con el árbol que en esa fase o paso parece ser la
mejor solución
- Adición secuencial
-El inconveniente es que esa ruta que se sigue no
necesariamente conduce a la solución óptima y se puede quedar
“entrampado” en un solución subóptima
-El proceso termina cuando se han incorporado todas las
secuencias o taxa
@2007González-Cózatl
Máxima Parsimonia
31
-Métodos de búsqueda de árboles óptimos
@2007González-Cózatl
Máxima Parsimonia
32
-Métodos de búsqueda de árboles óptimos
- Adición secuencial
- Permutación de ramas (brach swapping)
- Con el propósito de encontrar la mejor solución con este
algoritmo, se recomienda repetir el proceso varias veces
(réplicas) y que la adición de secuencias sea al azar
- Una vez que se ha generado un árbol inicial (mediante la
adición secuencial), se pueden implementar los métodos de
intercambio de ramas, los cuales involucran el corte del árbol
en uno o varios segmentos y un reensamble posterior de estos
elementos de tal forma que se obtenga un árbol distinto al
original
- Con esto se trata de iniciar la búsqueda desde distintos
puntos en el espacio de árboles posibles, esperando que al
menos una de esta rutas conduzca al árbol óptimo
- Al realizar estos rearreglos se intenta mejorar el valor del
árbol inicial. Si el valor del nuevo árbol no mejora, este se
rechaza y se regresa al árbol previo. Si el valor mejora, se
guarda el nuevo árbol y se intentan nuevos rearreglos
-El proceso se detiene cuando rearreglos adicionales no
mejoran el valor del mejor árbol guardado
@2007González-Cózatl
Máxima Parsimonia
33
-Métodos de búsqueda de árboles óptimos
@2007González-Cózatl
Máxima Parsimonia
34
- Justificaciones y objeciones para Parsimonia
- Rearreglos
- En general los métodos de parsimonia pueden ser muy eficaces
bajo diferentes escenarios evolutivos, sin embargo, se ha
demostrado que resultan más efectivos cuando las tasas de
evolución de los taxa analizados son lentas
- No obstante, se ha señalado que bajo ciertos escenarios
parsimonia puede ser potencialmente inconsistente, es decir, que
puede conducir a una solución equivocada (filogenia incorrecta)
incluso cuando se adicionan más datos al análisis
- Métodos de
permutación
de ramas
- El escenario clásico donde esto podría pasar, se conoce como el
fenómeno de atracción de ramas largas
+ Rearreglos
@2007González-Cózatl
Máxima Parsimonia
35
@2007González-Cózatl
Máxima Parsimonia
36
6
- Justificaciones y objeciones para Parsimonia
- Justificaciones y objeciones para Parsimonia
-El fenómeno de atracción de ramas largas se refiere a situaciones
en las que linajes o secuencias con una tasa de cambio muy
acelerada aparentemente muestran una relación muy estrecha, a
pesar de que esta no sea necesariamente cierta
- Para que parsimonia recupere el árbol correcto ((1,2),(3,4)) deben
existir más sitios apoyando la relación (1,2) / (3,4) que la topología
alternativa (1,4) / (2,3)
- Si la rama interna es relativamente más corta que las ramas
terminales, es muy posible entonces que por casualidad (azar) 1 y 4
hallan adquirido el mismo nucleótido independientemente
- Estas convergencias podrían
sobrepasar el número de sitios
que cambian en la rama interna
y así favorecer, bajo el enfoque
de parsimonia, el árbol incorrecto
@2007González-Cózatl
Máxima Parsimonia
37
- Justificaciones y objeciones para Parsimonia
- La probabilidad de encontrar sitios que covarian tiende a
reducirse cuando ramas largas se encuentran distantes
evolutivamente
Máxima Parsimonia
Máxima Parsimonia
38
- Justificaciones y objeciones para Parsimonia
- El potencial problema de la ramas largas no es en si la longitud de
las ramas, sino que sustituciones idénticas (homoplasias) hayan
ocurrido a lo largo de las dos ramas
@2007González-Cózatl
@2007González-Cózatl
39
- Una estrategia para reducir el posible efecto de atracción de
ramas largas consiste en la adición de secuencias que pudieran
unirse a estas ramas largas con el fin de romperlas y reducir su
longitud
@2007González-Cózatl
Máxima Parsimonia
40
7