AI Article Synopsis
- The text discusses the development of efficient cache-oblivious algorithms for key string problems in bioinformatics, including longest common subsequence and RNA structure prediction.
- These algorithms not only achieve the best-known time complexity but also match or enhance existing space efficiency and significantly improve cache efficiency.
- Experimental results indicate that these new algorithms outperform previous software implementations for these bioinformatics challenges.
Article 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.
Download full-text PDF |
Source |
|---|---|
| http://dx.doi.org/10.1109/TCBB.2008.94 | DOI Listing |
Publication Analysis
Top Keywords
Similar Publications
Want AI Summaries of new PubMed Abstracts delivered to your In-box?
Enter search terms and have AI summaries delivered each week - change queries or unsubscribe any time!