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

Reeder, Jens; Steffen, Peter; Giegerich, Robert

We will briefly sketch the way we implemented these ideas as an extension of the usual dynamic programming (DP) scheme for RNA folding [5, 6] . Since only two helices participate in one pseudoknot, we loop over all possible knots in one O(n 4 ) loop and store the result in a two-dimensional matrix. More detailed, for a pseudoknot between bases i and j, the algorithm enumerates all k and l, such that i5k5l5j. The first pseudoknot helix (a in Figure 2 ) starts at base pair i and l, the second (b) at position k and j. Now, we make use of our canonization: The maximal length of a helix can be pre-computed and stored in a two-dimensional array. Therefore, after choosing position k and l, the algorithm looks up the maximal helix lengths, h for (i, l) and h 0 for (k, j) and checks the applicability of Rule 3. Having the stems fixed, the location of the three enclosed pseudoknot loops (u,v,w in Figure 2 ) follows directly: loop u ranges from position i þ h þ 1 to kÀ1, loop v from k þ h 0 þ1 to lÀhÀ1, and loop w from l þ 1 to jÀh 0 À1. The best folding for these smaller subsequences has already been computed earlier in the DP scheme. The energy sum of the two pseudoknot helices and the loop folding energies gives us the total pseudoknot energy. The minimal one over all k and l, is stored is the two-dimensional pseudoknot matrix. This value competes with values of unknotted foldings for the interval (i, j).