NMFSt.P: um Notebook para Identificação em Paralelo de Subárvores Frequentes em Conjuntos de Árvores Filogenéticas
Resumo
A análise exploratória de informações evolutivas em árvores filogenéticas é uma tarefa importante no contexto da bioinformática. Tal análise depende em muitos casos da identificação de subárvores frequentes em um conjunto de árvores filogenéticas de entrada. Essa identificação pode ser uma tarefa computacionalmente intensiva e laboriosa, dependendo do tamanho do conjunto de árvores de entrada. Nesse artigo apresentamos o Notebook NMFSt.P, que permite a comparação de múltiplas árvores filogenéticas para a identificação de subárvores frequentes. Experimentos realizados mostraram que o NMFSt.P conseguiu gerar resultados similares a abordagem baseline ao mesmo tempo em que apresentou melhoria de desempenho de até 68,31% no tempo de execução com o uso de um maior número de vCPUs na nuvem.
Palavras-chave:
Bioinformática, Filogenia, Mineração de dados
Referências
Amir, A. and Keselman, D. (1997). Maximum agreement subtree in a set of evolutionary trees: Metrics and efficient algorithms. SIAM Journal on Computing, 26(6):1656–1669.
Babuji, Y. N. et al. (2019). Parsl: Pervasive parallel programming in python. In Weissman, J. B., Butt, A. R., and Smirni, E., editors, Proc. of the 28th HPDC, pages 25–36. ACM.
Bryant, D. (2003). A classification of consensus methods for phylogenetics, pages 163–183.
de Oliveira, D. C. M., Liu, J., and Pacitti, E. (2019). Data-Intensive Workflow Management: For Clouds and Data-Intensive and Scalable Computing Environments. Synthesis Lectures on Data Management. Morgan & Claypool Publishers.
Deepak, A. et al. (2014). Evominer: frequent subtree mining in phylogenetic databases. Knowledge and Information Systems, 41(3):559–590.
Deepak, A. and Fernández-Baca, D. (2014). Enumerating all maximal frequent subtrees in collections of phylogenetic trees. Algorithms for Molecular Biology, 9(1):16.
Felsenstein, J. (1983). Statistical inference of phylogenies. Journal of the Royal Statistical Society. Series A (General), 146(3):246–272.
Goloboff, P. A. et al. (2009). Phylogenetic analysis of 73 060 taxa corroborates major eukaryotic groups. Cladistics, 25(3):211–230.
Guedes, T., Ocaña, K., and de Oliveira, D. (2017). Sciphylominer: um workflow para mineração de dados filogemônicos de protozoários. In Anais do XI Brazilian e-Science Workshop, pages 69–76, Porto Alegre, RS, Brasil. SBC.
Molloy, E. K. and Warnow, T. (2019). TreeMerge: a new method for improving the scalability of species tree estimation methods. Bioinformatics, 35(14):i417–i426.
Ocaña, K. A. C. S. et al. (2011). Sciphy: A cloud-based workflow for phylogenetic analysis of drug targets in protozoan genomes. In Proc. of the 6th Brazilian Symposium on Bioinformatics, pages 66–70. Springer.
Ocaña, K. A. and Dávila, A. M. (2011). Phylogenomics-based reconstruction of protozoan species tree. Evol Bioinform Online, 7:107–121.
Puigbò, P., Wolf, Y. I., and Koonin, E. V. (2019). Genome-Wide Comparative Analysis of Phylogenetic Trees: The Prokaryotic Forest of Life, pages 241–269. Springer New York, New York, NY.
Ramu, A., Kahveci, T., and Burleigh, J. G. (2012). A scalable method for identifying frequent subtrees in sets of large phylogenetic trees. BMC Bioinformatics, 13(1):256.
Rasmussen, D. A. and Guo, F. (2022). Espalier: Efficient tree reconciliation and arg reconstruction using maximum agreement forests. bioRxiv.
Saitou, N. and Nei, M. (1987). The neighbor-joining method: a new method for reconstructing phylogenetic trees. Mol Biol Evol, 4(4):406–425.
Thompson, J. D., Higgins, D. G., and Gibson, T. J. (1994). ClustalW: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice. Nucleic Acids Res, 22(22):4673–4680.
Vilella, A. J., Severin, J., Ureta-Vidal, A., Heng, L., Durbin, R., and Birney, E. (2009). Ensemblcompara genetrees: Complete, duplication-aware phylogenetic trees in vertebrates. Genome research, 19 2:327–35.
Babuji, Y. N. et al. (2019). Parsl: Pervasive parallel programming in python. In Weissman, J. B., Butt, A. R., and Smirni, E., editors, Proc. of the 28th HPDC, pages 25–36. ACM.
Bryant, D. (2003). A classification of consensus methods for phylogenetics, pages 163–183.
de Oliveira, D. C. M., Liu, J., and Pacitti, E. (2019). Data-Intensive Workflow Management: For Clouds and Data-Intensive and Scalable Computing Environments. Synthesis Lectures on Data Management. Morgan & Claypool Publishers.
Deepak, A. et al. (2014). Evominer: frequent subtree mining in phylogenetic databases. Knowledge and Information Systems, 41(3):559–590.
Deepak, A. and Fernández-Baca, D. (2014). Enumerating all maximal frequent subtrees in collections of phylogenetic trees. Algorithms for Molecular Biology, 9(1):16.
Felsenstein, J. (1983). Statistical inference of phylogenies. Journal of the Royal Statistical Society. Series A (General), 146(3):246–272.
Goloboff, P. A. et al. (2009). Phylogenetic analysis of 73 060 taxa corroborates major eukaryotic groups. Cladistics, 25(3):211–230.
Guedes, T., Ocaña, K., and de Oliveira, D. (2017). Sciphylominer: um workflow para mineração de dados filogemônicos de protozoários. In Anais do XI Brazilian e-Science Workshop, pages 69–76, Porto Alegre, RS, Brasil. SBC.
Molloy, E. K. and Warnow, T. (2019). TreeMerge: a new method for improving the scalability of species tree estimation methods. Bioinformatics, 35(14):i417–i426.
Ocaña, K. A. C. S. et al. (2011). Sciphy: A cloud-based workflow for phylogenetic analysis of drug targets in protozoan genomes. In Proc. of the 6th Brazilian Symposium on Bioinformatics, pages 66–70. Springer.
Ocaña, K. A. and Dávila, A. M. (2011). Phylogenomics-based reconstruction of protozoan species tree. Evol Bioinform Online, 7:107–121.
Puigbò, P., Wolf, Y. I., and Koonin, E. V. (2019). Genome-Wide Comparative Analysis of Phylogenetic Trees: The Prokaryotic Forest of Life, pages 241–269. Springer New York, New York, NY.
Ramu, A., Kahveci, T., and Burleigh, J. G. (2012). A scalable method for identifying frequent subtrees in sets of large phylogenetic trees. BMC Bioinformatics, 13(1):256.
Rasmussen, D. A. and Guo, F. (2022). Espalier: Efficient tree reconciliation and arg reconstruction using maximum agreement forests. bioRxiv.
Saitou, N. and Nei, M. (1987). The neighbor-joining method: a new method for reconstructing phylogenetic trees. Mol Biol Evol, 4(4):406–425.
Thompson, J. D., Higgins, D. G., and Gibson, T. J. (1994). ClustalW: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice. Nucleic Acids Res, 22(22):4673–4680.
Vilella, A. J., Severin, J., Ureta-Vidal, A., Heng, L., Durbin, R., and Birney, E. (2009). Ensemblcompara genetrees: Complete, duplication-aware phylogenetic trees in vertebrates. Genome research, 19 2:327–35.
Publicado
25/09/2023
Como Citar
FERRARI, Camila; MORAES, João Vitor; DE OLIVEIRA, Daniel.
NMFSt.P: um Notebook para Identificação em Paralelo de Subárvores Frequentes em Conjuntos de Árvores Filogenéticas. In: BRAZILIAN E-SCIENCE WORKSHOP (BRESCI), 17. , 2023, Belo Horizonte/MG.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2023
.
p. 1-8.
ISSN 2763-8774.
DOI: https://doi.org/10.5753/bresci.2023.234110.
