Document Detail

Practicality and time complexity of a sparsified RNA folding algorithm.
MedLine Citation:
PMID:  22809342     Owner:  NLM     Status:  MEDLINE    
Commonly used RNA folding programs compute the minimum free energy structure of a sequence under the pseudoknot exclusion constraint. They are based on Zuker's algorithm which runs in time O(n(3)). Recently, it has been claimed that RNA folding can be achieved in average time O(n(2)) using a sparsification technique. A proof of quadratic time complexity was based on the assumption that computational RNA folding obeys the "polymer-zeta property". Several variants of sparse RNA folding algorithms were later developed. Here, we present our own version, which is readily applicable to existing RNA folding programs, as it is extremely simple and does not require any new data structure. We applied it to the widely used Vienna RNAfold program, to create sibRNAfold, the first public sparsified version of a standard RNA folding program. To gain a better understanding of the time complexity of sparsified RNA folding in general, we carried out a thorough run time analysis with synthetic random sequences, both in the context of energy minimization and base pairing maximization. Contrary to previous claims, the asymptotic time complexity of a sparsified RNA folding algorithm using standard energy parameters remains O(n(3)) under a wide variety of conditions. Consistent with our run-time analysis, we found that RNA folding does not obey the "polymer-zeta property" as claimed previously. Yet, a basic version of a sparsified RNA folding algorithm provides 15- to 50-fold speed gain. Surprisingly, the same sparsification technique has a different effect when applied to base pairing optimization. There, its asymptotic running time complexity appears to be either quadratic or cubic depending on the base composition. The code used in this work is available at: .
Slavica Dimitrieva; Philipp Bucher
Publication Detail:
Type:  Journal Article; Research Support, Non-U.S. Gov't    
Journal Detail:
Title:  Journal of bioinformatics and computational biology     Volume:  10     ISSN:  1757-6334     ISO Abbreviation:  J Bioinform Comput Biol     Publication Date:  2012 Apr 
Date Detail:
Created Date:  2012-07-19     Completed Date:  2012-11-19     Revised Date:  2014-10-13    
Medline Journal Info:
Nlm Unique ID:  101187344     Medline TA:  J Bioinform Comput Biol     Country:  England    
Other Details:
Languages:  eng     Pagination:  1241007     Citation Subset:  IM    
Export Citation:
APA/MLA Format     Download EndNote     Download BibTex
MeSH Terms
Base Pairing
Models, Molecular
Nucleic Acid Conformation
RNA / chemistry*,  metabolism
RNA Folding*
Sequence Analysis, RNA / methods*
Reg. No./Substance:

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

Previous Document:  Analysis of context-dependent errors for illumina sequencing.
Next Document:  Derived SNP alleles are used more frequently than ancestral alleles as risk-associated variants in c...