pknotsRG: RNA pseudoknot folding including near-optimal structures and sliding windows

Reeder, Jens; Steffen, Peter; Giegerich, Robert

General pseudoknot prediction in energy-based models is a Non-deterministic Polynomial time NP-complete problem (14) , and thus requires exponential run time. However, if we impose some restrictions on the helices forming the pseudoknots, we can achieve faster algorithms. The restrictions in pknotsRG are motivated by the observation, that most of the currently known pseudoknots are rather simple ones. They consist of only two helices, interacting in a crosswise fashion, as shown in Figure 2 . If we allow the unpaired strands (u,v,w in Figure 2 ) to build secondary structures internally in an arbitrary way, including multiloops and pseudoknots, we call this class simple recursive pseudoknots.