Pseudoknots have been shown to be functionally important in many RNA mediated processes. However, established RNA folding programs (e.g. MFOLD, RNAfold) exclude pseudoknots from consideration for reasons of computational complexity: While folding a sequence of length n into unknotted structures requires O(n^3) time and O(n^2) space, including arbitrary pseudoknots into the folding space has been proved to be NP-complete. We introduce a new, restricted class of pseudoknots, which we call canonical simple recursive pseudoknots (csr-pk). Evaluation against a large set of known pseudoknotted structures shows the adequacy of that class. We implemented an RNA folding algorithm that considers the class csr-pk. It requires O(n^4) time and O(n^2) space. Thus RNA pseudoknots of medium size can now be predicted reliably as well as efficiently.


August 2002

Fri Dec 19 10:54:56 CET 2014