Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics

Abstract

Background: The general problem of RNA secondary structure prediction under the widely used thermodynamic model is known to be NP-complete when the structures considered include arbitrary pseudoknots. For restricted classes of pseudoknots, several polynomial time algorithms have been designed, where the O(n⁶)time and O(n⁴) space algorithm by Rivas and Eddy is currently the best available program. Results: We introduce the class of canonical simple recursive pseudoknots and present an algorithm that requires O(n⁴) time and O(n²) space to predict the energetically optimal structure of an RNA sequence, possible containing such pseudoknots. Evaluation against a large collection of known pseudoknotted structures shows the adequacy of the canonization approach and our algorithm. Conclusions: RNA pseudoknots of medium size can now be predicted reliably as well as efficiently by the new algorithm.