Uma Visão Geral Sobre
Reconstrução Filogenética
André Ricardo
– [email protected]
Marlus Barbosa
– [email protected]
Agenda
 Filogenia
 Uso da filogenia em pesquisa biológica
 Etapas da análise filogenética
 Problemas de pesquisa em filogenia molecular
 Métodos de reconstrução de árvores filogenéticas
 Conclusão
Filogenia
Uso Da Filogenia
 Utilizações diversas e crescentes:
 Estudo comparativo.
 Testar hipóteses biogeográficas.
 Inferir informações “extintas”.
 Rastrear evolução de doenças.
 Casos criminais.
Análise Filogenética,
como é feita na prática?
Etapas:
Projeto Do Estudo
 Amostragem:
 Taxon, Tamanho, Geografia, Presença de amostra.
 Características:





Não-recombinável (mitocôndrias, cloroplastos).
De única cópia genética.
Prontamente amplificável (PCR).
Facilmente seqüenciados.
Boa velocidade de evolução.
Etapas:
Coleta De Organismos
Etapas:
Laboratorial
Etapas:
Alinhamento Múltiplo
Etapas:
Reconstrução Filogenética (1/8)
 Modelos estocásticos:
 Jukes-Cantor (JC).
 General Time Reversible (GTR).
 Padrão de evolução:
 Início na raiz,
 Evolução sobre a árvore.

Mudança de estados.
Etapas:
Reconstrução Filogenética (2/8)
 Freqüência de evolução:
Etapas:
Reconstrução Filogenética (3/8)
 Modelo JC:
 “Se um sítio muda seu estado, ele muda com igual
probabilidade para os outros estados”.
Etapas:
Reconstrução Filogenética (4/8)
 Modelo GTR:
 Reversível no tempo.
 Mudança de estado,

Matriz de substituição 4x4.
Etapas:
Reconstrução Filogenética (5/8)
 Métodos:
 Distância dos pares.

Tempo polinomial; rápida e prática.
 Maximum Parsimony (MP), Maximum Likelihood (ML).
 Markov Chain Monte Carlo (MCMC).
Etapas:
Reconstrução Filogenética (6/8)
 Método MP:
 Entrada: conjunto S de seqüências, de tamanho k, em
um alinhamento múltiplo.
 Saída: árvore T, cujas folhas são referenciadas por S, e
com seqüências adicionais, todas de tamanho k,
referenciando os nós internos de T, que minimiza a
fórmula:
 NP-hard.
Etapas:
Reconstrução Filogenética (7/8)
 Método ML:
 Entrada: Conjunto S de seqüências de mesmo tamanho,
e um valor B.
 Saída: Uma árvore modelo (T,p), de modo que
Pr[S|T,p] >= B, senão falha.
 NP-hard.
Etapas:
Reconstrução Filogenética (8/8)
 Método MCMC:
 “Random walk”.
 A saída não é uma árvore.

Distribuição de probabilidade.
Etapas:
Suporte à Avaliação
 Qual a melhor reconstrução?
 Medida de Confiabilidade.
 Arestas.



Data-mining.
Abordagem combinatória.
Abordagem estatística.
Suporte à Avaliação:
Abordagem Combinatória
 Técnica do consenso:
 Conjunto de melhores árvores.

Inicialmente igualmente confiáveis.
 Inferência da melhor árvore.

Bipartição induzida de arestas.
Suporte à Avaliação:
Abordagem Estatística (1/2)
 The Bootstrap:
 Reamostragem.
 “Árvore Bootstrap”.
 Comparação com a árvore reconstruída:

Armazenamento de informações sobre as arestas.
Suporte à Avaliação:
Abordagem Estatística (2/2)
 The Jackknife:
 Remoção aleatória de sítios.
 Reconstrução.
 MCMC:
 Freqüência de cada árvore visitada.
Problemas De Pesquisa Em
Filogenia Molecular
Problemas De Pesquisa:
Análise De Performance Algorítmica
 Simulação:
 Escolha de um modelo estocástico de evolução.
 Seqüência de tamanho qualquer.


Evolução sobre a árvore T.
Adição de outras sequências nas folhas.
 Método de reconstrução.

Reconstrução da árvore T’.
 Comparação T versus T’.
Problemas De Pesquisa:
Reconstrução Filogenética (1/3)
 Buscas heurísticas para MP e ML:
 Baseadas em hill-climbing.


Máximo local.
Fuga do máximo local: The Ratchet.
 Tempo impraticável.
Problemas De Pesquisa:
Reconstrução Filogenética (2/3)
 MP:
Por que MP é tão bom?
Problemas De Pesquisa:
Reconstrução Filogenética (3/3)
 ML:
