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.
Integrity signals
Registry
Cites
Statistics
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?
Predicting RNA structures with pseudoknots is NP-complete.
“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]
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 · see citing works
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 · see citing works
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 · see citing works
Gilbert, W. (1986) · Nature · Cited by 1,941 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
Rivas, E., & Eddy, S. R. (1999) · Journal of Molecular Biology · doi:10.1006/jmbi.1998.2436 · Cited by 763 · see citing works
Estimation of Secondary Structure in Ribonucleic Acids
Tinoco, I., Uhlenbeck, O. C., & Levine, M. (1971) · Nature · doi:10.1038/230362a0 · Cited by 686 · see citing works
Turner, D. H., Sugimoto, N., & Freier, S. M. (1988) · Annual Review of Biophysics and Biophysical Chemistry · doi:10.1146/annurev.bb.17.060188.001123 · Cited by 652 · see citing works
Fast algorithm for predicting the secondary structure of single-stranded RNA.
Nussinov, R., & Jacobson, A. B. (1980) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.77.11.6309 · Cited by 607 · see citing works
Nussinov, R., Pieczenik, G., Griggs, J. R., & Kleitman, D. J. (1978) · SIAM Journal on Applied Mathematics · doi:10.1137/0135006 · Cited by 587 · see citing works
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 · see citing works
Stochastic context-free grammers for tRNA modeling
Sakakibara, Y., Brown, M., Hughey, R., Mian, S. I., Sjölander, K. V., Underwood, R. C., & Haussler, D. H. (1994) · Nucleic Acids Research · doi:10.1093/nar/22.23.5112 · Cited by 383 · see citing works
RNA secondary structure prediction using stochastic context-free grammars and evolutionary history.
Knudsen, B. R., & Hein, J. (1999) · Bioinformatics · doi:10.1093/bioinformatics/15.6.446 · Cited by 349 · see citing works
Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots
Akutsu, T. (2000) · Discrete Applied Mathematics · doi:10.1016/s0166-218x(00)00186-4 · Cited by 308 · see citing works
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 193 · see citing works
Tree adjoining grammars for RNA structure prediction
Uemura, Y., Hasegawa, A., Kobayashi, S., & Yokomori, T. (1999) · Theoretical Computer Science · doi:10.1016/s0304-3975(98)00090-5 · Cited by 176 · see citing works
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 · see citing works
Fast evaluation of internal loops in RNA secondary structure prediction.
Lyngs√∏, R. B., Zuker, M., & Pedersen, C. N. (1999) · Bioinformatics · doi:10.1093/bioinformatics/15.6.440 · Cited by 147 · see citing works
Self-citationAn energy model that predicts the correct folding of both the tRNA and the 5S RNA molecules
Papanicolaou, C., Gouy, M., & Ninio, J. (1984) · Nucleic Acids Research · doi:10.1093/nar/12.1part1.31 · Cited by 123 · see citing works
Searls, D. B. (1992) · Cited by 119 · see citing works
Pseudoknots in RNA secondary structures
Lyngsø, R. B., & Pedersen, C. N. S. (2000) · doi:10.1145/332306.332551 · Cited by 104 · see citing works
Self-citationIeong, S., Kao, M., Lam, T., Sung, W.-K. K., & Yiu, S. (2003) · Journal of Computational Biology · doi:10.1089/106652703322756186 · Cited by 61 · see citing works
Brown, M., & Wilson, C. (1996) · PubMed · Cited by 52 · see citing works
Reynolds, G., & Rennert, J. (1980) · The Musical Times · doi:10.2307/963433 · Cited by 39 · see citing works
Finding common sequence and structure motifs in a set of RNA sequences.
Gorodkin, J., Heyer, L. J., & Stormo, G. D. (1997) · PubMed · Cited by 24 · see citing works
Flagged first, then by citations
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 469 · see citing works
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 400 · see citing works
Searls, D. B. (2002) · Nature · doi:10.1038/nature01255 · Cited by 387 · see citing works
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 · see citing works
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 357 · see citing works
Sato, K., Kato, Y., Hamada, M., Akutsu, T., & Asai, K. (2011) · Bioinform. · doi:10.1093/bioinformatics/btr215 · Cited by 322 · see citing works
Accurate SHAPE-directed RNA secondary structure modeling, including pseudoknots
Hajdin, C. E., Bellaousov, S., Huggins, W., Leonard, C. W., Mathews, D. H., & Weeks, K. M. (2013) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1219988110 · Cited by 332 · see citing works
Reeder, J., & Giegerich, R. (2004) · BMC Bioinformatics · doi:10.1186/1471-2105-5-104 · Cited by 303 · see citing works
HotKnots: heuristic prediction of RNA secondary structures including pseudoknots.
Ren, J.-H., Rastegari, B., Condon, A., & Hoos, H. (2005) · RNA: A publication of the RNA Society · doi:10.1261/rna.7284905 · Cited by 297 · see citing works
Xayaphoummine, A., Bucher, T., & Isambert, H. (2005) · Nucleic Acids Research · doi:10.1093/nar/gki447 · Cited by 262 · see citing works
Viral RNA pseudoknots: versatile motifs in gene expression and replication
Brierley, I., Pennell, S., & Gilbert, R. J. C. (2007) · Nature Reviews Microbiology · doi:10.1038/nrmicro1704 · Cited by 240 · see citing works
An Iterated loop matching approach to the prediction of RNA secondary structures with pseudoknots
Ruan, J., Stormo, G. D., & Zhang, W. (2003) · Bioinformatics · doi:10.1093/bioinformatics/btg373 · Cited by 225 · see citing works
ProbKnot: Fast prediction of RNA secondary structure including pseudoknots
Bellaousov, S., & Mathews, D. H. (2010) · RNA · doi:10.1261/rna.2125310 · Cited by 218 · see citing works
RNA Structure: Advances and Assessment of 3D Structure Prediction
Miao, Z., & Westhof, É. (2017) · Annual Review of Biophysics · doi:10.1146/annurev-biophys-070816-034125 · Cited by 186 · see citing works
LncRNA Structural Characteristics in Epigenetic Regulation
Wang, C., Wang, L., Ding, Y., Lu, X., Zhang, G., Yang, J., Zheng, H., Wang, H., Jiang, Y., & Xu, L. (2017) · International Journal of Molecular Sciences · doi:10.3390/ijms18122659 · Cited by 172 · see citing works
RNA Structure Prediction: An Overview of Methods
Seetin, M. G., & Mathews, D. H. (2012) · Methods in molecular biology · doi:10.1007/978-1-61779-949-5_8 · Cited by 159 · see citing works
Molecular knots in biology and chemistry
Lim, N. C. H., & Jackson, S. (2015) · Journal of Physics Condensed Matter · doi:10.1088/0953-8984/27/35/354101 · Cited by 161 · see citing works
Predicting RNA pseudoknot folding thermodynamics
Cao, S., & Chen, S. (2006) · Nucleic Acids Research · doi:10.1093/nar/gkl346 · Cited by 160 · see citing works
Computational approaches for RNA energy parameter estimation
Andronescu, M., Condon, A., Hoos, H. H., Mathews, D. H., & Murphy, K. P. (2010) · RNA · doi:10.1261/rna.1950510 · Cited by 132 · see citing works
Predicting RNA secondary structures from sequence and probing data
Lorenz, R., Wolfinger, M. T., Andrea Tanzer, A., & Hofacker, I. L. (2016) · Methods · doi:10.1016/j.ymeth.2016.04.004 · Cited by 122 · see citing works
Computational approaches to 3D modeling of RNA
Laing, C., & Tamar Schlick, A. (2010) · Journal of Physics Condensed Matter · doi:10.1088/0953-8984/22/28/283101 · Cited by 116 · see citing works
Integrating Chemical Footprinting Data into RNA Secondary Structure Prediction
Zarringhalam, K., Meyer, M. M., Dotú, I., Chuang, J. H., & Clote, P. (2012) · PLoS ONE · doi:10.1371/journal.pone.0045160 · Cited by 114 · see citing works
pknotsRG: RNA pseudoknot folding including near-optimal structures and sliding windows
Reeder, J., Steffen, P., & Giegerich, R. (2007) · Nucleic Acids Research · doi:10.1093/nar/gkm258 · Cited by 114 · see citing works
Review of machine learning methods for RNA secondary structure prediction
Zhao, Q., Zhao, Z., Fan, X., Yuan, Z., Mao, Q., & Yao, Y. (2021) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1009291 · Cited by 106 · see citing works
Topology and prediction of RNA pseudoknots
Reidys, C. M., Huang, F. W. D., Andersen, J. E., Penner, R., Stadler, P. F., & Nebel, M. E. (2011) · Bioinformatics · doi:10.1093/bioinformatics/btr090 · Cited by 106 · see citing works
RNA Secondary Structure Prediction By Learning Unrolled AlgorithmsPreprint
Chen, X., Li, Y., Umarov, R. K., Gao, X., & Song, L. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2002.05810 · Cited by 110 · see citing works
Sato, K., & Hamada, M. (2023) · Briefings in Bioinformatics · doi:10.1093/bib/bbad186 · Cited by 101 · see citing works
RNAiFOLD: A CONSTRAINT PROGRAMMING ALGORITHM FOR RNA INVERSE FOLDING AND MOLECULAR DESIGN
García-Martín, J. A., Clote, P., & Dotú, I. (2012) · Journal of Bioinformatics and Computational Biology · doi:10.1142/s0219720013500017 · Cited by 95 · see citing works
Multistrand RNA Secondary Structure Prediction and Nanostructure Design Including Pseudoknots
Bindewald, E., Afonin, K. A., Jaeger, L., & Shapiro, B. A. (2011) · ACS Nano · doi:10.1021/nn202666w · Cited by 89 · see citing works
Classifying RNA pseudoknotted structures
Condon, A., Davy, B., Rastegari, B., Zhao, S., & Tarrant, F. (2004) · Theoretical Computer Science · doi:10.1016/j.tcs.2004.03.042 · Cited by 89 · see citing works
DotKnot: pseudoknot prediction using the probability dot plot under a refined energy model
Sperschneider, J., & Datta, A. (2010) · Nucleic Acids Research · doi:10.1093/nar/gkq021 · Cited by 85 · see citing works
Stochastic modeling of RNA pseudoknotted structures: a grammatical approach
Cai, L., Malmberg, R. L., & Wu, Y. (2003) · Bioinformatics · doi:10.1093/bioinformatics/btg1007 · Cited by 85 · see citing works
From knotted to nested RNA structures: A variety of computational methods for pseudoknot removal
Smit, S., Rother, K. M., Heringa, J., & Knight, R. D. (2008) · RNA · doi:10.1261/rna.881308 · Cited by 84 · see citing works
Zhang, H., Zhang, L., Mathews, D. H., & Huang, L. (2020) · Bioinformatics · doi:10.1093/bioinformatics/btaa460 · Cited by 83 · see citing works
Schmitz, U., Lai, X., Winter, F., Wolkenhauer, O., Vera, J., & Gupta, S. K. (2014) · Nucleic Acids Research · doi:10.1093/nar/gku465 · Cited by 82 · see citing works
Jacobs, J. L., Belew, A. T., Rakauskaitė, R., & Dinman, J. D. (2006) · Nucleic Acids Research · doi:10.1093/nar/gkl1033 · Cited by 81 · see citing works
Meyer, I. M., & Miklós, I. (2007) · PLoS Computational Biology · doi:10.1371/journal.pcbi.0030149 · Cited by 78 · see citing works
Prediction of RNA Pseudoknots Using Heuristic Modeling with Mapping and Sequential Folding
Dawson, W., Fujiwara, K., & Kawai, G. (2007) · PLoS ONE · doi:10.1371/journal.pone.0000905 · Cited by 72 · see citing works
Prediction of RNA secondary structure including pseudoknots for long sequences
Sato, K., & Kato, Y. (2021) · Briefings in Bioinformatics · doi:10.1093/bib/bbab395 · Cited by 71 · see citing works
Pair stochastic tree adjoining grammars for aligning and predicting pseudoknot RNA structures
Matsui, H., Sato, K., & Sakakibara, Y. (2005) · Computer applications in the biosciences · doi:10.1093/bioinformatics/bti385 · Cited by 70 · see citing works
Prediction of consensus RNA secondary structures including pseudoknots
Witwer, C., Hofacker, I. L., & Stadler, P. F. (2004) · IEEE Transactions on Computational Biology and Bioinformatics · doi:10.1109/tcbb.2004.22 · Cited by 69 · see citing works
Computational methods in noncoding RNA research
Machado‐Lima, A., Portillo, H. A. D., & Durham, A. M. (2007) · Journal of Mathematical Biology · doi:10.1007/s00285-007-0122-6 · Cited by 67 · see citing works
Beyond Mfold: Recent advances in RNA bioinformatics
Reeder, J., Höchsmann, M., Rehmsmeier, M., Voß, B., & Giegerich, R. (2006) · Journal of Biotechnology · doi:10.1016/j.jbiotec.2006.01.034 · Cited by 66 · see citing works
Ieong, S., Kao, M., Lam, T., Sung, W.-K. K., & Yiu, S. (2003) · Journal of Computational Biology · doi:10.1089/106652703322756186 · Cited by 61 · see citing works
Prediction of RNA secondary structure with pseudoknots using integer programming
Poolsap, U., Kato, Y., & Akutsu, T. (2009) · BMC Bioinformatics · doi:10.1186/1471-2105-10-s1-s38 · Cited by 58 · see citing works
Inverse folding of RNA pseudoknot structures
Gao, J., Li, L. Y. M., & Reidys, C. M. (2010) · Algorithms for Molecular Biology · doi:10.1186/1748-7188-5-27 · Cited by 58 · see citing works
Structure Prediction: New Insights into Decrypting Long Noncoding RNAs
Yan, K. H., Arfat, Y., Li, D., Zhao, F., Chen, Z., Yin, C., Sun, Y., Hu, L., Yang, T., & Qian, A. (2016) · International Journal of Molecular Sciences · doi:10.3390/ijms17010132 · Cited by 57 · see citing works
Identification and classification of ncRNA molecules using graph properties
Childs, L. H., Nikoloski, Z., May, P., & Walther, D. (2009) · Nucleic Acids Research · doi:10.1093/nar/gkp206 · Cited by 57 · see citing works
Asymmetry in RNA pseudoknots: observation and theory
Aalberts, D. P. (2005) · Nucleic Acids Research · doi:10.1093/nar/gki508 · Cited by 57 · see citing works
Smith, O., Dunshea, G., Sinding, M. S., Fedorov, S., Germonpré, M., Bocherens, H., & Gilbert, M. T. P. (2019) · PLoS Biology · doi:10.1371/journal.pbio.3000166 · Cited by 54 · see citing works
Pseudoknots in RNA Secondary Structures: Representation, Enumeration, and Prevalence
Rødland, E. A. (2006) · Journal of Computational Biology · doi:10.1089/cmb.2006.13.1197 · Cited by 52 · see citing works
Complexity of Pseudoknot Prediction in Simple Models
Lyngsø, R. B. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-27836-8_77 · Cited by 51 · see citing works
Self-citationRNA Challenges for Computational Chemists
Yildirim, I., & Turner, D. H. (2005) · Biochemistry · doi:10.1021/bi051236o · Cited by 50 · see citing works
A fast and robust iterative algorithm for prediction of RNA pseudoknotted secondary structures
Jabbari, H., & Condon, A. (2014) · BMC Bioinformatics · doi:10.1186/1471-2105-15-147 · Cited by 43 · see citing works
RNA secondary structure prediction with pseudoknots: Contribution of algorithm versus energy model
Jabbari, H., Wark, I., & Montemagno, C. D. (2018) · PLoS ONE · doi:10.1371/journal.pone.0194583 · Cited by 49 · see citing works
Zhang, J., Dundas, J., Lin, M. T., Chen, R., Wang, W., & Liang, J. (2009) · RNA · doi:10.1261/rna.1723609 · Cited by 49 · see citing works
Choudhary, K., Deng, F., & Aviran, S. (2017) · Quantitative Biology · doi:10.1007/s40484-017-0093-6 · Cited by 44 · see citing works
An O ( n 5 ) Algorithm for MFE Prediction of Kissing Hairpins and 4-Chains in Nucleic Acids
Chen, H.-L., Condon, A., & Jabbari, H. (2009) · Journal of Computational Biology · doi:10.1089/cmb.2008.0219 · Cited by 46 · see citing works
Grammatical Representations of Macromolecular Structure
Chiang, D., Joshi, A. K., & Searls, D. B. (2006) · Journal of Computational Biology · doi:10.1089/cmb.2006.13.1077 · Cited by 45 · see citing works
Predicting RNA secondary structures with pseudoknots by MCMC sampling
Metzler, D., & Nebel, M. E. (2007) · Journal of Mathematical Biology · doi:10.1007/s00285-007-0106-6 · Cited by 44 · see citing works
A heuristic approach for detecting RNA H-type pseudoknots
Huang, C.-H., Lu, C. L., & Chiu, H.-T. (2005) · Bioinformatics · doi:10.1093/bioinformatics/bti568 · Cited by 44 · see citing works
The jerky and knotty dynamics of RNA
Isambert, H. (2009) · Methods · doi:10.1016/j.ymeth.2009.06.005 · Cited by 43 · see citing works
Heuristic RNA pseudoknot prediction including intramolecular kissing hairpins
Sperschneider, J., Datta, A., & Wise, M. J. (2010) · RNA · doi:10.1261/rna.2394511 · Cited by 43 · see citing works
Computing the Partition Function for Kinetically Trapped RNA Secondary Structures
Lorenz, W. A., & Clote, P. (2011) · PLoS ONE · doi:10.1371/journal.pone.0016178 · Cited by 41 · see citing works
Biphasic Folding Kinetics of RNA Pseudoknots and Telomerase RNA Activity
Cao, S., & Chen, S. (2007) · Journal of Molecular Biology · doi:10.1016/j.jmb.2007.01.006 · Cited by 41 · see citing works
Overview of DNA origami for molecular self‐assembly
Saaem, I., & LaBean, T. H. (2013) · Wiley Interdisciplinary Reviews Nanomedicine and Nanobiotechnology · doi:10.1002/wnan.1204 · Cited by 39 · see citing works
Computational RNA Structure Prediction
Martı́-Renom, M. A., & Capriotti, E. (2008) · Current Bioinformatics · doi:10.2174/157489308783329823 · Cited by 39 · see citing works
Chen, X., He, S., Bu, D., Zhang, F., Wang, Z., Chen, R., & Gao, W. X. (2008) · Bioinformatics · doi:10.1093/bioinformatics/btn327 · Cited by 39 · see citing works
Efficient Parameterized Algorithms for Biopolymer Structure-Sequence Alignment
Song, Y., Liu, C., Huang, X., Malmberg, R. L., Xu, Y., & Cai, L. (2006) · IEEE Transactions on Computational Biology and Bioinformatics · doi:10.1109/tcbb.2006.52 · Cited by 38 · see citing works
RNA pseudoknots: folding and finding
Liu, B., Mathews, D. H., & Turner, D. H. (2010) · F1000 Biology Reports · doi:10.3410/b2-8 · Cited by 38 · see citing works
RNA origami: design, simulation and application
Poppleton, E., Urbanek, N., Chakraborty, T., Griffo, A., Monari, L., & Göpfrich, K. (2023) · RNA Biology · doi:10.1080/15476286.2023.2237719 · Cited by 37 · see citing works
Dependence among Sites in RNA Evolution
Yu, J., & Thorne, J. L. (2006) · Molecular Biology and Evolution · doi:10.1093/molbev/msl015 · Cited by 37 · see citing works
TT2NE: a novel algorithm to predict RNA secondary structures with pseudoknots
Bon, M., & Orland, H. (2011) · Nucleic Acids Research · doi:10.1093/nar/gkr240 · Cited by 37 · see citing works
Complete RNA inverse folding: computational design of functional hammerhead ribozymes
Dotu, I., Garcia-Martin, J. A., Slinger, B. L., Mechery, V., Meyer, M. M., & Clote, P. (2014) · Nucleic Acids Research · doi:10.1093/nar/gku740 · Cited by 36 · see citing works
Designing RNA Secondary Structures Is Hard
Bonnet, É., Rzążewski, P., & Sikora, F. (2020) · Journal of Computational Biology · doi:10.1089/cmb.2019.0420 · Cited by 36 · see citing works
Efficient sampling of RNA secondary structures from the Boltzmann ensemble of low-energy
Ponty, Y. (2007) · Journal of Mathematical Biology · doi:10.1007/s00285-007-0137-z · Cited by 36 · see citing works
Cache-Oblivious Dynamic Programming for Bioinformatics
Chowdhury, R. A., Le, H.-S., & Ramachandran, V. (2008) · IEEE Transactions on Computational Biology and Bioinformatics · doi:10.1109/tcbb.2008.94 · Cited by 36 · see citing works
McGenus: a Monte Carlo algorithm to predict RNA secondary structures with pseudoknots
Bon, M., Micheletti, C., & Orland, H. (2012) · Nucleic Acids Research · doi:10.1093/nar/gks1204 · Cited by 36 · see citing works
Pseudoknots in RNA folding landscapes
Kucharík, M., Hofacker, I. L., Stadler, P. F., & Qin, J. (2015) · Bioinformatics · doi:10.1093/bioinformatics/btv572 · Cited by 35 · see citing works
Prediction of contacts from correlated sequence substitutions
Taylor, W. R., Hamilton, R. S., & Sadowski, M. I. (2013) · Current Opinion in Structural Biology · doi:10.1016/j.sbi.2013.04.001 · Cited by 34 · see citing works
iVaccine-Deep: Prediction of COVID-19 mRNA vaccine degradation using deep learning
Muneer, A., Fati, S. M., Akbar, N. A., Agustriawan, D., & Wahyudi, S. T. (2021) · Journal of King Saud University - Computer and Information Sciences · doi:10.1016/j.jksuci.2021.10.001 · Cited by 35 · see citing works
RNA folding using quantum computers
Fox, D. M., MacDermaid, C. M., Schreij, A. M. A., Zwierzyna, M., & Walker, R. C. (2022) · PLOS Computational Biology · doi:10.1371/journal.pcbi.1010032 · Cited by 33 · see citing works
Bi-objective integer programming for RNA secondary structure prediction with pseudoknots
Legendre, A., Angel, É., & Tahi, F. (2018) · BMC Bioinformatics · doi:10.1186/s12859-018-2007-7 · Cited by 33 · see citing works
Ward, M., Datta, A., Wise, M. J., & Mathews, D. H. (2017) · Nucleic Acids Research · doi:10.1093/nar/gkx512 · Cited by 32 · see citing works
Prediction of RNA Secondary Structure Including Kissing Hairpin Motifs
Theis, C., Janssen, S., & Giegerich, R. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-15294-8_5 · Cited by 32 · see citing works
Novel and Efficient RNA Secondary Structure Prediction Using Hierarchical Folding
Jabbari, H., Condon, A., & Zhao, S. (2008) · Journal of Computational Biology · doi:10.1089/cmb.2007.0198 · Cited by 32 · see citing works
Predicting RNA secondary structure by free energy minimization
Mathews, D. H. (2005) · Theoretical Chemistry Accounts · doi:10.1007/s00214-005-0027-7 · Cited by 33 · see citing works
Parsing Nucleic Acid Pseudoknotted Secondary Structure: Algorithm and Applications
Rastegari, B., & Condon, A. (2007) · Journal of Computational Biology · doi:10.1089/cmb.2006.0108 · Cited by 32 · see citing works
Deschenes, A., & Wiese, K. C. (2004) · IEEE Congress on Evolutionary Computation (CEC) · doi:10.1109/cec.2004.1330912 · Cited by 32 · see citing works
Complete RNA inverse folding: computational design of functional hammerhead ribozymesPreprint
Dotú, I., García-Martín, J. A., Slinger, B. L., Mechery, V., Meyer, M. M., & Clote, P. (2014) · Cited by 32 · see citing works
KnotSeeker: Heuristic pseudoknot detection in long RNA sequences
Sperschneider, J., & Datta, A. (2008) · RNA · doi:10.1261/rna.968808 · Cited by 31 · see citing works
Lu, W., Tang, Y., Wu, H., Huang, H., Fu, Q., Qiu, J., & Li, H. (2019) · BMC Bioinformatics · doi:10.1186/s12859-019-3258-7 · Cited by 30 · see citing works
ILM: a web server for predicting RNA secondary structures with pseudoknots
Ruan, J., Stormo, G. D., & Zhang, W. (2004) · Nucleic Acids Research · doi:10.1093/nar/gkh444 · Cited by 30 · see citing works
Approximating the 2-Interval Pattern Problem
Maxime Crochemore, A., Hermelin, D., Landau, G. M., & Vialette, S. (2005) · Lecture notes in computer science · doi:10.1007/11561071_39 · Cited by 28 · see citing works
Gong, T., Ju, F., & Bu, D. (2024) · Communications Biology · doi:10.1038/s42003-024-05952-w · Cited by 27 · see citing works
Computational analysis of RNA structures with chemical probing data
Ge, P., & Zhang, S. (2015) · Methods · doi:10.1016/j.ymeth.2015.02.003 · Cited by 26 · see citing works
Risk Factors of Venous Thromboembolism in Indian Patients with Pelvic-Acetabular Trauma
Sen, R. K., Kumar, A., Tripathy, S. K., Aggarwal, S., & Khandelwal, N. (2011) · Journal of orthopaedic surgery · doi:10.1177/230949901101900105 · Cited by 25 · see citing works
Al-Khatib, R. M., Rashid, N. A. A., & Abdullah, R. (2011) · Journal of Biomolecular Structure and Dynamics · doi:10.1080/07391102.2011.10507373 · Cited by 24 · see citing works
Random k -noncrossing RNA structures
Chen, W. Y. C., Han, H. S. W., & Reidys, C. M. (2009) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0907269106 · Cited by 24 · see citing works
Approximating the 2-interval pattern problem
Maxime Crochemore, A., Hermelin, D., Landau, G. M., Rawitz, D., & Vialette, S. (2008) · Theoretical Computer Science · doi:10.1016/j.tcs.2008.01.007 · Cited by 24 · see citing works
- 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 › Computer Science › Artificial Intelligence › Algorithms and Data Compression
- Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › 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