Abstract
Background
Although many RNA molecules contain pseudoknots, computational prediction of pseudoknotted RNA structure is still in its infancy due to high running time and space consumption implied by the dynamic programming formulations of the problem.
Results
In this paper, we introduce sparsification to significantly speedup the dynamic programming approaches for pseudoknotted RNA structure prediction, which also lower the space requirements. Although sparsification has been applied to a number of RNArelated structure prediction problems in the past few years, we provide the first application of sparsification to pseudoknotted RNA structure prediction specifically and to handling gapped fragments more generally  which has a much more complex recursive structure than other problems to which sparsification has been applied. We analyse how to sparsify four pseudoknot structure prediction algorithms, among those the most general method available (the RivasEddy algorithm) and the fastest one (ReederGiegerich algorithm). In all algorithms the number of "candidate" substructures to be considered is reduced.
Conclusions
Our experimental results on the sparsified ReederGiegerich algorithm suggest a linear speedup over the unsparsified implementation.
Background
Recently discovered catalytic and regulatory RNAs [1,2] exhibit their functionality due to specific secondary and tertiary structures [3,4]. The vast majority of computational analysis of noncoding RNAs have been restricted to nested secondary structures, neglecting pseudoknots  which are "among the most prevalent RNA structures" [5]. For example, Xayaphoummine et al. [6] estimated that up to 30% of the base pairs in G+Crich sequences form pseudoknots.
However the general problem of pseudoknotted RNA structure prediction is NPhard. As a result, a number of approaches have been introduced for handling restricted classes of pseudoknots [713]. Condon et al. [14] give an overview of their structure classes and the algorithmspecific restrictions and Möhl et al. [15] develop a general framework showing that all these algorithms follow a general scheme, which they use for efficient alignment of pseudoknotted RNA.
The most general algorithm (with respect to the pseudoknot classes handled) among the above by Rivas and Eddy (R&E) has a running time of O(n^{6}) time and space consumption of O(n^{4}). It is therefore too expensive to directly apply this algorithm for large scale data analysis. Unfortunately, even the most efficient algorithm by Reeder and Giegerich (R&G) still has a high running time of O(n^{4}), although it strongly restricts the class of predictable pseudoknots.
In this paper we introduce the technique of sparsification to the problem of pseudoknotted RNA structure prediction. Sparsification improves the expected running time and space usage of a dynamic programming based structure prediction algorithm without introducing additional restrictions on the structure class handled or compromising the optimality of solutions. Sparsification has been recently applied to improve time and space complexity of various existing RNArelated structure prediction algorithms. In particular, it turned out to be successful for RNA folding for pseudoknotfree structures [16,17], simultaneous alignment and folding [18] as well as RNARNA interaction prediction [19].
Contributions
We study sparsification of pseudoknotted RNA structure prediction. Algorithms developed for this problem differ from the previously sparsified algorithms by their use of gapped fragments and their more complex recursion structure. Our main contribution in this paper is the solution to the algorithmic challenges due to this increased complexity. Among all DP based pseudoknot prediction algorithms, we focus on the fastest algorithm (R&G) and the most general one (R&E) and develop sparse variants of these dynamic programming algorithms. Furthermore, we consider sparsification of the algorithm by Akutsu et al. and Uemura et al. (A&U) [9,10] as well as the algorithm by Dirks and Pierce (D&P) [12]. Due to sparsification, the resulting algorithms need to consider only a limited number of candidates substructures compared to the original algorithms. As a result, we analyze the theoretical worst case complexities in terms of the number of candidate substructures. We also present experimental results, comparing our implementations of the original and sparsified R&G algorithm. These results suggest a significant (roughly a linear factor) reduction in the number of candidates over the original algorithm.
Methods
Sparsification of the Reeder and Giegerich algorithm
The R&G algorithm [13] predicts the minimum free energy structure allowing canonical pseudoknots for a sequence S of length n. It extends the Zuker algorithm by adding one more matrix K (for knot), where K(i, j) denotes the energy for the best canonical pseudoknot that starts at position i and ends at position j. Note that the original presentation of the algorithm in terms of the ADP framework does not explicitly consider a matrix K but only a motif knot. Canonical pseudoknots are defined as follows. Each pair of base pairs p_{1 }= (i, i') and p_{2 }= (j', j) with i <j' <i' <j induces one canonical pseudoknot that consists of two crossing stems {(i, i'), (i+1, i' 1),..., (i+d_{i, i' } 1, i' d_{i, i' }+1)} and {(j', j), (j' + 1, j  1),..., (j' + d_{j', j } 1, j  d_{j', j }+ 1)} where the stacking length of the two stems, d_{i, i' }and d_{j', j}, respectively, is maximally extended as long as all base pairs are valid WatsonCrick base pairs.
To allow for sparsification, we restrict the scoring scheme slightly such that the energy of a canonical pseudoknot only depends on the left ends of its base pairs and hence can be described as PKEnergy(i, d_{i, i'}, j', d_{j', j}). This implies that the scoring scheme does not distinguish between GC and GU base pairs in pseudoknotstems, since their left ends are identical. Then,
with
As shown in Figure 1(a), for each canonical pseudoknot starting at i and ending at j the recursion decomposes into the pseudoknot itself and the three fragments inbetween its two crossing stems. Such pseudoknots add one case in the computation of a matrix entry W(i, j), which, as in the Zuker algorithm, contains the optimal energy of a substructure starting at position i and ending at position j. Due to the restriction to canonical pseudoknots, the recursion of R&G minimizes only over all possible instances of i' and j', because the maximal stacking lengths d_{i, i' }and d_{j', j }are uniquely determined once i' and j' are fixed. Furthermore, Reeder and Giegerich note that the maximal stacking length d_{x, y }can be precomputed for all x, y in O(n^{3}) time and stored in an O(n^{2}) table.
Figure 1. Recursion for canonical pseudoknots (a) and their sparsification (b).
In order to sparsify the algorithm, we develop an appropriate notion of a candidate such that it is not necessary to minimize over all possible i' and j' but only over the candidates.
Definition 1 (R&G candidate)
Let and . Then dominates with respect to (i, j' d_{j', j}), iff
where
We say that is a candidate with respect to (i, j', d_{j', j}) if there does not exist any that dominates it.
The notion of a candidate is visualized in Figure 1(b). There, dominates if the score for the gray area at the top (including the dashed part whose exact position is not determined) is not better than the score for the corresponding gray area at the bottom plus the green part. Note that these scores (and hence the candidate i') depend only on i, j', and d_{j',j }and are independent of d_{i,i' }and j. The following lemma shows that the notion of a candidate given in Def. 1 is suitable for sparsification, i.e. some i' needs to be considered in the recursion (for all j) only if it is a candidate, because otherwise it is dominated by a candidate that yields a better score.
Lemma 1 (R&G sparsification)
Let be dominated by with respect to some (i, j', d_{j', j}). Then for all j it holds .
Proof We start with the inequality of Def. 1 and add on both sides.^{. }Then the claim follows immediately from . In Figure 1(b) this corresponds to the fact that the score for the red box is at least as good as the score from the green and the blue box together. This triangle inequality holds by the correctness of the (unsparsified) algorithm: For all x < y < z we have W(x, y)+W(y+1, z) ≤ W(x, z) since the concatenation of the best structures for the ranges (x, y) and (y, z) always forms a valid structure for the range (x, z) with score W(x, y)+W(y+1, z) which is hence never better than the optimal score W(x, z) for that range. □
The sparsified algorithm maintains lists L_{i }of candidates for each pair (j', d_{j', j}) since only the lists for one i need to be maintained in memory at the same time. Whenever in the computation of some score(i, j', i', j) the i' is considered the first time for this i and j', it is checked whether it is a candidate and if so, it is added to the respective list. For all other instances of j, i' is then considered only if it is contained in the list. The sparsified algorithm is given by the following pseudocode (n := S).
1: for i := n to 1 do
2: for all d_{j', j}, j' ≤ n do
3: L_{i}(j', d_{j', j}) := empty list;
4: end for
5: for j := i + 3 to n do
6: K(i, j) := ∞
7: for j' := i + 1 to j  2 do
8: // check new elements for candidacy
10: if for all i' ∈L_{i}(j', d_{j', j}) then
11: add i_{c }to L_{i}(j', d_{j', j})
12: end if
13: end for
15: // iterate over all candidates
16: K_{i, j', j }:= ∞
17: for all i' ∈ L_{i}(j', d_{j', j}) do
18: K_{i, j', j }:= min {K_{i, j', j}, score(i, j', i', j)}
19: end for
20: K(i, j) := min {K(i, j), K_{i, j', j}}
21: end for
22: compute matrix entries V (i, j) and W(i, j) as in Wexler et al.
23: W(i, j) := min(W(i, j), K(i, j))
24: end for
25: end for
The candidate lists are initialized in line 2. In lines 7 to 11 all new values i_{c }that have not been considered so far, are tested for candidacy. Here, denotes the largest i' that has been checked for candidacy in list L_{i}(j', d_{j', j}).
Lines 14 to 17 compute scores score(i, j', i', j) for all candidates i'. In line 20, we compute W(i, j) and V(i, j) as in the sparsified pseudoknotfree structure prediction approach due to Wexler et al. [16]. The computation of matrices K and W is interleaved such that all entries K(i, j) and W(i, j) are computed before all entries K(i', j') and W(i', j') for i ≤ i' ≤ j' ≤ j and i ≠ i' or j ≠ j'.
Complexity Analysis
Whereas the original algorithm requires O(n^{4}) time (for n = S), the sparsified variant requires O(n^{3}L) time where L is the total size for all candidate lists of some i i.e. . Obviously, L ≤ n. In order to maintain the asymptotic space complexity O(n^{2}) of the original algorithm, we do not maintain all lists L_{i}(j', d_{j', j}) in memory but only the lists with d_{j', j }≤ k where k > 0 is a small constant. Please note that to keep presentation simple, we didn't make this explicit in the pseudocode. Since the maximal stacking length is usually small, there are only very few instances of j with d_{j', j }>k such that for those few j it is cheap to consider all i' as candidates. Hence, we store O(kn) = O(n) candidate lists each requiring at most O(n) space.
Wexler et al. [16] use the assumption that RNA folding satisfies the polymerzeta property to derive a tighter bound on the expectedcase asymptotic complexity. However, we focus on the practical speedup that is obtained by our implementation due to the following reasons. First, it is unclear whether the energymodels for pseudoknot prediction exhibit this property and second it is unclear whether the asymptotic behaviour already appears in the feasible range of input sizes. As shown in the results, the sparsified variant runs two to four times faster than the unsparsified variant for input sizes up to 1000 nucleotides.
Sparsification of the Rivas and Eddy Algorithm
The class of structures predicted by the R&E algorithm [8], here called class of R&E structures, is the most general RNA secondary structure prediction algorithm described in the literature [14]. To keep presentation simple we explain the sparsification strategy for a basepair maximization algorithm that handles the R&E structure class. Finally, we motivate that sparsification can be transferred to the R&E energy minimization algorithm.
First, we give recursions of base pair maximization for R&E structures. Note that the recursions are intentionally very close to the recursions of the R&E energy minimization algorithm. After initialization for i ≥ j and k ≥ l
and
Where is the base pair contribution, the recursions (R&E recursions) are given for 1 ≤ i <j <k <l ≤ S as
It is easy to check that W(1, S) is the maximal number of base pairs in a R&E structure of S, because the recursions perform the same decompositions as the original R&E recursions. Note that W(i, j; k, l) is the maximal number of base pairs in structures with at least one base pair that spans the gap. We label each recursion case in a way that illustrates the type of the decomposition of this case. The idea of these labels is taken from Möhl et al. [15], where we developed a type system for decompositions, which there are called splits. For this reason, we call these labels split types, however, we won't need any details of the typing system. The decomposition by R&E is illustrated in Figure 2.
Figure 2. Decomposition for R&E base pair maximization annotated with labels, i.e. split types, of the corresponding recursion cases.
A fragment is defined as a set of positions of the fixed sequence S. The fragments corresponding to matrix entries in the R&E recursion can be described conveniently by their boundaries. We distinguish ungapped fragments F = {i,...,j}, written (i, j), and 1gap fragments F' = {i,...,j} ∪ {k,...,l}, written (i, j; k, l) where i, j, k, l, are called boundaries of respective F or F'. A split of a fragment F is a tuple (F_{1}, F_{2}) such that F = F_{1 }∪ F_{2 }and F_{1 }∩ F_{2}∅.
For our sparsification approach, we will show that in each recursion case, certain optimally decomposable fragments do not have to be considered for computing an optimal solution, because each decomposition using these fragments can be replaced by a decomposition using a smaller fragment. We define optimal decomposability with respect to the split type of a R&E recursion case.
Definition 2 (Optimally decomposable)
A fragment F is optimally decomposable by a split of type T (TOD) iff there is a split (F_{1}, F_{2}) that occurs in recursion case T and W(F_{1}) + W (F_{2}) ≥ W (F ).
A fragment F is optimally decomposable w.r.t a set of split types iff F is TOD for some .
Here, we emphasize that testing TOD for a fragment F is simple in a run of the DP algorithm. After evaluating the case T in the computation of W(F), one compares the maximum of the case to W(F). For example, a fragment (i, j; k, l) is 12G21OD iff W(i, j; k, l) = max_{j', k' }W (i, j'  1; k' + 1, l) + W(j', j; k, k').
In the following we show that for the maximization in a recursion case T, we do not need to consider T'OD fragments as second fragment of the split, where T' is from a Tspecific set of split types. As an example consider the recursion case 12G21, which splits fragments (i, j; k, l) into F_{1 }= (i, j'  1; k' +1, l) and F_{2 }= (j', j; k, k'). Assume that F_{2 }is 12G21OD. Then we can show that every evaluation of W(F) where W(F) = W(F_{1}) + W (F_{2}) can be replaced by another at least equally good evaluation that splits F into and , where is the second fragment in the 12G21split of F_{2}. However, note that the argument is split type specific and cannot be applied e.g. when F_{2 }is 12G12OD.
For sparsifying R&E, we define the following sets of split types.
These sets are defined such that in a recursion case T, whenever the second fragment of a split (F_{1}, F_{2}) of F can be optimally decomposed by a split of a type in , a different split of type T can be applied to F, where . As we show later, this split will be just as good as (F_{1}, F_{2}) for computing W(F).
Then, one systematically obtains sparsified recursion equations W'(i, j) and W'(i, j; k, l) from the equations for W(i, j) and W(i, j; k, l) by replacing symbol W by W' and modifying them in the following way. For each case T in the recursion of W(i, j) and W(i, j; k, l) that maximizes over W(F_{1})+W (F_{2}) for respective splits of the fragment F = (i, j) or F = (i, j; k, l), maximize only over fragments F_{2 }that are not OD. In an algorithm that evaluates the sparsified recursion, such nonOD fragments correspond to entries of candidate lists. For example, case 12G21 of W is modified in the equation for W' (i, j, k, l) to
Theorem 1
Let W be the matrix of the R&E recursion and W' its sparsified variant, then W(1, S) = W'(1, S).
Proof We show for all 1 ≤ i, j, k, l ≤ S, W(i, j) = W'(i, j) and W(i, j, k, l) = W'(i, j; k, l). First note that it holds that W(i, j) ≥ W'(i, j) and W(i, j; k, l) ≥ W'(i, j; k, l). The claim is shown by induction on the fragment size and a case distinction over recursion cases. For the case of split type 12, we show that
Let (j', j) be 12OD for some j' : i ≤ j' ≤ j. By IH, it suffices to find a (smaller) fragment (j'', j), where j'' > j and W(i, j''  1) + W(j'', j) ≥ W(i, j'  1) + W(j', j). Either (j', j) is not 12OD or there is a j'', such that W(j', j) = W(j', j''  1) + W(j'', j) and thus W(i, j''  1)+W(j'', j) ≥ W(i, j'  1)+W(j', j) because
The triangle inequality (Δineq) is an immediate consequence of the correctness of the recursion for W. Thus, for the decompositions of all recursion cases there holds such a corresponding inequation. Analogous arguments can be given for all other modified recursion cases. Exemplarily, we elaborate the argument for the complex case 12G21. Let F_{1 }= (i, j'  1; k' + 1, l) and F_{2 }= (j', j; k, k'), such that (F_{1}, F_{2}) is a split of type 12G21 of (j, j; k, k). We need to show for all OD fragments F_{2 }there are nonempty ungapped or 1gap fragments and , where and and the split occurs in a recursion case of R&E. Again, either F_{2 }is not OD or one of the following cases applies. Case 1 (12G2): for some j'', W(j', j; k, k') = W(j', j''  1)+W(j'', j; k, k'). Then, the claim holds for and by triangle inequality and split occurs in recursion case 12G21. Case 2 (2G21): for some k'', W(j', j; k, k') = W(j', j; k, k'') + W(k'' + 1, k'). The claim holds for . Case 3 (12G21): for some j'', k'', W(j', j; k, k') = W(j', j''  1; k'' + 1, k')+W(j'', j; k, k''). Again, this satisfies the claim by triangle inequality.
Algorithm
The recursion equation W' tailors a sparsified dynamic programming algorithm for the evaluation of W' (1, S) with very limited overhead. We maintain separate candidate lists for each sparsified recursion case. As already mentioned, the TOD properties of each fragment F can be easily checked after evaluation of each case of W(F). A fragment is added to a candidate list for recursion case T iff it is not OD. The maximizations are restricted to run only over the candidates in the respective candidate list. Their intended use dictates the exact nature of such candidate lists. For a case T, which splits a fragments T into T_{1 }and T_{2}, there are candidate lists for all boundaries of a fragment T_{2 }that are not adjacent to boundaries of T_{1 }due to split type T. The list entries are tuples of the adjacent boundaries and the fragment score for T_{2}. In order to profit from a reduced number of candidates in space, we maintain two threedimensional slices of the matrix for W(i, j; k, l), storing entries only for the current i and i + 1. Scores W(i, j; k, l) for larger i are stored for candidates only. Pseudocode of the sparsified algorithm is given in Figure 3.
Figure 3. Pseudocode for R&Estyle base pair maximization.
R&E Free Energy Minimization
Sparsification is analogously applied to the energy minimizing R&E algorithm. This algorithm distinguishes several additional matrices that contain minimal energies for fragments (i, j) or (i, j; k, l) under the condition that respectively the base pair (i, j) or base pairs (i, l) and (j, k) or one of them exist. Almost all decompositions in the recursion for these matrices are of discussed split types and are sparsified analogously. The only notable exception is due to internal loops. Internal loops require minimizing over all possible positions of the inner loop base pair, where commonly the loop size is restricted by a constant K such that minimizing takes constant time. However, handling inner loops requires access to entries of noncandidate fragments (i', j'; k', l') for i ≤ i' ≤ i + K + 2. This is handled by maintaining matrix slices for i to i + K + 2 in O(n^{3}) space, which preserves total space complexity.
Complexity Analysis
The described algorithm profits from sparsification in time and space. Compared to O(n^{6}) time and O(n^{4}) space of the unsparsified algorithm (for n = S), we obtain complexities in the number of candidates. Let Z_{T }denote the maximal length of a candidate lists for case T and Z denote the total number of entries in all lists. Then, the time complexity is O(n^{2}(Z_{12 }+ Z_{1212}) + n^{4}(Z_{12G2 }+ Z_{12G1}+Z_{1G21}+Z_{1G12}+Z_{12G21}+Z_{12G12}+Z_{1G212}+Z_{121G2})) and space complexity is O(n^{3}+Z). In the worst case, Z_{12}, Z_{12G2}, Z_{12G1}, Z_{1G21 }and Z_{1G12 }are O(n), Z_{12G21}, Z_{12G12}, Z_{1G212}, Z_{121G2 }are O(n^{2}), and Z_{1212 }is O(n^{3}), finally Z is O(n^{4}) in the worst case.
Sparsification of the Dirks and Pierce Algorithm
Dirks and Pierce [12] present a pseudoknot prediction algorithm that takes O(n^{5}) time and O(n^{4}) space. Note that whereas Dirks and Pierce present their decomposition for computing the partition function, we sparsify the corresponding minimum free energy prediction algorithm. As mentioned in [15] this algorithm can be considered as a restriction of the algorithm by Rivas and Eddy to the cases
with an additional case 1'2G21' that composes a gapped fragment (i, j; k, l) from a single base pair (i, l) and (i + 1, j; k, l  1).
The nonconstant cases 12, 1212, 12G2, 12G1, 1G21, and 1G12 can be sparsified exactly as the corresponding cases of the Rivas and Eddy algorithm with the following sets of split types:
Note that the additional case 1'2G21' does not need to be sparsified, because it is computed in constant time. Analogously to our discussion of the R&E algorithm, one obtains space and time complexities of the sparsified algorithm in terms of the length of candidate lists and the total number of candidates.
Sparsification of the Akutsu and Uemura Algorithm
In this section we consider the pseudoknot prediction algorithm that was developed by Uemura et al. [9] based on tree adjoining grammars and later reformulated by Akutsu et al. [10] as dynamic programming algorithm. The algorithm predicts simple pseudoknots in O(n^{4}) time and O(n^{3}) space. It can also be considered as a restriction of the algorithm by Rivas and Eddy. It is restricted to splits of the following types (again following the typing scheme of [15]):
and ommitted trivial, constant cases. Compared to the R&E algorithm, all cases that dominate the complexity are restricted to have only one possible split per instance (as indicated by the ' symbols; confer the additional case/split type of the algorithm by Dirks and Pierce). All nonconstant cases, i.e. the first two rules, can still be sparsified analogous to sparsification of the algorithm of Rivas and Eddy using split type sets
The restriction introduced by Akutsu and Uemura could be considered as a very simple, static form of sparsification. For each fragment annotated with symbol ', only one candidate (namely the smallest possible one) is considered. In contrast to sparsification as it is discussed in this paper, Akutsu's and Uemura's modification of the R&E algorithm reduces the worstcase complexity at the price of restricting the class of pseudoknots.
Results and Discussion
In order to evaluate the effect of sparsification on pseudoknotted RNA secondary structure prediction, we implemented original and sparsified variants of the Reeder and Giegerich (R&G) algorithm.
Data Set
We obtained all RNA sequences from PseudoBase [20], which are known to have some pseudoknots in their secondary structures. This set contains 294 sequences that their length is distributed between 76 nt and 93399 nt. We randomly divided all long sequences into subsequences shorter than 1000 nt. Therefore the data set that we used in our experiments contains 1563 sequences with length between 76 nt and 1000 nt.
Performance
We applied both variants of the R&G algorithm to our data set. Figure 4 shows the running time of the algorithms on a server with Intel Core Duo CPU at 2.53 GHz and 4 GB RAM. The results in Figure 4 show that sparsification significantly improves the running time of the R&G algorithm. As the RNA sequences get longer, the relative performance of the sparsified algorithm (with respect to the nonsparsified ones) improves. Figure 4(b) shows the speedup of the sparsified algorithm, which fits well to a linear regression (R^{2 }= 0.84).
Figure 4. Running times of the original and sparsified variants of the R&G algorithm.
Number of candidates
For a better understanding of the effect of sparsification on the R&G algorithm, we measured the number of (i', j') pairs which are checked in each fragment [i, j] in both original and sparsified variants of the algorithm. Note that the number of (i', j') pairs is in order of O((j  i)^{2}) in the worst case. Figure 5 shows the average number of (i', j') pairs on fragments of equal length which are checked by the two variants of the algorithm. As expected, this amount is significantly smaller for the sparsified algorithm compared to the original one. Moreover, we observe that as the fragments get longer, the difference between the average number of (i', j') pairs in the sparsified and the original algorithm increases. We define the work load per each fragment [i, j] as the number of candidate (i', j') pairs. Figure 5(b), shows a significant reduction of the work load in the sparsified algorithms. As it can be seen for subsequences of length 1000 nt, the work load by the sparsified algorithm is reduced by a factor of about 10 compared to the original algorithm. Note that the work load reduction at fragment length 1000 nt does not yield the same speedup for sequences of length 1000 nt (here this speedup is about 3.5, confer Figure 4(b)), because for a sequence of length n, all fragments of smaller length are processed by the algorithm.
Figure 5. Average number of (i', j') candidates in the original and sparsified variants of the R&G algorithm.
Conclusions
The presented work gives four examples for sparsification in the context of gap fragments and a complex recursion structure. We successfully sparsified the fastest and the most complex pseudoknot structure prediction algorithm for RNA, as well as two algorithms with intermediate complexity. Since sparsification is similar in all these algorithms, the paper motivates further generalization of sparsification for systematic application to complex DPalgorithms as RNA structure prediction algorithms. Even more, by providing detailed examples the paper directly suggests such generalization. Our results from an implementation of the sparsified Reeder and Giegerich algorithm show a significant, presumably even linear, expected work load reduction due to sparsification. As future work, it would be interesting to develop optimizations for the partition function based variants of pseudoknot prediction where sparsification is not directly applicable.
Competing interests
The authors declare that they have no competing interests.
Authors' contributions
All authors developed the ideas for this project. MM, RS, and SW elaborated the technical contribution and wrote the paper. RS did the implementation and evaluation. All authors read and approved the final manuscript.
Acknowledgements
This work is partially supported by DFG grants WI 3628/11, EXC 294, and BA 2168/31. R. Salari was supported by SFUCTEF funded Bioinformatics for Combating Infectious Diseases Project colead by S.C. Sahinalp. S.C. Sahinalp was supported by MITACS, NSERC, the CRC program and the Michael Smith Foundation for Health Research.
References

Sharp PA: The centrality of RNA.
Cell 2009, 136(4):57780. PubMed Abstract  Publisher Full Text

Amaral PP, Dinger ME, Mercer TR, Mattick JS: The eukaryotic genome as an RNA machine.
Science 2008, 319(5871):17879. PubMed Abstract  Publisher Full Text

Washietl S, Pedersen JS, Korbel JO, Stocsits C, Gruber AR, Hackermuller J, Hertel J, Lindemeyer M, Reiche K, Tanzer A, Ucla C, Wyss C, Antonarakis SE, Denoeud F, Lagarde J, Drenkow J, Kapranov P, Gingeras TR, Guigo R, Snyder M, Gerstein MB, Reymond A, Hofacker IL, Stadler PF: Structured RNAs in the ENCODE selected regions of the human genome.
Genome Res 2007, 17(6):85264. PubMed Abstract  Publisher Full Text  PubMed Central Full Text

Mattick JS, Makunin IV: Noncoding RNA.
Hum Mol Genet 2006, 15(Spec No 1):R1729. PubMed Abstract  Publisher Full Text

Staple DW, Butcher SE: Pseudoknots: RNA structures with diverse functions.
PLoS Biol 2005, 3(6):e213.. PubMed Abstract  Publisher Full Text  PubMed Central Full Text

Xayaphoummine A, Bucher T, Thalmann F, Isambert H: Prediction and statistics of pseudoknots in RNA structures using exactly clustered stochastic simulations.
Proc Natl Acad Sci USA 2003, 100(26):153105. PubMed Abstract  Publisher Full Text  PubMed Central Full Text

Lyngso RB, Pedersen CNS: Pseudoknots in RNA Secondary Structures. In Proceedings of the Fourth Annual International Conferences on Computational Molecular Biology. ACM Press; 2000.

Rivas E, Eddy SR: A dynamic programming algorithm for RNA structure prediction including pseudoknots.
J Mol Biol 1999, 285(5):205368. PubMed Abstract  Publisher Full Text

Uemura Y, Hasegawa A, Kobayashi S, Yokomori T: Tree adjoining grammars for RNA structure prediction.
Theor Comput Sci 1999, 210:277303. Publisher Full Text

Akutsu T: Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots.
Discrete Appl Math 2000, 104:4562. Publisher Full Text

Deogun JS, Donis R, Komina O, Ma F: RNA secondary structure prediction with simple pseudoknots. In Proceedings of the second conference on AsiaPacific bioinformatics. Darlinghurst, Australia, Australia: Australian Computer Society, Inc.; 2004:239246.

Dirks RM, Pierce NA: A partition function algorithm for nucleic acid secondary structure including pseudoknots.
J Comput Chem 2003, 24(13):166477. PubMed Abstract  Publisher Full Text

Reeder J, Giegerich R: Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics.
BMC Bioinformatics 2004, 5:104. PubMed Abstract  BioMed Central Full Text  PubMed Central Full Text

Condon A, Davy B, Rastegari B, Zhao S, Tarrant F: Classifying RNA pseudoknotted structures.
Theor Comput Sci 2004, 320:3550. Publisher Full Text

Möhl M, Will S, Backofen R: Lifting prediction to alignment of RNA pseudoknots.
J Comput Biol 2010, 17(3):42942. PubMed Abstract  Publisher Full Text

Wexler Y, Zilberstein CBZ, ZivUkelson M: A Study of Accessible Motifs and RNA Folding Complexity. In Proceedings of the Tenth Annual International Conferences on Computational Molecular Biology, Volume 3909 of Lect Notes Comput Sci. Edited by Apostolico A, Guerra C, Istrail S, Pevzner PA, Waterman MS. Springer; 2006:473487.

Backofen R, Tsur D, Zakov S, ZivUkelson M: Sparse RNA Folding: Time and Space Eficient Algorithms. In Proceedings of the 20th Symposium on Combinatorial Pattern Matching, Volume 5577 of Lect Notes Comput Sci. Edited by Kucherov G, Ukkonen E. Springer; 2009:249262.

ZivUkelson M, GatViks I, Wexler Y, Shamir R: A Faster Algorithm for RNA Cofolding. In Proceedings of the 8th Workshop on Algorithms in Bioinformatics, Volume 5251 of Lect Notes Comput Sci. Edited by Crandall KA, Lagergren J. Springer; 2008:174185.

Salari R, Möhl M, Will S, Sahinalp S, Backofen R: Time and Space Efficient RNARNA Interaction Prediction via Sparse Folding. In Proceedings iof the Fourteenth Annual International Conferences on Computational Molecular Biology, Volume 6044 of Lect Notes Comput Sci. Edited by Berger B. Springer Berlin/Heidelberg; 2010:473490.

van Batenburg FH, Gultyaev AP, Pleij CW, Ng J, Oliehoek J: PseudoBase: a database with RNA pseudoknots.
Nucleic Acids Res 2000, 28:2014. PubMed Abstract  Publisher Full Text  PubMed Central Full Text