APRIMORAMENTOS DA SOLUÇÃO PARALELA BASEADA EM OPERAÇÕES COLETIVAS PARA O BOOTSTRAP DA RECONSTRUÇÃO DE ÁRVORES FILOGENÉTICAS NO PHYML 3.0
Palavras-chave:
reconstrução de árvores filogenéticas; processamento paralelo; MPIResumo
A filogenética é um ramo de estudos que objetiva determinar as relações evolutivas entre grupos de espécies. Como produto, é obtida uma hipótese que relaciona a coleção de espécies analisadas, que normalmente é representada através de uma árvore filogenética. PhyML é um dos principais programas que realizam a Reconstrução de Árvores Filogenéticas. O bootstrap é um método estatístico utilizado para medir a confiança de um determinado conjunto de dados, que é usualmente aplicado na análise de árvores filogenéticas inferidas. No PhyML, esse método possui duas implementações paralelas MPI: com operações ponto-a-ponto e operações coletivas. A segunda versão é mais eficiente que a primeira, porém apresenta uma limitação no número de bootstrap a ser utilizado devido ao aumento no consumo de memória. Para solucionar esse problema foram desenvolvidas três soluções. O objetivo deste trabalho foi realizar a validação destas versões juntamente com testes de desempenho. A validação mostrou que as soluções propostas apresentam resultados equivalentes à versão ponto-a-ponto. Já nas simulações de desempenho, duas soluções se mostraram superiores à versão ponto-a-ponto, sendo que a melhor conseguiu ganhos de 28,46% e 39,64% para 32 e 64 processos, respectivamente. Portanto, os aprimoramentos permitem alternativas à versão ponto-a-ponto sem limitação de memória.
Downloads
Referências
AVILA, R. B.; NAVAUX, P. O. A.; LOMBARD, P.; LEBRE, A. and DENNEULIN, Y. Performance evaluation of a prototype distributed NFS server In: 16th Symposium on Computer Architecture and High Performance Computing, 2004, Foz do Iguacu, 2004, p. 100-105. doi: 10.1109/SBAC-PAD.2004.33.
FELSENSTEIN, J. Inferring Phylogenies. Sunderland, Massachusetts: Sinauer Associates, 2004. 664 p.
GUINDON, S.; GASCUEL, O. A Simple, Fast, and Accurate Algorithm to Estimate Large Phylogenies by Maximum Likelihood. Systematic Biology, v. 52 n. 5, p. 696-704, 2003. Disponível em: <https://pubmed.ncbi.nlm.nih.gov/14530136/>. Acesso: 06 jul. 2020.
ISMAIL, R,; HAMID, N.; OTHMAN, M. and LATIP, R. Performance analysis of message passing interface collective communication on Intel Xeon quad-core Gigabit Ethernet and InfiniBand clusters. Journal of Computer Science, v. 9, p. 455-462, jan. 2013. Disponível em: <https://thescipub.com/abstract/10.3844/jcssp.2013.455.462/>. Acesso: 06 jul. 2020.
LATHAM, R.; ROSS, R. and THAKUR, R. The Impact of File Systems on MPI-IO Scalability. In: Kranzlmüller D., Kacsuk P., Dongarra J. (eds) Recent Advances in Parallel Virtual Machine and Message Passing Interface. EuroPVM/MPI 2004. Lecture Notes in Computer Science, vol 3241. Springer, Berlin, Heidelberg. Disponível em: < https://link.springer.com/chapter/10.1007/978-3-540-30218-6_18 />. Acesso: 06 jul. 2020.
ROBINSON, D.F. and FOULDS, L.R. Comparison of phylogenetic trees. Mathematical Bioscienses, v.53 (1), p. 131-147, 1981.
SORIA-CARRASCO, V.; TALAVERA, G.; IGEA, J. and CASTRESANA, J. The K tree score: quantification of differences in the relative branch length and topology of phylogenetic trees. Bioinformatics, v.23 (21), p. 2954-2956, 2007. doi:10.1093/bioinformatics/btm466
TICONA, W. G. C. Algoritmos evolutivos multi-objetivo para a reconstrução de árvores filogenéticas. 2008. 134 f. Tese (Doutorado em Ciências na área de Ciência da Computação e Matemática Computacional) -Instituto de ciências Matemáticas e de Computação, Universidade de São Paulo, São Carlos. Disponível em: < https://www.teses.usp.br/teses/disponiveis/55/55134/tde-02042008-142554/publico/tese_waldo_corregida.pdf>. Acesso: 06 jul. 2020.
TREEBASE: A Database of Phylogenetic Knowledge. Disponível em: <http://treebase.org/treebase-web/home.html>. Acesso em: 06 jul. 2020.
TORRES M. and DA SILVA J.O. Parallel Solution Based on Collective Communication Operations for Phylogenetic Bootstrapping in PhyML 3.0. In: Alves R. (eds) Advances in Bioinformatics and Computational Biology. BSB 2018. Lecture Notes in Computer Science, vol 11228. Springer, Cham.
PATTENGALE, N.D.; ALIPOUR M.; BININDA-EMOND, O.R.P.; MORET B.M.E. and STAMATAKIS, A. How Many Bootstrap Replicates Are Necessary?. In: Batzoglou S. (eds) Research in Computational Molecular Biology. RECOMB 2009. Lecture Notes in Computer Science, vol 5541. Springer, Berlin, Heidelberg.
TREEBASE: A Database of Phylogenetic Knowledge. Disponível em: <http://treebase.org/treebase-web/home.html>. Acesso em: 06 jul. 2020.
VERLI, Hugo. Bioinformática: da biologia à flexibilidade molecular. São Paulo: Sbbq, 2014. 282 p. Disponível em: <http http://www.gradadm.ifsc.usp.br/dados/20171/7600011-3/Bioinformatica_1.1.pdf>. Acesso em: 06 jul. 2020.