HotKnots: heuristic prediction of RNA secondary structures including pseudoknots.
We present HotKnots, a new heuristic algorithm for the prediction of RNA secondary structures including pseudoknots. Based on the simple idea of iteratively forming stable stems, our algorithm explores many alternative secondary structures, using a free energy minimization algorithm for pseudoknot free secondary structures to identify promising candidate stems. In an empirical evaluation of the algorithm with 43 sequences taken from the Pseudobase database and from the literature on pseudoknotted structures, we found that overall, in terms of the sensitivity and specificity of predictions, HotKnots outperforms the well-known Pseudoknots algorithm of Rivas and Eddy and the NUPACK algorithm of Dirks and Pierce, both based on dynamic programming approaches for limited classes of pseudoknotted structures. It also outperforms the heuristic Iterated Loop Matching algorithm of Ruan and colleagues, and in many cases gives better results than the genetic algorithm from the STAR package of van Batenburg and colleagues and the recent pknotsRG-mfe algorithm of Reeder and Giegerich. The HotKnots algorithm has been implemented in C/C++ and is available from http://www.cs.ubc.ca/labs/beta/Software/HotKnots.
Ren
Jihong
J
Department of Computer Science, University of British Columbia, Vancouver, BC V6T 1Z4, Canada.
Rastegari
Baharak
B
Condon
Anne
A
Hoos
Holger H
HH
D000465:Algorithms; D020029:Base Pairing; D001483:Base Sequence; D019295:Computational Biology; D008969:Molecular Sequence Data; D009690:Nucleic Acid Conformation; D011237:Predictive Value of Tests; D012313:RNA / Q000737:chemistry*; D012680:Sensitivity and Specificity; D017423:Sequence Analysis, RNA; D012689:Sequence Homology, Nucleic Acid; D012984:Software
D012313:RNA