Cache-oblivious dynamic programming for bioinformatics.
We present efficient cache-oblivious algorithms for some well-studied string problems in bioinformatics including the longest common subsequence, global pairwise sequence alignment and three-way sequence alignment (or median), both with affine gap costs, and RNA secondary structure prediction with simple pseudoknots. For each of these problems, we present cache-oblivious algorithms that match the best-known time complexity, match or improve the best-known space complexity, and improve significantly over the cache-efficiency of earlier algorithms. We present experimental results which show that our cache-oblivious algorithms run faster than software and implementations based on previous best algorithms for these problems.
Chowdhury
Rezaul Alam
RA
Center for Computational Visualization, Institute for Computational Engineering and Sciences, The University of Texas at Austin, Austin, TX 78712-0027, USA. shaikat@cs.utexas.edu
Le
Hai-Son
HS
Ramachandran
Vijaya
V
D000465:Algorithms; D020029:Base Pairing; D001483:Base Sequence; D019295:Computational Biology / Q000379:methods*; D009690:Nucleic Acid Conformation; D012313:RNA / Q000737:chemistry*; D016415:Sequence Alignment / Q000379:methods*; D012984:Software
D012313:RNA