aula12_ibm1029

Prévia do material em texto

1
Profª Drª Silvana Giuliatti
Departamento de Genética – Bloco G
Ramal: 4503
silvana@rge.fmrp.usp.br
Faculdade de Medicina
Departamento de Genética
IBM1029
Introdução à Bioinformática
Aula 12
Árvores Filogenéticas
3. Método de Fitch e Margoliash
• Fitch e Margoliash (1987).
• Usa matriz de distâncias. 
• As sequências são combinadas em grupos de três e 
os dados combinados são usados para o cálculo dos 
comprimentos dos ramos.
• As sequências são adicionadas progressivamente.
Árvores Filogenéticas
Exemplo: O Método para Três Sequências
• Suponha três sequências: A, B e C.
• O número de topologias para esse arranjo é N = 1.
b
ca
A
B
C
Árvores Filogenéticas
As distâncias entre as sequências são 
apresentadas na matriz abaixo:
A B C
A - - -
B 22 - -
C 39 41 -
O comprimento dos ramos são calculados 
algebricamente.
Árvores Filogenéticas
A B C
A - - -
B 22 - -
C 39 41 -
• Subtraindo (III) de (II): a – b = -2 (IV)
• Adicionando (I) a (IV): 2a = 20, a = 10
• De (I) e (II): b = 12 e c = 29.
a + b = 22 (I)
a + c = 39 (II)
b + c = 41 (III)
2
2910
A
B
C
Árvores Filogenéticas
Exemplo: O Método para Cinco Sequências
• Suponha cinco sequências: A, B, C, D e E.
• A matriz de distâncias é apresentada abaixo:
A B C D E 
A - - - - -
B 22 - - - -
C 39 41 - - -
D 39 41 18 - -
E 41 43 20 10 -
2
Árvores Filogenéticas
1. Determinar o par de sequências que apresenta menor 
distância entre elas. Nesse caso: dDE = 10.
A B C D E 
A - - - - -
B 22 - - - -
C 39 41 - - -
D 39 41 18 - -
E 41 43 20 10 -
2. Tratar o resto das sequências
como uma única sequência
composta.
3. Calcular a distância média de D 
em relação a todas as outras 
sequências e de E em relação 
a todas as outras sequências.
dD = (dDA+dDB+dDC)/3 = (39 + 41 + 18)/3 ≅ 32,7
dE = (dEA+dEB+dEC)/3 = (41 + 43 + 20)/3 ≅ 34,7
Árvores Filogenéticas
4. Usar esses valores para calcular os comprimentos d e e , 
como num caso para três sequências.
e
d´d
D
E
ABC
d + e = 22 (I)
d + d´ = 39 (II)
e + d´ = 41 (III)
• Subtraindo (III) de (II): e – d = 2 (IV)
• Adicionando (I) a (IV): 2e = 12, e = 6
• De (I) e (II): d = 4 .
D E ABC 
D - - -
E 10 - -
ABC 32,7 34,7 -
Árvores Filogenéticas
5. Trate D e E como uma única sequência composta, calcule 
as distâncias médias entre DE e cada uma das outras 
sequências e faça uma nova tabela com esses valores.
A distância média de A até DE é a média da distância de A 
à D e de A à E. O mesmo para as outras sequências.
(dAD + dAE)/2 = (39+41)/2= 40
(dBD + dBE)/2 = (41+43)/2= 42
(dCD + dCE)/2 = (18+20)/2= 19
A B C (DE) 
A - - - -
B 22 - - -
C 39 41 - -
(DE) 40 42 19 -
Árvores Filogenéticas
6. Tratar o resto das sequências
como uma única sequência
composta.
7. Calcular a distância média de C 
em relação a todas as outras 
sequências e de (DE) em 
relação a todas as outras 
sequências.
dC = (dCA+dCB)/2 = (39 + 41)/2 = 40
dDE = (d(DE)A+d(DE)B)/2 = (40 + 42)/2 = 41
5. Identifique o próximo par que apresenta menor distância 
e repita o processo. 
Como no item 1, calcule o próximo conjunto de ramos: 
dC(DE) = 19.
A B C (DE) 
A - - - -
B 22 - - -
C 39 41 - -
(DE) 40 42 19 -
Árvores Filogenéticas
8. Usar esses valores para calcular o comprimento c, como 
num caso para três sequências.
de
d´´c
C
DE
AB
c + de = 19 (I)
c + d´´ = 40 (II)
de + d´´ = 41 (III)
• Subtraindo (III) de (II): de – c = 1 (IV)
• Adicionando (I) a (IV): 2de = 20, de = 10
• De (I) e (II): c = 9 .
DE C AB
DE - - -
C 19 - -
AB 41 40 -
Árvores Filogenéticas
9. Quando necessário, subtraia os comprimentos dos ramos 
para calcular os comprimentos dos ramos intermediários.
Pela matriz de distâncias, sabemos que:
• D até C : dDC = 18 
• E até C : dCE = 20
4
6
E
D
C
9
4
x6
E
D
C
9
3
Árvores Filogenéticas
Então:
• D até C = dDC= d + c + x = 18
x = dDC– d – c = 18 – 9 – 4 = 5
• E até C = dCE – c – e = 20 – 9 – 6 = 5
4
56
E
D
C
9
Árvores Filogenéticas
10. Calcule as distâncias médias.
(dAC + dA(DE))/2 = (39+40)/2= 39,5
(dBC + dB(DE))/2 = (41+42)/2= 41,5
A B (CDE) 
A - - -
B 22 - -
(CDE) 39,5 41,5 -
11. Identifique o próximo par que apresenta menor 
distância e repita o processo. 
Calcule o próximo conjunto de ramos: dAB = 22.
Árvores Filogenéticas
12. Calcular os comprimentos a e b, como num caso para 
três sequências.
b
d´´´a
A
B
CDE
a + b = 22 (I)
a + d´´´ = 39,5 (II)
b + d´´´ = 41,5 (III)
• Subtraindo (III) de (II): b – a = 2 (IV)
• Adicionando (I) a (IV): 2b = 24, b = 12
• De (I) e (II): a = 10 .
Árvores Filogenéticas
13. Quando necessário, subtraia os comprimentos dos 
ramos para calcular os comprimentos dos ramos 
intermediários.
• A até C = dAC – a – c = 39 – 10 – 9 = 20
• B até C = dBC – b – c = 41 – 12 – 9 = 20
10
2012
B
A
C
9
Árvores Filogenéticas
Portanto, a árvore final é:
10
2012
B
A
C
9
4
5
6 E
D
Árvores Filogenéticas
Máxima Probabilidade 
• São baseados em modelos probabilísticos.
• Usam todas as informações disponíveis, ao invés de usar 
um conjunto de distâncias. Cada coluna fornecerá a 
probabilidade da árvore.
• Supõe uma topologia para a árvore e seleciona os 
comprimentos dos ramos de maneira a maximizar a 
probabilidade dos dados analisados.
• Essas probabilidades são comparadas com outras 
topologias: a de maior probabilidade é a escolhida.
4
Árvores Filogenéticas
• Primeiro, selecionar um modelo evolucionário.
• A evolução envolve apenas substituições, sem deleções
ou inserções.
• Cada sitio envolvido em um ramo da árvore não depende 
de sua evolução ao longo de nenhum outro ramo.
• Método implementado como parte do pacote PHYLIP 
(http://evolution.genetics.washington.edu/phylip.html).
• O algoritmo é computacionalmente intensivo.
Árvores Filogenéticas
Qual a probabilidade do 
nucleotídeo da sequência 4 ser T, 
considerando que ele poderia ter 
sido qualquer um dos 4 
nucleotídeos possíveis no nó X?
Isso significa somar as 
probabilidades do nucleotídeo em 
X ter sido A e mudado para T, ter 
sido G e mudado para T, ter sido C 
e mudado para T e de não ter 
mudado.
X
Y
Z
TGCA
1 2 3 4
Árvores Filogenéticas
O Método
A) Suponha as seguintes sequências:
A: ACGCGTTGGG
B: ACGCGTTGGG
C: ACGCAATGAA
D: ACACAGGGAA
B) Para 4 sequências, 3 possíveis topologias. Considere uma 
dessas 3: A
B D
C
Árvores Filogenéticas
C) Selecionar um coluna para análise:
A: ACGCGTTGGG
B: ACGCGTTGGG
C: ACGCAATGAA
D: ACACAGGGAA
D) Todas as possíveis árvores com raiz que podem ser 
derivadas de uma árvore sem raiz são analisadas. Um 
exemplo é apresentado abaixo:
A DCB
Árvores Filogenéticas
• A posição da raiz não é importante, uma vez que a 
probabilidade da árvore será a mesma independente da 
localização da raiz.
• As bases da coluna selecionada são mostradas na árvore.
A DCB
T T A G
1 2
0
O objetivo é considerar cada base possível nesses 3 nós 
(0, 1 e 2) e calcular a probabilidade de cada escolha.
Árvores Filogenéticas
• Há 4 bases e 3 nós. Portanto: 4 x 4 x 4 = 64 possíveis 
combinações. 
• A árvore também apresenta 6 valores de probabilidades 
L1-L6, para a probabilidade de uma mudança de base 
por sítio ao longodos respectivos ramos da árvore. A 
probabilidade L0 é para a base no nó zero.
A DCB
T T A G
1 2
0L1 L2
L4L3 L5 L6
L0
5
Árvores Filogenéticas
• Essas probabilidades dependem das bases nos 3 nós e 
do tipo resultante de substituição naquela árvore em 
consideração.
• A probabilidade de uma árvore com uma escolha de 
bases em particular nos nós é dada pelo produto de cada 
probabilidade de substituição:
L(árvore) = L0 x L1 x L2 x L3 x L4 x L5 x L6
Árvores Filogenéticas
E) A árvore abaixo é uma possível árvore com T nos nós 0 e 
1 e G no nó 2. 
A DCB
T T A G
1 2
0
L1 L2
L4L3 L5 L6
L0
T
T
G
Árvores Filogenéticas
F) Todas as possibilidades são avaliadas. Isso é feito para 
todas as colunas do alinhamento. 
A: ACGCGTTGGG
B: ACGCGTTGGG
C: ACGCAATGAA
D: ACACAGGGAA A DCB
A
G
1 2
0L1 L2
L4L3 L5 L6
L0
A A A
C C C C
G G G C
............G
AA
Árvores Filogenéticas
G) A possibilidade para cada topologia é avaliada. 
L(árvore1) = L(col1) x L(col2) x L(col3) x... X L(col10)
L(árvore2) = L(col1) x L(col2) x L(col3) x... X L(col10)
L(árvore3) = L(col1) x L(col2) x L(col3) x... X L(col10)
Como os valores tendem a ser muito pequenos, é comum o uso 
de ln L. Dessa forma, as probabilidades poderão ser adicionadas.
Árvores Filogenéticas
Modelos Evolucionários 
• Descrevem o processo de substituição em 
nucleotídeos e aminoácidos ao longo do tempo. 
• Concentrar em sequências de DNA, uma vez que 
outras sequências são tratadas similarmente.
Árvores Filogenéticas
Matrizes de Probabilidades de Transição 
Para as quatro bases de DNA: A, C, T, G. 
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜
⎝
⎛
=
)()()()(
)()()()(
)()()()(
)()()()(
)(
tptptptp
tptptptp
tptptptp
tptptptp
tP
TCTGTTTA
GCGGGTGA
CCCGCTCA
ACAGATAA
Exemplo: pAC(t) é a probabilidade de mudar do estado A para 
o estado C no tempo t.
6
Árvores Filogenéticas
Se num certo tempo t0 o sitio estiver num estado i, 
então a probabilidade do evento no tempo t0+δ estar 
num estado j depende somente de i, j e t, sendo 
exatamente o elemento pij(t) da matriz P(t).
P(t) tem a forma: P(t) = exp (t Q), onde Q é
alguma matriz 4x4.
Árvores Filogenéticas
Modelos evolucionários mais usados para filogenia.
A) Modelo de Jukes-Cantor (1969)
É um dos mais antigos modelos e não muito realístico.
Assume que as probabilidade para encontrar um 
nucleotídeo em um dos 4 possíveis estados são iguais a 1/4 
para todo t.
Árvores Filogenéticas
É dado pela matriz:
⎟⎟
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜⎜
⎜
⎝
⎛
−
−
−
−
=
4
3
444
44
3
44
444
3
4
4444
3
αααα
αααα
αααα
αααα
Q
Onde, α é uma constante positiva chamada taxa evolucionária..
Árvores Filogenéticas
Calculando a matriz P(t) = exp (t Q), encontra-se:
.),exp(
4
1
4
1)(
.),exp(
4
3
4
1)(
jitodoparattp
itodoparattp
ij
ii
≠−−=
−+=
α
α
Árvores Filogenéticas
B) Modelo de Kimura (1980)
É a generalização do método de Jukes-Cantor.
Incorpora uma diferença entre dois tipos de 
substituições de nucleotideos: 
- transições ( A → C, C → A, A → T, T → A) 
- transversões ( A → G, G → A, C → T, T → C)
Árvores Filogenéticas
É dado por:
⎟⎟
⎟⎟
⎟⎟
⎟⎟
⎠
⎞
⎜⎜
⎜⎜
⎜⎜
⎜⎜
⎝
⎛
+−
+−
+−
+−
=
4
)12(
444
44
)12(
44
444
)12(
4
4444
)12(
αββααβα
βααββαα
αβααββα
βααβααβ
Q
Onde, β é um parâmetro adicional.
Quando β = 1, o modelo de Kimura torna-se o modelo 
de Jukes-Cantor.
7
Árvores Filogenéticas
Calculando a matriz P(t) = exp (t Q), encontra-se:
⎟⎠
⎞⎜⎝
⎛ +−−−+====
−−==
======
⎟⎠
⎞⎜⎝
⎛ +−+−+=
2
)1(exp
2
1)exp(
4
1
4
1)()()()(
)exp(
4
1
4
1)()(
)()()()()()(
.,
2
)1(exp
2
1)exp(
4
1
4
1)(
αββα
βα
αββα
tttptptptp
ttptp
tptptptptptp
itodoparatttp
TCCTGAAG
TGGT
GCCGTAATCAAC
ii
Árvores Filogenéticas
C) Modelo de Felsenstein (1981)
É também uma generalização do método de Jukes-
Cantor. É dado por:
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜
⎝
⎛
++−
++
++−
++−
=
)(
)(
)(
)(
GCAGCA
TTCACA
TGTGAA
TGCTGC
Q
πππααπαπαπ
αππππααπαπ
απαππππααπ
απαπαππππα
Onde, π i são parâmetros que satisfazem: π A + π C + π G + π T = 1.
O modelo de Jukes-Cantor é um caso especial de Felsenstein
para π A = π C = π G = π T = 1/4. 
Árvores Filogenéticas
Calculando a matriz P(t) = exp (t Q), encontra-se:
( )
.,)exp()(
.,exp)1()(
jitodoparattp
itodoparattp
jjij
iiii
≠−−=
−−+=
παπ
αππ
Árvores Filogenéticas
Avaliando a Significância da Árvore
• Teste de Confiança: Bootstrap
• Dado um conjunto de dados, consistindo de um alinhamento, 
um conjunto de dados artificial de mesmo tamanho é gerado 
escolhendo, aleatoriamente, colunas do alinhamento original.
• Uma nova árvore é gerada com o novo conjunto de dados.
• O processo é repetido várias vezes.
• Valores de frequência são usados para medir a confiança. Se, na 
nova amostragem, determinados ramos permanecerem sempre 
juntos nas novas topologias simuladas, aquele nó que os une 
receberá um valor de 100%.
Árvores Filogenéticas
Suponha o seguinte alinhamento original:
Coluna: 1 2 3 4 5 6 7 8 9 10
A: A C G C G T T G G G
B: A C G C G T T G G T
C: A C G C A A T G A A
D: A C A C A G G G A A
Coluna: 1 1 8 4 8 6 1 8 9 9 
A: A A G C G T A C G G
B: A A G C G T A C G G 
C: A A G C G A A C A A
D: A A G C G G A C A A
Coluna: 9 6 8 7 8 6 1 8 9 9 
A: G T G T G T A C G G
B: G T G T G T A C G G 
C: A A G T G A A C A A
D: A G G G G G A C A A
Bootstrap – Alinhamento 1 Bootstrap – Alinhamento 2
Árvores Filogenéticas
89
75
98
D
C
B
A
N = 100
8
Árvores Filogenéticas
Qual método usar?
Escolha um 
conjunto de 
sequências
relacionadas
Obtenha uma 
alinhamento 
múltiplo
Similaridade 
é forte?
Sim
Não
Máxima 
parcimônia 
ou máxima 
probabilidade
Sim
Não
Métodos de 
Distância
Tentar usar métodos de máxima 
probabilidade, focar nas regiões de 
similaridade localizadas.
Analisar o quanto a 
variação das sequências, 
presente no alinhamento, 
apóia o resultado da 
análise.
Similaridade 
reconhecível?
Árvores Filogenéticas
Softwares
• CLUSTALW
(http://www.ebi.ac.uk/clustalw/) -WEB
• PHYLIP 
(http://evolution.genetics.washington.edu/phylip.html).
(bioweb.pasteur.fr/seqanal/phylogeny/phylip-uk.html) -
WEB
• PAUP
(http://paup.csit.fsu.edu/)