Reconstrução filogenética:
Método de parcimônia
1. Árvores
2. Critério de parcimônia
3. Busca de árvores ótimas
Objetivos: Compreender o uso do
critério de parcimônia na reconstrução
de árvores filogenéticas e os métodos
de busca de árvores ótimas.
1
Métodos de distâncias
267 2
1. Distâncias genéticas
Árvore sem raiz
C
H
G
O
G
3
Árvore sem raiz
H
G
H
O
Raiz
G
Tempo
C
Árvore com raiz
C
G
O
G
Raiz
4
Número de possíveis árvores filogenéticas
 Número de árvores com raiz com bifurcações, NR para
n espécies
NR 
(2n  3)!
2
n 2
(n  2)!
 Número de árvores sem raiz com bifurcações, NU para
n espécies
NU 
(2n  5)!
2n3 (n  3)!
5
25
6
Reconstrução filogenética:
Método de parcimônia
1. Árvores 
2. Critério de parcimônia
3. Busca de árvores ótimas
7
267
8
Não esquecer os métodos de inferência Bayesiana.
267
9
A função a ser maximizada ou minimizada é chamada função objetivo.
267
10
 Ordinarily, phylogenetic inference under
criterion-based methods couples the
selection of a suitable optimality criterion
with a search for an optimal tree topology
under that criterion.
 Seleção
 Busca
267-268
11
268
12
 The basic idea underlying parsimony
analysis is simple: one seeks the tree,
or collection of trees, that minimizes
the amount of evolutionary change
(i.e. transformations of one character
into another) required to explain the
data.
268-269 13
279
14
270
15
Análise de parcimônia
 Determinar a quantidade de mudança
nos caracteres  comprimento de uma
dada árvore
 Busca pelas árvores que minimizam o
comprimento da árvore
270
16
Função objetivo
270
17
N
L( )   l j
j 1
This length lj is the amount of character
change implied by a most parsimonious
reconstruction that assigns a character
state xij to each node i for each site j.
270
18
a(k)
k
b(k)
271
19
271
20
271
21
W
X
Y
Z
...
...
...
...
ACAGGAT
ACACGCT
GTAAGGT
GCACGAC
...
...
...
...
((W,Y),(X,Z))
WG
CX
?
YA
?
CZ
271
22
W
X
Y
Z
23
• O que é conhecido?
– Número de topologias de árvores com
e sem raiz para um conjunto de
sequências
– Estado do nucleotídeo nos nós
terminais
• O que é desconhecido?
– Topologia verdadeira
– Estado do nucleotídeo nos nós
internos (ancestrais hipotéticos)
24
Árvore I
((W,X),(Y,Z))
A
G
A
C
G
T
C
?
?
A
C
G
T
C
25
• Princípio de Parcimônia Máxima
 Identificação de uma topologia que
exija o menor número de eventos
evolutivos para explicar as diferenças
observadas entre as sequências em
estudo

Melhor hipótese exige o menor número
de premissas
 Substituições de nucleotídeos
