Evaluation of several lightweight stochastic context-free grammars for RNA secondary structure prediction
Open accessThe DOI matches its Crossref record; 62 of the 62 references it cites were found in a registry or an index.
Abstract
BACKGROUND: RNA secondary structure prediction methods based on probabilistic modeling can be developed using stochastic context-free grammars (SCFGs). Such methods can readily combine different sources of information that can be expressed probabilistically, such as an evolutionary model of comparative RNA sequence analysis and a biophysical model of structure plausibility. However, the number of free parameters in an integrated model for consensus RNA structure prediction can become untenable if the underlying SCFG design is too complex. Thus a key question is, what small, simple SCFG designs perform best for RNA secondary structure prediction? RESULTS: Nine different small SCFGs were implemented to explore the tradeoffs between model complexity and prediction accuracy. Each model was tested for single sequence structure prediction accuracy on a benchmark set of RNA secondary structures. CONCLUSIONS: Four SCFG designs had prediction accuracies near the performance of current energy minimization programs. One of these designs, introduced by Knudsen and Hein in their PFOLD algorithm, has only 21 free parameters and is significantly simpler than the others.
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
Introduction to automata theory, languages and computation
(1981) · Mathematics and Computers in Simulation · doi:10.1016/0378-4754(81)90068-9 · Cited by 10,699
Introduction to automata theory, languages, and computation
(1980) · Computer Languages · doi:10.1016/0096-0551(80)90011-9 · Cited by 6,824
Information theory, inference, and learning algorithms
(2004) · Choice Reviews Online · doi:10.5860/choice.41-5949 · Cited by 6,362
Information Theory, Inference, and Learning Algorithms
(2004) · Kybernetes · doi:10.1108/03684920410534506 · Cited by 4,937
Probability theory the logic of science
Jaynes, E. T., & Bretthorst, G. L. (2003) · Cited by 4,643
Probability Theory: The Logic of Science
Jaynes, E. T. (2003) · doi:10.1017/cbo9780511790423 · Cited by 4,045
Mathews, D. H., Sabina, J., Zuker, M., & Turner, D. H. (1999) · Journal of Molecular Biology · doi:10.1006/jmbi.1999.2700 · Cited by 3,795 · cited 10×
“Both mfold and RNAstructure was run with MAX = 750 P = 20 W = 0 and efn2 rearrangement as recommended by [7].”
BackgroundMethodResultInfluentialBiological 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-citationIntroduction to the Theory of Computation
Sipser, M. (1996) · ACM SIGACT News · doi:10.1145/230514.571645 · Cited by 2,784
Fast folding and comparison of RNA secondary structures
Hofacker, I. L., Fontana, W., Stadler, P. F., Bonhoeffer, L. S., Tacker, M., & Schuster, P. (1994) · Monatshefte f�r Chemie Chemical Monthly · doi:10.1007/bf00818163 · Cited by 2,306
守屋, 悦. (1980) · 情報処理 · Cited by 1,791
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
Griffiths-Jones, S. (2003) · Nucleic Acids Research · doi:10.1093/nar/gkg006 · Cited by 1,594
Non–coding RNA genes and the modern RNA world
Eddy, S. R. (2001) · Nature Reviews Genetics · doi:10.1038/35103511 · Cited by 1,426
Self-citationThe 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
Introduction to formal language theory
(1980) · Computer Languages · doi:10.1016/0096-0551(80)90068-5 · Cited by 1,254
Michel, F., & Westhof, E. (1990) · Journal of Molecular Biology · doi:10.1016/0022-2836(90)90386-z · Cited by 1,236
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-citationRivas, E., & Eddy, S. R. (1999) · Journal of Molecular Biology · doi:10.1006/jmbi.1998.2436 · Cited by 754
Self-citationLessons from an evolving rRNA: 16S and 23S rRNA structures from a comparative perspective
Gutell, R. R., Larsen, N. E., & Woese, C. R. (1994) · Microbiological Reviews · doi:10.1128/mmbr.58.1.10-26.1994 · Cited by 723
Secondary Structure Prediction for Aligned RNA Sequences
Hofacker, I. L., Fekete, M., & Stadler, P. F. (2002) · Journal of Molecular Biology · doi:10.1016/s0022-2836(02)00308-x · Cited by 639
Nussinov, R., Pieczenik, G., Griggs, J. R., & Kleitman, D. J. (1978) · SIAM Journal on Applied Mathematics · doi:10.1137/0135006 · Cited by 587
A statistical sampling algorithm for RNA secondary structure prediction
Ding, Y. (2003) · Nucleic Acids Research · doi:10.1093/nar/gkg938 · Cited by 566
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
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-citationWalter, 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
Pfold: RNA secondary structure prediction using stochastic context-free grammars
Knudsen, B., & Hein, J. (2003) · Nucleic Acids Research · doi:10.1093/nar/gkg614 · Cited by 456
Brown, J. (1998) · Nucleic Acids Research · doi:10.1093/nar/26.1.351 · Cited by 429
Stochastic 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
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
The accuracy of ribosomal RNA comparative structure models
Gutell, R. R., Lee, J. C., & Cannone, J. J. (2002) · Current Opinion in Structural Biology · doi:10.1016/s0959-440x(02)00339-1 · Cited by 364 · cited 2×
“Comparative sequence analysis is extremely reliable, and has produced strikingly accurate RNA structure predictions [14,20], but one is usually not blessed with the large number of sequences (nor the time and human expertise) that a purely comparative approach requires.”
Background[11] Predicting thermodynamic properties of RNA
(1995) · Methods in Enzymology · doi:10.1016/0076-6879(95)59047-1 · Cited by 358
RNA secondary structure prediction using stochastic context-free grammars and evolutionary history.
Knudsen, B., & Hein, J. (1999) · Bioinformatics · doi:10.1093/bioinformatics/15.6.446 · Cited by 348
Gutell, R. R., Power, A., Hertz, G. Z., Putz, E. J., & Stormo, G. D. (1992) · Nucleic Acids Research · doi:10.1093/nar/20.21.5785 · Cited by 296
Two methods for improving performance of an HMM and their application for gene finding.
Krogh, A. (1997) · PubMed · Cited by 290
Rivas, E., & Eddy, S. R. (2000) · Bioinformatics · doi:10.1093/bioinformatics/16.7.583 · Cited by 279
Self-citationBrown, J. W. (1999) · Nucleic Acids Research · doi:10.1093/nar/27.1.314 · Cited by 279
RNA secondary structure: a complete mathematical analysis
Waterman, M. S., & Smith, T. F. (1978) · Mathematical Biosciences · doi:10.1016/0025-5564(78)90099-8 · Cited by 270
The European database on small subunit ribosomal RNA
Wuyts, J., Peer, Y. V. D., Winkelmans, T., & Wachter, R. D. (2002) · Nucleic Acids Research · doi:10.1093/nar/30.1.183 · Cited by 251
Calculating nucleic acid secondary structure
Zuker, M. (2000) · Current Opinion in Structural Biology · doi:10.1016/s0959-440x(00)00088-9 · Cited by 227
The European Large Subunit Ribosomal RNA Database
Wuyts, J. (2001) · Nucleic Acids Research · doi:10.1093/nar/29.1.175 · Cited by 220
Finding the most significant common sequence and structure motifs in a set of RNA sequences
Gorodkin, J., Heyer, L. J., & Stormo, G. D. (1997) · Nucleic Acids Research · doi:10.1093/nar/25.18.3724 · Cited by 209
SRPDB: Signal Recognition Particle Database
Rosenblad, M. A. (2003) · Nucleic Acids Research · doi:10.1093/nar/gkg107 · Cited by 191
Ding, Y. (2001) · Nucleic Acids Research · doi:10.1093/nar/29.5.1034 · Cited by 161
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
Discovering common stem-loop motifs in unaligned RNA sequences
Gorodkin, J. (2001) · Nucleic Acids Research · doi:10.1093/nar/29.10.2135 · Cited by 138
Inferring consensus structure from nucleic acid sequences
Chiu, D., & Kolodziejczak, T. (1991) · Computer applications in the biosciences · doi:10.1093/bioinformatics/7.3.347 · Cited by 136
Evolutionary analyses of DNA sequences subject to constraints of secondary structure.
Muse, S. V. (1995) · Genetics · doi:10.1093/genetics/139.3.1429 · Cited by 130
Knudsen, B. R. (2001) · Nucleic Acids Research · doi:10.1093/nar/29.1.171 · Cited by 126
New insight into RNase P RNA structure from comparative analysis of the archaeal RNA
Harris, J. K., Haas, E. S., WILLIAMS, D., Frank, D. N., & Brown, J. W. (2001) · RNA · doi:10.1017/s1355838201001777 · Cited by 117
Phylogenetic comparative analysis and the secondary structure of ribonuclease P RNA — a review
Pace, N. R., Smith, D. K., Olsen, G. J., & James, B. D. (1989) · Gene · doi:10.1016/0378-1119(89)90031-0 · Cited by 112
Ji, Y., Xu, X., & Stormo, G. D. (2004) · Bioinformatics · doi:10.1093/bioinformatics/bth131 · Cited by 107
Construct a tool for thermodynamic controlled prediction of conserved secondary structure
Rupert, L., Gräf, S., & Gerhard, S. (1999) · Nucleic Acids Research · doi:10.1093/nar/27.21.4208 · Cited by 96
Zwieb, C. W. (2003) · Nucleic Acids Research · doi:10.1093/nar/gkg019 · Cited by 80
RNA Secondary Structure Prediction Based on Free Energy and Phylogenetic Analysis
Juan, V., & Wilson, C. (1999) · Journal of Molecular Biology · doi:10.1006/jmbi.1999.2801 · Cited by 71
Thermodynamics of Coaxially Stacked Helixes with GA and CC Mismatches
Kim, J., Walter, A. E., & Turner, D. H. (1996) · Biochemistry · doi:10.1021/bi960913z · Cited by 65
Finding the common structure shared by two homologous RNAs
Perriquet, O., Touzet, H., & Dauchet, M. (2002) · Bioinformatics · doi:10.1093/bioinformatics/19.1.108 · Cited by 59
Pairwise RNA Structure Comparison with Stochastic Context-Free Grammars
Holmes, I., & Rubin, G. M. (2001) · Pacific Symposium on Biocomputing (PSB) · doi:10.1142/9789812799623_0016 · Cited by 53
Explaining and Controlling Ambiguity in Dynamic Programming
Giegerich, R. (2000) · Lecture notes in computer science · doi:10.1007/3-540-45123-4_6 · Cited by 41
Using multiple alignments and phylogenetic trees to detect RNA secondary structure.
Gulko, B., & Haussler, D. H. (1996) · PubMed · Cited by 23
Cited by
Lorenz, R., Bernhart, S. H., Höner zu Siederdissen, C., Tafer, H., Flamm, C., Stadler, P. F., & Hofacker, I. L. (2011) · Algorithms for Molecular Biology · doi:10.1186/1748-7188-6-26 · Cited by 5,098
“These numbers are then used to compute the sensitivity , also known as true positive rate (TPR), and precision , also known as positive predictive value (PPV) [105].”
MethodRNAstructure: software for RNA secondary structure prediction and analysis
Reuter, J. S., & Mathews, D. H. (2010) · BMC Bioinformatics · doi:10.1186/1471-2105-11-129 · Cited by 2,012
Architecture and secondary structure of an entire HIV-1 RNA genome
Watts, J. M., Dang, K. K., Gorelick, R. J., Leonard, C. W., Bess Jr, J. W., Swanstrom, R., Burch, C. L., & Weeks, K. M. (2009) · Nature · doi:10.1038/nature08237 · Cited by 837
Accurate SHAPE-directed RNA structure determination
Deigan, K. E., Li, T. W., Mathews, D. H., & Weeks, K. M. (2009) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0806929106 · Cited by 696
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
Metadata
- Authors
- Dowell, R. D., & Eddy, S. R.
- Venue
- BMC Bioinformatics
- Published
- 2004-06-04
- Volume
- 5
- Issue
- 1
- Pages
- 71-71
- ISSN
- 1471-2105 (ISSN-L)
- OpenAlex
- W1861164398
- Cited by
- 280
- References
- 62
- FWCI
- 6.23
- Type
- journal article
- Language
- en
- Open access
- gold
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.