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

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.