Fast Flexible Neighbor-Joining Using Multicomputing
A. Chastel Lima, Elói Araújo, Marco A. Stefanes, Luiz C. S. Rozante · 2023
In this study, we tackle the challenge of reconstructing the evolutionary history of a group of species, a crucial problem in bioinformatics. Phylogenetic trees visually represent relationships among organisms. While the Neighbor-Joining method (NJ) is effective, it faces limitations with larger datasets, whereas the Unweighted Pair Group Method with Arithmetic Mean (UPGMA) is more efficient for such sets. However, the quality of the UPGMA tree may be compromised due to its assumptions about uniform evolutionary rates. In this work, we introduce a parallel implementation strategy using multi-threaded computing. This approach combines accuracy comparable to Neighbor-Joining with the time efficiency of UPGMA. Experimental tests on synthetic datasets ranging from 1k to 32k OTUs show good performance, accuracy, and scalability of the proposed solution when compared to Biotite, a popular tool employing a parallel approach for UPGMA and NJ. For large dataset (16k-32k) we achieved speedup up to 6 using a 24-core CPU. Morover, with appropriated setup our implementation is up to 447 times faster than NJ and up to 133 times faster than UPGMA with satisfactory quality.