Parsing Nucleic Acid Pseudoknotted Secondary Structure: Algorithm and Applications
- 1 January 2007
- journal article
- research article
- Published by Mary Ann Liebert Inc in Journal of Computational Biology
- Vol. 14 (1) , 16-32
- https://doi.org/10.1089/cmb.2006.0108
Abstract
Accurate prediction of pseudoknotted nucleic acid secondary structure is an important computational challenge. Prediction algorithms based on dynamic programming aim to find a structure with minimum free energy according to some thermodynamic ("sum of loop energies") model that is implicit in the recurrences of the algorithm. However, a clear definition of what exactly are the loops in pseudoknotted structures, and their associated energies, has been lacking. In this work, we present a complete classification of loops in pseudoknotted nucleic secondary structures, and describe the Rivas and Eddy and other energy models as sum-of-loops energy models. We give a linear time algorithm for parsing a pseudoknotted secondary structure into its component loops. We give two applications of our parsing algorithm. The first is a linear time algorithm to calculate the free energy of a pseudoknotted secondary structure. This is useful for heuristic prediction algorithms, which are widely used since (pseudoknotted) RNA secondary structure prediction is NP-hard. The second application is a linear time algorithm to test the generality of the dynamic programming algorithm of Akutsu for secondary structure prediction.Together with previous work, we use this algorithm to compare the generality of state-of-the-art algorithms on real biological structures.Keywords
This publication has 38 references indexed in Scilit:
- Pseudoknots: RNA Structures with Diverse FunctionsPLoS Biology, 2005
- Algorithmic Self-Assembly of DNA Sierpinski TrianglesPLoS Biology, 2004
- The brave new world of RNANature, 2002
- A Linear-Time Algorithm for Computing Inversion Distance between Signed Permutations with an Experimental StudyJournal of Computational Biology, 2001
- The Protein Data BankNucleic Acids Research, 2000
- 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
- Effects of Mg2+, K+, and H+ on an equilibrium between alternative conformations of an RNA pseudoknotJournal of Molecular Biology, 1997
- The Computer Simulation of RNA Folding Pathways Using a Genetic AlgorithmJournal of Molecular Biology, 1995