Many RNAs fold into structures that are important for their regulatory, catalytic, or structural roles in the cell. The secondary structure of a RNA molecule is the set of base pairings in its 3D structure, most of which are Watson-Crick pairs between complementary bases. It plays a ciritical role in shaping the 3D structure of the molecule. When the number of sequences is small or there is a single RNA molecule, prediction of RNA structure based on free energy minimization is the most widely used approach. The secondary structure with the lowest free energy value is predicted to be the secondary structure for that strand. Nowadays, most algorithms that predict RNA secondary structures cannot output non-nested structures - pseudoknots. The general problem of predicting RNA secondary structure including pseudoknots has been proven to be NP-complete for an idealized thermodynamic model (Lyngso, Pedersen, 2000). Rivas and Eddy 1999 developed dynamic programming algorithms that find minimum free energy structure from a restricted class that includes certain pseudoknotted structures. In this project, we are developing a heuristic approach based on minimum free energy. The heuristic algorithm is based on an observation that substructures with very low energy are stable and more likely to form in the secondary structure. Our algorithm builds up candidate secondary structures by adding substructures one at a time to partally formed structures. Testing results show that this heuristic approach is much faster than Rivas and Eddy algorithm and the prediction quality is at least comparable as Rivas and Eddy algorithm.

Reference: Rivas E., Eddy S.R., A Dynamic Programming Algorithm for RNA Structure Prediction Including Pseduoknots. J. Mol. Biol. (1999) 285, 2053-2068.

The paper is available at ftp://ftp.genetics.wustl.edu/pub/eddy/papers/rivas-pseudoknot.ps