# A dynamic programming algorithm for RNA structure prediction including pseudoknots.

@article{Rivas1999ADP, title={A dynamic programming algorithm for RNA structure prediction including pseudoknots.}, author={Elena Rivas and Sean R. Eddy}, journal={Journal of molecular biology}, year={1999}, volume={285 5}, pages={ 2053-68 } }

We describe a dynamic programming algorithm for predicting optimal RNA secondary structure, including pseudoknots. The algorithm has a worst case complexity of O(N6) in time and O(N4) in storage. The description of the algorithm is complex, which led us to adopt a useful graphical representation (Feynman diagrams) borrowed from quantum field theory. We present an implementation of the algorithm that generates the optimal minimum energy structure for a single RNA sequence, using standard RNA… Expand

#### Figures, Tables, and Topics from this paper

#### Paper Mentions

#### 776 Citations

RNA Secondary Structure Prediction with Simple Pseudoknots

- Computer Science
- APBC
- 2004

This paper presents a dynamic programming algorithm for prediction of simple pseudoknots in optimal secondary structure of a single RNA sequence using standard thermodynamic parameters for RNA folding and claims to be the most accurate and efficient algorithm to date. Expand

Predicting Algorithm of RNA Folding Structure with Pseudoknots

- Computer Science
- 2015 11th International Conference on Computational Intelligence and Security (CIS)
- 2015

A 2-approximation algorithm is presented by analyzing the RNA folding structure, there exists 1+t (t>0) polynomial time approximation scheme in searching maximum number of stackings, and the proof of the approximation scheme is given in RNA structure. Expand

Linear Time Algorithm for Parsing RNA Secondary Structure

- Computer Science
- WABI
- 2005

A comprehensive classification of loops in pseudoknotted RNA secondary structures is presented and a linear time algorithm for parsing a secondary structures into its component loops is obtained. Expand

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

- Computer Science, Medicine
- BMC Bioinformatics
- 2004

RNA pseudoknots of medium size can now be predicted reliably as well as efficiently by the new algorithm, and the adequacy of the canonization approach and the algorithm is shown. Expand

New Heuristic Algorithm of RNA Structure Prediction Including Pseudoknots

- Computer Science
- J. Comput.
- 2013

An improved heuristic algorithm is presented to predict RNA pseudoknotted structure, and it can compute arbitrary pseudoknots and is more effective than the existing algorithms. Expand

An Approximation Scheme for RNA Folding Structure Prediction Including Pseudoknots

- Mathematics, Computer Science
- 2013 Ninth International Conference on Computational Intelligence and Security
- 2013

The contribution of this paper is to obtain an efficient Approximation algorithm for finding RNA pseudoknotted structure, compared with other algorithms, the algorithm takes O(n3) time and O( n2) space. Expand

Linear Time Algorithm for Parsing RNA Secondary Structure Extended Abstract

- Mathematics
- 2005

Accurate prediction of pseudoknotted RNA secondary struc- ture is an important computational challenge. Typical prediction algo- rithms aim to find a structure with minimum free energy according to… Expand

Prediction of RNA Pseudoknots Using Heuristic Modeling with Mapping and Sequential Folding

- Physics, Medicine
- PloS one
- 2007

An algorithm utilizing structure mapping and thermodynamics is introduced for RNA pseudoknot prediction that finds the minimum free energy and identifies information about the flexibility of the RNA. Expand

Parsing Nucleic Acid Pseudoknotted Secondary Structure: Algorithm and Applications

- Computer Science, Medicine
- J. Comput. Biol.
- 2007

This work presents a complete classification of loops in pseudoknotted nucleic secondary structures, and describes the Rivas and Eddy and other energy models as sum-of-loops energy models. Expand

The Algorithm and Scheme of Prediction in RNA Folding Structure with Pseudoknots

- Computer Science
- 2017 13th International Conference on Computational Intelligence and Security (CIS)
- 2017

The paper presents an efficient algorithm for predicting RNA structure with pseudoknots, and the algorithm takes O(n3) time and O( n2) space and can predict arbitrary pseudok nots. Expand

#### References

SHOWING 1-10 OF 84 REFERENCES

Prediction of RNA secondary structure, including pseudoknotting, by computer simulation.

- Biology, Medicine
- Nucleic acids research
- 1990

A computer program is presented which determines the secondary structure of linear RNA molecules by simulating a hypothetical process of folding. This process implies the concept of 'nucleation… Expand

An APL-programmed genetic algorithm for the prediction of RNA secondary structure.

- Biology, Medicine
- Journal of theoretical biology
- 1995

The possibilities of using a genetic algorithm for the prediction of RNA secondary structure were investigated, and a fair number of correct stems are predicted, even when using computationally quick, but very crude, fitness criteria such as stem length and stacking energy. Expand

An RNA folding method capable of identifying pseudoknots and base triples

- Computer Science, Medicine
- Bioinform.
- 1998

Improved performance in MWM structure prediction was achieved in two ways, and new ways of calculating base pair likelihoods have been developed, and accuracy was improved by developing techniques for filtering out spurious base pairs predicted by the MWM program. Expand

On finding all suboptimal foldings of an RNA molecule.

- Physics, Medicine
- Science
- 1989

The mathematical problem of determining how well defined a minimum energy folding is can now be solved and all predicted base pairs that can participate in suboptimal structures may be displayed and analyzed graphically. Expand

Computer prediction of RNA structure.

- Chemistry, Medicine
- Methods in enzymology
- 1989

This chapter deals with computer methods to predict the occurrence of hydrogen bonds, which comprise the secondary structure, or folding, of the RNA molecule, which is a great simplification of reality. Expand

The computer simulation of RNA folding pathways using a genetic algorithm.

- Biology, Medicine
- Journal of molecular biology
- 1995

It is shown that the folding pathway simulation can result in structure predictions that are more consistent with phylogenetically proven structures than minimum energy solutions, suggesting that RNA folding kinetics is very important for the formation of functional RNA structures. Expand

Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information

- Biology, Computer Science
- Nucleic Acids Res.
- 1981

A new computer method for folding an RNA molecule that finds a conformation of minimum free energy using published values of stacking and destabilizing energies and is much more efficient, faster, and can fold larger molecules than procedures which have appeared up to now in the biological literature. Expand

Predicting thermodynamic properties of RNA.

- Chemistry, Medicine
- Methods in enzymology
- 1995

Publisher Summary This chapter discusses the thermodynamic properties of RNA and explores the rules governing the folding of biological molecules into their three-dimensional structures. RNA is an… Expand

Automated Alignment of RNA Sequences to Pseudoknotted Structures

- Computer Science, Medicine
- ISMB
- 1997

The operation of Seq7 is described and the use of the program in an Expectation-Maximization procedure that automates the process of structural modeling and alignment of RNA sequences. Expand

Graph-Theoretic Approach to RNA Modeling Using Comparative Data

- Computer Science, Medicine
- ISMB
- 1995

The utility of a graph-theoretic algorithm for building comparative RNA models using a maximum weighted matching algorithm to find the optimal set of basepairs given the mutual information for all pairs of alignment positions is examined. Expand