DotKnot: pseudoknot prediction using the probability dot plot under a refined energy model

Sperschneider, Jana; Datta, Amitava

When only a single sequence is given, the most popular approach for RNA structure prediction is free energy minimization. In the minimum free energy (MFE) model, continuous base pairs contribute enthalpic terms and loop regions are purely entropic. RNA comprises various secondary structure elements, i.e. stems, hairpin loops, bulge loops, internal loops and multiloops. Much experimental work has been done to determine their free energy parameters (7, 8) . The key concept that allows for dynamic programming is that all of these motifs are non-crossing and self-contained in terms of their free energy. The MFE secondary structure based on the additive free energy model can be predicted in Oðn 3 Þ time and Oðn 2 Þ space using dynamic programming (9, 10) . MFE prediction has been extended in several ways (11) . Suboptimal structures with free energy close to the MFE can be calculated (12, 13) . Using the dynamic programming principle, the full equilibrium partition function for RNA secondary structure is computed in Oðn 3 Þ time and Oðn 2 Þ space (14) . From the partition function, probabilities for base pairs and structure elements are derived. The main advantage of the MFE algorithm is its guarantee to find an optimal structure with regards to the underlying energy model. However, the inability to predict crossing structure elements, so-called pseudoknots, is a major drawback.