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
|
