CUDA ClustalW: An efficient parallel algorithm for progressive multiple sequence alignment on Multi-GPUs

Che-Lun Hung; Yu-Shiang Lin; Chun-Yuan Lin; Yeh-Ching Chung; Yi-Fang Chung

doi:10.1016/j.compbiolchem.2015.05.004

CUDA ClustalW: An efficient parallel algorithm for progressive multiple sequence alignment on Multi-GPUs

Comput Biol Chem. 2015 Oct:58:62-8. doi: 10.1016/j.compbiolchem.2015.05.004. Epub 2015 May 21.

Authors

Che-Lun Hung¹, Yu-Shiang Lin², Chun-Yuan Lin³, Yeh-Ching Chung², Yi-Fang Chung⁴

Affiliations

¹ Department of Computer Science and Communication Engineering, Providence University, 200, Sec. 7, Taiwan Boulevard, Shalu Dist., Taichung City 43301, Taiwan. Electronic address: clhung@pu.edu.tw.
² Department of Computer Science, National Tsing Hua University, 101, Sec. 2, Kuang-Fu Road, Hsinchu City 30013, Taiwan.
³ Department of Computer Science and Information Engineering, Chang Gung University, 259, Wen-Hwa 1st Road, Kwei-Shan, Taoyuan City 33302, Taiwan. Electronic address: cyulin@mail.cgu.edu.tw.
⁴ Department of Computer Science and Information Engineering, Chang Gung University, 259, Wen-Hwa 1st Road, Kwei-Shan, Taoyuan City 33302, Taiwan.

PMID: 26052076
DOI: 10.1016/j.compbiolchem.2015.05.004

Abstract

For biological applications, sequence alignment is an important strategy to analyze DNA and protein sequences. Multiple sequence alignment is an essential methodology to study biological data, such as homology modeling, phylogenetic reconstruction and etc. However, multiple sequence alignment is a NP-hard problem. In the past decades, progressive approach has been proposed to successfully align multiple sequences by adopting iterative pairwise alignments. Due to rapid growth of the next generation sequencing technologies, a large number of sequences can be produced in a short period of time. When the problem instance is large, progressive alignment will be time consuming. Parallel computing is a suitable solution for such applications, and GPU is one of the important architectures for contemporary parallel computing researches. Therefore, we proposed a GPU version of ClustalW v2.0.11, called CUDA ClustalW v1.0, in this work. From the experiment results, it can be seen that the CUDA ClustalW v1.0 can achieve more than 33× speedups for overall execution time by comparing to ClustalW v2.0.11.

Keywords: CUDA; ClustalW; GPU; Parallel computing; Progressive multiple sequence alignment.

Publication types

Research Support, Non-U.S. Gov't

MeSH terms

Algorithms
Sequence Alignment*
Sequence Analysis, Protein
Software*