Uma Visão Geral SobreReconstrução Filogenética

André Ricardo – arsl@cin.ufpe.brMarlus Barbosa

– mbs2@cin.ufpe.br

AgendaFilogeniaUso da filogenia em pesquisa biológicaEtapas da análise filogenéticaProblemas de pesquisa em filogenia

molecularMétodos de reconstrução de árvores

filogenéticasConclusão

Filogenia

Uso Da FilogeniaUtilizaçõ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 EstudoAmostragem:

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çãoQual a melhor reconstrução?

Medida de Confiabilidade.Arestas.

Data-mining. Abordagem combinatória. Abordagem estatística.

Suporte à Avaliação:Abordagem CombinatóriaTé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ítmicaSimulaçã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-escalaMétodos NP-hardConjunto das melhores árvoresDados desconhecidosMSA 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ômicasAo 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õesMé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.