The DOI matches its Crossref record; 45 of the 45 references it cites were found in a registry or an index.
A dynamic programming algorithm for RNA structure prediction including pseudoknots 1 1Edited by I. Tinoco
Abstract
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 folding thermodynamic parameters augmented by a few parameters describing the thermodynamic stability of pseudoknots. We demonstrate the properties of the algorithm by using it to predict structures for several small pseudoknotted and non-pseudoknotted RNAs. Although the time and memory demands of the algorithm are steep, we believe this is the first algorithm to be able to fold optimal (minimum energy) pseudoknotted RNAs with the accepted RNA thermodynamic model.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Biological sequence analysis probabilistic models of proteins and nucleic acids
Durbin, R. M., Eddy, S. R., Krogh, A., & Mitchison, G. (1998) · Cited by 3,565
Self-citationOptimal computer folding of large RNA sequences using thermodynamics and auxiliary information
Zuker, M., & Stiegler, P. (1981) · Nucleic Acids Research · doi:10.1093/nar/9.1.133 · Cited by 3,562
Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids
Durbin, R., Eddy, S. R., Krogh, A., & Mitchison, G. (1998) · Cambridge University Press eBooks · doi:10.1017/cbo9780511790492 · Cited by 3,246
Self-citationGilbert, W. (1986) · Nature · doi:10.1038/319618a0 · Cited by 2,721
Bjorken, J. D., Drell, S. D., & Kahn, P. B. (1966) · American Journal of Physics · doi:10.1119/1.1972989 · Cited by 2,548
On Finding All Suboptimal Foldings of an RNA Molecule
Zuker, M. (1989) · Science · doi:10.1126/science.2468181 · Cited by 2,005
Gilbert, W. (1986) · Nature · Cited by 1,941
Compilation of tRNA sequences and sequences of tRNA genes
Sprinzl, M. (2004) · Nucleic Acids Research · doi:10.1093/nar/gki012 · Cited by 1,914
Maximum matching and a polyhedron with 0,1-vertices
Edmonds, J. (1965) · Journal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics · doi:10.6028/jres.069b.013 · Cited by 1,712
On certain formal properties of grammars
Chomsky, N. (1959) · Information and Control · doi:10.1016/s0019-9958(59)90362-6 · Cited by 1,588
Improved free-energy parameters for predictions of RNA duplex stability.
Freier, S. M., Kierzek, R., Jaeger, J. A., Sugimoto, N., Caruthers, M. H., Neilson, T., & Turner, D. H. (1986) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.83.24.9373 · Cited by 1,470
The equilibrium partition function and base pair binding probabilities for RNA secondary structure
McCaskill, J. S. (1990) · Biopolymers · doi:10.1002/bip.360290621 · Cited by 1,310
Shukla, S., Mishra, B., Avashthi, H., & Chandra, M. (2022) · Bioinformatics · doi:10.1016/b978-0-323-89775-4.00003-1 · Cited by 1,244
From sequences to shapes and back: a case study in RNA secondary structures
(1994) · Proceedings of the Royal Society of London. Series B: Biological Sciences · doi:10.1098/rspb.1994.0040 · Cited by 827
RNA sequence analysis using covariance models
Eddy, S. R., & Durbin, R. (1994) · Nucleic Acids Research · doi:10.1093/nar/22.11.2079 · Cited by 793
Self-citationCrystal structure of a hepatitis delta virus ribozyme
Ferré-D'Amaré, A. R., Zhou, K., & Doudna, J. A. (1998) · Nature · doi:10.1038/26912 · Cited by 785
The pacific symposium on biocomputing
Dunker, A. K. (1998) · Journal of Molecular Graphics and Modelling · doi:10.1016/s1093-3263(98)80012-0 · Cited by 657
Nussinov, R., Pieczenik, G., Griggs, J. R., & Kleitman, D. J. (1978) · SIAM Journal on Applied Mathematics · doi:10.1137/0135006 · Cited by 587
Simultaneous Solution of the RNA Folding, Alignment and Protosequence Problems
Sankoff, D. (1985) · SIAM Journal on Applied Mathematics · doi:10.1137/0145048 · Cited by 530
RNA secondary structures and their prediction
Zuker, M., & Sankoff, D. (1984) · Bulletin of Mathematical Biology · doi:10.1007/bf02459506 · Cited by 511
Walter, A. E., Turner, D. H., Kim, J., Lyttle, M. H., Müller, P., Mathews, D. H., & Zuker, M. (1994) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.91.20.9218 · Cited by 466
A new principle of RNA folding based on pseudoknotting
Pleij, C. W. A., Rietveld, K., & Bosch, L. (1985) · Nucleic Acids Research · doi:10.1093/nar/13.5.1717 · Cited by 422
RNA pseudoknots that inhibit human immunodeficiency virus type 1 reverse transcriptase.
Tuerk, C., MacDougal, S., & Gold, L. (1992) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.89.15.6988 · Cited by 415
[20] Computer prediction of RNA structure
Zuker, M. (1989) · Methods in Enzymology · doi:10.1016/0076-6879(89)80106-5 · Cited by 388 · cited 15×
“The Zuker algorithm (implemented in the programs MFOLD (Zuker, 1989a) and ViennaRNA (Schuster et al. , 1994)) is an efficient dynamic programming algorithm for identifying the globally minimal energy structure for a sequence, as defined by such a thermodynamic model (Zuker & Stiegler, 1981; Zuker &…”
MethodInfluentialStochastic context-free grammers for tRNA modeling
Sakakibara, Y., Brown, M., Hughey, R., Mian, I. S., Sjölander, K., Underwood, R. C., & Haussler, D. (1994) · Nucleic Acids Research · doi:10.1093/nar/22.23.5112 · Cited by 383
[11] Predicting thermodynamic properties of RNA
(1995) · Methods in Enzymology · doi:10.1016/0076-6879(95)59047-1 · Cited by 358
An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs
Gabow, H. N. (1976) · Journal of the ACM · doi:10.1145/321941.321942 · Cited by 342
The Computer Simulation of RNA Folding Pathways Using a Genetic Algorithm
Gultyaev, A. P., van Batenburg, F. H. D., & Pleij, C. W. A. (1995) · Journal of Molecular Biology · doi:10.1006/jmbi.1995.0356 · Cited by 321
Molecular Modeling of Nucleic Acids
(1997) · ACS Symposium Series · doi:10.1021/bk-1998-0682 · Cited by 301
Statistics of RNA secondary structures
Fontana, W., Konings, D. A. M., Stadler, P. F., & Schuster, P. (1993) · Biopolymers · doi:10.1002/bip.360330909 · Cited by 293
Prediction of RNA secondary structure, including pseudoknotting, by computer simulation
Abrashams, J. P., Berg, M. V. D., Batenburg, E. V., & Pleij, C. (1990) · Nucleic Acids Research · doi:10.1093/nar/18.10.3035 · Cited by 223
An APL-programmed genetic algorithm for the prediction of RNA secondary structure
Van Batenburg, F. H. D., Gultyaev, A. P., & Pleij, C. W. A. (1995) · Journal of Theoretical Biology · doi:10.1006/jtbi.1995.0098 · Cited by 194
Near identity of 3′ RNA secondary structure in bromoviruses and cucumber mosaic virus
Ahlquist, P., Dasgupta, R., & Kaesberg, P. (1981) · Cell · doi:10.1016/0092-8674(81)90283-x · Cited by 191
Structural and functional aspects of RNA pseudoknots
Ten Dam, E., Pleij, K., & Draper, D. (1992) · Biochemistry · doi:10.1021/bi00162a001 · Cited by 183
4 Probing RNA Structure, Function, and History by Comparative Analysis
Pace, N. R., Thomas, B. C., & Woese, C. R. (1993) · doi:10.1101/087969589.37.113 · Cited by 158
Compilation of tRNA sequences and sequences of tRNA genes
Steinberg, S., Misch, A., & Sprinzl, M. (1993) · Nucleic Acids Research · doi:10.1093/nar/21.13.3011 · Cited by 158
van Belkum, A., Abrahams, J. P., Pleij, C. W. A., & Bosch, L. (1985) · Nucleic Acids Research · doi:10.1093/nar/13.21.7673 · Cited by 151
An RNA folding method capable of identifying pseudoknots and base triples.
Tabaska, J. E., Cary, R. B., Gabow, H. N., & Stormo, G. D. (1998) · Bioinformatics · doi:10.1093/bioinformatics/14.8.691 · Cited by 149
Sequence of 1000 nucleotides at the 3′ end of tobacco mosaic virus RNA
Guilley, H., Jonard, G., Kukla, B. A., & Richards, K. (1979) · Nucleic Acids Research · doi:10.1093/nar/6.4.1287 · Cited by 132
Assessing the reliability of RNA folding using statistical mechanics
Huynen, M. A., Gutell, R. R., & Konings, D. A. M. (1997) · Journal of Molecular Biology · doi:10.1006/jmbi.1997.0889 · Cited by 120
Dumas, P., Moras, D., Florentz, C., Giegé, R., Verlaan, P. W. G., van Belkum, A., & Pleij, C. W. A. (1987) · Journal of Biomolecular Structure and Dynamics · doi:10.1080/07391102.1987.10507674 · Cited by 101
Zuker, M., & Jacobson, A. B. (1995) · Nucleic Acids Research · doi:10.1093/nar/23.14.2791 · Cited by 100
Thermodynamics of Folding a Pseudoknotted mRNA Fragment
Gluick, T. C., & Draper, D. E. (1994) · Journal of Molecular Biology · doi:10.1006/jmbi.1994.1493 · Cited by 96
RNA structures and folding: from conventional to new issues in structure predictions.
Schuster, P., Stadler, P. F., & Renner, A. (1997) · Current Opinion in Structural Biology · doi:10.1016/s0959-440x(97)80030-9 · Cited by 64
Brown, M., & Wilson, C. (1996) · PubMed · Cited by 52
Cited by
Fast and effective prediction of microRNA/target duplexes
REHMSMEIER, M., STEFFEN, P., HÖCHSMANN, M., & GIEGERICH, R. (2004) · RNA · doi:10.1261/rna.5248604 · Cited by 2,560
Mathews, D. H., Disney, M. D., Childs, J. L., Schroeder, S. J., Zuker, M., & Turner, D. H. (2004) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0401799101 · Cited by 1,622
CONTRAfold: RNA secondary structure prediction without physics-based models
Do, C. B., Woods, D. A., & Batzoglou, S. (2006) · Bioinformatics · doi:10.1093/bioinformatics/btl246 · Cited by 619
Comparative Genomics of Foot-and-Mouth Disease Virus
Carrillo, C., Tulman, E. R., Delhon, G., Lu, Z., Carreno, A., Vagnozzi, A., Kutish, G. F., & Rock, D. L. (2005) · Journal of Virology · doi:10.1128/jvi.79.10.6487-6504.2005 · Cited by 505
Noncoding RNA gene detection using comparative sequence analysis
Rivas, E., & Eddy, S. R. (2001) · BMC Bioinformatics · doi:10.1186/1471-2105-2-8 · Cited by 491
Self-citation
Metadata
- Authors
- Rivas, E., & Eddy, S. R.
- Venue
- Journal of Molecular Biology
- Publisher
- Elsevier BV
- Published
- 1999-02
- Volume
- 285
- Issue
- 5
- Pages
- 2053-2068
- ISSN
- 0022-2836 (ISSN-L)
- OpenAlex
- W2123241418
- Cited by
- 754
- References
- 45
- Type
- book review
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.