A new method for prediction of RNA secondary structure with pseudoknots, based on helix removal and refinement

摘要

RNA secondary structure is predicted by computing the structure with the minimum free energy. Although RNA structure without pseudoknots can be found using dynamic programming algorithms, finding general structures with pseudoknots is a nondeterministic polynomial-time (NP) hard problem. Several methods, such as recursive simple pseudoknots, have been developed in the past for obtaining a conformation with globally minimal energy among the restricted class of pseudoknots. In this work, we develop a new method for approximating a conformation with low energy, posing no restrictions on type of pseudoknots contained in the RNA secondary structure. In our method, the low-energy RNA secondary structure is obtained by repeatedly removing helices and performing dynamic programming to obtain the structure with energy lower than that obtained in the previous iteration. This method can be considered as a local minimization, and can be combined with any global optimization method that takes advantage of local minimization. We tested performance and convergency of the method by predicting a secondary structure of several RNA sequences, which is a priori known to contain pseudoknots.