2008/09/09 by Rezaul Alan Chowdhury, Hai-Son Le, Vijaya Ramachandran · 1 citation
Computer Science · Biochemistry, Genetics and Molecular Biology · Mathematics · #Algorithms and Data Compression #Genomics and Phylogenetic Studies #Error Correcting Code Techniques #Computer science #Cache #Parallel computing #Longest common subsequence problem #Dynamic programming #Pairwise comparison #String (physics) #Theoretical computer science #Algorithm #Mathematics #Artificial intelligence
paper · doi:10.1109/tcbb.2008.94
openalex publication_date 2008/09/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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.