title: RNA pseudoknot prediction in energy-based models.
abstract: RNA molecules are sequences of nucleotides that serve as more than mere intermediaries between DNA and proteins, e.g., as catalytic molecules. Computational prediction of RNA secondary structure is among the few structure prediction problems that can be solved satisfactorily in polynomial time. Most work has been done to predict structures that do not contain pseudoknots. Allowing pseudoknots introduces modeling and computational problems. In this paper we consider the problem of predicting RNA secondary structures with pseudoknots based on free energy minimization. We first give a brief comparison of energy-based methods for predicting RNA secondary structures with pseudoknots. We then prove that the general problem of predicting RNA secondary structures containing pseudoknots is NP complete for a large class of reasonable models of pseudoknots.
authors: Baskin Center for Computer Science and Engineering, University of California, Santa Cruz 95064, USA. rlyngsoe@cse.ucsc.edu
authors: R B
authors: RB
authors: Lyngsø
authors: C N
authors: CN
authors: Pedersen
mesh_terms: D000465:Algorithms; D019295:Computational Biology; D008958:Models, Molecular; D009690:Nucleic Acid Conformation; D012313:RNA / Q000737:chemistry*; D013816:Thermodynamics
chemical_list: D012313:RNA