Document Detail


A faster algorithm for simultaneous alignment and folding of RNA.
MedLine Citation:
PMID:  20649420     Owner:  NLM     Status:  MEDLINE    
Abstract/OtherAbstract:
The current pairwise RNA (secondary) structural alignment algorithms are based on Sankoff's dynamic programming algorithm from 1985. Sankoff's algorithm requires O(N(6)) time and O(N(4)) space, where N denotes the length of the compared sequences, and thus its applicability is very limited. The current literature offers many heuristics for speeding up Sankoff's alignment process, some making restrictive assumptions on the length or the shape of the RNA substructures. We show how to speed up Sankoff's algorithm in practice via non-heuristic methods, without compromising optimality. Our analysis shows that the expected time complexity of the new algorithm is O(N(4)sigma(N)), where sigma(N) converges to O(N), assuming a standard polymer folding model which was supported by experimental analysis. Hence, our algorithm speeds up Sankoff's algorithm by a linear factor on average. In simulations, our algorithm speeds up computation by a factor of 3-12 for sequences of length 25-250. Code and data sets are available, upon request.
Authors:
Michal Ziv-Ukelson; Irit Gat-Viks; Ydo Wexler; Ron Shamir
Publication Detail:
Type:  Journal Article; Research Support, Non-U.S. Gov't    
Journal Detail:
Title:  Journal of computational biology : a journal of computational molecular cell biology     Volume:  17     ISSN:  1557-8666     ISO Abbreviation:  J. Comput. Biol.     Publication Date:  2010 Aug 
Date Detail:
Created Date:  2010-08-23     Completed Date:  2010-12-07     Revised Date:  -    
Medline Journal Info:
Nlm Unique ID:  9433358     Medline TA:  J Comput Biol     Country:  United States    
Other Details:
Languages:  eng     Pagination:  1051-65     Citation Subset:  IM    
Affiliation:
Department of Computer Science, Ben-Gurion University, Beer Sheva, Israel. michaluz@cs.bgu.ac.il
Export Citation:
APA/MLA Format     Download EndNote     Download BibTex
MeSH Terms
Descriptor/Qualifier:
Algorithms*
Animals
Base Sequence
Caenorhabditis elegans / genetics
DNA / chemistry
Nucleic Acid Conformation
RNA / chemistry*
Sequence Alignment / economics,  methods*
Chemical
Reg. No./Substance:
63231-63-0/RNA; 9007-49-2/DNA

From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine


Previous Document:  Effects of acute low-temperature events on development of Erysiphe necator and susceptibility of Vit...
Next Document:  Re-evaluating the "rules" of protein topology.