title: CUDA ClustalW: An efficient parallel algorithm for progressive multiple sequence alignment on Multi-GPUs.
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.
authors.affiliation: 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.
authors.forename: Che-Lun
authors.initials: CL
authors.lastname: Hung
authors.affiliation: Department of Computer Science, National Tsing Hua University, 101, Sec. 2, Kuang-Fu Road, Hsinchu City 30013, Taiwan.
authors.forename: Yu-Shiang
authors.initials: YS
authors.lastname: Lin
authors.affiliation: 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.
authors.forename: Chun-Yuan
authors.initials: CY
authors.lastname: Lin
authors.affiliation: Department of Computer Science, National Tsing Hua University, 101, Sec. 2, Kuang-Fu Road, Hsinchu City 30013, Taiwan.
authors.forename: Yeh-Ching
authors.initials: YC
authors.lastname: Chung
authors.affiliation: Department of Computer Science and Information Engineering, Chang Gung University, 259, Wen-Hwa 1st Road, Kwei-Shan, Taoyuan City 33302, Taiwan.
authors.forename: Yi-Fang
authors.initials: YF
authors.lastname: Chung
mesh_terms: D000465:Algorithms; D016415:Sequence Alignment; D020539:Sequence Analysis, Protein; D012984:Software
keywords: CUDA; ClustalW; GPU; Parallel computing; Progressive multiple sequence alignment