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

Sperschneider, Jana; Datta, Amitava

RNA secondary structure prediction with arbitrary pseudoknots under a basic energy model is NP-complete (22, 23) . Restricted classes of pseudoknots can be included in the dynamic programming algorithm for prediction of the MFE structure, resulting in high computational complexity. In dynamic programming, there is always a trade-off between the generality of pseudoknots, which can be predicted, and runtime. Rivas and Eddy (24) cover a broad class of pseudoknots including kissing hairpins in their algorithm, which requires Oðn 6 Þ time and Oðn 4 Þ space. More restricted pseudoknots are included in other dynamic programming algorithms, which have runtime of Oðn 5 Þ using Oðn 4 Þ or Oðn 3 Þ space (22, 23, 25) . All of these algorithms are only feasible for short RNA sequences. The most practical method is pknotsRG, which computes the MFE structure with canonical simple recursive pseudoknots in Oðn 4 Þ time and Oðn 2 Þ space (26) . Dynamic programming does guarantee to find a structure with minimum free energy with respect to the underlying energy model. However, the energy model for pseudoknots used in dynamic programming is only a simple parameterization adopted from the affine multiloop energy model (24) (25) (26) . It was first introduced by Rivas and Eddy (24) because of the lack of experimentally measured parameters for pseudoknot energies. Predictive accuracy of MFE folding is always limited by the underlying energy model, and hence pseudoknot prediction results are poor for longer sequences.