Paper Info
Title
Sparse RNA Folding Revisited: Space-Efficient Minimum Free Energy Prediction
Abstract
RNA secondary structure prediction by energy minimization is the central computational tool for the analysis of structural noncoding RNAs and their interactions. Sparsification has been successfully applied to improve the time efficiency of various structure prediction algorithms while guaranteeing the same result; however, for many such folding problems, space efficiency is of even greater concern, in particular for long RNAs and complex folding algorithms. So far, space-efficient sparsified RNA folding with fold reconstruction was solved only for simple pseudo-energy models. Here, we revisit the problem of space-efficient free energy minimization. Whereas the space-efficient minimization of the free energy has been sketched before, the reconstruction of the optimum structure has not even been discussed. We show that this reconstruction is not possible in trivial extension of the method for simple energy models. Then, we present the time-and space-efficient sparsified free energy minimization algorithm SPARSEMFEFold, which guarantees optimal structure prediction. In particular, this novel algorithm provides efficient fold reconstruction based on dynamically garbage collected trace arrows. We provide theoretical and empirical results on the efficiency of the method. SparseMFEFold is free software, available at http://www.bioinf.uni-leipzig.de/(similar to)will/Software/SparseMFEFold.
Year
DOI
Venue
2015
10.1007/978-3-662-48221-6_19
ALGORITHMS IN BIOINFORMATICS (WABI 2015)
Keywords
Field
DocType
Space efficient sparsification,Pseudoknot-free rna folding,RNA secondary structure prediction
Computer science,Rna folding,Minification,Rna secondary structure prediction,Software,Prediction algorithms,Bioinformatics,Energy minimization,Minimum free energy
Conference
Volume
ISSN
Citations 
9289
0302-9743
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Sebastian Will1759.25
Hosna Jabbari2303.94