title: Pairwise sequence alignment for very long sequences on GPUs.
abstract: We develop novel single-GPU parallelisations of the Smith-Waterman algorithm for pairwise sequence alignment. Our algorithms, which are suitable for the alignment of a single pair of very long sequences, can be used to determine the alignment score as well as the actual alignment. Experimental results demonstrate an order of magnitude reduction in run time relative to competing GPU algorithms.
authors.affiliation: Department of Computer and Information Science and Engineering, University of Florida, Gainesville, FL-32611, USA.
authors.forename: Junjie
authors.initials: J
authors.lastname: Li
authors.affiliation: Department of Computer and Information Science and Engineering, University of Florida, Gainesville, FL-32611, USA.
authors.forename: Sanjay
authors.initials: S
authors.lastname: Ranka
authors.affiliation: Department of Computer and Information Science and Engineering, University of Florida, Gainesville, FL-32611, USA.
authors.forename: Sartaj
authors.initials: S
authors.lastname: Sahni
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D003196:Computer Graphics; D030562:Databases, Protein; D016247:Information Storage and Retrieval; D016415:Sequence Alignment / Q000379:methods*; D012984:Software
keywords: CUDA; GPU; Smith–Waterman algorithm; bioinformatics; graphics processing units; local alignment; pairwise sequence alignment