The DOI matches its Crossref record; 28 of the 28 references it cites were found in a registry or an index.
RNA Pseudoknot Prediction in Energy-Based Models
Abstract
RNA molecules are sequences of nucleotides that serve as more than mere intermediaries between DNA and proteins, e.g., as catalytic molecules. Computational prediction of RNA secondary structure is among the few structure prediction problems that can be solved satisfactorily in polynomial time. Most work has been done to predict structures that do not contain pseudoknots. Allowing pseudoknots introduces modeling and computational problems. In this paper we consider the problem of predicting RNA secondary structures with pseudoknots based on free energy minimization. We first give a brief comparison of energy-based methods for predicting RNA secondary structures with pseudoknots. We then prove that the general problem of predicting RNA secondary structures containing pseudoknots is NP complete for a large class of reasonable models of pseudoknots.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“Moreover, predicting structures with pseudoknots is classified as an NP-complete problem [5].”
From Towards secondary structure prediction of longer mRNA sequences using a quantum-centric optimization scheme (2025) · cites this paper as [5]
Citations
Cites
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
Optimal 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,604
Improved Estimation of Secondary Structure in Ribonucleic Acids
Tinoco, I., Borer, P. N., Dengler, B., Levine, M., Uhlenbeck, O. C., Crothers, D. M., & Gralla, J. D. (1973) · Nature New Biology · doi:10.1038/newbio246040a0 · Cited by 2,270
Gilbert, W. (1986) · Nature · Cited by 1,941
Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
Zhang, K., & Shasha, D. E. (1989) · SIAM Journal on Computing · doi:10.1137/0218082 · Cited by 1,312
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,288
A linear space algorithm for computing maximal common subsequences
Hirschberg, D. S. (1975) · Communications of the ACM · doi:10.1145/360825.360861 · Cited by 1,110
RNA sequence analysis using covariance models
Eddy, S. R., & Durbin, R. M. (1994) · Nucleic Acids Research · doi:10.1093/nar/22.11.2079 · Cited by 791
Rivas, E., & Eddy, S. R. (1999) · Journal of Molecular Biology · doi:10.1006/jmbi.1998.2436 · Cited by 763
Estimation of Secondary Structure in Ribonucleic Acids
Tinoco, I., Uhlenbeck, O. C., & Levine, M. (1971) · Nature · doi:10.1038/230362a0 · Cited by 686
Research works printed but not linked: 1
- Searls D.B., 1992, American Scientist, 80, 579
Cited by
Sorted by citations
Understanding 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 482
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 409
Searls, D. B. (2002) · Nature · doi:10.1038/nature01255 · Cited by 387
A partition function algorithm for nucleic acid secondary structure including pseudoknots
Dirks, R. M., & Pierce, N. (2003) · Journal of Computational Chemistry · doi:10.1002/jcc.10296 · Cited by 403
Thermodynamic Analysis of Interacting Nucleic Acid Strands
Dirks, R. M., Bois, J. S., Schaeffer, J., Winfree, E., & Pierce, N. A. (2007) · SIAM Review · doi:10.1137/060651100 · Cited by 374
Metadata
- Authors
- Lyngsø, R. B., & Pedersen, C. N. S.
- Affiliations
- University of California, Santa Cruz (US)
- Aarhus University (DK)
- Venue
- Journal of Computational Biology
- Publisher
- SAGE Publications
- Published
- 2000-08
- Volume
- 7
- Issue
- 3-4
- Pages
- 409-427
- ISSN
- 1066-5277 (ISSN-L)
- 1557-8666
- OpenAlex
- W2076756368
- Cited by
- 359
- References
- 28
- Citations by year
- 2026: 4 · 2025: 3 · 2024: 25 · 2023: 8 · 2022: 27 · 2021: 9 · 2020: 8 · 2019: 9 · 2018: 11 · 2017: 10 · 2016: 11 · 2015: 13 · 2014: 11 · 2013: 16 · 2012: 21
- FWCI
- 1.33
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- Journal of Computational Biology (publishedVersion)
- PubMed (publishedVersion)
- Topics
- Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › RNA and protein synthesis mechanisms
- Physical Sciences › Mathematics › Theoretical Computer Science › Algorithms and Data Compression
- Physical Sciences › Mathematics › Theoretical Computer Science › DNA and Biological Computing
- Keywords
- RNA pseudoknots, RNA secondary structure prediction, energy-based models, free energy minimization, NP-completeness, computational complexity
- MeSH terms
- Algorithms, Models, Molecular, Nucleic Acid Conformation, RNA, Thermodynamics, Computational Biology
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
