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
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-citationUnderstanding the transcriptome through RNA structure
Wan, Y., Kertesz, M., Spitale, R. C., Segal, E., & Chang, H. Y. (2011) · Nature Reviews Genetics · doi:10.1038/nrg3049 · Cited by 468
Prediction of RNA secondary structure by free energy minimization
Mathews, D. H., & Turner, D. H. (2006) · Current Opinion in Structural Biology · doi:10.1016/j.sbi.2006.05.010 · Cited by 405
Dynalign: an algorithm for finding the secondary structure common to two RNA sequences
Mathews, D. H., & Turner, D. H. (2002) · Journal of Molecular Biology · doi:10.1006/jmbi.2001.5351 · Cited by 372
MATHEWS, D. H. (2004) · RNA · doi:10.1261/rna.7650904 · Cited by 371
A partition function algorithm for nucleic acid secondary structure including pseudoknots
Dirks, R. M., & Pierce, N. A. (2003) · Journal of Computational Chemistry · doi:10.1002/jcc.10296 · Cited by 361
RNA Pseudoknot Prediction in Energy-Based Models
Lyngsø, R. B., & Pedersen, C. N. S. (2000) · Journal of Computational Biology · doi:10.1089/106652700750050862 · Cited by 359
Thermodynamic Analysis of Interacting Nucleic Acid Strands
Dirks, R. M., Bois, J. S., Schaeffer, J. M., Winfree, E., & Pierce, N. A. (2007) · SIAM Review · doi:10.1137/060651100 · Cited by 356
Sato, K., Kato, Y., Hamada, M., Akutsu, T., & Asai, K. (2011) · Bioinformatics · doi:10.1093/bioinformatics/btr215 · Cited by 331
Baird, S. D., Turcotte, M., Korneluk, R. G., & Holcik, M. (2006) · RNA · doi:10.1261/rna.157806 · Cited by 306
Reeder, J., & Giegerich, R. (2004) · BMC Bioinformatics · doi:10.1186/1471-2105-5-104 · Cited by 303
Partition function and base pairing probabilities of RNA heterodimers
Bernhart, S. H., Tafer, H., Mückstein, U., Flamm, C., Stadler, P. F., & Hofacker, I. L. (2006) · Algorithms for Molecular Biology · doi:10.1186/1748-7188-1-3 · Cited by 303
RNA Folding: Conformational Statistics, Folding Kinetics, and Ion Electrostatics
Chen, S.-J. (2008) · Annual Review of Biophysics · doi:10.1146/annurev.biophys.37.032807.125957 · Cited by 299
RNA secondary structure: physical and computational aspects
Higgs, P. G. (2000) · Quarterly Reviews of Biophysics · doi:10.1017/s0033583500003620 · Cited by 287
Ding, F., Sharma, S., Chalasani, P., Demidov, V. V., Broude, N. E., & Dokholyan, N. V. (2008) · RNA · doi:10.1261/rna.894608 · Cited by 283
HotKnots: Heuristic prediction of RNA secondary structures including pseudoknots
REN, J., RASTEGARI, B., CONDON, A., & HOOS, H. H. (2005) · RNA · doi:10.1261/rna.7284905 · Cited by 281
Dowell, R. D., & Eddy, S. R. (2004) · BMC Bioinformatics · doi:10.1186/1471-2105-5-71 · Cited by 280
Self-citationRivas, E., & Eddy, S. R. (2000) · Bioinformatics · doi:10.1093/bioinformatics/16.7.583 · Cited by 279
“…RNA folding—implemented in the programs MFOLD (Zuker and Stiegler, 1981), ViennaRNA (Schuster et al., 1994), and (with pseudoknots) in Rivas and Eddy (1999)—use thermodynamic parameters (Freier et al., 1986; Turner et al., 1987) to describe the different elements of RNA secondary…”
BackgroundMethodInfluentialSelf-citationRNA STRAND: The RNA Secondary Structure and Statistical Analysis Database
Andronescu, M., Bereg, V., Hoos, H. H., & Condon, A. (2008) · BMC Bioinformatics · doi:10.1186/1471-2105-9-340 · Cited by 272
Xayaphoummine, A., Bucher, T., & Isambert, H. (2005) · Nucleic Acids Research · doi:10.1093/nar/gki447 · Cited by 262
Fontana, W. (2002) · BioEssays · doi:10.1002/bies.10190 · Cited by 179
“Thermodynamic((18)) and kinetic((19)) algorithms that account for pseudoknots have been developed recently.”
Background3D RNA and Functional Interactions from Evolutionary Couplings
Weinreb, C., Riesselman, A. J., Ingraham, J. B., Gross, T., Sander, C., & Marks, D. S. (2016) · Cell · doi:10.1016/j.cell.2016.03.030 · Cited by 159
“Comparative sequence analyses of RNA continue to contribute to successful RNA sequence alignment (Nawrocki and Eddy, 2013) and secondary structure prediction methods (Hofacker et al., 2002; Nussinov and Jacobson, 1980; Rivas and Eddy, 1999; Zuker, 2003) (review Hofacker and Lorenz, 2014), but existing techniques for i…”
The four ingredients of single-sequence RNA secondary structure prediction. A unifying perspective
Rivas, E. (2013) · RNA Biology · doi:10.4161/rna.24971 · Cited by 57
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.