A GPU-based parallel method for evolutionary tree construction

作者：Zheng Ran^*; Zhang Qiongyao; Jin Hai; Shao Zhiyuan; Feng Xiaowen

来源：Computers & Electrical Engineering, 2014, 40(5): 1580-1591.

DOI：10.1016/j.compeleceng.2014.04.013

Evolutionary trees are widely applied in various applications to show the inferred evolutionary relationships among species or entities. Neighbor-Joining is one solution for data-intensive and time-consuming evolutionary tree construction, with polynomial time complexity. However, its performance becomes poorer with the growth of massive datasets. Graphics Processing Units (GPUs) have brought about new opportunities for these time-consuming applications. Based on its high efficiency, a GPU-based parallel Neighbor-Joining method is proposed, and two efficient parallel mechanisms, data segmentation with asynchronous processing and the minimal chain model with bitonic sort, are put forward to speed up the processing. The experimental results show that an average speedup of 25.1 is achieved and even approximately 30 can be obtained with a sequence dataset ranging from 16,000 to 25,000. Moreover, the proposed parallel mechanisms can be effectively exploited in some other high performance applications.

• 出版日期2014-7
• 单位华中科技大学