{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,27]],"date-time":"2026-02-27T06:16:30Z","timestamp":1772172990127,"version":"3.50.1"},"update-to":[{"DOI":"10.1371\/journal.pcbi.1010032","type":"new_version","label":"New version","source":"publisher","updated":{"date-parts":[[2022,4,21]],"date-time":"2022-04-21T00:00:00Z","timestamp":1650499200000}}],"reference-count":55,"publisher":"Public Library of Science (PLoS)","issue":"4","license":[{"start":{"date-parts":[[2022,4,11]],"date-time":"2022-04-11T00:00:00Z","timestamp":1649635200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["www.ploscompbiol.org"],"crossmark-restriction":false},"short-container-title":["PLoS Comput Biol"],"abstract":"<jats:p>The 3-dimensional fold of an RNA molecule is largely determined by patterns of intramolecular hydrogen bonds between bases. Predicting the base pairing network from the sequence, also referred to as RNA secondary structure prediction or RNA folding, is a nondeterministic polynomial-time (NP)-complete computational problem. The structure of the molecule is strongly predictive of its functions and biochemical properties, and therefore the ability to accurately predict the structure is a crucial tool for biochemists. Many methods have been proposed to efficiently sample possible secondary structure patterns. Classic approaches employ dynamic programming, and recent studies have explored approaches inspired by evolutionary and machine learning algorithms. This work demonstrates leveraging quantum computing hardware to predict the secondary structure of RNA. A Hamiltonian written in the form of a Binary Quadratic Model (BQM) is derived to drive the system toward maximizing the number of consecutive base pairs while jointly maximizing the average length of the stems. A Quantum Annealer (QA) is compared to a Replica Exchange Monte Carlo (REMC) algorithm programmed with the same objective function, with the QA being shown to be highly competitive at rapidly identifying low energy solutions. The method proposed in this study was compared to three algorithms from literature and, despite its simplicity, was found to be competitive on a test set containing known structures with pseudoknots.<\/jats:p>","DOI":"10.1371\/journal.pcbi.1010032","type":"journal-article","created":{"date-parts":[[2022,4,11]],"date-time":"2022-04-11T13:38:12Z","timestamp":1649684292000},"page":"e1010032","update-policy":"https:\/\/doi.org\/10.1371\/journal.pcbi.corrections_policy","source":"Crossref","is-referenced-by-count":30,"title":["RNA folding using quantum computers"],"prefix":"10.1371","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4594-4219","authenticated-orcid":true,"given":"Dillion M.","family":"Fox","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2376-8867","authenticated-orcid":true,"given":"Christopher M.","family":"MacDermaid","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8940-2855","authenticated-orcid":true,"given":"Andrea M. A.","family":"Schreij","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7445-6030","authenticated-orcid":true,"given":"Magdalena","family":"Zwierzyna","sequence":"additional","affiliation":[]},{"given":"Ross C.","family":"Walker","sequence":"additional","affiliation":[]}],"member":"340","published-online":{"date-parts":[[2022,4,11]]},"reference":[{"key":"pcbi.1010032.ref001","volume-title":"The Cell: A Molecular Approach","author":"GM Cooper","year":"2000","edition":"2"},{"key":"pcbi.1010032.ref002","doi-asserted-by":"crossref","first-page":"1787","DOI":"10.1126\/science.1155472","article-title":"The eukaryotic genome as an RNA machine","volume":"319","author":"PP Amaral","year":"2008","journal-title":"Science"},{"key":"pcbi.1010032.ref003","doi-asserted-by":"crossref","first-page":"776","DOI":"10.1038\/nrg2172","article-title":"Ribozymes, riboswitches and beyond: Regulation of gene expression without proteins","volume":"8","author":"A Serganov","year":"2007","journal-title":"Nature Reviews Genetics"},{"key":"pcbi.1010032.ref004","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1038\/s41467-020-18577-4","article-title":"A possible universal role for mRNA secondary structure in bacterial translation revealed using a synthetic operon","volume":"11","author":"Y Chemla","year":"2020","journal-title":"Nature Communications"},{"key":"pcbi.1010032.ref005","doi-asserted-by":"crossref","first-page":"3022","DOI":"10.1093\/nar\/gkv199","article-title":"Trade-offs between tRNA abundance and mRNA secondary structure support smoothing of translation elongation rate","volume":"43","author":"TE Gorochowski","year":"2015","journal-title":"Nucleic Acids Research"},{"key":"pcbi.1010032.ref006","doi-asserted-by":"crossref","first-page":"1005","DOI":"10.1038\/nbt.4238","article-title":"Evaluation of 244,000 synthetic sequences reveals design principles to optimize translation in escherichia coli","volume":"36","author":"G Cambray","year":"2018","journal-title":"Nature Biotechnology"},{"key":"pcbi.1010032.ref007","doi-asserted-by":"crossref","DOI":"10.1093\/nar\/gkt290","article-title":"RNAstructure: Web servers for RNA secondary structure prediction and analysis","volume":"41","author":"S Bellaousov","year":"2013","journal-title":"Nucleic acids research"},{"key":"pcbi.1010032.ref008","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1093\/bioinformatics\/btm223","article-title":"Efficient parameter estimation for RNA secondary structure prediction","volume":"23","author":"M Andronescu","year":"2007","journal-title":"Bioinformatics"},{"key":"pcbi.1010032.ref009","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":"M Zuker","year":"1981","journal-title":"Nucleic Acids Research"},{"key":"pcbi.1010032.ref010","doi-asserted-by":"crossref","first-page":"706","DOI":"10.1038\/s41586-019-1923-7","article-title":"Improved protein structure prediction using potentials from deep learning","volume":"577","author":"AW Senior","year":"2020","journal-title":"Nature"},{"key":"pcbi.1010032.ref011","doi-asserted-by":"crossref","DOI":"10.1038\/s41467-019-13395-9","article-title":"RNA secondary structure prediction using an ensemble of two-dimensional deep neural networks and transfer learning","volume":"10","author":"J Singh","year":"2019","journal-title":"Nature Communications"},{"key":"pcbi.1010032.ref012","first-page":"1","article-title":"A new method of RNA secondary structure prediction based on convolutional neural network and dynamic programming","volume":"10","author":"H Zhang","year":"2019","journal-title":"Frontiers in Genetics"},{"key":"pcbi.1010032.ref013","first-page":"1","article-title":"Predicting RNA secondary structure via adaptive deep recurrent neural networks with energy-based filter","volume":"20","author":"W Lu","year":"2019","journal-title":"BMC Bioinformatics"},{"key":"pcbi.1010032.ref014","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/j.jbiotec.2017.07.007","article-title":"Recent advances in RNA folding","volume":"261","author":"J Fallmann","year":"2017","journal-title":"Journal of Biotechnology"},{"key":"pcbi.1010032.ref015","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1137\/17M112720X","article-title":"Truly subcubic algorithms for language edit distance and RNA folding via fast bounded-difference min-plus product","volume":"48","author":"K Bringmann","year":"2019","journal-title":"SIAM Journal on Computing"},{"key":"pcbi.1010032.ref016","doi-asserted-by":"crossref","first-page":"i295","DOI":"10.1093\/bioinformatics\/btz375","article-title":"LinearFold: Linear-time approximate RNA folding by 5\u2019-to-3\u2019 dynamic programming and beam search","volume":"35","author":"L Huang","year":"2019","journal-title":"Bioinformatics"},{"key":"pcbi.1010032.ref017","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1089\/106652700750050862","article-title":"RNA pseudoknot prediction in energy-based models","volume":"7","author":"RB Lyngs\u00f8","year":"2000","journal-title":"Journal of Computational Biology"},{"key":"pcbi.1010032.ref018","article-title":"Messenger RNA encoding the full-length SARS-CoV-2 spike glycoprotein","year":"2020","journal-title":"WHO MedNet"},{"key":"pcbi.1010032.ref019","doi-asserted-by":"crossref","DOI":"10.1051\/0004-6361\/201629543","article-title":"Planck 2015 results","volume":"594","author":"J Alves","year":"2016","journal-title":"Astronomy and Astrophysics"},{"key":"pcbi.1010032.ref020","doi-asserted-by":"crossref","first-page":"3429","DOI":"10.1093\/nar\/gkg599","article-title":"Vienna RNA secondary structure server","volume":"31","author":"IL Hofacker","year":"2003","journal-title":"Nucleic Acids Research"},{"key":"pcbi.1010032.ref021","doi-asserted-by":"crossref","first-page":"526","DOI":"10.1016\/j.jmb.2006.01.067","article-title":"Revolutions in RNA Secondary Structure Prediction","volume":"359","author":"DH Mathews","year":"2006","journal-title":"Journal of Molecular Biology"},{"key":"pcbi.1010032.ref022","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":"B Knudsen","year":"2003","journal-title":"Nucleic Acids Research"},{"key":"pcbi.1010032.ref023","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/1748-7188-9-17","article-title":"RNA-RNA interaction prediction using genetic algorithm","volume":"9","author":"S Montaseri","year":"2014","journal-title":"Algorithms for Molecular Biology"},{"key":"pcbi.1010032.ref024","first-page":"1","article-title":"An efficient simulated annealing algorithm for the RNA secondary structure prediction with Pseudoknots","volume":"20","author":"Z Kai","year":"2019","journal-title":"BMC Genomics"},{"key":"pcbi.1010032.ref025","doi-asserted-by":"crossref","first-page":"1460","DOI":"10.1126\/science.abe8770","article-title":"Quantum computational advantage using photons","volume":"1463","author":"H-S Zhong","year":"2020","journal-title":"Science"},{"key":"pcbi.1010032.ref026","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1038\/s41586-019-1666-5","article-title":"Quantum supremacy using a programmable superconducting processor","volume":"574","author":"F Arute","year":"2019","journal-title":"Nature"},{"key":"pcbi.1010032.ref027","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1140\/epjqt\/s40507-021-00091-1","article-title":"Commercial applications of quantum computing.","volume":"8","author":"F Bova","year":"2021","journal-title":"EPJ Quantum Technology"},{"key":"pcbi.1010032.ref028","doi-asserted-by":"crossref","first-page":"1","DOI":"10.3389\/fchem.2020.587143","article-title":"Application of Quantum Computing to Biochemical Systems: A Look to the Future","volume":"8","author":"HP Cheng","year":"2020","journal-title":"Frontiers in Chemistry"},{"key":"pcbi.1010032.ref029","first-page":"1","article-title":"How will quantum computers provide an industrially relevant computational advantage in quantum chemistry?","author":"VE Elfving","year":"2020","journal-title":"arXiv"},{"key":"pcbi.1010032.ref030","doi-asserted-by":"crossref","first-page":"5388","DOI":"10.1039\/b804804e","article-title":"Quantum algorithm for obtaining the energy spectrum of molecular systems","volume":"10","author":"H Wang","year":"2008","journal-title":"Physical Chemistry Chemical Physics"},{"key":"pcbi.1010032.ref031","doi-asserted-by":"crossref","first-page":"1704","DOI":"10.1126\/science.1113479","article-title":"Chemistry: Simulated quantum computation of molecular energies","volume":"309","author":"A Aspuru-Guzik","year":"2005","journal-title":"Science"},{"key":"pcbi.1010032.ref032","doi-asserted-by":"crossref","first-page":"10856","DOI":"10.1021\/acs.chemrev.8b00803","article-title":"Quantum Chemistry in the Age of Quantum Computing","volume":"119","author":"Y Cao","year":"2019","journal-title":"Chemical Reviews"},{"key":"pcbi.1010032.ref033","doi-asserted-by":"crossref","first-page":"18681","DOI":"10.1073\/pnas.0808245105","article-title":"Polynomial-time quantum algorithm for the simulation of chemical dynamics","volume":"105","author":"I Kassal","year":"2008","journal-title":"Proceedings of the National Academy of Sciences of the United States of America"},{"key":"pcbi.1010032.ref034","doi-asserted-by":"crossref","first-page":"4764","DOI":"10.1021\/acs.jctc.9b00236","article-title":"Accuracy and Resource Estimations for Quantum Chemistry on a Near-Term Quantum Computer","volume":"15","author":"M K\u00fchn","year":"2019","journal-title":"Journal of Chemical Theory and Computation"},{"key":"pcbi.1010032.ref035","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1103\/PhysRevX.6.031010","article-title":"Tunneling and speedup in quantum optimization for permutation-symmetric problems","volume":"6","author":"S Muthukrishnan","year":"2016","journal-title":"Physical Review X"},{"key":"pcbi.1010032.ref036","first-page":"1","article-title":"Efficient combinatorial optimization using quantum annealing","author":"H Djidjev","year":"2018","journal-title":"arXiv"},{"key":"pcbi.1010032.ref037","article-title":"mRNA codon optimization on quantum computers","author":"DM Fox","year":"2021","journal-title":"bioRxiv."},{"key":"pcbi.1010032.ref038","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1093\/nar\/28.1.201","article-title":"PseudoBase: A database with RNA pseudoknots","volume":"28","author":"FHD Van Batenburg","year":"2000","journal-title":"Nucleic Acids Research"},{"key":"pcbi.1010032.ref039","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":"FHD Van Batenburg","year":"2001","journal-title":"Nucleic Acids Research"},{"key":"pcbi.1010032.ref040","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1093\/nar\/gkn806","article-title":"PseudoBase++: An extension of PseudoBase for easy searching, formatting and visualization of pseudoknots","volume":"37","author":"M Taufer","year":"2009","journal-title":"Nucleic Acids Research"},{"key":"pcbi.1010032.ref041","doi-asserted-by":"crossref","first-page":"1870","DOI":"10.1261\/rna.2125310","article-title":"ProbKnot: Fast prediction of RNA secondary structure including pseudoknots","volume":"16","author":"S Bellaousov","year":"2010","journal-title":"Rna"},{"key":"pcbi.1010032.ref042","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/1748-7188-6-26","article-title":"ViennaRNA Package 2.0","volume":"6","author":"R Lorenz","year":"2011","journal-title":"Algorithms for Molecular Biology"},{"key":"pcbi.1010032.ref043","article-title":"Quantum Computing With Particles Of Light: A $215 Million Gamble","author":"P. Smith-Goodson","year":"2020","journal-title":"Forbes"},{"key":"pcbi.1010032.ref044","doi-asserted-by":"crossref","first-page":"3497","DOI":"10.1093\/nar\/gkf481","article-title":"The non-Watson-Crick base pairs and their associated isostericity matrices","author":"NB Leontis","year":"2002","journal-title":"Nucleic Acids Research"},{"key":"pcbi.1010032.ref045","doi-asserted-by":"crossref","first-page":"942","DOI":"10.1261\/rna.1919010","article-title":"On the role of Hoogsteen:Hoogsteen interactions in RNA: Ab initio investigations of structures and energies","volume":"16","author":"S Purshotam","year":"2010","journal-title":"RNA"},{"key":"pcbi.1010032.ref046","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1038\/s41586-020-2649-2","article-title":"Array programming with {NumPy}","volume":"585","author":"CR Harris","year":"2020","journal-title":"Nature"},{"key":"pcbi.1010032.ref047","article-title":"Pegasus: The second connectivity graph for large-scale quantum annealing hardware","author":"N Dattani","year":"2019","journal-title":"arXiv"},{"key":"pcbi.1010032.ref048","doi-asserted-by":"crossref","first-page":"909","DOI":"10.1080\/01621459.1995.10476590","article-title":"Annealing Markov Chain Monte Carlo with Applications to Ancestral Inference","volume":"90","author":"CJ Geyer","year":"1995","journal-title":"Journal of the American Statistical Association"},{"key":"pcbi.1010032.ref049","doi-asserted-by":"crossref","first-page":"1604","DOI":"10.1143\/JPSJ.65.1604","article-title":"Exchange Monte Carlo Method and Application to Spin Glass Simulations","volume":"65","author":"H Koji","year":"1996","journal-title":"Journal of the Physical Society of Japan"},{"key":"pcbi.1010032.ref050","doi-asserted-by":"crossref","first-page":"2607","DOI":"10.1103\/PhysRevLett.57.2607","article-title":"Replica Monte Carlo Simulation of Spin-Glasses","volume":"57","author":"RH Swendsen","year":"1986","journal-title":"Physical Review Letters"},{"key":"pcbi.1010032.ref051","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1093\/biomet\/57.1.97","article-title":"Monte Carlo sampling methods using Markov chains and their applications","volume":"57","author":"WK Hastings","year":"1970","journal-title":"Biometrika"},{"key":"pcbi.1010032.ref052","doi-asserted-by":"crossref","first-page":"6911","DOI":"10.1063\/1.1507776","article-title":"On the acceptance probability of replica-exchange Monte Carlo trials","volume":"117","author":"DA Kofke","year":"2002","journal-title":"The Journal of Chemical Physics"},{"key":"pcbi.1010032.ref053","doi-asserted-by":"crossref","first-page":"1108","DOI":"10.1016\/j.jpdc.2005.03.010","article-title":"MPI for Python","volume":"65","author":"L Dalc\u00edn","year":"2005","journal-title":"Journal of Parallel and Distributed Computing"},{"key":"pcbi.1010032.ref054","doi-asserted-by":"crossref","first-page":"1124","DOI":"10.1016\/j.advwatres.2011.04.013","article-title":"Parallel distributed computing using Python","volume":"34","author":"LD Dalcin","year":"2011","journal-title":"Advances in Water Resources"},{"key":"pcbi.1010032.ref055","doi-asserted-by":"crossref","first-page":"655","DOI":"10.1016\/j.jpdc.2007.09.005","article-title":"MPI for Python: Performance improvements and MPI-2 extensions","volume":"68","author":"L Dalc\u00edn","year":"2008","journal-title":"Journal of Parallel and Distributed Computing"}],"updated-by":[{"DOI":"10.1371\/journal.pcbi.1010032","type":"new_version","label":"New version","source":"publisher","updated":{"date-parts":[[2022,4,21]],"date-time":"2022-04-21T00:00:00Z","timestamp":1650499200000}}],"container-title":["PLOS Computational Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dx.plos.org\/10.1371\/journal.pcbi.1010032","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,21]],"date-time":"2022-04-21T13:44:32Z","timestamp":1650548672000},"score":1,"resource":{"primary":{"URL":"https:\/\/dx.plos.org\/10.1371\/journal.pcbi.1010032"}},"subtitle":[],"editor":[{"given":"Shi-Jie","family":"Chen","sequence":"first","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2022,4,11]]},"references-count":55,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2022,4,11]]}},"URL":"https:\/\/doi.org\/10.1371\/journal.pcbi.1010032","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/2021.05.27.446060","asserted-by":"object"}]},"ISSN":["1553-7358"],"issn-type":[{"value":"1553-7358","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,4,11]]}}}