title: Cache-oblivious dynamic programming for bioinformatics.
abstract: 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.
authors.affiliation: 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
authors.forename: Rezaul Alam
authors.initials: RA
authors.lastname: Chowdhury
authors.forename: Hai-Son
authors.initials: HS
authors.lastname: Le
authors.forename: Vijaya
authors.initials: V
authors.lastname: Ramachandran
mesh_terms: 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
chemical_list: D012313:RNA