Métodos para inferências filogenéticas

17/10/2012
Árvore filogenética
• Representação gráfica das relações de
ancestralidade entre os diversos táxons analisados
Inferência
filogenética
1
Táxons:
2
nós terminais
3
4
Métodos de máxima parcimônia (MP) e
máxima verossimilhança (MV)
Ancestrais:
5
nós internos
0.5
Árvore filogenética
Árvore filogenética
• Árvore sem raiz
• Árvore sem raiz
o não infere sobre o sentido do processo evolutivo
o não infere sobre o sentido do processo evolutivo
1
2
1
1
2
2
3
3
4
3
4
5
4
5
0.5
5
0.5
Árvore filogenética
3
• Árvore sem raiz
3
Árvore filogenética
• Árvore sem raiz
4
4
0.5
0.5
2
2
1
1
5
5
1
17/10/2012
Árvore filogenética
• Árvore com raiz
Árvore filogenética
• Árvore com raiz
o “Escolhido” o taxon 5 para ser raiz
o Taxon “5” NÃO é o ancestral!!!!
o “Escolhido” o taxon 5 para ser raiz = “outgroup”
o Certeza de que não tem ancestralidade recente com algum dos taxons
do “ingroup”
1
2
3
4
5
0.5
Árvore filogenética
Quantas árvores
possíveis existem para
4 taxons?
Com raiz ou sem raiz?
Sem
Raiz
Árvore filogenética
Com
Raiz
Árvore filogenética
• Além da topologia: comprimento dos ramos
o diferenças de nucleotídeos (distância, dependendo do
modelo evolutivo calculado) ou número de alterações ou
tempo de divergência**
o ** se as taxas evolutivas forem as mesmas para todos os
taxons.
o exemplo: roedores tem taxas evolutivas mais altas entre os
mamíferos (comparar as diferenças entre taxons do ingroup
com taxons do outgroup – devem ter valores similares)
2
17/10/2012
Inferência filogenética
• Métodos para inferência
o Métodos fenéticos:
medem um conjunto de distâncias e
gera uma topologia após
agrupamento hierárquico
o Métodos cladísticos:
inferem características ancestrais em
cada uma das topologias possíveis e
escolhe a reconstrução de acordo
com alguma premissa evolutiva
Inferência filogenética
Inferência filogenética
• Métodos para inferência
o Métodos fenéticos:
distância
o Métodos cladísticos:
máxima parcimônia e máxima
verossimilhança
Máxima Parcimônia
• Máxima parcimônia
o Nucleotídeos do taxon ancestral são inferidos
separadamente (para cada sítio) em cada uma das
possíveis topologias não enraizadas para aquele
determinado número de taxons analisados
EXERCÍCIOS
o Quanto maior o número de taxons, maior será o número
de topologias a serem verificadas
o A topologia que no final computar o menor número de
subsituições será a melhor árvore
Máxima Parcimônia
Máxima Parcimônia
• Na Máxima parcimônia, a partir de um
alinhamento, os sítios:
o invariáveis são descartados (invariable sites)
o que possuem mutações que aparecem apenas uma vez
são descartados (singleton sites)
o que possuem mutações que aparecem pelo menos duas
vezes são utilizados (parsimony informative sites)
1: A
2: A
3: A
4: G
5: G
6: T
Sítio
informativo
para MP
3
17/10/2012
Máxima Parcimônia
Máxima Parcimônia
• Na Máxima Parcimônia,
o A topologia que no final computar o menor número de
subsituições será a melhor árvore
1: A
2: A
3: C
4: T
5: G
6: A
o Premissa evolutiva: menor número de passos para explicar
o processo evolutivo
Sítio NÃO
informativo
para MP
Máxima Parcimônia
• Na Máxima Parcimônia,
o É possível estabelecer pesos para as substituições, de
forma que as alterações não serão todas iguais, por
exemplo:
• transversões > transições
• 2a posição do codon > 1a posição > 3a posição
o Tree length ou length
Máxima Verossimilhança
• Máxima Verossimilhança
o Nucleotídeos do taxon ancestral também são inferidos
separadamente (para cada sítio) em cada uma das possíveis
topologias não enraizadas para aquele determinado número
de taxons analisados
o Quanto maior o número de taxons, maior será o número de
topologias a serem verificadas
o unweight MP x weight MP
o A cada subsituição inferida, será atribuído um valor de
probabillidade ,com base em um modelo conhecido a priori
o Premissa evolutiva única sendo descontruída: “passões” e
“passinhos”
o A topologia que no final computar um conjunto de
subsituições com o maior valor de probabilidade será a
melhor árvore (todos os valores são somados)
Máxima Verossimilhança
• Máxima Verossimilhança
Máxima Verossimilhança
• esta é uma das topologias não enraizadas entre as
3 possíveis para organizar os 4 taxons…
o Considere o alinhamento para os 4 taxons seguir:
#1
#2
#3
#4
……TCAAAAATGCGCTTTATT……
……TCAGTGATGTGCGTGAAT……
……TTAGAAATGTGCTTGATT……
……TTAGTGATGGGCTTTATC……
o Considere o sítio i marcado em vermelho
#2 T
#1 C
X
#4 G
Y
I
#3 T
4
17/10/2012
Máxima Verossimilhança
• lembre: há tres topologias possíveis para 4 taxons!
III
II
Máxima Verossimilhança
• voltamos à topologia I, considerando o sítio
marcado em vermelho (sítio i):
#1 C
#2 T
existem 16 possibilidades
para X e Y
X
Y
#4 G
X pode ser:
A,T,C,G
I
Máxima Verossimilhança
• Considere uma das 16 possibilidades:
Onde X=A e Y=T
#1 C
A
Máxima Verossimilhança
#4 G
#2 T
T
#4 G
#3 T
P1 = PA x PAG x PAC x PAT x PTT x PTT
Y pode ser:
A,T,C,G
Onde X=G e Y=A
Onde X=A e Y=T
#1 C
A
#3 T
G
Máxima Verossimilhança
T
• Calculemos a probabilidade (P2)de outra situação:
#1 C
Y pode ser:
A,T,C,G
• Calculemos a probabilidade (P1)desta situação:
#2 T
#4 G
X pode ser:
A,T,C,G
#3 T
#2 T
Máxima Verossimilhança
• Calculemos as probabilidades (P3-16)de cada uma
das demais situações para o sítio i:
#2 T
#1 C
A
N
#3 T
P2 = PG x PGG x PGC x PGA x PAT x PAT
#4 G
PTOP
N
#3 T
I sítio i =
P1 + P2 + P3 + P4 + … + P16
5
17/10/2012
Máxima Verossimilhança
Máxima Verossimilhança
• Fazemos tudo novamente, agora para o sítio j:
• Máxima Verossimilhança
#1 T
o Acontece que há mais sítios polimorficos para serem
analisados:
#1
#2
#3
#4
……TCAAAAATGCGCTTTATT……
……TCAGTGATGTGCGTGAAT……
……TTAGAAATGTGCTTGATT……
……TTAGTGATGGGCTTTATC……
#2 G
existem 16 possibilidades
para X e Y
X
Y
#4 T
#3 G
o Agora, considere o sítio marcado em verde, o sítio j
X pode ser:
A,T,C,G
Y pode ser:
A,T,C,G
Máxima Verossimilhança
Máxima Verossimilhança
• Calculemos as probabilidades (P1-16)de cada uma
das 16 situações para o sítio j:
• Calculemos as probabilidades (P1-16)de cada uma
das 16 situações para todos os sítios polimórficos:
#1 T
existem 16 possibilidades
para X e Y
X
I sítio j=
#1
#3 G
#4
Máxima Verossimilhança
TOPOLOGIA I
#2
Máxima Verossimilhança
• Os valores de probabilidades são expressos em
logarítmo e o resultado final da topologia I e
computado e comparado com o das outras 2
topologias.
PTOP I = PTOP
I sítio i
PTOP II = PTOP
II sítio i
PTOP
#4
PTOP I = PTOP
#3
P1 + P2 + P3 + P4 + … + P16
• Calculamos a probabilidade final da Topologia I
multiplicando todas as probabilidades calculadas
para cada um dos sítios polimórficos:
#1
#2
TOPOLOGIA I
Y
#4 T
PTOP
#2 G
#3
I sítio i
x PTOP I sítio j x … x PTOP
III =
x PTOP I sítio j x … x PTOP
I sítio z
x PTOP II sítio j x … x PTOP
PTOP III sítio i x PTOP
III sítio j
II sítio z
x … x PTOP III sítio z
• A topologia de maior probabilidade é a árvore a
ser escolhida.
I sítio z
6
17/10/2012
Busca de árvores
Busca de árvores
• MP e ML são métodos que procuram topologias
que melhor se adequem ao modelo evolutivo que
eles pressupõem
• Os softwares de análise filogenética sempre pedem
para informarmos qual o método de busca de
árvore que desejamos usar
• Nos exemplos até agora, testamos todas as
topologias possíveis, ou seja fizemos uma busca
exaustiva
• Confuso, pois o papel deles não é desenhar
topologias?
• Não, o papel deles é aplicar algorítimos de
resolução de problemas sobre topologias que nós
damos a eles!
• Busca exaustiva é computacionalmente
impraticável, em particular para os ML, quando o
número de taxons é elevado
Busca de árvores
Busca de árvores
• Estratégias de busca:
• Branch and bound
o Construa uma topologia com todos os seus taxons, uma topologia
aleatória sem fundamento (quanto pior melhor)
o Exaustiva
• Computacionalmente pesada, mas encontra a melhor topologia,
pois testa todas
o Compute seu valor, de acordo com o método de análise (MP ou ML)
o Crie uma árvore em estrela com tres taxons e derive nova árvores como
segue
o Branch and bound
• Computacionalmente pesada, mas encontra a melhor topologia
sem necessariamente testar todas
o Heurística
• Computacionalmente bem mais leve, probabilidade de encontrar a
melhor topologia, pois nunca testa todas
1
1
2
2
Adicione um
taxon
3
3
Calcule o score desta topologia:
1
4
2
1
4
2
1
2
1
4
4
3
3
3
3
2
Se for pior que random tree descarte-a bem como
toda sua descendencia e passe para a topologia ao
lado
Se for melhor que random tree, adicione outro
taxon e analise a primeira topologia após a adição,
O score desta árvore deverá ser o padrão daqui
em diante (substitui o score de random tree)
7
17/10/2012
1
1 de 3
2
4
3 de 4
15 de 5
3
Adicione outro taxon
1
1
2
4
2
4
1
2
35
35
35
105 de 6
315
315
315
945 de 7
3465
3465
3465
10395 de 8
Busca de árvores
• Heurística
o stepwise addition: inicie com uma árvore de tres taxons e adicione um
taxon, produzindo 3 árvores, exatamente como em branch and bound. A
de melhor score é escolhida e as demais são descartadas
4
3
1
3
1
2
4
5
1
4
5
5
3
2
1
2
4
1
4 5
4
2
o Star decomposition: Inicie com uma árvore multifurcada com um nó e a
seguir construa topologias selecionando um par de taxons e deixando os
outros em estrela. Calcule o scores para todas as possibilidades e escolha
a melhor decomposição. Repetir o processo a partir da primeira
decomposição escolhendo um novo par para retirar da estrela.
2
5
3
3
3
3
3
8