STM Journals Peer-reviewed research from Consortium e-Learning Network

International Journal of Algorithms Design and Analysis Review Review Article

Parallel Greedy Approach for Phylogenetic Tree Construction in the Context of Marine Species

  1. Sathi Lakshmi Teja Sri Department of Computer Science and Engineering, Pragati Engineering College, Surampalem
  2. Manas Kumar Yogi Department of Computer Science and Engineering, Pragati Engineering College, Surampalem

Abstract

The rebuilding of phylogenetic trees for marine species shows major computing problems because of the massive genomic data and the huge biodiversity inherent in ocean ecosystems. Traditional phylogenetic methods are accurate but become more expensive when they are processing with thousands of marine taxa parallelly. This article shows a critical analysis of parallel greedy algorithms as an adaptable solution for large-scale marine phylogenetics. It examines the main principles of greedy heuristics applied in the construction of tree based on distance, specifically on neighbor joining and its variations. The paper demonstrates that the implementation of the parallelization techniques, data parallelism, task parallelism, and the hybrid models may be utilized to overcome the time complexity factors that restrict the use of the traditional implementation of the usual methods in a quadratic manner. The analysis integrates current advances in shared computing architectures, graphical processing units (GPU) acceleration, and algorithmic optimizations that show the working of marine metagenomic datasets that have tens of thousands of operational taxonomic units. Performance improvements are evaluated in various fields of marine research, such as microbial community studies and vertebrate evolutionary studies, and examples of nearly linear speedup of parallel greedy approaches on high-performance computing clusters have been documented. In addition to this, we discuss the synthesis of these methods with advanced technologies such as cloud computing and software containerization to enable accessible marine biodiversity studies. The results show that parallel greedy methods decrease phylogenetic rebuilding time complexity from days to hours for datasets containing 10,000+ marine species, showcasing live analysis of natural samples and providing large-scale evolutionary studies crucial for conservation and climate impact assessment.

Keywords

References (20)

  1. Stewart EEM, Hartmann FT, Morgenstern Y, Storrs KR, Maiello G, Fleming RW. Mental object rotation based on two-dimensional visual representations. Current Biology. 2022;32(21):R1224-R1225. doi:10.1016/j.cub.2022.09.036
  2. Lin X, Amalraj M, Blanton C, Avila B, Holmes TC, Nitz DA, et al. Noncanonical projections to the hippocampal CA3 regulate spatial learning and memory by modulating the feedforward hippocampal trisynaptic pathway. PLOS Biology. 2021;19(12):e3001127. doi:10.1371/journal.pbio.3001127
  3. Kapli P, Yang Z, Telford MJ. Phylogenetic tree building in the genomic age. Nature Reviews Genetics. 2020;21(7):428-444. doi:10.1038/s41576-020-0233-0
  4. Purkayastha P, Pendyala K, Saxena AS, Hakimjavadi H, Chamala S, Dixit P, et al. Reverse Plasticity Underlies Rapid Evolution by Clonal Selection within Populations of Fibroblasts Propagated on a Novel Soft Substrate. Molecular Biology and Evolution. 2021;38(8):3279-3293. doi:10.1093/molbev/msab102
  5. Borenstein E, Kupiec M, Feldman MW, Ruppin E. Large-scale reconstruction and phylogenetic analysis of metabolic environments. Proceedings of the National Academy of Sciences. 2008;105(38):14482-14487. doi:10.1073/pnas.0806162105
  6. Sunagawa S, Acinas SG, Bork P, Bowler C, Tara Oceans Coordinators, Acinas SG, et al. Tara Oceans: towards global ocean ecosystems biology. Nature Reviews Microbiology. 2020;18(8):428-445. doi:10.1038/s41579-020-0364-5
  7. Obradovic A, Chowdhury N, Haake SM, Ager C, Wang V, Vlahos L, et al. Single-cell protein activity analysis identifies recurrence-associated renal tumor macrophages. Cell. 2021;184(11):2988-3005.e16. doi:10.1016/j.cell.2021.04.038
  8. Karmin M, Flores R, Saag L, Hudjashov G, Brucato N, Crenna-Darusallam C, et al. Episodes of Diversification and Isolation in Island Southeast Asian and Near Oceanian Male Lineages. Molecular Biology and Evolution. 2022;39(3). doi:10.1093/molbev/msac045
  9. Ren Y, Chakraborty T, Doijad S, Falgenhauer L, Falgenhauer J, Goesmann A, et al. Prediction of antimicrobial resistance based on whole-genome sequencing and machine learning. Bioinformatics. 2021;38(2):325-334. doi:10.1093/bioinformatics/btab681
  10. Price MN, Dehal PS, Arkin AP. FastTree 2 – Approximately Maximum-Likelihood Trees for Large Alignments. PLoS ONE. 2010;5(3):e9490. doi:10.1371/journal.pone.0009490
  11. Friedman ST, Collyer ML, Price SA, Wainwright PC. Divergent Processes Drive Parallel Evolution in Marine and Freshwater Fishes. Systematic Biology. 2021;71(6):1319-1330. doi:10.1093/sysbio/syab080
  12. Nyström-Persson J, Keeble-Gagnère G, Zawad N. Compact and evenly distributed k -mer binning for genomic sequences. Bioinformatics. 2021;37(17):2563-2569. doi:10.1093/bioinformatics/btab156
  13. Gao Y, Liu Y, Ma Y, Liu B, Wang Y, Xing Y. abPOA: an SIMD-based C library for fast partial order alignment using adaptive band. Bioinformatics. 2020;37(15):2209-2211. doi:10.1093/bioinformatics/btaa963
  14. Hughes EC, Edwards DP, Thomas GH. The homogenization of avian morphological and phylogenetic diversity under the global extinction crisis. Current Biology. 2022;32(17):3830-3837.e3. doi:10.1016/j.cub.2022.06.018
  15. Shao H, Ruan J. BSAlign: A Library for Nucleotide Sequence Alignment. Genomics, Proteomics & Bioinformatics. 2024;22(2). doi:10.1093/gpbjnl/qzae025
  16. Czech L, Stamatakis A. Scalable methods for analyzing and visualizing phylogenetic placement of metagenomic samples. PLOS ONE. 2019;14(5):e0217050. doi:10.1371/journal.pone.0217050
  17. Günder M, Ispizua Yamati FR, Kierdorf J, Roscher R, Mahlein AK, Bauckhage C. Agricultural plant cataloging and establishment of a data framework from UAV-based crop images by computer vision. GigaScience. 2022;11. doi:10.1093/gigascience/giac054
  18. Yap TK, Frieder O, Martino RL. Parallel computation in biological sequence analysis. IEEE Transactions on Parallel and Distributed Systems. 1998;9(3):283-294. doi:10.1109/71.674320
  19. van Rosmalen L, Riedstra B, Beemster N, Dijkstra C, Hut RA. Differential temperature effects on photoperiodism in female voles: A possible explanation for declines in vole populations. Molecular Ecology. 2022;31(12):3360-3373. doi:10.1111/mec.16467
  20. Johnston A, Matechou E, Dennis EB. Outstanding challenges and future directions for biodiversity monitoring using citizen science data. Methods in Ecology and Evolution. 2022;14(1):103-116. doi:10.1111/2041-210x.13834