Tool that Integrates Distance Based Programs for
Reconstructing Phylogenetic Trees
M. Torres, G. Dias, G. Gonçalves and C. Vieira
Abstract— The main existing methods for reconstructing
phylogenetic trees are based on maximum likelihood, bayesian
inference, maximum parsimony or distance. There are many
distance based programs for phylogenetic trees reconstruction.
The five most important distance based programs were selected:
NJ, BioNJ, UPGMA, Weighbor and FastME. Synthetic data sets
were applied in order to evaluate the distance-based methods
under consideration. Then, the tool DiGrafu was developed, so as
to exploit the best characteristics of these programs. Besides, the
validation of this proposed solution was presented using real
data.
Keywords— bioinformatics, phylogenetic tree reconstruction,
distance methods.
I.
O
INTRODUÇÂO
OBJETIVO da análise filogenética é inferir a relação
correta entre três ou mais espécies contemporâneas,
representadas por dados de sequência (podem ser de
aminoácidos, nucleotídeos, códons, etc) de membros
representativos de cada espécie [1]. A representação da
história evolutiva dessas espécies ou grupos de espécies é feita
através das árvores filogenéticas, onde as sequências são
agrupadas e são estabelecidos os relacionamentos entre estas.
Neste contexto, as aplicações de árvores filogenéticas têm
crescido rapidamente. Hoje em dia elas são usadas não apenas
no entendimento das relações históricas entre as espécies, mas
também em estudos sobre: organização do genoma,
epidemiologia, predição de funções de proteínas e decisão de
quais genes analisar em estudos comparativos. Em outras
palavras, a reconstrução de árvores filogenéticas é importante
para compreender a história evolutiva das espécies, ajudar no
desenvolvimento de vacinas, na predição de novos genes, no
estudo da biodiversidade, no entendimento da biologia
macrobiana, na produção de novas drogas para propósitos
agrícolas e médicos, etc.
Árvores filogenéticas representam uma série de hipóteses a
respeito de eventos evolucionários. São compostas de folhas,
que são as seqüências genéticas que representam as espécies
ou grupos destas, os galhos, que são as interligações entre os
nós da árvore e representam o tempo de evolução entre eles, e
Este trabalho foi financiado pela FAPESB, termo de outorga No.
APR0179/2008.
M. Torres, Universidade Estaudal de Santa Cruz, Ilhéus, Bahia, Brasil.
[email protected]
G. Dias, Universidade Estadual de Santa Cruz, Ilhéus, Bahia, Brasil,
[email protected]
G. Gonçalves, Universidade Federal de Minas Gerais, Belo Horizonte,
Minas Gerais, Brasil, [email protected]
C. Vieira, Universidade Estadual de Campinas, Campinas, Sao Paulo,
Brasil, [email protected]
os nós internos, que são os hipotéticos ancestrais das
sequências analisadas.
Os principais métodos para reconstrução de árvores
filogenéticas segundo [2] são: Máxima Parcimônia, Distância,
Máxima Verossimilhança, e Inferência Bayesiana.
No
entanto, existem dificuldades no uso dos programas de
reconstrução de árvores filogenéticas: o usuário deve escolher
qual método de reconstrução utilizar, conhecendo as
vantagens e desvantagens de cada um. De maneira geral é
conhecido que os métodos de distância são os mais velozes e
os métodos de máxima verossimilhança e inferência bayesiana
são mais exatos, mas, independente desse fator, dentre todos
os programas que existem para cada método, o usuário precisa
escolher o que atenda às suas necessidades e expectativas.
Embora os métodos de distância sejam menos exatos, eles
continuam sendo muito utilizados devido ao seu baixo tempo
de execução. Há muitos programas baseados no método de
distância e a escolha de um deles vem se tornando cada vez
mais difícil para os usuários que desejam resultados rápidos e
condizentes com a realidade da evolução das espécies. Este
trabalho apresenta a ferramenta DiGrafu, que reúne os
melhores programas de reconstrução de árvores filogenéticas
baseados em distância [2][3][4] : NJ (Neighbor Joining) [5],
BioNJ [6], UPGMA (Unweighted Pair Grouping Method with
Arithmetic Means) [7],
Weighbor (Weighted Neighbor
Joining) [8] e FastME (Fast Minimum Evolution) [4]. Esta
ferramenta explora as potencialidades de cada programa e é
capaz de inferir qual deles melhor satisfaz a necessidade do
usuário.
O artigo está dividido nas seguintes partes: a parte II
explica os programas baseados no método de distância, na
parte III apresenta-se em detalhe a proposta deste trabalho. A
parte IV descreve a validação da ferramenta DiGrafu com
dados reais e na parte V as conclusões são apresentadas.
II. MÉTODOS BASEADOS EM DISTÂNCIA
De maneira geral, os programas de reconstrução de árvores
filogenéticas recebem como entrada um arquivo com
sequências genéticas (DNA, RNA, códons, proteínas) de um
grupo de espécies, devidamente alinhadas. Os métodos de
distância não trabalham diretamente com as sequências das
espécies, mas com uma matriz de distâncias (daí a expressão
“baseado em distância”). Essa matriz é construída com base
em modelos evolutivos, os quais são modelos matemáticos
que descrevem a evolução dos caracteres observados nas
espécies analisadas. Os programas Dnadist e Protdist do
pacote
Phylip
(disponível
em
http://evolution.genetics.washington.edu/phylip.html)
são
geradores de matrizes para sequências de DNA e de proteína,
respectivamente, são largamente usados pela qualidade da
matriz gerada.
Assim, a maioria dos métodos de distância inicia sua
heurística apenas depois de gerar a matriz de distância, ou seja
os métodos de distância aplicam seus respectivos algoritmos
sobre ela para obter a melhor hipótese de árvore filogenética.
Os métodos UPGMA, NJ, BioNJ e Weighbor são baseados
em métodos de agrupamento hierárquico usados em
reconhecimento de padrões [9]. Estes algoritmos selecionam
um par de espécies (nós) a ser fundido a cada passo utilizando
um critério específico. Os dois nós selecionados são então
substituídos por um novo nó simples e a matriz de distâncias é
reduzida por substituir as distâncias relativas aos dois nós
unidos por este novo nó. Sua heurística considera dois passos
principais, que são repetidos até que a árvore esteja completa.
O primeiro passo consiste na escolha de pares de nós a serem
unidos, isto é, substituídos por um novo nó simples
representando o imediato ancestral comum deles, e no
segundo passo, as distâncias do novo nó para todos os outros
nós são calculadas. O que diferencia cada um dos métodos é a
maneira de escolher os nós a serem unidos e de calcular as
distâncias.
A seguir serão mostradas as principais características destes
métodos:
A. UPGMA
Foi pioneiro na reconstrução de árvores, principalmente
quando os dados utilizados eram fenotípicos. Caiu em desuso
quando sequências genéticas passaram a ser utilizadas pela
filogenia e métodos mais exatos foram construídos.
O algoritmo UPGMA usa os mesmos critérios de um
algoritmo de agrupamento hierárquico clássico: os dois nós a
serem agrupados são aqueles que apresentam a menor
distância e essas são calculadas através do valor médio da
distância entre nós e grupos.
Sua principal vantagem é a boa representação das
diferenças fenotípicas das espécies, porém deixa de analisar
grande parte das topologias de árvore para ganhar tempo,
considerando que todas as árvores seguem a idéia de relógio
molecular [10]. Nessas árvores, os galhos são simétricos entre
seus nós, de forma que cada nó, de um par de nós, possui a
mesma distância até o nó ancestral comum que os une.
B. NJ
Faz construção de árvores de maneira rápida, considerando
tanto árvores com relógio molecular, quanto sem relógio
molecular (árvores nas quais os galhos que unem dois
descendentes de um mesmo nó podem assumir comprimentos
independentes um do outro, representando mais fielmente as
diferenças entre as espécies e seus ancestrais). O critério de
seleção dos nós a serem agrupados e o cálculo da distância utiliza
o método matemático dos mínimos-quadrados [11], onde o valor
da distância entre cada nó é diferente. No caso do UPGMA, a
distância dos nós a serem agrupados é igual. Por outro lado, este
método pode perder precisão no cálculo dos comprimentos dos
galhos quando há galhos muito longos, segundo [8].
C. BioNJ
Este é um aprimoramento do NJ. Sua contribuição ao NJ
inclui a maior precisão no cálculo dos tamanhos dos galhos.
Seu procedimento atribui pesos diferentes, no cálculo do
tamanho dos galhos, às espécies sendo unidas na árvore por
aquele galho. Com isso, pretende-se obter uma maior
aproximação da realidade, uma vez que indivíduos envolvidos
no caminho evolutivo dos seres, ainda existentes ou já
extintos, provavelmente não contribuíram em taxas iguais para
as mutações ocorridas.
D. Weighbor
Substitui o critério de evolução mínima, utilizado pelo NJ,
por verossimilhança, método estatístico usado para estimar
funções de densidade de probabilidade desconhecida [9]. O
Weighbor escolhe os nós a serem unidos de uma maneira
diferente do NJ, mantendo o cálculo dos tamanhos dos ramos
não muito diferente do BioNJ, que já o havia reformulado.
Uma relativa melhora nos resultados foi observada ainda
mantendo-se em um tempo aceitável de execução, apesar
desse ter aumentado consideravelmente. Além disso, não
perde precisão quando há galhos muito longos na árvore.
E. FastME
Este é baseado no princípio de otimização de árvores por
tree swapping. Esse método atua sobre uma árvore
filogenética inicial, trocando os galhos dessa árvore entre si
para poder analisar outras topologias próximas da topologia
inicial. Por padrão, há dois métodos de geração de árvore
inicial (FASTNNI e BNNI) e dois métodos de otimização
(GME e BME). Assim, a inclusão do FastME representa a
inclusão de quatro combinações possíveis de métodos de
otimização: GME+FASTNNI, GME+BNNI, BME+FASTNNI
e BME+BNNI.
Segundo [3], métodos de distancia baseados em evolução
mínima como NJ, BioNJ e FastME são mais rápidos para
inferir filogenias e segundo [4] o método FastME na sua
versão BME+FASTNNI é mais exato do que NJ, BioNJ e
Weighbor.
III. DESCRIÇÃO DA PROPOSTA
Para tornar possível a integração dos métodos de distância
foi necessária a avaliação de desempenho dos mesmos e o
estudo detalhado dos resultados da exatidão dos métodos com
relação às sequências originais.
Foram usados dados
sintéticos para realizar a avaliação e em um ambiente
simulado, a árvore verdadeira foi artificialmente gerada e
formou a base para comparação entre os métodos.
A inovação de nossa proposta é usar a relação entre os
resultados dos métodos e as sequências originais através da
divergência máxima das sequências. Divergência máxima [12]
(MD, maximum divergence em inglês) pode ser vista como a
porcentagem do maior valor da diferença entre as sequências
(comparadas par a par). Assim, MD nada mais é que a
porcentagem de diferenças que há entre as duas sequências
mais divergentes. Para realizar a comparação entre os
programas escolhidos seguimos a métrica de [12] que é
padrão para realizar este tipo de estudos.
A seguir será descrita a metodologia aplicada para realizar a
avaliação de desempenho dos principais métodos de distância.
A. Metodologia para Avaliação de desempenho
Com o objetivo de realizar o estudo do comportamento dos
principais métodos de distância de acordo com o valor de MD
das sequências, foi utilizado um computador Intel Xeon 3.2
Ghz, 2 GB de memória ram e 160 GB de disco rígido,
rodando sobre a plataforma Linux, e foram escritos alguns
scripts na linguagem Perl.
Baseando-se na metodologia utilizada em [12], foram
utilizadas as 5000 árvores descritas nesse mesmo artigo,
disponíveis em <http://atgc-montpellier.fr/phyml/>. Segundo
esse trabalho, tais árvores, compostas por 40 espécies cada
uma, apresentam uma grande variedade de desvios do relógio
molecular e muitas taxas evolucionárias. O tamanho médio
dos galhos é igual a 0,06 substituições/sítio. A média da taxa
do tamanho da maior para o tamanho da menor linhagem, ao
longo das 5000 filogenias, é igual a 3,4. Esses valores vêm de
uma análise das taxas de substituição em vários organismos;
eles representam, então, as características de quase todos os
conjuntos de dados reais.
A partir dessas árvores, foram geradas sequências genéticas
de DNA sintéticas de 500 sítios através do programa Seq-Gen,
um programa apresentado em [13] que gera sequências através
do método de Monte Carlo. Seq-Gen gera uma quantidade de
sequências aleatórias baseado em uma árvore modelo e em um
modelo evolucionário e tem sido muito utilizado para geração
de sequências em testes sintéticos [11]-[12],[14].
Apenas um arquivo para cada combinação de árvoremodelo e modelo evolucionário foi gerado, sendo criados
5000 arquivos para cada modelo. Foram, então, utilizados dois
modelos para a geração das sequências: JC69 (Jukes e Cantor
(1969)) e K2P (Kimura (1980), com taxa de
transição/transversão igual a 2,0) totalizando 10000 arquivos
de seqüência.
Todas as sequências genéticas geradas foram então
classificadas por MD para o propósito do estudo, variando de
10% até 80%, porque como será explicado mais adiante, os
métodos existentes não podem reconstruir com exatidão
árvores filogenéticas fora desta margem [12].
Os programas de distância foram integrados com o gerador
de matrizes Dnadist. Com as sequências classificadas por MD,
os métodos de distância foram executados e seus resultados
comparados às respectivas árvores-modelo utilizadas na
geração das sequências.
Para essa avaliação, foram considerados dois critérios
importantes na comparação de métodos de distância: o tempo
de execução e a diferenciação simétrica.
Para mensurar o tempo de execução, foi utilizada a função
“times” da biblioteca padrão da linguagem Perl. Essa função
foi útil, uma vez que mede o tempo de processamento dos
processos-filhos do programa em execução, e os métodos de
distância poderiam ser executados como uma coleção de
processos-filhos. Para cada conjunto de sequências com um
dado valor de MD, foi calculada a média aritmética dos
tempos de execução para aquele MD e esse valor foi
computado como seu tempo de execução. Ou seja, o tempo de
execução analisado trata-se do tempo médio gasto pelo
método de distância naquele conjunto de dados. Outra
observação a ser feita sobre os tempos de execução analisados
é que o tempo do Dnadist (ou seja, o tempo gasto para a
geração das matrizes de distância utilizadas pelos métodos) foi
somado ao tempo de execução dos métodos, uma vez que eles
necessitam da matriz para a execução.
Para medir a diferenciação simétrica foi usada a distância
Robinson-Foulds [15], implementada no programa Treedist,
também do pacote Phylip, que computa distâncias entre
árvores filogenéticas a nível de diferenciação simétrica
(compara a topologia das árvores). A diferenciação simétrica
entre árvores filogenéticas é uma medida baseada na
contagem de partições (no caso de árvores sem raiz, partições
são divisões feitas na árvore a partir de cada galho) que
pertencem a uma árvore, mas não pertencem à outra. Essa
contagem constitui uma pontuação, sendo que, quanto menor
é o valor da pontuação, mais parecida é a topologia das
árvores (valor 0,0 significa árvores idênticas).
A seguir, a análise dos resultados obtidos através da
simulação realizada.
B. Análise dos resultados
A Fig. 1 mostra os resultados das execuções dos métodos
de distância selecionados, com suas respectivas pontuações
dadas pelo Treedist para o modelo evolutivo JC69 e a Fig. 2
mostra esses resultados usando o modelo evolutivo K2P. Os
resultados estão de acordo com o esperado e com simulações
publicadas anteriormente [11]-[12], [16]; quando o valor de
MD é baixo (<10%, sequências muito parecidas) a
reconstrução da árvore filogenética é difícil porque não há
informação suficiente nos dados para calcular os pequenos
galhos internos. Quando o valor de MD é alto (>80%,
sequências demasiado diferentes) a saturação corrompe o sinal
filogenético e a reconstrução novamente é problemática. Isto
explica porque todos os métodos são mais exatos com valores
de MD médios.
Os valores de exatidão topológica do programa UPGMA
não foram registrados nas Fig. 1 e 2 porque tiveram valores
altos, entre 20 e 27. Ou seja, UPGMA sempre obteve os
piores índices nas pontuações (os valores mais altos). Isso
deixa claro a razão pela qual ele foi um método muito
utilizado, mas, aos poucos, cedeu lugar a métodos mais
exigentes computacionalmente. Também pode ser inferido
desta figura que os métodos Weighbor, GME+BNNI e
BME+BNNI foram os mais exatos.
A Fig. 3 apresenta os resultados dos tempos de execução
utilizando o modelo JC69. A Fig. 4 mostra esses resultados
para o modelo K2P. Os tempos de execução do programa
0 ,0 7
0 ,0 6
Tempo (em segundos)
Weighbor não foram registrados porque tiveram valores altos,
acima de 0,7 segundos, já que por utilizar cálculos de
verossimilhança para aumentar a exatidão, aumenta a
exigência computacional de maneira considerável. Os gráficos
mostram que, os métodos se mantiveram próximos, o BioNJ,
notavelmente, quase sempre se manteve como o método mais
veloz, mais rápido inclusive que o NJ, no qual ele se baseia.
Isso fica claro se é observado que o BioNJ é uma otimização
do código do NJ, tanto em relação aos seus resultados, quanto
em se tratando do tempo gasto na execução. Exceto para MD
de 80% do modelo K2P, onde as versões FastME
apresentaram melhor desempenho, como mostra a Fig. 4.
0 ,0 5
Neighbor
UPGMA
BIONJ
GME+ FASTNNI
GME+ BNNI
BME+ FASTNNI
BME+ BNNI
0 ,0 4
0 ,0 3
0 ,0 2
10 15 20 25 30 35 40 45 50 55 60 65 70 75
16
14
12
Neighbor
BIONJ
Weighbor
GME+ FASTNNI
GME+ BNNI
BME+ FASTNNI
BME+ BNNI
Diver gência das Sequências
Figura 3. Tempos de execução dos programas Neighbor, UPGMA, BIONJ,
GME+FASTNNI, GME+BNNI, BME+FASTNNI e BME+BNNI, classificada
por divergência de sequências (MD), utilizando o modelo JC69.
0 ,1 3
10
0 ,1 2
8
6
10 15 20 25 30 35 40 45 50 55 60 65 70 75
Diver gência das Sequências
Figura 1. Exatidão topológica dos programas Neighbor, BIONJ, Weighbor,
GME+FASTNNI, GME+BNNI, BME-FASTNNI e BME+BNNI, classificada
por divergência das sequências (MD), utilizando o modelo JC69.
Tem po (em segundos)
Exatidão Topológica
18
0 ,1 1
0 ,1
Ne ig h b o r
UPGMA
BIONJ
GME+ FASTNNI
GME+ BNNI
BME+ FASTNNI
BME+ BNNI
0 ,0 9
0 ,0 8
0 ,0 7
0 ,0 6
0 ,0 5
10 15 20 25 30 35 40 45 50 55 60 65 70 75 80
22
20
Ex atidão Topológica
18
16
Neighbor
BIONJ
Weighbor
GME+ FASTNNI
GME+ BNNI
BME+ FASTNNI
BME+ BNNI
14
12
10
8
6
10 15 20 25 30 35 40 45 50 55 60 65 70 75 80
Diver gência das Sequências
Figura 2. Exatidão topológica dos programas Neighbor, BIONJ, Weighbor,
GME+FASTNNI, GME+BNNI, BME-FASTNNI e BME+BNNI, classificada
por divergência das sequências (MD), utilizando o modelo K2P.
Metodologia similar foi adotada para analisar o
comportamento de sequências de proteína, neste caso foi
usado o gerador de matrizes Protdist.
Com base nos
resultados obtidos procede-se agora à construção da
ferramenta DiGrafu.
Diver gência das Sequências
Figura 4. Tempos de execução dos programas Neighbor, UPGMA, BIONJ,
GME+FASTNNI, GME+BNNI, BME+FASTNNI e BME+BNNI, classificada
por divergência de sequências (MD), utilizando o modelo K2P.
C. A ferramenta DiGrafu
Assim, a ferramenta DiGrafu é implementada levando em
consideração os resultados obtidos. Onde UPGMA é
descartado pelo seu pobre desempenho. DiGrafu escolhe o
melhor método em cada valor de MD e para cada modelo; o
valor de MD é medido usando o arquivo de entrada de
sequencias do usuário . Quando o usuário seleciona tempo de
execução como prioridade, DiGrafu executa BioNJ, que é o
mais eficiente em quase todos os casos. Quando o usuário
escolhe tempo de execução e exatidão, DiGrafu executa o
método que proporciona maior exatidão, exceto nos casos nos
quais o método de maior exatidão seja o Weighbor (seu tempo
de execução é muito alto comparado aos outros métodos),
nesses casos será usado o método FastME (nas versões:
BME+BNNI e GME+BNNI). Quando o usuário seleciona
exatidão, DiGrafu escolhe o método com maior exatidão;
Weighbor é o método mais usado e FastME, nas versões
BME+BNNI e GME+BNNI foram escolhidos algumas vezes.
Como mostrado na Fig. 5, a ferramenta DiGrafu possui
também um conversor de formatos com suporte aos formatos
Fasta [17], Nexus [18] e Phylip (sequencial e interleaved), os
arquivos de sequência são analisados e o formato é
automaticamente reconhecido e convertido para o formato
Phylip seqüencial utilizado pelos programas Dnadist e
Protdist.
Figura 5. Diagrama que mostra a implementação da ferramenta.
Esta ferramenta é de domínio público e está disponível em
<http://github.com/said/digrafu>. Além disso, a ferramenta
DiGrafu pode ser utilizada de maneira gráfica através de
IGrafu (Interface Gráfica para solução de Reconstrução de
Árvores
Filogenéticas)
disponível
em
<http://github.com/said/igrafu>. A tela gráfica inclui todos os
parâmetros requeridos pelos programas Dnadist e Prodist além
das opções próprias da DiGrafu. A figura 6 mostra a tela para
um arquivo de entrada de sequencias de DNA.
(http://www.treebase.org/treebase/index.html), sete arquivos
de sequências alinhadas de DNA de fungos e bactérias (M520,
67 espécies com 1098 sítios; M535, 36 espécies com 1856
sítios; M536, 33 espécies com 2418 sítios; M795, 66 espécies
com 510 sítios; M925, 41 espécies com 893 sítios; M926, 40
espécies com 806 sítios; M2898, 38 espécies com 1419 sítios),
e oito arquivos de sequências alinhadas de proteínas de
bactérias (M2302, 24 espécies com 365 sítios; M2304, 31
espécies com 429 sítios; M2636, 20 espécies com 1275 sítios;
M2637, 20 espécies com 320 sítios; M2638, 18 espécies com
378 sítios; M2639, 19 espécies com 331 sítios; M2640, 18
espécies com 243 sítios; M2641, 20 espécies com 253 sítios)
além de uma sequência de DNA de mamíferos e roedores
(M62, 62 espécies com 3768 sítios) publicada em [19].
Para a avaliação das árvores, os dados reais foram
submetidos ao programa PhyML 3.0 [12], este programa
realiza reconstrução de árvores filogenéticas usando o método
de máxima verossimilhança, considerado um dos métodos
mais exatos porém com grande demanda computacional.
Portanto, as árvores geradas pelo PhyML foram assumidas
como as árvores verdadeiras para aquelas sequências.
Os métodos foram utilizados com os parâmetros default, e
as matrizes de distância foram geradas através dos programas
Dnadist e Protdist. DiGrafu foi executada com a preferência
pela exatidão do resultado e o FastME foi executado com os
algoritmos BME + BNNI para construir e otimizar a árvore. A
exatidão dos resultados vista nos gráficos é traduzida pela da
porcentagem de semelhança entre a árvore reconstruída pelo
método e a árvore do PhyML, assumida como a árvore real
daquela sequência.
Figura 7. Resultados obtidos através dos dados reais de sequências de DNA,
usando o modelo JC69. Nos gráficos acima a linha indica a variação de MD
nas sequências selecionadas.
Figura 6. Tela da ferramenta Digrafu usando sequencias de DNA.
IV.
TESTE DA FERRAMENTA DIGRAFU COM DADOS REAIS
Para testar o funcionamento da ferramenta DiGrafu com
dados reais aplica-se a mesma técnica usada anteriormente.
Para isto foram selecionados do banco de dados Treebase
A Fig. 7, mostra os resultados das sequências de DNA
usando o modelo evolutivo JC69 . A Fig. 8 mostra os mesmos
resultados usando o modelo evolutivo K2P. Como foi descrito
anteriormente, quando o usuário seleciona exatidão, DiGrafu
escolhe o método Weighbor na maioria dos casos e algumas
vezes é escolhido FastME, nas versões BME+BNNI e
GME+BNNI. No caso do modelo JC69, DiGrafu escolheu
sempre o Weighbor o qual foi a melhor resposta para quatro
dos cinco exemplos avaliados. No caso do modelo K2P, em
três dos cinco exemplos foi escolhido o método Weighbor e
nos dois casos restantes foi escolhido o método FastMe: na
sequência M520 o método escolhido foi o GME+BNNI e na
sequência M926 foi o BME+BNNI. Pode-se observar que
DiGrafu apresenta o comportamento esperado, realizando a
seleção do método apropriado para a opção de exatidão.
Dos dez exemplos DiGrafu escolheu sete vezes o método
mais exato: nos demais casos escolheu o segundo método
mais exato. A justificativa para tal resultado é que DiGrafu foi
desenvolvida com um conjunto finito de valores de MD e
depois disso foi feita a generalização dividindo o
comportamento em faixas, sendo assim, DiGrafu não pode
acertar 100% das vezes porque é inviável fazer uma varredura
completa de todos os valores possíveis de MD. De outra
maneira pode-se sim aumentar a porcentagem de acertos
produzindo árvores sintéticas com maior diversidade de
valores de MD.
Figura 9. Resultados obtidos através dos dados reais de sequências de proteína
usando o modelo JTT.
Dos oito exemplos DiGrafu escolheu seis vezes o método
mais exato, nos demais casos escolheu o segundo método
mais exato. Como foi descrito anteriormente, DiGrafu não
pode acertar 100% das vezes porque é inviável fazer uma
varredura completa de todos os valores possíveis de MD.
De maneira geral, dos 18 casos avaliados, em 13 casos,
DiGrafu escolheu o método mais exato. Nos demais, escolheu
o segundo método mais exato, ou seja teve uma porcentagem
de acerto de 72%, para esta opção. Avaliando DiGrafu usando
a opção de tempo de execução, a porcentagem de acerto foi de
100%, o mesmo para tempo de execução+ exatidão.
Os valores indicam que as árvores geradas pela DiGrafu
foram semelhantes às geradas pelo PhyML, sabendo que os
métodos de distância não são tão exatos quantos os métodos
baseados em máxima verossimilhança ou bayesianos.
V.CONCLUSÕES
Figura 8. Resultados obtidos através dos dados reais de sequências de DNA,
usando o modelo K2P. Nos gráficos acima a linha indica a variação de MD
nas sequências selecionadas.
A Fig. 9, ilustra os resultados das sequências de proteína
usando o modelo evolutivo JTT [20]. Neste caso em quatro
dos oito exemplos foi escolhido o método Weighbor e nos
outros quatro casos foi escolhido o método FastMe: na
sequência M2638 o método escolhido foi o GME+BNNI e nas
sequências M2637, M2639 e M2641 foi usado o BME+BNNI.
Novamente pode-se observar que DiGrafu apresentou o
comportamento esperado, escolhendo os métodos previstos
para a opção de exatidão.
Neste artigo, apresentou-se uma solução integradora de
programas para reconstrução de árvores filogenéticas
baseados no método de distância. Esta solução permite
realizar uma seleção automática do programa, baseando-se na
relação entre os resultados dos programas e as sequências: a
divergência máxima. Além disso, DiGrafu também integra os
geradores de matrizes Dnadist e Protdist. Ademais, o usuário
também pode escolher entre a exatidão do método ou o menor
tempo de execução, ou ambas as alternativas (nesse caso,
obtendo um resultado razoável e com um tempo de execução
médio). Baseando-se na escolha do usuário e nos resultados
obtidos na análise dos testes de desempenho, DiGrafu escolhe
o melhor método para aquela execução.
Com essa nova solução, pretende-se facilitar o uso de
métodos de distância e automatizar alguns dos processos que
envolvem a escolha de tais métodos. Mesmo porque também
foi desenvolvida uma versão com uso de interface gráfica
amigável que, além disso, incrementa o número de formatos
de entradas que podem ser utilizados para realizar
reconstrução de árvores filogenéticas sob o método de
distância.
AGRADECIMIENTOS
Os autores reconhecem a contribuição de C. Bravo pela
ajuda na formatação do artigo e de G. Segundo pela correção
do português.
REFERENCES
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[10]
[11]
[12]
[13]
[14]
[15]
[16]
[17]
[18]
[19]
[20]
E. Schardt, J. Sinsheimer, and K. Lange, “Computational advances in
maximum likelihood methods for molecular phylogeny,” Genome
Research, vol. 8, pp. 222-233, 1998.
J. Felesenstein, Inferring phylogenies. Sunderland: Sinauer associates,
Inc., 2004.
M. Price, P. Dehal, and A. Arkin, “FastTree: Computing Large
Minimum-Evolution Trees with Profiles instead of a Distance Matrix,”
Molecular Biology and Evolution, vol. 26, pp. 1641-1650, 2009.
R. Desper, and O. Gascuel, “Fast and accurate phylogeny reconstruction
algorithms based on the Minimum-Evolution principle,” Comput. Evol.,
vol. 9, no. 5, pp. 687–705, 2002.
N. Saito, and M. Nei, “The neighbor-joining method: a new method for
reconstructing phylogenetic trees”. Mol. Biol. Evol., vol. 4, pp. 406–425,
1987.
O. Gascuel, “BIONJ: An improved version of the NJ algorithm based on
a simple model of sequence data”. Mol. Biol. Evol., vol. 14, pp. 685–
695, 1997.
P.H. Sneath, R.R. Sokal, Numerical taxonomy: the principles and
practice of numerical classification. San Francisco: W. H. Freeman,
1973.
W. Bruno, N. Socci, and A. Halpern, “Weighted neighbor joining: A
likelihood-based approach to distance-based phylogeny reconstruction,”
Mol. Biol. Evol., vol. 17, pp. 189–197, 2000.
S. Theodoridis, and K. Koutroumbas, Pattern recognition third edition.
San Diego: Elseiver, 2006.
D. Yoder, and Z. Yang, “Estimation of Primate Speciation Dates Using
Local Molecular Clocks,” Mol. Biol. Evol., vol. 17, no. 7, pp. 10811090, 2000.
V. Ranwez, and O. Gascuel, “Quarted-based phylogenetic inference:
Improvements and limits,” Mol. Biol. Evol., vol. 18, pp. 1103–1116,
2001.
S. Guindon, and O Gascuel, “A Simple, Fast, and Accurate algorithm to
estimate large phylogenies by maximum likelihood, ” Syst. Biol., vol. 52,
no. 5, pp. 696–704, 2003.
A. Rambaut, and N. Grassly, “Seq-Gen: An application for the Monte
Carlo simulation of DNA sequence evolution along phylogenetic trees,”
Comput. Appl. Biosci., vol. 13, pp. 235–238, 1997.
D. Barker, “LVB: Parsimony and simulated annealing in the search for
phylogenetic trees,” Bioinformatics, vol. 20, pp. 274-275, 2004.
D. Robinson, and L. Foulds, “Comparison of phylogenetic trees,”
Mathematical Biosciences, vol. 53, pp. 131–147, 1981.
V. Ranwez, and O. Gascuel, “Quarted-based phylogenetic inference:
Improvements and limits,” Mol. Biol. Evol., vol. 18, pp. 1103–1116,
2001.
W.R. Pearson, Improved tools for biological sequence comparison,
Proceedings of the National Academy of Science of the United States of
America, vol. 85, no. 8, pp. 2444-8, 1988.
D.R. Maddison, D.L. Swofford and W. P. Maddison, “NEXUS: an
extensible file format for systematic information,” Systematic Biology,
vol. 46, no. 4, pp. 590-621, 1997.
C. Poux, C. Pascale, D. Huchon, W. Jong, and E. Douzery, “Arrival and
Diversification of Caviomorph Rodents and Platyrrhine Primates in
South America,” Syst. Biol. vol. 55, no.2, pp. 228-244, 2006.
D. Jones, W. Taylor, and J. Thornton, “The rapid generation of mutation
data matrices from protein sequences,” Comput. Appl. Biosci. vol. 8, pp.
275-282, 1992.
M. Torres Nasceu em Cali, Colômbia, aos 18 de Abril de
1968. Graduou-se em Engenharia Elétrica na Universidad
Del Valle em 1991, Mestre em Sistemas Eletrônicos na
Universidade de São Paulo em 1994 e Doutor em
Sistemas Eletrônicos na Universidade de São Paulo em
1999. Trabalha no Departamento de Ciências Exatas e
Tecnológicas da Universidade Estadual de Santa Cruz,
Ilhéus, Bahia, onde é professora desde 2004 e coordena o Programa de PósGraduação em Sistemas Embarcados. Seus interesses estão relacionados com
sistemas embarcados, computação de alto desempenho e bioinformática.
G. Dias Nasceu em Guarulhos, São Paulo, Brasil, aos 8
de abril de 1988. Graduando em Ciência da Computação
na Universidade Estadual de Santa Cruz ingresso em
2007. Seus interesses estão relacionados com
desenvolvimento de software e sistemas distribuídos.
G. Gonçalves Nasceu em Salto de Divisa, Minas Gerais,
Brasil, aos 8 de Dezembro de 1981. Graduo-se em
Ciência da Computação na Universidade Estadual de
Santa Cruz em 2007, mestrando em Ciência da
Computação na Universidade Federal de Minas Gerais
ingresso em 2010. Seus interesses estão relacionados
com análise de desempenho de sistemas, computação de
alto desempenho e bioinformática.
C. Vieira Nasceu em Ilhéus, Bahia, Brasil, aos 28 de
Setembro de 1986. Graduo-se em Ciência da
Computação na Universidade Estadual de Santa Cruz em
2007, mestrando em Ciência da Computação na
Universidade Estadual de Campinas ingresso em 2008.
Seus interesses estão relacionados com desenvolvimento
de software, arquitetura de computadores, compiladores
e processamento paralelo e distribuído.