Evaluating the Predictability of RNA Pseudoknots

J. Reeder1, R. Giegerich2
1robert@techfak.uni-bielefeld.de, Bielefeld University; 2jreeder@techfak.uni-bielefeld.de, Bielefeld University

Pseudoknots have been shown to be functionally relevant elements of RNA secondary structure. Determining such structures including pseudoknots in full generality has been shown to be an NP-hard problem. For more restricited classes of pseudoknots, polynomial algorithms have been devised. The program pknotsRE by Rivas and Eddy can handle chained simple recursive pseudoknots in O(n^6) time and O(n^4) space, which is practical only for molecules of less then 140 nucleotides in length.
Canonized simple recursive pseudoknots
We consider non-chained simple recursive pseudoknots and impose a condition of canonization. Such csr-PK pseudoknots can be predicted in O(n^4) time and O(n^2) space. Two orders of magnitude improvement allow to handle sequences up to n = 500. The approach results in three variants of our algorithm: For given RNA sequence s, Using the three programs in combination opens new ways to check for the potential of an important pseudoknotted structure in a given RNA molecule.
Evaluation of Pseudobase
Using the above algorithms, we performed a systematic evaluation of Batenburg's pseudoknot database ``Pseudobase''. Out of 212 pseudoknots tested, 149 fall in class csr-PK, of which 138 are recognized correctly. Others are partially or not at all recognized for a variety of reasons. We report on the number of confirmed structures, spot cases where we hit algorithmic limitations, analyse cases where the pseudoknot may be in competition with an alternative structure, and comment on the performance of the energy model. The programs are available at the Bielefeld Bioinformatics Server