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

doi:10.1109/HPCC.2012.120

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 proceeding › Conference contribution › peer-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 language	English
Title of host publication	Proceedings 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
Pages	849-854
Number of pages	6
DOIs	https://doi.org/10.1109/HPCC.2012.120
State	Published - 2012
Event	14th 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 06 2012 → 27 06 2012

Publication series

Name	Proceedings 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

Conference	14th IEEE International Conference on High Performance Computing and Communications, HPCC-2012 - 9th IEEE International Conference on Embedded Software and Systems, ICESS-2012
Country/Territory	United Kingdom
City	Liverpool
Period	25/06/12 → 27/06/12

Keywords

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

Access to Document

10.1109/HPCC.2012.120

Cite this

Chen, Y. R., Hung, C. L., Lin, Y. S., Lin, C. Y., Lee, T. L., & Lee, K. Z. (2012). Parallel UPGMA algorithm on graphics processing units using CUDA. In Proceedings 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 (pp. 849-854). Article 6332258 (Proceedings 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). https://doi.org/10.1109/HPCC.2012.120

Chen, Yu Rong ; Hung, Che Lun ; Lin, Yu Shiang et al. / Parallel UPGMA algorithm on graphics processing units using CUDA. Proceedings 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. 2012. pp. 849-854 (Proceedings 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).

@inproceedings{98e1e9ec28b94054b57bd487c4daec36,

title = "Parallel UPGMA algorithm on graphics processing units using CUDA",

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.",

keywords = "CUDA, Distance matrix, Evolutionary tree construction, Phylogenetic Tree, UPGMA, graphics processing units",

author = "Chen, \{Yu Rong\} and Hung, \{Che Lun\} and Lin, \{Yu Shiang\} and Lin, \{Chun Yuan\} and Lee, \{Tien Lin\} and Lee, \{Kual Zheng\}",

year = "2012",

doi = "10.1109/HPCC.2012.120",

language = "英语",

isbn = "9780769547497",

series = "Proceedings 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",

pages = "849--854",

booktitle = "Proceedings 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",

note = "14th IEEE International Conference on High Performance Computing and Communications, HPCC-2012 - 9th IEEE International Conference on Embedded Software and Systems, ICESS-2012 ; Conference date: 25-06-2012 Through 27-06-2012",

}

Chen, YR, Hung, CL, Lin, YS, Lin, CY, Lee, TL & Lee, KZ 2012, Parallel UPGMA algorithm on graphics processing units using CUDA. in Proceedings 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., 6332258, Proceedings 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, pp. 849-854, 14th 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, 25/06/12. https://doi.org/10.1109/HPCC.2012.120

Parallel UPGMA algorithm on graphics processing units using CUDA. / Chen, Yu Rong; Hung, Che Lun; Lin, Yu Shiang et al.
Proceedings 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. 2012. p. 849-854 6332258 (Proceedings 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).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Parallel UPGMA algorithm on graphics processing units using CUDA

AU - Chen, Yu Rong

AU - Hung, Che Lun

AU - Lin, Yu Shiang

AU - Lin, Chun Yuan

AU - Lee, Tien Lin

AU - Lee, Kual Zheng

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

KW - CUDA

KW - Distance matrix

KW - Evolutionary tree construction

KW - Phylogenetic Tree

KW - UPGMA

KW - graphics processing units

UR - https://www.scopus.com/pages/publications/84870468279

U2 - 10.1109/HPCC.2012.120

DO - 10.1109/HPCC.2012.120

M3 - 会议稿件

AN - SCOPUS:84870468279

SN - 9780769547497

T3 - Proceedings 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

SP - 849

EP - 854

BT - Proceedings 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

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

Y2 - 25 June 2012 through 27 June 2012

ER -

Chen YR, Hung CL, Lin YS, Lin CY, Lee TL, Lee KZ. Parallel UPGMA algorithm on graphics processing units using CUDA. In Proceedings 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. 2012. p. 849-854. 6332258. (Proceedings 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). doi: 10.1109/HPCC.2012.120

Parallel UPGMA algorithm on graphics processing units using CUDA

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this