Parallel UPGMA algorithm on graphics processing units using CUDA

Yu Rong Chen, Che Lun Hung, Yu Shiang Lin, Chun Yuan Lin*, Tien Lin Lee, Kual Zheng Lee

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

9 Scopus citations

Abstract

The construction of phylogenetic trees is important for the computational biology, especially for the development of biological taxonomies. UPGMA is one of the most popular heuristic algorithms for constructing ultrametric trees (UT). Although the UT constructed by the UPGMA often is not a true tree unless the molecular clock assumption holds, the UT is still useful for the clocklike data. However, a fundamental problem with the previous implementations of this method is its limitation to handle large tax a sets within a reasonable time. In this paper, we present GPU-UPGMA which can provide a fast construction of very large datasets for biologists. Experimental results show that GPU-UPGMA obtains about 95 times speedup on NVIDIA Tesla C2050 GPU over the 2.13 GHz CPU implementation.

Original languageEnglish
Title of host publicationProceedings of the 14th IEEE International Conference on High Performance Computing and Communications, HPCC-2012 - 9th IEEE International Conference on Embedded Software and Systems, ICESS-2012
Pages849-854
Number of pages6
DOIs
StatePublished - 2012
Event14th IEEE International Conference on High Performance Computing and Communications, HPCC-2012 - 9th IEEE International Conference on Embedded Software and Systems, ICESS-2012 - Liverpool, United Kingdom
Duration: 25 Jun 201227 Jun 2012

Publication series

NameProceedings of the 14th IEEE International Conference on High Performance Computing and Communications, HPCC-2012 - 9th IEEE International Conference on Embedded Software and Systems, ICESS-2012

Conference

Conference14th IEEE International Conference on High Performance Computing and Communications, HPCC-2012 - 9th IEEE International Conference on Embedded Software and Systems, ICESS-2012
Country/TerritoryUnited Kingdom
CityLiverpool
Period25/06/1227/06/12

Keywords

  • CUDA
  • Distance matrix
  • Evolutionary tree construction
  • Phylogenetic Tree
  • UPGMA
  • graphics processing units

Fingerprint

Dive into the research topics of 'Parallel UPGMA algorithm on graphics processing units using CUDA'. Together they form a unique fingerprint.

Cite this