Um Consenso Completamente Resolvido entre Árvores
Filogenéticas Completamente Resolvidas
José Augusto Amgarten Quitzau
Organização






Introdução
n-Árvores e Sistemas de Cortes
Métodos de Consenso
Árvore Mais Provável
Um Algoritmo para Determinar as
Árvores Mais Prováveis
Testes
Introdução
Introdução
Introdução
Introdução

Grafo:



Acíclico
Conexo
Com no máximo um vértice de grau 2.
Introdução





Vértices de grau 1 são denominados folhas
Todos os demais são nós internos
No máximo um vértice pode ser eleito para
ser a raiz da árvore
Se houver um vértice de grau 2, ele é
obrigatoriamente a raiz
Denotamos o conjunto de
folhas por L
Introdução


Vértices de grau maior que três são
denominados politomias
Uma árvore filogenética sem politomias é
considerada completamente resolvida
n-Árvores e Sistemas de Cortes

Sistema de Classificação de Linnaeus




Hierarquia de Classes
Cada ser vivo pertence a exatamente uma
classe em cada nível da hierarquia
Se um ser vivo de uma classe qualquer A num
nível inferior pertence a uma classe qualquer B
num nível superior, então A  B
Os subconjuntos de L determinados pelas
classes são o que se costuma chamar de
uma n-Árvore
n-Árvores e Sistemas de Cortes

Um conjunto  de subgrupos
(subconjuntos) de L é denominado uma
n-árvore se e somente se as quatro
condições abaixo forem verificadas:





L
{x}   para todo x  L
AB  {A, B, } para todos os subgrupos
A,B  
n-Árvores e Sistemas de Cortes


Toda n-árvore determina exatamente
uma árvore filogenética com raiz.
Dizemos que uma n-Árvore  é
completamente resolvida se e
somente se a inclusão em  de
qualquer subgrupo não vazio que não
pertença a  fere a condição de que
AB  {A, B, } para todos os
subgrupos A, B  
n-Árvores e Sistemas de Cortes


Uma n-árvore  é completamente
resolvida se e somente se para
qualquer subgrupo S com
cardinalidade maior que um existirem
dois subgrupos A,B tais que AB =
S e AB =  [Teo 2.2.3]
O número de subgrupos de uma nárvore completamente resolvida sobre L
é 2|L| - 1 [Teo 2.2.4]
n-Árvores e Sistemas de Cortes
L= {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19}; {1, 2, 3,
4, 5, 6, 7, 8, 15, 16, 17, 18, 19}; Protista = {1, 2, 3, 4, 5, 6, 7, 8}; Plantae = {9, 10,
11, 12, 13, 14}; {1, 2, 3, 5, 6, 7, 8}; Animalia = {5, 16, 17, 18, 19}; {16, 17, 18,
19}; {9, 10, 11, 12}; {16, 17, 18}; {9, 10, 11}; {6, 7, 8}; {1, 3, 5}; {16, 17}; {13,
14}; {9, 11}; {6, 7}; {1, 3}; {19}; {18}; {17}; {16}; {15}; {14}; {13};
{12}; {11}; {10}; {9}; {8}; {7}; {6}; {5}; {4}; {3}; {2}; {1}
n-Árvores e Sistemas de Cortes
n-Árvores e Sistemas de Cortes
n-Árvores e Sistemas de Cortes



Um corte S={A,B} de um conjunto
qualquer X é uma bipartição de X em
dois subconjuntos não vazios A e B
Dois cortes S e S’ são chamados
compatíveis se e somente se existem
cortes AS e A’S’ tais que AA’=;
caso contrário, eles são chamados
incompatíveis
Um conjunto de cortes é chamado um
sistema de cortes
n-Árvores e Sistemas de Cortes


A distância de cortes () entre dois
sistemas de cortes é definido como o
número mínimo de inserções e
remoções de cortes que deve ser
aplicado em um sistema para
transformá-lo no outro.
(S1,S2) = |S1| + |S2| - 2|S1S2|
[Teo2.1.6]
n-Árvores e Sistemas de Cortes



A função  é uma enumeração arbitrária dos
elementos de L
Se R é um subgrupo de L,
(R) = {(r) | r  R}
Sejam R e S subgrupos de L, então R<S se e
somente se:



|R| < |S|, ou
min((R\S)) < min((S\R))
Se A, B e C são três subgrupos distintos de L.
Se A<B e B<C, então A<C[Teo 2.3.2]
n-Árvores e Sistemas de Cortes



Seja S={A,B} um corte de L tal que A<B,
então chamamos A de subgrupo pequeno de
S e denotamos A por Sp
Dois cortes são compatíveis se e somente se
seus subgrupos pequenos são compatíveis
[Teo 2.3.3]
Seja L um conjunto de cardinalidade maior
que dois e T uma árvore filogenética sem raiz
com conjunto de folhas L. Então T é
completamente resolvida se e somente se
F(T) tiver exatamente três n-árvores
maximais e estas árvores forem
completamente resolvidas [Teo 2.3.5]
Métodos de Consenso
Métodos de Consenso
Consenso Estrito
Componentes Combináveis
Consenso de Nelson
Regra da Maioria
Árvore Mais Provável

Seja L um conjunto de unidades taxonômicas e T uma coleção
não vazia qualquer de árvore filogenéticas completamente
resolvidas e sem raiz com conjunto de folhas L

Freqüência relativa com que o corte C é encontrado numa
coleção de cortes:

