Prediction of minimum free energy structure for simple non-standard pseudoknot

Abstract

Predicting the secondary structure with minimum free energy of an RNA molecule is an important problem in computational biology. Unfortunately, the problem is in general NP-hard if there are pseudoknots in the structure. Existing algorithms usually target at some restricted classes of pseudoknots. In this paper, we extend the current classification of pseudoknots to capture more complicated pseudoknots, namely the simple non-standard pseudoknots of degree k. We provide an algorithm to compute the structure with minimum free energy for this type of pseudoknots of degree 4 which covers all known secondary structures of RNAs in this class. Our algorithm runs in O(m 4) time where m is the length of the input RNA sequence. © 2011 Springer-Verlag Berlin Heidelberg.