26
4 sequências e 9 sítios de nucleotídeos
Sítios
Sequências
1
2
1
A
2
4
5
6
7
8
9
A
3
G
A
G
T
T
C
A
A
G
C
C
G
T
T
C
T
3
A
G
A
T
A
T
C
C
A
4
A
G
A
G
A
T
C
C
T
Árvore I
((1,2),(3,4))
Árvore II
((1,3),(2,4))
Árvore III
((1,4),(2,3))
1
3
1
2
1
2
2
4
3
4
4
3 27
Sequências 1
A
1
2
A
G
C
C
G
T
T
C
T
7
T
8
C
9
A
A
G
A
T
A
T
C
C
A
4
A
G
A
G
A
T
C
C
T
A3
A
2A
3
G
3
1A
Sítio 1
2
A
Sítios
4 5 6
A G T
A2
1A
A
A
A4
3A
1A
A2
A
A
A4
4A
A
A3
• Sítio 1 é invariante pois todas as
sequências têm o nucleotídeo A
– Nenhuma mudança é exigida em qualquer
uma das três possíveis árvores
28
Sítios
Sequências 1 2 3 4 5 6 7 8 9
1
A A G A G T T C A
2
A G C C G T T C T
3
A G A T A T C C A
4
A G A G A T C C T
1A
G3
G
Sítio 2
2G
G2
1A
G
G
G4
3G
1A
G2
G
G
G4
G
4G
G3
• Sequência 1 tem G e as demais têm A
– Pressuposição simples que o nucleotídeo mudou de
G para A na linhagem que deu origem à sequência 1
• Sítio 2 não é informativo sob o critério de parcimônia
pois cada uma das três árvores exige uma mudança
29
Sítios
Sequências 1 2 3 4 5 6 7 8 9
1
A A G A G T T C A
2
A G C C G T T C T
3
A G A T A T C C A
4
A G A G A T C C T
1G
Sítio 3
A3
G
2C
C2
1G
A
A
A4
3A
1G
C2
A
A
A4
4A
A
A3
• Para o sítio 3, cada uma das três topologias exige 2
mudanças
– O sítio 3 não é informativo sob o critério de parcimônia
30
Sítios
Sequências 1 2 3 4 5 6 7 8 9
1
A A G A G T T C A
2
A G C C G T T C T
3
A G A T A T C C A
4
A G A G A T C C T
1A
Sítio 4
T3
C
2C
C2
1A
T
T
G4
3T
1A
C2
A
C
G4
4G
T
T3
• Para o sítio 4, cada uma das três topologias
exige 3 mudanças
– O sítio 4 não é informativo sob o critério de
parcimônia
31
Sítios
Sequências 1 2 3 4 5 6 7 8 9
1
A A G A G T T C A
2
A G C C G T T C T
3
A G A T A T C C A
4
A G A G A T C C T
1G
Sítio 5
A3
G
2G
G2
1G
A
A
A4
3A
1G
G2
A
A
A4
A
4A
A3
• Para o sítio 5, a topologia I exige somente uma
mudança evolutiva, ao passo que as topologias
II e III exigem 2 mudanças
– O sítio 5 é informativo sob o critério de parcimônia
32
Sítios
Sequências 1 2 3 4 5 6 7 8 9
1
A A G A G T T C A
2
A G C C G T T C T
3
A G A T A T C C A
4
A G A G A T C C T
1A
Sítio 9
A3
T
2T
T2
1A
T
A
T4
3A
1A
T2
T
T
T4
T
A3
4T
• Para o sítio 9, a topologia II exige somente uma
mudança evolutiva, ao passo que as topologias I
e III exigem 2 mudanças
– O sítio 9 é informativo sob o critério de parcimônia
33
• Princípio de Parcimônia Máxima
 Como um dado sítio de nucleotídeo
pode se comportar com relação ao
seu conteúdo de informação sob o
critério de parcimônia?
 Invariante
 Não-informativo sob o critério de
parcimônia
 Informativo sob o critério de parcimônia
34
• Princípio de Parcimônia Máxima
 Identificação de uma topologia que
exija o menor número de eventos
evolutivos para explicar as diferenças
observadas entre as sequências em
estudo

Melhor hipótese exige o menor número
de premissas
 Substituições de nucleotídeos
