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

Sperschneider, Jana; Datta, Amitava

Due to the computational complexity of dynamic programming for pseudoknot prediction, heuristic approaches were developed as an alternative. Heuristic methods do not necessarily return the MFE structure; however, they can include a wide class of pseudoknots and more advanced energy models in reasonable runtime. RNA secondary structure prediction including pseudoknots has been approached using genetic algorithms (27, 28) , stochastic context-free grammars (29, 30) , kinetic folding simulations (31, 32) and maximum weighted matching in a folding graph (33) . Iterative stem adding procedures have also been developed (34) (35) (36) . In several heuristic algorithms, the underlying energy model for secondary structures is simple base pair maximization, neglecting loop entropies (33, 34) . This may lead to unreliable results, especially for longer sequences. Another drawback is that most heuristic methods reported in the literature employ the same affine pseudoknot energy model as dynamic programming.