Email updates

Keep up to date with the latest news and content from Algorithms for Molecular Biology and BioMed Central.

Open Access Research

RNA Accessibility in cubic time

Stephan H Bernhart*, Ullrike Mückstein and Ivo L Hofacker

Author Affiliations

Theoretical Biochemistry group, Institute for theoretical chemistry, University of Vienna, Währingerstrasse 17, Vienna, Austria

For all author emails, please log on.

Algorithms for Molecular Biology 2011, 6:3  doi:10.1186/1748-7188-6-3

Published: 9 March 2011

Abstract

Background

The accessibility of RNA binding motifs controls the efficacy of many biological processes. Examples are the binding of miRNA, siRNA or bacterial sRNA to their respective targets. Similarly, the accessibility of the Shine-Dalgarno sequence is essential for translation to start in prokaryotes. Furthermore, many classes of RNA binding proteins require the binding site to be single-stranded.

Results

We introduce a way to compute the accessibility of all intervals within an RNA sequence in (n3) time. This improves on previous implementations where only intervals of one defined length were computed in the same time. While the algorithm is in the same efficiency class as sampling approaches, the results, especially if the probabilities get small, are much more exact.

Conclusions

Our algorithm significantly speeds up methods for the prediction of RNA-RNA interactions and other applications that require the accessibility of RNA molecules. The algorithm is already available in the program RNAplfold of the ViennaRNA package.