MGUPGMA: A Fast UPGMA Algorithm With Multiple Graphics Processing Units Using NCCL. (October 2017)

• Record Type: Journal Article
• Authors: Hua, Guan-Jie; Hung, Che-Lun; Lin, Chun-Yuan; Wu, Fu-Che; Chan, Yu-Wei; Tang, Chuan Yi
• Is Part Of: Evolutionary bioinformatics online. Volume 13(2017)
• Publication Date: 2017-10
• Subjects: Phylogenetic tree -- UPGMA -- GPU -- parallel computing -- multiple GPUs; Bioinformatics -- Periodicals; Evolutionary computation -- Periodicals; Genetic programming (Computer science) -- Periodicals; Computational Biology; Evolution, Molecular; Bioinformatics; Electronic journals; Periodicals; Fulltext; Internet Resources; Periodicals; Periodicals; 576.8
• DOI: 10.1177/1176934317734220
• Languages: English
• ISSNs: 1176-9343

Abstract

A phylogenetic tree is a visual diagram of the relationship between a set of biological species. The scientists usually use it to analyze many characteristics of the species. The distance-matrix methods, such as Unweighted Pair Group Method with Arithmetic Mean and Neighbor Joining, construct a phylogenetic tree by calculating pairwise genetic distances between taxa. These methods have the computational performance issue. Although several new methods with high-performance hardware and frameworks have been proposed, the issue still exists. In this work, a novel parallel Unweighted Pair Group Method with Arithmetic Mean approach on multiple Graphics Processing Units is proposed to construct a phylogenetic tree from extremely large set of sequences. The experimental results present that the proposed approach on a DGX-1 server with 8 NVIDIA P100 graphic cards achieves approximately 3-fold to 7-fold speedup over the implementation of Unweighted Pair Group Method with Arithmetic Mean on a modern CPU and a single GPU, respectively.