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

Chun Yuan Lin*, Yu Shiang Lin

*Corresponding author for this work

Research output: Contribution to journalJournal Article peer-review

12 Scopus citations

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.

Original languageEnglish
Pages (from-to)11-20
Number of pages10
JournalInternational Journal of Computational Science and Engineering
Volume9
Issue number1-2
DOIs
StatePublished - 2014

Keywords

  • CUDA
  • Dynamic programming
  • GPUs
  • Graphics processing units
  • Multiple sequence alignments
  • Parallel processing
  • Regular expression

Fingerprint

Dive into the research topics of 'Efficient parallel algorithm for multiple sequence alignments with regular expression constraints on graphics processing units'. Together they form a unique fingerprint.

Cite this