GPU-UPGMA: High-performance computing for UPGMA algorithm based on graphics processing units

Yu Shiang Lin, Chun Yuan Lin, Che Lun Hung*, Yeh Ching Chung, Kual Zheng Lee

*此作品的通信作者

研究成果: Article同行評審

8 引文 斯高帕斯(Scopus)

摘要

Summary Constructing phylogenetic trees is of priority concern in computational biology, especially for developing biological taxonomies. As a conventional means of constructing phylogenetic trees, unweighted pair group method with arithmetic (UPGMA) is also an extensively adopted heuristic algorithm for constructing ultrametric trees (UT). Although the UT constructed by UPGMA is often not a true tree unless the molecular clock assumption holds, UT is still useful for the clocklike data. Moreover, UT has been successfully adopted in other problems, including orthologous-domain classification and multiple sequence alignment. However, previous implementations of the UPGMA method have a limited ability to handle large taxa sets efficiently. This work describes a novel graphics processing unit (GPU)-UPGMA approach, capable of providing rapid construction of extremely large datasets for biologists. Experimental results indicate that the proposed GPU-UPGMA approach achieves an approximately 95× speedup ratio on NVIDIA Tesla C2050 GPU over the implementation with 2.13'GHz CPU. The developed techniques in GPU-UPGMA also can be applied to solve the classification problem for large data set with more than tens of thousands items in the future.

原文English
頁(從 - 到)3403-3414
頁數12
期刊Concurrency Computation Practice and Experience
27
發行號13
DOIs
出版狀態Published - 10 9月 2015

指紋

深入研究「GPU-UPGMA: High-performance computing for UPGMA algorithm based on graphics processing units」主題。共同形成了獨特的指紋。

引用此