{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T01:17:09Z","timestamp":1773278229435,"version":"3.50.1"},"reference-count":62,"publisher":"Oxford University Press (OUP)","issue":"12","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":2315,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/2.0\/uk\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010,6,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Thermodynamics-based dynamic programming RNA secondary structure algorithms have been of immense importance in molecular biology, where applications range from the detection of novel selenoproteins using expressed sequence tag (EST) data, to the determination of microRNA genes and their targets. Dynamic programming algorithms have been developed to compute the minimum free energy secondary structure and partition function of a given RNA sequence, the minimum free-energy and partition function for the hybridization of two RNA molecules, etc. However, the applicability of dynamic programming methods depends on disallowing certain types of interactions (pseudoknots, zig-zags, etc.), as their inclusion renders structure prediction an nondeterministic polynomial time (NP)-complete problem. Nevertheless, such interactions have been observed in X-ray structures.<\/jats:p>\n               <jats:p>Results: A non-Boltzmannian Monte Carlo algorithm was designed by Wang and Landau to estimate the density of states for complex systems, such as the Ising model, that exhibit a phase transition. In this article, we apply the Wang-Landau (WL) method to compute the density of states for secondary structures of a given RNA sequence, and for hybridizations of two RNA sequences. Our method is shown to be much faster than existent software, such as RNAsubopt. From density of states, we compute the partition function over all secondary structures and over all pseudoknot-free hybridizations. The advantage of the WL method is that by adding a function to evaluate the free energy of arbitary pseudoknotted structures and of arbitrary hybridizations, we can estimate thermodynamic parameters for situations known to be NP-complete. This extension to pseudoknots will be made in the sequel to this article; in contrast, the current article describes the WL algorithm applied to pseudoknot-free secondary structures and hybridizations.<\/jats:p>\n               <jats:p>Availability: The WL RNA hybridization web server is under construction at http:\/\/bioinformatics.bc.edu\/clotelab\/.<\/jats:p>\n               <jats:p>Contact: \u00a0clote@bc.edu<\/jats:p>","DOI":"10.1093\/bioinformatics\/btq218","type":"journal-article","created":{"date-parts":[[2010,6,7]],"date-time":"2010-06-07T07:28:13Z","timestamp":1275895693000},"page":"i278-i286","source":"Crossref","is-referenced-by-count":10,"title":["Thermodynamics of RNA structures by Wang\u2013Landau sampling"],"prefix":"10.1093","volume":"26","author":[{"given":"Feng","family":"Lou","sequence":"first","affiliation":[{"name":"1 Laboratoire de Recherche en Informatique (LRI), Universit\u00e9 Paris-Sud XI, b\u00e2t. 490, 91405 Orsay cedex, France, 2 Department of Biology, Boston College, Chestnut Hill, MA 02467, USA and 3 Digiteo Chair, Laboratoire d'Informatique (LIX), Ecole Polytechnique, 91128 Palaiseau, France"}]},{"given":"Peter","family":"Clote","sequence":"additional","affiliation":[{"name":"1 Laboratoire de Recherche en Informatique (LRI), Universit\u00e9 Paris-Sud XI, b\u00e2t. 490, 91405 Orsay cedex, France, 2 Department of Biology, Boston College, Chestnut Hill, MA 02467, USA and 3 Digiteo Chair, Laboratoire d'Informatique (LIX), Ecole Polytechnique, 91128 Palaiseau, France"},{"name":"1 Laboratoire de Recherche en Informatique (LRI), Universit\u00e9 Paris-Sud XI, b\u00e2t. 490, 91405 Orsay cedex, France, 2 Department of Biology, Boston College, Chestnut Hill, MA 02467, USA and 3 Digiteo Chair, Laboratoire d'Informatique (LIX), Ecole Polytechnique, 91128 Palaiseau, France"},{"name":"1 Laboratoire de Recherche en Informatique (LRI), Universit\u00e9 Paris-Sud XI, b\u00e2t. 490, 91405 Orsay cedex, France, 2 Department of Biology, Boston College, Chestnut Hill, MA 02467, USA and 3 Digiteo Chair, Laboratoire d'Informatique (LIX), Ecole Polytechnique, 91128 Palaiseau, France"}]}],"member":"286","published-online":{"date-parts":[[2010,6,1]]},"reference":[{"key":"2023012508042840200_B1","doi-asserted-by":"crossref","first-page":"3035","DOI":"10.1093\/nar\/18.10.3035","article-title":"Prediction of RNA secondary structure, including pseudoknotting, by computer simulation","volume":"18","author":"Abrahams","year":"1990","journal-title":"Nucleic Acids Res."},{"key":"2023012508042840200_B2","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1021\/bi00052a021","article-title":"Thermal unfolding of a group I ribozyme: The low-temperature transition is primarily disruption of tertiary structure","volume":"32","author":"Banerjee","year":"1993","journal-title":"Biochemistry"},{"key":"2023012508042840200_B3","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1093\/bioinformatics\/btf868","article-title":"Towards a computational model for \u22121 eukaryotic frameshifting sites","volume":"19","author":"Bekaert","year":"2003","journal-title":"Bioinformatics"},{"key":"2023012508042840200_B4","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1186\/1748-7188-1-3","article-title":"Partition function and base pairing probabilities of RNA heterodimers","volume":"1","author":"Bernhart","year":"2006","journal-title":"Algorithms. Mol. Biol."},{"key":"2023012508042840200_B5","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1016\/0968-0004(91)90180-4","article-title":"Selenoprotein synthesis: An expansion of the genetic code","volume":"16","author":"B\u00f6ck","year":"1991","journal-title":"Trends Biochem. Sci."},{"key":"2023012508042840200_B6","volume-title":"Pr\u00e9diction de structures secondaires d'ARN avec pseudo-noeuds. PhD thesis, Ecole Polytechnique, 2009.","author":"Bon","year":"2009"},{"key":"2023012508042840200_B7","doi-asserted-by":"crossref","first-page":"1868","DOI":"10.1126\/science.1113801","article-title":"Toward high-resolution de novo structure prediction for small proteins","volume":"309","author":"Bradley","year":"2005","journal-title":"Science"},{"key":"2023012508042840200_B8","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1038\/nature05769","article-title":"Control of alternative RNA splicing and gene expression by eukaryotic riboswitches","volume":"447","author":"Cheah","year":"2007","journal-title":"Nature"},{"key":"2023012508042840200_B9","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1142\/S0219720006001965","article-title":"Structure prediction of helical transmembrane proteins at two length scales","volume":"4","author":"Chen","year":"2006","journal-title":"J. Bioinform. Comput. Biol."},{"key":"2023012508042840200_B10","doi-asserted-by":"crossref","first-page":"i365","DOI":"10.1093\/bioinformatics\/btp212","article-title":"A partition function algorithm for interacting nucleic acid strands","volume":"25","author":"Chitsaz","year":"2009","journal-title":"Bioinformatics"},{"key":"2023012508042840200_B11","doi-asserted-by":"crossref","first-page":"17349","DOI":"10.1073\/pnas.0906625106","article-title":"Assembly mechanisms of RNA pseudoknots are determined by the stabilities of constituent secondary structures","volume":"106","author":"Cho","year":"2009","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012508042840200_B12","doi-asserted-by":"crossref","first-page":"47915","DOI":"10.1074\/jbc.M306874200","article-title":"Temperature-controlled structural alterations of an RNA thermometer","volume":"278","author":"Chowdhury","year":"2003","journal-title":"J. Biol. Chem."},{"key":"2023012508042840200_B13","first-page":"279","volume-title":"Computational Molecular Biology: An Introduction.","author":"Clote","year":"2000"},{"key":"2023012508042840200_B14","doi-asserted-by":"crossref","first-page":"869","DOI":"10.1142\/S0219720009004333","article-title":"Asymptotics of canonical and saturated RNA secondary structures","volume":"7","author":"Clote","year":"2009","journal-title":"J. Bioinform. Comput. Biol."},{"key":"2023012508042840200_B15","first-page":"184","article-title":"Dynamic programming algorithm for the density of states of RNA secondary structures","volume-title":"Computer Science and Biology 96 (Prooceedings of the German Conference on Bioinformatics)","author":"Cupal","year":"1996"},{"key":"2023012508042840200_B16","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1142\/S0219720006001904","article-title":"RNAKinetics: a web server that models secondary structure kinetics of an elongating RNA","volume":"4","author":"Danilova","year":"2006","journal-title":"J. Bioinform. Comput. Biol."},{"key":"2023012508042840200_B17","doi-asserted-by":"crossref","first-page":"14664","DOI":"10.1073\/pnas.0703836104","article-title":"Automated de novo prediction of native-like RNA tertiary structures","volume":"104","author":"Das","year":"2007","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012508042840200_B18","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1529\/biophysj.103.020743","article-title":"Prediction of hybridization and melting for double-stranded nucleic acids","volume":"87","author":"Dimitrov","year":"2004","journal-title":"Biophys. J."},{"key":"2023012508042840200_B19","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1137\/060651100","article-title":"Thermodynamic analysis of interacting nucleic acid strands","volume":"49","author":"Dirks","year":"2007","journal-title":"SIAM Rev"},{"key":"2023012508042840200_B20","doi-asserted-by":"crossref","first-page":"1664","DOI":"10.1002\/jcc.10296","article-title":"A partition function algorithm for nucleic acid secondary structure including pseudoknots","volume":"24","author":"Dirks","year":"2003","journal-title":"J. Comput. Chem."},{"key":"2023012508042840200_B21","doi-asserted-by":"crossref","first-page":"1457","DOI":"10.1038\/nbt1104-1457","article-title":"How do RNA folding algorithms work?","volume":"22","author":"Eddy","year":"2004","journal-title":"Nat. Biotechnol."},{"key":"2023012508042840200_B22","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1017\/S1355838200992161","article-title":"RNA folding at elementary step resolution","volume":"6","author":"Flamm","year":"2000","journal-title":"RNA"},{"key":"2023012508042840200_B23","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1017\/S1355838201000863","article-title":"Design of multistable RNA molecules","volume":"7","author":"Flamm","year":"2001","journal-title":"RNA."},{"key":"2023012508042840200_B24","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1093\/nar\/gkg006","article-title":"Rfam: an RNA family database","volume":"31","author":"Griffiths-Jones","year":"2003","journal-title":"Nucleic Acids Res."},{"key":"2023012508042840200_B25","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/BF00818163","article-title":"Fast folding and comparison of RNA secondary structures","volume":"125","author":"Hofacker","year":"1994","journal-title":"Monatsh. Chem."},{"key":"2023012508042840200_B26","doi-asserted-by":"crossref","first-page":"3429","DOI":"10.1093\/nar\/gkg599","article-title":"Vienna RNA secondary structure server","volume":"31","author":"Hofacker","year":"2003","journal-title":"Nucleic Acids Res."},{"key":"2023012508042840200_B27","doi-asserted-by":"crossref","first-page":"6515","DOI":"10.1073\/pnas.110533697","article-title":"Modeling RNA folding paths with pseudoknots: application to hepatitis delta virus ribozyme","volume":"97","author":"Isambert","year":"2000","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012508042840200_B28","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1126\/science.220.4598.671","article-title":"Optimization by simulated annealing","volume":"220","author":"Kirkpatrick","year":"1983","journal-title":"Science"},{"key":"2023012508042840200_B29","doi-asserted-by":"crossref","first-page":"3423","DOI":"10.1093\/nar\/gkg614","article-title":"Pfold: RNA secondary structure prediction using stochastic context-free grammars","volume":"31","author":"Knudsen","year":"2003","journal-title":"Nucleic Acids Res."},{"key":"2023012508042840200_B30","doi-asserted-by":"crossref","first-page":"1581","DOI":"10.1214\/009053606000000515","article-title":"Equi-energy sampler with applications in statistical inference and statistical mechanics","volume":"34","author":"Kou","year":"2006","journal-title":"Ann. Stat."},{"key":"2023012508042840200_B31","doi-asserted-by":"crossref","first-page":"244903","DOI":"10.1063\/1.2208607","article-title":"A study of density of states and ground states in hydrophobic-hydrophilic protein folding models by equi-energy sampling","volume":"124","author":"Kou","year":"2006","journal-title":"J. Chem. Phys."},{"key":"2023012508042840200_B32","first-page":"222","article-title":"An optimized parsing algorithm well-suited to rna folding. In AAAI press, editor","volume-title":"Proceedings of the Third International Conference on Intelligent Systems for Molecular Biology","author":"Lefebvre","year":"1995"},{"key":"2023012508042840200_B33","doi-asserted-by":"crossref","first-page":"1540","DOI":"10.1126\/science.1080372","article-title":"Vertebrate microRNA genes","volume":"299","author":"Lim","year":"2003","journal-title":"Science"},{"key":"2023012508042840200_B34","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1089\/106652700750050862","article-title":"RNA pseudoknot prediction in energy-based models","volume":"7","author":"Lyngso","year":"2000","journal-title":"J. Comput. Biol."},{"key":"2023012508042840200_B35","doi-asserted-by":"crossref","first-page":"577","DOI":"10.1016\/S0092-8674(03)00391-X","article-title":"Riboswitches control fundamental biochemical pathways in Bacillus subtilis and other bacteria","volume":"113","author":"Mandal","year":"2003","journal-title":"Cell"},{"key":"2023012508042840200_B36","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/978-1-60327-429-6_1","article-title":"UNAFold: software for nucleic acid folding and hybridization","volume":"453","author":"Markham","year":"2008","journal-title":"Methods Mol. Biol."},{"key":"2023012508042840200_B37","volume-title":"Algorithms and software for nucleic acid sequences","author":"Markham","year":"2006"},{"key":"2023012508042840200_B38","doi-asserted-by":"crossref","first-page":"7287","DOI":"10.1073\/pnas.0401799101","article-title":"Incorporating chemical modification constraints into a dynamic programming algorithm for prediction of RNA secondary structure","volume":"101","author":"Mathews","year":"2004","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012508042840200_B39","doi-asserted-by":"crossref","first-page":"1087","DOI":"10.1063\/1.1699114","article-title":"Equation of state calculations by fast computing machines","volume":"21","author":"Metropolis","year":"1953","journal-title":"J. Chem. Phys."},{"key":"2023012508042840200_B40","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/s00285-007-0106-6","article-title":"Predicting RNA secondary structures with pseudoknots by MCMC sampling","volume":"56","author":"Metzler","year":"2008","journal-title":"J. Math. Biol."},{"key":"2023012508042840200_B41","doi-asserted-by":"crossref","first-page":"1177","DOI":"10.1093\/bioinformatics\/btl024","article-title":"Thermodynamics of RNA-RNA binding","volume":"22","author":"M\u00fcckstein","year":"2006","journal-title":"Bioinformatics"},{"key":"2023012508042840200_B42","doi-asserted-by":"crossref","first-page":"1335","DOI":"10.1093\/bioinformatics\/btp157","article-title":"Infernal 1.0: inference of RNA alignments","volume":"25","author":"Nawrocki","year":"2009","journal-title":"Bioinformatics"},{"key":"2023012508042840200_B43","doi-asserted-by":"crossref","first-page":"6309","DOI":"10.1073\/pnas.77.11.6309","article-title":"Fast algorithm for predicting the secondary structure of single stranded RNA","volume":"77","author":"Nussinov","year":"1980","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012508042840200_B44","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1126\/science.288.5465.517","article-title":"Homologues of small nucleolar RNAs in Archaea","volume":"288","author":"Omer","year":"2000","journal-title":"Science"},{"key":"2023012508042840200_B45","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1006\/jmbi.1997.1595","article-title":"Fold assembly of small proteins using Monte Carlo simulations driven by restraints derived from multiple sequence alignments","volume":"277","author":"Ortiz","year":"1998","journal-title":"J. Mol. Biol."},{"key":"2023012508042840200_B46","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1186\/1471-2105-5-104","article-title":"Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics","volume":"5","author":"Reeder","year":"2004","journal-title":"BMC. Bioinformatics"},{"key":"2023012508042840200_B47","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/j.sbi.2007.03.012","article-title":"Emerging themes in non-coding RNA quality control","volume":"17","author":"Reinisch","year":"2007","journal-title":"Curr. Opin. Struct. Biol."},{"key":"2023012508042840200_B48","doi-asserted-by":"crossref","first-page":"1494","DOI":"10.1261\/rna.7284905","article-title":"Hotknots: heuristic prediction of RNA secondary structures including pseudoknots","volume":"11","author":"Ren","year":"2005","journal-title":"RNA"},{"key":"2023012508042840200_B49","doi-asserted-by":"crossref","first-page":"2053","DOI":"10.1006\/jmbi.1998.2436","article-title":"A dynamic programming algorithm for RNA structure prediction including pseudoknots","volume":"285","author":"Rivas","year":"1999","journal-title":"J. Mol. Biol."},{"key":"2023012508042840200_B50","doi-asserted-by":"crossref","first-page":"691","DOI":"10.1093\/bioinformatics\/14.8.691","article-title":"An RNA folding method capable of identifying pseudoknots and base triples","volume":"14","author":"Tabaska","year":"1998","journal-title":"Bioinformatics"},{"key":"2023012508042840200_B51","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1016\/j.sbi.2005.05.003","article-title":"Riboswitches as versatile gene control elements","volume":"15","author":"Tucker","year":"2005","journal-title":"Curr. Opin. Struct. Biol."},{"key":"2023012508042840200_B52","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1093\/nar\/29.1.194","article-title":"Pseudobase: structural information on RNA pseudoknots","volume":"29","author":"Van Batenburg","year":"2001","journal-title":"Nucleic Acids Res."},{"key":"2023012508042840200_B53","doi-asserted-by":"crossref","first-page":"056101(1)","DOI":"10.1103\/PhysRevE.64.056101","article-title":"Determining the density of states for classical statistical models: a random walk algorithm to produce a flat histogram","volume":"64","author":"Wang","year":"2001","journal-title":"Phys. Rev. E"},{"key":"2023012508042840200_B54","doi-asserted-by":"crossref","first-page":"2050","DOI":"10.1103\/PhysRevLett.86.2050","article-title":"Efficient, multiple-range random walk algorithm to calculate the density of states","volume":"86","author":"Wang","year":"2001","journal-title":"Phys. Rev. Lett."},{"key":"2023012508042840200_B55","doi-asserted-by":"crossref","first-page":"1101","DOI":"10.1038\/nsmb841","article-title":"Substrate-assisted catalysis of peptide bond formation by the ribosome","volume":"11","author":"Weinger","year":"2004","journal-title":"Nat. Struct. Mol. Biol."},{"key":"2023012508042840200_B56","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1109\/TNB.2005.853646","article-title":"JViz.Rna\u2013a Java tool for RNA secondary structure visualization","volume":"4","author":"Wiese","year":"2005","journal-title":"IEEE. Trans. Nanobiosci."},{"key":"2023012508042840200_B57","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1002\/(SICI)1097-0282(199902)49:2<145::AID-BIP4>3.0.CO;2-G","article-title":"Complete suboptimal folding of RNA and the stability of secondary structures","volume":"49","author":"Wuchty","year":"1999","journal-title":"Biopolymers"},{"key":"2023012508042840200_B58","doi-asserted-by":"crossref","first-page":"W605","DOI":"10.1093\/nar\/gki447","article-title":"Kinefold web server for RNA\/DNA folding path and structure prediction including pseudoknots and knots","volume":"33","author":"Xayaphoummine","year":"2005","journal-title":"Nucleic Acids Res."},{"key":"2023012508042840200_B59","doi-asserted-by":"crossref","first-page":"14719","DOI":"10.1021\/bi9809425","article-title":"Thermodynamic parameters for an expanded nearest-neighbor model for formation of RNA duplexes with Watson-Crick base pairs","volume":"37","author":"Xia","year":"1999","journal-title":"Biochemistry"},{"key":"2023012508042840200_B60","doi-asserted-by":"crossref","first-page":"225101","DOI":"10.1063\/1.2736681","article-title":"Biopolymer structure simulation and optimization via fragment regrowth Monte Carlo","volume":"126","author":"Zhang","year":"2007","journal-title":"J. Chem. Phys."},{"key":"2023012508042840200_B61","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1007\/s00285-007-0124-4","article-title":"Rapid ab initio prediction of RNA pseudoknots via graph tree decomposition","volume":"56","author":"Zhao","year":"2008","journal-title":"J. Math. Biol."},{"key":"2023012508042840200_B62","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1093\/nar\/9.1.133","article-title":"Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information","volume":"9","author":"Zuker","year":"1981","journal-title":"Nucleic Acids Res."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/26\/12\/i278\/48856142\/bioinformatics_26_12_i278.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/26\/12\/i278\/48856142\/bioinformatics_26_12_i278.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T08:08:33Z","timestamp":1674634113000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/26\/12\/i278\/286276"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,6,1]]},"references-count":62,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2010,6,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btq218","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2010,6,15]]},"published":{"date-parts":[[2010,6,1]]}}}