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

摘要

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