aula11_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 11
Filogenia
Árvores Filogenéticas
Métodos para Determinação de Árvores Filogenéticas
• Há três métodos principais
D Parcimônia Máxima
1. Distância
2. Máxima Verossimilhança
Árvores Filogenéticas
2. Distâncias
• Baseados em distâncias genéticas entre as sequências
alinhadas. 
• O objetivo é identificar a árvore que posicione as 
sequências com menor distância entre si (sequências
vizinhas).
Árvores Filogenéticas
• Primeiro, as sequências são organizadas num 
alinhamento múltiplo.
• As distâncias calculadas são colocadas numa matriz. 
• Os vizinhos são colocados em ramos adjacentes.
• Os vizinhos mais distantes são adicionados 
progressivamente à árvore.
Árvores Filogenéticas
Exemplo: Considere o seguinte alinhamento de 4 
sequências.
Seq. 1: ACGCGTTGGGCGATGGCAAC
Seq. 2: ACGCGTTGGGCGACGGTAAT
Seq. 3: ACGCATTGAATGATGATAAT
Seq. 4: ACACATTGAGTGATAATAAT
Suponha que as distâncias entre os pares foram calculados e 
os seguintes valores foram obtidos:
N12 = 3 N14 = 8 N24 = 7
N13 = 7 N23 = 6 N34 = 3
2
Árvores Filogenéticas
As distâncias são colocadas numa matriz:
Seq. 1 2 3 4
1 - 3 7 8
2 - - 6 7
3 - - - 3
4 - - - -
• Usando a matriz, uma árvore pode ser desenhada. 
• A soma dos comprimentos dos ramos entre quaisquer 
duas sequências na árvore tem o mesmo valor da 
distância entre elas.
Árvores Filogenéticas
Seq. 1: ACGCGTTGGGCGATGGCAAC
Seq. 2: ACGCGTTGGGCGACGGTAAT
Seq. 3: ACGCATTGAATGATGATAAT
Seq. 4: ACACATTGAGTGATAATAAT
Seq. 1 2 3 4
1 - 3 7 8
2 - - 6 7
3 - - - 3
4 - - - -
1
1
2
2 4
Seq.1 
Seq. 2
Seq. 3
Seq. 4 
Árvores Filogenéticas
1. Método UPGMA (Unweighted Pair Group Method
Using Arithmetic Averages)
• É o método mais simples baseado em distâncias. 
• Usa agrupamento de sequências.
• Assume que a taxa de mudanças ao longo dos ramos 
da árvore é constante.
Árvores Filogenéticas
A equação geral da distâncias entre os clusteres Ci
e Cj é : 
∑
∈∈
=
ji CqCp
pq
ji
ij dCNCN
d
,)()(
1
Onde, N(Ci) e N(Cj) são os elementos de cada cluster..
Árvores Filogenéticas
As Etapas do Algoritmo
1. Uma medida de distância é computada para todos os 
pares de sequências e os valores dispostos numa matriz.
1 2 3 4
1 - - - -
2 d12 - - -
3 d13 d23 - -
4 d14 d24 d34 -
dij: distância entre a sequência i e j.
Árvores Filogenéticas
2. O processo de clusterização começa com o par que 
apresentar o menor valor de distância.
Suponha a seguinte matriz:
Nesse exemplo, o menor valor d35 = 2.
1 2 3 4 5 
1 - - - - -
2 16 - - - -
3 6 16 - - -
4 16 8 16 - -
5 6 16 2 16 -
3
Árvores Filogenéticas
3. O primeiro agrupamento será da sequência 3 com a 5, 
com um ramo de comprimento d35/2.
As sequências 3 e 5 são agora combinadas em um 
cluster C6. 
3
5
1
1
6
Árvores Filogenéticas
As distâncias entre os clusteres são calculadas: 
16)(
21
1
16)(
21
1
6)66(
2
1)(
21
1
)()(
1
454346
252326
1513
,61
16
=+=
=+=
=+=+== ∑
∈∈
dd
x
d
dd
x
d
dd
x
d
CNCN
d
ji CqCp
pq
1 2 4 6 
1 - - - -
2 16 - - -
4 16 8 - -
6 6 16 16 -
Gerando uma nova matriz.
Repetir o processo até não ter mais 
sequências para serem agrupadas
Árvores Filogenéticas
A árvore final apresentará a seguinte topologia: 
4 2
4
4
8
1
2
3
3
5
1
1
6
7
4
5
Árvores Filogenéticas
2. Junção de Vizinhos (“Neigbor-Joining”)
• Método eficiente de construção de árvores 
filogenéticas. 
• Não examina todas as topologias possíveis.
• Descrito por Saitou e Nei (1987).
• O método identifica os pares mais próximos 
(vizinhos).
• A topologia final é construída por uniões sucessivas 
de vizinhos.
Árvores Filogenéticas
• O método começa com uma estrutura em forma de 
estrela.
• Depois de combinados, os vizinhos resultam em uma 
árvore de menor comprimento total. 
• O processo é repetido até que existam apenas 3 
elementos combinados na estrutura.
DA
E
CB B
A
E
D
C
Árvores Filogenéticas
As Etapas do Algoritmo
1. Primeiro, suponha a seguinte topologia, onde as 
distâncias entre os pares de sequências são conhecidas: 
d12, d13 e d23.
y
zx
1
2
3
x + y = d12
x + z = d13
y + z = d23
4
Árvores Filogenéticas
A solução para essas equações é:
( )
( )
( )122313
132312
231312
2
1
2
1
2
1
dddz
dddy
dddx
−+=
−+=
−+=
Árvores Filogenéticas
A Equação da Distância entre os Pares
( )jiijij rrdD +−=
Onde, ∑
=−=
N
k
iki dN
r
12
1
Para i, j = 1, ..., N, i < j.
Árvores Filogenéticas
Exemplo: Considere 6 sequências (N = 6) e suponha as 
seguintes distâncias entre elas:
1 2 3 4 5 6
1 - - - - - -
2 8 - - - - -
3 3 9 - - - -
4 14 10 15 - - -
5 10 6 11 10 - -
6 12 8 13 8 8 -
Árvores Filogenéticas
1. Calcular os valores de r para cada sequência.
∑
=−=
N
k
iki dN
r
12
1
( )
( )
4
47121014380
4
1
4
1
26
1
1
161514131211
1
11
=+++++=
+++++=−= ∑=
r
dddddddr
N
k
k
Para a sequência 1:
Fazer esse cálculo para as outras 5 sequências.
Árvores Filogenéticas
O valor de r para cada sequência é:
4
49
4
45
4
57
4
51
4
41
4
47
65
43
21
==
==
==
rr
rr
rr
Árvores Filogenéticas
2. Calcular o valor de D para cada par.( )jiijij rrdD +−=
( )
14
4
41
4
47812
211212
−=⎟⎠
⎞⎜⎝
⎛ +−=
+−=
D
rrdDPara o par 1-2:
Fazer esse cálculo para todos os pares.
5
Árvores Filogenéticas
O valor de D para cada par é calculado e os valores são 
dispostos em uma matriz:
D 1 2 3 4 5 6
1 - - - - - -
2 -14 - - - - -
3 -43/2 -14 - - - -
4 -12 -29/2 -12 - - -
5 -13 -31/2 -13 -31/2 - -
6 -12 -29/2 -12 -37/2 -31/2 -
Árvores Filogenéticas
O menor valor na matriz D é: D13 = -43/2.
D 1 2 3 4 5 6
1 - - - - - -
2 -14 - - - - -
3 -43/2 -14 - - - -
4 -12 -29/2 -12 - - -
5 -13 -31/2 -13 -31/2 - -
6 -12 -29/2 -12 -37/2 -31/2 -
Portanto, as sequências 1 e 3 serão agrupadas.
Árvores Filogenéticas
3. Calcular o comprimento de cada ramo.
O agrupamento de 1 e 3 será representado por 
um novo elemento: 7.
A distância entre dois elementos agrupados é dada por:
)(
2
1
)(
2
1
,1
,1
ijijjN
jiijiN
rrdd
rrdd
−+=
−+=
+
+
Árvores Filogenéticas
Então: 
2)(
2
1
1)
4
51
4
473(
2
1)(
2
1
13133,7
31131,7
=−+=
=−+=−+=
rrdd
rrdd
Portanto:
2
1
3
1
7
Árvores Filogenéticas
4. Recalcular as distâncias.
As distâncias entre cada sequência e o novo 
elemento devem ser calculadas por:
)(
2
1
,1 ijjmimmN dddd −+=+
Árvores Filogenéticas
Então: 
11)(
2
1
9)(
2
1
13)(
2
1
7)398(
2
1)(
2
1
1336166,7
1335155,7
1334144,7
1332122,7
=−+=
=−+=
=−+=
=−+=−+=
dddd
dddd
dddd
dddd
6
Árvores Filogenéticas
A nova matriz de distâncias é:
2 4 5 6 7
2 - - - - -
4 10- - - -
5 6 10 - - -
6 8 8 8 - -
7 7 13 9 11 -
Todo o processo é repetido.
Árvores Filogenéticas
2
1
3
1
7
5
2
7
2
9
1
2
3
8
5
9
3
5
6
4
8
⇒
⇒
⇒
2
1
3
1
7 5
2
2
9
1 2
3
5
3
5
6
4
8