description
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.

people

start
August 2002

Fri Dec 19 10:54:56 CET 2014