Comparar possíveis scores.
Problemas De Pesquisa:
Alinhamento Múltiplo (MSA)
Nenhum critério atingiu aceitação geral...
Problemas De Pesquisa:
Filogenia em Larga-escala
 Métodos NP-hard
 Conjunto das melhores árvores
 Dados desconhecidos
 MSA complicado
Aspectos De Reconstrução De
Árvores Filogenéticas (1/2)
 Árvores:
 Topologia.
 Distância entre nós.
 Raiz.
Aspectos De Reconstrução De
Árvores Filogenéticas (2/2)
 Entradas:
 Características discretas (matriz de estados).
 Dados numéricos comparativos (matriz de distâncias).
 Características contínuas.
Problema Da Filogenia Perfeita
(1/3)
 Dados um conjunto de objetos e um conjunto de
características, temos uma matriz de estados.
 Problemas ao se criar uma filogenia:
 Convergência ou evolução paralela.
 Reversões.
 Para evitar isso, na árvore T desejada, queremos
que, para cada estado de uma característica, o
conjunto de todos os nós que possuem essa
característica forme uma subárvore.
Problema Da Filogenia Perfeita
(2/3)
 Computacionalmente difícil.
 Mas pode ser simplificado em casos especiais:
 Características binárias.
 Duas características.
Problema Da Filogenia Perfeita
(3/3)
Filogenia Com Matrizes De
Distância (1/7)
 Dois problemas:
 Dada uma matriz de distâncias, construir uma árvore
com arestas com peso, onde cada folha seja apenas um
objeto da matriz e tal que as distâncias entre duas folhas
correspondam às distâncias dadas na matriz.
 Esse problema exige que as distâncias na matriz sejam
aditivas, uma condição pouco comum. Daí surge o
segundo problema:
 Construir a árvore com duas matrizes, que servirão como
limites superior e inferior das distâncias entre os objetos.
Filogenia Com Matrizes De
Distância (2/7)
 Árvores aditivas.
 Matriz de entrada precisa ser um espaço métrico aditivo.
 O algoritmo consiste em calcular a árvore para dois
objetos (uma aresta) e a partir daí acrescentar outros
objetos.
Filogenia Com Matrizes De
Distância (3/7)
Filogenia Com Matrizes De
Distância (4/7)
 O problema com árvores aditivas é que distâncias dois
a dois sempre possuem incertezas.
 Utilizar duas matrizes.
 Limites inferior e superior.
 Árvores ultramétricas:
 Árvores enraizadas, tais que o comprimento de todos os
caminhos raiz-folha seja igual.
Filogenia Com Matrizes De
Distância (5/7)
 Minimum Spanning Tree (MST).
 Calcular Cut-Weights para cada aresta.
 Construir a árvore propriamente.
Filogenia Com Matrizes De
Distância (6/7)
Filogenia Com Matrizes De
Distância (7/7)
Métodos Supertree (1/5)
 Tentam estimar a história evolucionária de um
conjunto através das histórias dos seus
subconjuntos.
 “Tree of Life”.
 Recomendado para problemas de larga escala e
com dados faltando.
 Meta análises.
 Supermatrizes.
 Métodos supertree podem ser usados como parte
de uma estratégia dividir e conquistar.
Métodos Supertree (2/5)
 Compatibilidade de árvores.
 Refinamento.
 Compatibilidade.
 Problema: dado um conjunto de árvores, cada um sobre um
conjunto de características, encontrar uma árvore que
refine todas as árvores do conjunto.
 Problema NP-hard.
 Caso em que as árvores são enraizadas: tempo
polinomial.
 Infelizmente, as entradas para o problema tendem a não ser
compatíveis.
Métodos Supertree (3/5)
Métodos Supertree (4/5)
 Matrix Representation Parsimony (MRP).
 Método que lida com incompatibilidades nas entradas.
 Cria uma matriz para cada árvore, concatena todas as
matrizes e analisa a matriz concatenada com o método
de máxima parsimônia.
 Apesar de ser bom na teoria, sua aplicação prática é
pouco clara.
Métodos Supertree (5/5)
 Existem outros métodos que lidam com árvores que
contém erros.
 Consenso estrito de Gordon e DCM.
 Apesar do potencial dos métodos pouco se sabe sobre
seu funcionamento com dados reais.
Reconstrução De Filogenias
Genômicas
 Ao invés de analisar seqüências, analisa genomas
completos.
 Modificações genômicas e análises mais profundas.
 Modelos estatísticos pouco desenvolvidos.
 Computacionalmente muito mais complexo.
Conclusões
 Métodos de reconstrução filogenéticas apresentam
desafios profundos e complexos.
 Compreender aspectos como dados e métodos e como
os biólogos usam filogenias pode ser crucial.