Novel and Efficient RNA Secondary Structure Prediction Using Hierarchical Folding
Authors:
- 1 March 2008
- journal article
- research article
- Published by SAGE Publications in Journal of Computational Biology
- Vol. 15 (2) , 139-163
Abstract
Algorithms for prediction of RNA secondary structure—the set of base pairs that form when an RNA molecule folds—are valuable to biologists who aim to understand RNA structure and function. Improving the accuracy and efficiency of prediction methods is an ongoing challenge, particularly for pseudoknotted secondary structures, in which base pairs overlap. This challenge is biologically important, since pseudoknotted structures play essential roles in functions of many RNA molecules, such as splicing and ribosomal frameshifting. State-of-the-art methods, which are based on free energy minimization, have high run-time complexity (typically Θ(n5) or worse), and can handle (minimize over) only limited types of pseudoknotted structures. We propose a new approach for prediction of pseudoknotted structures, motivated by the hypothesis that RNA structures fold hierarchically, with pseudoknot-free (non-overlapping) base pairs forming first, and pseudoknots forming later so as to minimize energy relative to the folded pseudoknot-free structure. Our HFold algorithm uses two-phase energy minimization to predict hierarchically formed secondary structures in O(n3) time, matching the complexity of the best algorithms for pseudoknot-free secondary structure prediction via energy minimization. Our algorithm can handle a wide range of biological structures, including kissing hairpins and nested kissing hairpins, which have previously required Θ(n6) time.Keywords
This publication has 25 references indexed in Scilit:
- Parsing Nucleic Acid Pseudoknotted Secondary Structure: Algorithm and ApplicationsJournal of Computational Biology, 2007
- Predicting RNA pseudoknot folding thermodynamicsNucleic Acids Research, 2006
- Pseudoknots: RNA Structures with Diverse FunctionsPLOS Biology, 2005
- Prediction of consensus RNA secondary structures including pseudoknotsIEEE/ACM Transactions on Computational Biology and Bioinformatics, 2004
- Using an RNA secondary structure partition function to determine confidence in base pairs predicted by free energy minimizationRNA, 2004
- The brave new world of RNANature, 2002
- How RNA foldsJournal of Molecular Biology, 1999
- Expanded sequence dependence of thermodynamic parameters improves prediction of RNA secondary structureJournal of Molecular Biology, 1999
- A dynamic programming algorithm for RNA structure prediction including pseudoknots 1 1Edited by I. TinocoJournal of Molecular Biology, 1999
- Tree adjoining grammars for RNA structure predictionTheoretical Computer Science, 1999