Title: Efficient parallel algorithm for multiple sequence alignments with regular expression constraints on graphics processing units

Authors: Chun Yuan Lin; Yu Shiang Lin

Addresses: Department of Computer Science and Information Engineering, Chang Gung University, Taoyuan, 333, Taiwan ' Department of Computer Science and Information Engineering, Chang Gung University, Taoyuan, 333, Taiwan

Abstract: Multiple sequence alignments with constraints has become an important problem in computational biology. The concept of constrained sequence alignment is proposed to incorporate the biologist's domain knowledge into sequence alignments such that the user-specified residues/segments are aligned together in the alignment results. Over the past decade, a series of constrained multiple sequence alignment tools were proposed in the literature. RE-MuSiC is the newest tool with the regular expression constraints and useful for a wide range of biological applications. However, the computation time of REMuSiC is large for a large amount of sequences or long sequences and this problem limits the application usage. Therefore, in this paper, a tool, GPU-REMuSiC v1.0, is proposed to reduce the computation time of RE-MuSiC by using the graphics processing units with CUDA. GPU-REMuSiC v1.0 can achieve 29× speedups for overall computation time by the experimental results.

Keywords: multiple sequence alignments; regular expression; CUDA; graphics processing units; GPUs; parallel processing; dynamic programming; computational biology; bioinformatics; gene sequences.

DOI: 10.1504/IJCSE.2014.058687

International Journal of Computational Science and Engineering, 2014 Vol.9 No.1/2, pp.11 - 20

Received: 01 Feb 2012
Accepted: 04 Mar 2012
Published online: 24 May 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article