35
(a) Sítio 3
Árvore I
((1,2),(3,4))
1G
A3
A
G
Árvore II
((1,3),(2,4))
C2
1G
A
A
Árvore III
((1,4),(3,4))
1G
C2
A
A
2C
A4
3A
A4
4A
A3
1A
T3
1A
C2
1A
C2
(b) Sítio 4
C
T
G4
A3
2C
1G
(c) Sítio 5
G
T
2T
G4
G2
A
A4
A3
A
T4
3A
T3
G2
A
A4
T2
A
A3
4A
1A
T2
T
T
T4
T
4G
1G
A
3A
1A
T
A
C
3T
1G
A
2G
1A
(d) Sítio 9
T
4T
T
A3
36
Árvore I
((1,2),(3,4))
1G
Sítio 5
A3
G
2T
G2
A
A4
A3
T
1G
A
2G
1A
Sítio 9
Árvore II
((1,3),(2,4))
A4
T2
3A
1A
T
A
T4
A
3A
Árvore III
((1,4),(3,4))
1G
A
A3
T2
4A
1A
T
T
T4
A
G2
4T
T
A3
• Duas árvores com o mesmo número
mínimo de mudanças
 Não é possível inferir uma única árvore
 Verdadeiro se os diferentes tipos de mutação
são ponderados igualmente
37
• Eventos de mutação ponderados
igualmente
 Parcimônia não-ponderada
• Os eventos de mutação
ponderados segundo o tipo de
mutação
 Parcimônia ponderada
38
• Parcimônia ponderada
 Eventos de mutação por
transição

Mais frequentes durante o
processo evolutivo
 Menor peso
39
• Parcimônia ponderada
 Eventos de mutação por
transversão

Menos frequentes durante o
processo evolutivo
 Maior peso
40
Árvore I
((1,2),(3,4))
1G
Sítio 5
A3
G
Árvore II
((1,3),(2,4))
1G
A
G2
Sítio 9
A3
T
2T
A4
3A
G  A
1A
A
A
A4
2G
1G
A
A
G2
A3
4A
Transição
T2
1A
T
A
T4
Árvore III
((1,4),(3,4))
3A
1A
T2
T
T
T4
A  T
4T
T
A3
Transversão
41
Árvore I
((1,2),(3,4))
1G
Sítio 5
A3
G
Árvore II
((1,3),(2,4))
1G
A
G2
Sítio 9
A3
T
2T
A4
3A
G  A
1A
A
A
A4
2G
1G
A
A
G2
A3
4A
Transição
T2
1A
T
A
T4
Árvore III
((1,4),(3,4))
3A
1A
T2
T
T
T4
A  T
T
A3
4T
Transversão
• Maior peso atribuído ao evento de
transversão
 Árvore II é a árvore de parcimônia máxima
42
• Princípio de Parcimônia Máxima
 Identificação de uma topologia que
exija o menor número de eventos
evolutivos para explicar diferenças
observadas entre as sequências em
estudo

Comprimento da árvore
 Número total de substituições nos sítios
informativos e não-informativos
43
Reconstrução filogenética:
Método de parcimônia
1. Árvores 
2. Critério de parcimônia 
3. Busca de árvores ótimas
44
 Ordinarily, phylogenetic inference under
criterion-based methods couples the
selection of a suitable optimality criterion
with a search for an optimal tree topology
under that criterion.
 Seleção
 Busca
267-268 45
8.4 Searching for optimal trees
 Having specified a means for calculating
the score of a tree under our chosen
criterion, the more difficult task of
searching for an optimal tree can be
confronted. The methods described in the
following sections can be used for
parsimony, least-squares distance criteria,
and maximum likelihood.
273
46
277
47
48
278
49
279
279
50
An alternative exact procedure, the
branch-and-bound method, is useful for
data sets containing 12 to 25 or so taxa,
depending on the “messiness” of the
data. This method operates by implicitly
evaluating all possible trees, but cutting
off paths of the search tree when it is
determined that they cannot possibly
lead to optimal trees.
279-280 51
Árvore de busca (search tree)
281
52
282
53
Heurísticas
 Heuristic (Greek: "Εὑρίσκω", "find" or
"discover") refers to experiencebased techniques for problem solving,
learning, and discovery.
 Heuristic methods are used to speed
up the process of finding a good
enough solution, where an exhaustive
search is impractical.
54
282
55
284
56
282
57
286
58
Reconstrução filogenética:
Método de parcimônia
1. Árvores 
2. Critério de parcimônia 
3. Busca de árvores ótimas 
59