Peso de uma árvore:

Uma árvore que maximiza p(T,T ) é uma Árvore Mais Provável
para o conjunto.
Árvore Mais Provável

Definições semelhantes para subgrupos:

Freqüência relativa com que o subgrupo C é
encontrado numa coleção de cortes:

Peso de uma n-árvore:
O Algoritmo


Usa a relação entre peso de árvores e peso
de n-árvores dada pelo Teorema 6.0.2:
Baseado no Teorema 2.3.5, procura
encontrar pares de subgrupos para tentar
resolver subgrupos maiores
O Algoritmo

Um subgrupo S é considerado resolvido se:



|S| = 1, ou
Há um par de subgrupos A,B associados a ele tal que
AB=S e AB=
O algoritmo usará uma estrutura composta por
três tipos de sub-estruturas para representar as
árvores mais prováveis
O Algoritmo


Analisa todos os possíveis pares de
subgrupos pequenos encontrados na coleção
de árvores
Cada par A,B de subgrupos pode se
enquadrar em exatamente um dos três casos
abaixo:



O par é solução de um terceiro subgrupo pequeno
O subgrupo C = L\{AB} é um subgrupo pequeno
e {A, B, C} pode ser uma Árvore mais provável
Nenhum dos casos acima ocorre
O Algoritmo


Analisa todos os possíveis pares de
subgrupos pequenos encontrados na coleção
de árvores
Cada par A,B de subgrupos pode se
enquadrar em exatamente um dos três casos
abaixo:

O par é solução de um terceiro subgrupo pequeno


O subgrupo C = L\{AB} é um subgrupo pequeno
e {A, B, C} pode ser uma Árvore mais provável


O par é condicionalmente adicionado à lista de soluções
A tripla é condicionalmente adicionada à lista de árvores
Nenhum dos casos acima ocorre

O par é descartado
O Algoritmo
O Algoritmo
O Algoritmo

Complexidade: O(l2t2lglt)
O Algoritmo

Complexidade: O(l2t2lglt)
O Algoritmo
Testes
Nr.
Software
Detalhes
1
fastMe
Distâncias obtidas pelo modelo de Jukes-Cantor
2
fastMe
Distâncias obtidas pelo modelo de 2 parâmetros de Kimura (K2P)
3
Mega
Reconstrução por evolução mínima e distâncias por Jukes-Cantor
4
Mega
Reconstrução por evolução mínima e distâncias por K2P
5
Mega
Reconstrução por evolução mínima e distâncias por Tamura-Nei
6
Mega
Reconstrução por maximização de parcimônia através de troca de vizinhos
7
Mega
Reconstrução por Neighbor-Joining e distâncias por Jukes-Cantor
8
Mega
Reconstrução por Neighbor-Joining e distâncias por K2P
9
Mega
Reconstrução por Neighbor-Joining e distâncias por Tamura-Nei
10
Dnacomp
Reconstrução por compatibilidade
11
Dnaml
Reconstrução por probabilidade máxima
12
Dnamlk
Reconstrução por probabilidade máxima assumindo a hipótese do relógio molecular
13
Dnapars
Reconstrução por maximização de parcimônia
14
Neighbor
Reconstrução por Neighbor-Joining e distâncias por Jukes-Cantor
15
Neighbor
Reconstrução por Neighbor-Joining e distâncias por K2P
16
Neighbor
Reconstrução por UPGMA e distâncias por Jukes-Cantor
17
Neighbor
Reconstrução por UPGMA e distâncias por K2P
18
Weighbor
Distâncias obtidas pelo modelo de Jukes-Cantor
19
Weighbor
Distâncias obtidas pelo modelo K2P
Testes
CD1
CD2
CD3
CD4
REAIS
C
M
M
C
M
M
C
M
M*
O
48
48
118
86
88
108
88
88
88
1
26
26
66
36
38
64
18
50
22
2
26
26
72
40
42
70
26
56
30
3
30
30
60
24
20
46
n/u
50
n/u
4
34
34
62
30
34
40
n/u
50
n/u
5
34
34
66
20
24
40
n/u
60
n/u
6
46
46
112
64
72
96
n/u
76
n/u
7
28
28
74
24
22
56
n/u
52
n/u
8
18
18
72
36
36
56
n/u
54
n/u
9
26
26
78
18
18
56
n/u
58
n/u
10
144
144
118
172
172
112
n/u
126
n/u
11
44
44
108
72
72
88
-
-
-
12
-
-
-
-
-
-
-
-
-
13
46
46
94
66
66
94
74
64
74
14
16
16
50
26
24
46
32
62
28
15
18
18
50
22
16
56
32
62
28
16
100
100
106
122
120
102
n/u
50
n/u
17
102
102
104
122
120
102
n/u
50
n/u
18
22
22
54
36
26
58
38
54
38
19
22
22
54
32
26
62
n/u
58
n/u
MÉDIA
43,68
43,68
77,78
53,44
52,67
69,11
36,67
60,17
36,67
EX
144
144
118
172
172
112
88
126
88
IS
16
16
50
18
16
40
18
50
22
Testes
CD1
CD2
CD3
CD4
REAIS
C
M
M
C
M
M
C
M
M*
PERDE
5
5
11
2
4
5
0
0
0
EMPATA
0
0
1
2
2
1
1
1
1
GANHA
13
13
6
14
12
12
5
16
5
%
72%
72%
33%
78%
67%
67%
83%
94%
83%