Um Consenso Completamente Resolvido entre Árvores Filogenéticas Completamente Resolvidas

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


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 AB {A, B, } para todos os

subgrupos A,B


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 AB {A, B, } para todos os subgrupos A, B


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 AB = S e AB = [Teo 2.2.3]

O número de subgrupos de uma n-árvore completamente resolvida sobre L é 2|L| - 1 [Teo 2.2.4]


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}




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 AS e A’S’ tais que AA’=; caso contrário, eles são chamados incompatíveis

Um conjunto de cortes é chamado um sistema 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|S1S2|

[Teo2.1.6]


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]


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 AB=S e AB=

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\{AB} é 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 par é condicionalmente adicionado à lista de soluções

O subgrupo C = L\{AB} é um subgrupo pequeno e {A, B, C} pode ser uma Árvore mais provável

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

TestesNr. Softwar

eDetalhes

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

TestesCD1 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%

Documents

Um Consenso Completamente Resolvido entre Árvores Filogenéticas Completamente Resolvidas