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

Sperschneider, Jana; Datta, Amitava

A different algorithmic framework is used in heuristic pseudoknot detection programs (37) (38) (39) (40) . Here, one attempts to find promising pseudoknot candidates in a sequence as a first step. These potential pseudoknots are subsequently analysed and verified. After pseudoknot detection, the remaining sequence can be folded using free energy minimization in Oðn 3 Þ time and Oðn 2 Þ space. Pseudoknot detection has two main advantages over dynamic programming. First, it is computationally much more efficient and, therefore, practical for scanning long RNA sequences for pseudoknots. Second, the underlying framework is less restrictive and allows for easy incorporation of sophisticated energy rules for pseudoknots or even comparative information. Pseudoknot detection delivers accurate pseudoknot prediction results for longer sequences in many cases (37, 39) .