| Cache-oblivious dynamic programming for bioinformatics. | |
| | |
MedLine Citation:
|
PMID: 20671320 Owner: NLM Status: MEDLINE |
Abstract/OtherAbstract:
|
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:
|
Rezaul Alam Chowdhury; Hai-Son Le; Vijaya Ramachandran |
Publication Detail:
|
Type: Journal Article; Research Support, U.S. Gov't, Non-P.H.S. |
Journal Detail:
|
Title: IEEE/ACM transactions on computational biology and bioinformatics / IEEE, ACM Volume: 7 ISSN: 1557-9964 ISO Abbreviation: IEEE/ACM Trans Comput Biol Bioinform Publication Date: 2010 Jul-Sep |
Date Detail:
|
Created Date: 2010-07-30 Completed Date: 2010-12-22 Revised Date: - |
Medline Journal Info:
|
Nlm Unique ID: 101196755 Medline TA: IEEE/ACM Trans Comput Biol Bioinform Country: United States |
Other Details:
|
Languages: eng Pagination: 495-510 Citation Subset: IM |
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 |
Export Citation:
|
APA/MLA Format Download EndNote Download BibTex |
| MeSH Terms | |
Descriptor/Qualifier:
|
Algorithms* Base Pairing Base Sequence Computational Biology / methods* Nucleic Acid Conformation RNA / chemistry* Sequence Alignment / methods* Software* |
| Chemical | |
Reg. No./Substance:
|
63231-63-0/RNA |
From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine
Previous Document: OntoGene in BioCreative II.5.
Next Document: CollHaps: a heuristic approach to haplotype inference by parsimony.