RNA Accessibility in cubic time

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.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.The importance of RNA within living cells has been realized in the last two decades. RNA provides a layer of regulation in eukaryotes, e.g. via miRNA, but also in prokaryotes via small RNAs (sRNAs) and riboswitches. Many of these regulatory functions are mediated by RNA interactions. These interactions are mainly realized through Watson-Crick or wobble base pairing between two RNA molecules. For the initialization of these interactions, a part of the interacting molecules has to be single-stranded. The tendency to be single-stranded is thus also important for the quality of putative target sites of miRNAs [1], siRNAs [2] and most probably sRNAs. Furthermore, the accessibilities of the Shine-Dalgarno sequence and the start codons are indicators of translational efficacy [3]. In addition, RNA accessibility will also influence the efficacy of single-strand binding proteins like HuR [4]. As it is not known how big exactly a putative target site is, and where it is located, it is best to know the accessibilities of all possible intervals within a RNA molecule. In particular, programs like RNAup [5,6] or IntaRNA [7] predict RNA-RNA interactions by computing a total binding energy δGtot = δGint + δGopen, composed of a stabilizing energy for the intermolecular duplex δGint and the cost of opening the binding sites δGopen. The opening energy can be computed from the acc