{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T21:28:37Z","timestamp":1775338117802,"version":"3.50.1"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,3,6]],"date-time":"2021-03-06T00:00:00Z","timestamp":1614988800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,3,6]],"date-time":"2021-03-06T00:00:00Z","timestamp":1614988800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Heuristics"],"published-print":{"date-parts":[[2021,8]]},"DOI":"10.1007\/s10732-021-09471-3","type":"journal-article","created":{"date-parts":[[2021,3,6]],"date-time":"2021-03-06T16:02:45Z","timestamp":1615046565000},"page":"695-717","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Qfold: a new modeling paradigm for the RNA folding problem"],"prefix":"10.1007","volume":"27","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8506-7380","authenticated-orcid":false,"given":"Mark W.","family":"Lewis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amit","family":"Verma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Todd T.","family":"Eckdahl","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,3,6]]},"reference":[{"issue":"1","key":"9471_CR1","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1186\/1471-2105-9-340","volume":"9","author":"M Andronescu","year":"2008","unstructured":"Andronescu, M., Bereg, V., Hoos, H.H., Condon, A.: RNA STRAND: the RNA secondary structure and statistical analysis database. BMC Bioinform. 9(1), 340 (2008)","journal-title":"BMC Bioinform."},{"issue":"3","key":"9471_CR2","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1287\/opre.36.3.493","volume":"36","author":"F Barahona","year":"1988","unstructured":"Barahona, F., Grotschel, M., Junger, M., Reainelt, G.: An application of combinatorial optimization to statistical physics and circuit layout design. Oper. Res. 36(3), 493\u2013513 (1988)","journal-title":"Oper. Res."},{"issue":"11","key":"9471_CR3","doi-asserted-by":"publisher","first-page":"1069","DOI":"10.1057\/jors.1990.166","volume":"41","author":"JE Beasley","year":"1990","unstructured":"Beasley, J.E.: OR-Library: distributing test problems via electronic mail. J. Oper. Res. Soc. 41(11), 1069\u20131072 (1990)","journal-title":"J. Oper. Res. Soc."},{"issue":"1","key":"9471_CR4","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1007\/s11128-015-1150-6","volume":"15","author":"TKAD Boothby","year":"2016","unstructured":"Boothby, T.K.A.D., Roy, A.: Fast clique minor generation in Chimera qubit connectivity graphs. Quantum Inf. Process. 15(1), 495\u2013508 (2016)","journal-title":"Quantum Inf. Process."},{"key":"9471_CR5","unstructured":"Chen, X. et al.: RNA secondary structure prediction by learning unrolled algorithms. In: International Conference of Learning Presentations (2020)"},{"key":"9471_CR6","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/s11128-008-0082-9","volume":"7","author":"V Choi","year":"2008","unstructured":"Choi, V.: Minor-embedding in adiabatic quantum computation: I. The parameter setting problem. Quantum Inf. Process. 7, 193\u2013201 (2008)","journal-title":"Quantum Inf. Process."},{"key":"9471_CR7","unstructured":"D-Wave Systems: D-Wave (2020). https:\/\/www.dwavesys.com\/"},{"key":"9471_CR8","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/j.jbiotec.2017.07.007","volume":"261","author":"J Fallmann","year":"2017","unstructured":"Fallmann, J., et al.: Recent advances in RNA folding. J. Biotechnol. 261, 97\u2013104 (2017)","journal-title":"J. Biotechnol."},{"key":"9471_CR9","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1016\/j.ymeth.2018.04.003","volume":"143","author":"S Findeiss","year":"2018","unstructured":"Findeiss, S., et al.: In silico design of ligand triggered RNA switches. Methods 143, 90\u2013101 (2018)","journal-title":"Methods"},{"issue":"2","key":"9471_CR10","first-page":"110","volume":"3","author":"R Forrester","year":"2008","unstructured":"Forrester, R., Greenberg, H.: Quadratic binary programming models in computational biology. Algorithmic Oper. Res. 3(2), 110\u2013129 (2008)","journal-title":"Algorithmic Oper. Res."},{"key":"9471_CR11","unstructured":"Fujitsu: Digital Annealer\u2014Quantum Computing Technology, Available Today (2020). https:\/\/www.fujitsu.com\/global\/services\/business-services\/digital-annealer\/"},{"key":"9471_CR12","first-page":"140","volume":"5","author":"P Gardner","year":"2004","unstructured":"Gardner, P., Giegerich, R.: A comprehensive comparison of comparative RNA structure prediction approaches. Bioinformatics 5, 140 (2004)","journal-title":"Bioinformatics"},{"key":"9471_CR13","unstructured":"Glover, F.: Exploiting Local Optimality in Metaheuristic Search (2020). https:\/\/arxiv.org\/ftp\/arxiv\/papers\/2010\/2010.05394.pdf"},{"issue":"2","key":"9471_CR14","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1016\/S0377-2217(01)00209-0","volume":"13","author":"F Glover","year":"2002","unstructured":"Glover, F., Alidaee, B., Rego, C., Kochenberger, G.: One-pass heuristics for large-scale unconstrained binary quadratic problems. Eur. J. Oper. Res. 13(2), 272\u2013287 (2002)","journal-title":"Eur. J. Oper. Res."},{"key":"9471_CR15","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/s10288-019-00424-y","volume":"17","author":"F Glover","year":"2019","unstructured":"Glover, F., Kochenberger, G., Du, Y.: Quantum bridge analytics I: a tutorial on formulating and using QUBO models. 4OR Q. J. Oper. Res. 17, 335\u2013371 (2019)","journal-title":"4OR Q. J. Oper. Res."},{"issue":"3","key":"9471_CR16","doi-asserted-by":"publisher","first-page":"829","DOI":"10.1016\/j.ejor.2017.08.025","volume":"265","author":"F Glover","year":"2018","unstructured":"Glover, F., Lewis, M., Kochenberger, G.: Logical and inequality implications for reducing the size and difficulty of quadratic unconstrained binary optimization problems. Eur. J. Oper. Res. 265(3), 829\u2013842 (2018)","journal-title":"Eur. J. Oper. Res."},{"key":"9471_CR17","doi-asserted-by":"crossref","unstructured":"Gusfield, D.: Chapter 6 The RNA-folding problem. In: Integer Linear Programming in Computational and Systems Biology: An Entry-Level Text and Course. Cambridge University Press, New York (2019)","DOI":"10.1017\/9781108377737"},{"key":"9471_CR18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-85823-9","volume-title":"Boolean Methods in Operations Research and Related Areas","author":"P Hammer","year":"1968","unstructured":"Hammer, P., Rudeanu, S.: Boolean Methods in Operations Research and Related Areas. Sprnger, Berlin (1968)"},{"key":"9471_CR19","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1093\/bioinformatics\/btz375","volume":"35","author":"L Huang","year":"2019","unstructured":"Huang, L., et al.: LinearFold: linear-time approximate RNA folding by 5\u2019-to-3\u2019dynamic programming and beam search. Bioinformatics 35, 295\u2013304 (2019)","journal-title":"Bioinformatics"},{"key":"9471_CR20","unstructured":"ILOG, C.I.: V12 User's Manual for CPLEX (2019)"},{"key":"9471_CR21","unstructured":"Kelley, S.: Kelly Bioinformatics (2020). https:\/\/www.kelleybioinfo.org\/algorithms\/default.php?o=3#"},{"key":"9471_CR22","doi-asserted-by":"publisher","DOI":"10.1128\/9781683670025","volume-title":"Computational Biology: A Hypertextbook","author":"S Kelly","year":"2018","unstructured":"Kelly, S., Didulo, D.: Computational Biology: A Hypertextbook, 1st edn. ASM Press, Washington (2018)","edition":"1"},{"issue":"20","key":"9471_CR23","doi-asserted-by":"publisher","first-page":"3377","DOI":"10.1093\/bioinformatics\/btv372","volume":"31","author":"P Kerpediev","year":"2015","unstructured":"Kerpediev, P., Hammer, S., Hofacker, I.: Forna (force-directed RNA): simple and effective online RNA secondary structure diagrams. Bioinformatics 31(20), 3377\u20133379 (2015)","journal-title":"Bioinformatics"},{"issue":"3","key":"9471_CR24","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/s00291-003-0153-3","volume":"26","author":"G Kochenberger","year":"2004","unstructured":"Kochenberger, G., Glover, F., Alidaee, B., Rego, C.: A unified modeling and solution framework for combinatorial optimization problems. OR Spectrum 26(3), 237\u2013250 (2004)","journal-title":"OR Spectrum"},{"key":"9471_CR25","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1007\/s10878-014-9734-0","volume":"28","author":"G Kochenberger","year":"2014","unstructured":"Kochenberger, G., et al.: The unconstrained binary quadratic programming problem: a survey. J. Comb. Optim. 28, 58\u201381 (2014)","journal-title":"J. Comb. Optim."},{"key":"9471_CR26","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0957-4174(93)90056-C","volume":"6","author":"M Laguna","year":"1993","unstructured":"Laguna, M., Glover, F.: Integrating target analysis and tabu search for improved scheduling systems. Expert Syst. Appl. 6, 287\u2013292 (1993)","journal-title":"Expert Syst. Appl."},{"issue":"1","key":"9471_CR27","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1504\/IJOR.2016.075647","volume":"26","author":"M Lewis","year":"2016","unstructured":"Lewis, M., Kochenberger, G.: Probabilistic multistart with path relinking for solving the unconstrained binary quadratic problem. Int J Oper Res 26(1), 13\u201333 (2016)","journal-title":"Int J Oper Res"},{"key":"9471_CR28","doi-asserted-by":"publisher","first-page":"5","DOI":"10.3389\/fphy.2014.00005","volume":"2","author":"A Lucas","year":"2014","unstructured":"Lucas, A.: Ising formulations of many NP problems. Front. Phys. 2, 5 (2014)","journal-title":"Front. Phys."},{"key":"9471_CR29","doi-asserted-by":"publisher","first-page":"31","DOI":"10.4204\/EPTCS.231.3","volume":"231","author":"A Mamuye","year":"2016","unstructured":"Mamuye, A., Merelli, E., Tesei, L.: A graph grammar for modelling RNA folding. Electr. Proc. Theor. Comput. Sci. 231, 31\u201341 (2016)","journal-title":"Electr. Proc. Theor. Comput. Sci."},{"key":"9471_CR30","unstructured":"Mathews, D.: Free Energy and Enthalpy Change Parameters (2020). https:\/\/rna.urmc.rochester.edu\/NNDB\/turner04\/index.html"},{"key":"9471_CR31","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1016\/j.ymeth.2019.04.003","volume":"162","author":"DH Mathews","year":"2019","unstructured":"Mathews, D.H.: How to benchmark RNA secondary structure prediction accuracy. Methods 162, 60\u201367 (2019)","journal-title":"Methods"},{"key":"9471_CR32","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/j.ejor.2011.09.016","volume":"217","author":"GR Mauri","year":"2012","unstructured":"Mauri, G.R., Lorena, L.A.N.: A column generation approach for the unconstrained binary quadratic programming problem. Eur. J. Oper. Res. 217, 69\u201374 (2012)","journal-title":"Eur. J. Oper. Res."},{"key":"9471_CR33","unstructured":"Meta-Analytics: Alpha-QUBO: Optimization Technology for the modern age (2020). http:\/\/meta-analytics.net\/Home\/AlphaQUBO. Accessed 2020"},{"issue":"2","key":"9471_CR34","doi-asserted-by":"publisher","first-page":"279","DOI":"10.15388\/Informatica.2006.138","volume":"17","author":"G Palubeckis","year":"2006","unstructured":"Palubeckis, G.: Iterated tabu search for the unconstrained binary quadratic optimization problem. Informatica 17(2), 279\u2013296 (2006)","journal-title":"Informatica"},{"issue":"2","key":"9471_CR35","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0167-6377(92)90043-3","volume":"11","author":"P Pardalos","year":"1992","unstructured":"Pardalos, P., Jha, S.: Complexity of uniqueness and local search in quadratic 0\u20131 programming. Oper Res Lett 11(2), 119\u2013123 (1992)","journal-title":"Oper Res Lett"},{"issue":"2","key":"9471_CR36","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/BF02247879","volume":"45","author":"PM Pardalos","year":"1990","unstructured":"Pardalos, P.M., Rodgers, G.P.: Computational aspects of a branch and bound algorithm for quadratic zero-one programming. Computing 45(2), 131\u2013144 (1990a)","journal-title":"Computing"},{"key":"9471_CR37","unstructured":"RNA STRAND Database: RNA STRAND (2008). http:\/\/www.rnasoft.ca\/strand\/. Accessed 2020 June."},{"key":"9471_CR38","first-page":"321","volume-title":"Combinatorial Pattern Matching","author":"S Saad","year":"2012","unstructured":"Saad, S., Backofen, R., Ponty, Y.: Impact of the Energy Model on the Complexity of RNA Folding with Pseudoknots. In: Karkkainen, J., Stoye, J. (eds.) Combinatorial Pattern Matching, pp. 321\u2013333. Springer, Berlin (2012)"},{"key":"9471_CR39","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1159\/000501480","volume":"84","author":"S Shi","year":"2019","unstructured":"Shi, S., et al.: Prediction of the RNA secondary structure using a multi-population assisted quantum genetic algorithm. Hum Heredity 84, 1\u20138 (2019)","journal-title":"Hum Heredity"},{"key":"9471_CR40","first-page":"1","volume":"12","author":"J Singh","year":"2019","unstructured":"Singh, J., Hanson, J., Paliwal, K., Zhou, Y.: RNA secondary structure prediction using an ensemble of two-dimensional deep neural networks and transfer learning. Nat. Commun. 12, 1\u201313 (2019)","journal-title":"Nat. Commun."},{"key":"9471_CR41","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1093\/nar\/gkp892","volume":"38","author":"D Turner","year":"2009","unstructured":"Turner, D., Mathews, D.: NNDB: the nearest neighbor parameter database for predicting stability of nucleic acid secondary structure. Nucleic Acids Res. 38, 280\u2013282 (2009)","journal-title":"Nucleic Acids Res."},{"key":"9471_CR42","unstructured":"Verma, A.: Qfold (2020). https:\/\/github.com\/amitverma1509\/Qfold. Accessed 25 June 2020"},{"key":"9471_CR43","unstructured":"Vienna RNA Web Service: RNA Secondary Structure Visualization Using a Force Directed Graph Layout (2020). http:\/\/rna.tbi.univie.ac.at\/forna\/. Accessed 2020"},{"issue":"3","key":"9471_CR44","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1016\/j.ejor.2012.07.012","volume":"223","author":"Y Wang","year":"2012","unstructured":"Wang, Y., Lu, Z., Glover, F., Hao, J.: Path relinking for unconstrained binary quadratic programming. Eur. J. Oper. Res. 223(3), 595\u2013604 (2012)","journal-title":"Eur. J. Oper. Res."},{"key":"9471_CR45","doi-asserted-by":"publisher","first-page":"737","DOI":"10.1038\/171737a0","volume":"171","author":"JD Watson","year":"1953","unstructured":"Watson, J.D., Crick, F.H.C.: A structure for deoxyribose nucleic acid. Nature 171, 737\u2013738 (1953)","journal-title":"Nature"},{"key":"9471_CR46","doi-asserted-by":"publisher","unstructured":"Yan, Z., Hamilton, W., Blanchette, M.: Graph neural representational learning of RNA secondary structures for predicting RNA-protein interactions (2020). https:\/\/doi.org\/10.1101\/2020.02.11.931030","DOI":"10.1101\/2020.02.11.931030"},{"key":"9471_CR47","doi-asserted-by":"publisher","first-page":"467","DOI":"10.3389\/fgene.2019.00467","volume":"10","author":"H Zhang","year":"2019","unstructured":"Zhang, H., et al.: A new method of RNA secondary structure prediction based on convolutional neural network and dynamic programming. Front. Genet. 10, 467 (2019)","journal-title":"Front. Genet."},{"key":"9471_CR48","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1093\/nar\/9.1.133","volume":"9","author":"M Zuker","year":"1981","unstructured":"Zuker, M., Stiegler, P.: Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information. Nucleic Acids Res. 9, 133\u2013148 (1981)","journal-title":"Nucleic Acids Res."}],"container-title":["Journal of Heuristics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-021-09471-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10732-021-09471-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-021-09471-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,17]],"date-time":"2021-06-17T12:12:04Z","timestamp":1623931924000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10732-021-09471-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,6]]},"references-count":48,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,8]]}},"alternative-id":["9471"],"URL":"https:\/\/doi.org\/10.1007\/s10732-021-09471-3","relation":{},"ISSN":["1381-1231","1572-9397"],"issn-type":[{"value":"1381-1231","type":"print"},{"value":"1572-9397","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,3,6]]},"assertion":[{"value":"10 July 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 November 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 February 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 March 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}