{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T01:29:46Z","timestamp":1773365386756,"version":"3.50.1"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2016,8,29]],"date-time":"2016-08-29T00:00:00Z","timestamp":1472428800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-14-CE34-0011"],"award-info":[{"award-number":["ANR-14-CE34-0011"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,11]]},"DOI":"10.1007\/s00453-016-0196-x","type":"journal-article","created":{"date-parts":[[2016,8,29]],"date-time":"2016-08-29T13:54:53Z","timestamp":1472478893000},"page":"835-856","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Combinatorial RNA Design: Designability and Structure-Approximating Algorithm in Watson\u2013Crick and Nussinov\u2013Jacobson Energy Models"],"prefix":"10.1007","volume":"79","author":[{"given":"Jozef","family":"Hale\u0161","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alice","family":"H\u00e9liou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J\u00e1n","family":"Ma\u0148uch","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yann","family":"Ponty","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ladislav","family":"Stacho","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,8,29]]},"reference":[{"key":"196_CR1","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1186\/1471-2105-8-34","volume":"8","author":"R Aguirre-Hern\u00e1ndez","year":"2007","unstructured":"Aguirre-Hern\u00e1ndez, R., Hoos, H.H., Condon, A.: Computational RNA secondary structure design: empirical complexity and improved methods. BMC Bioinform. 8, 34 (2007). doi: 10.1186\/1471-2105-8-34","journal-title":"BMC Bioinform."},{"issue":"1","key":"196_CR2","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1186\/1471-2105-12-319","volume":"12","author":"A Avihoo","year":"2011","unstructured":"Avihoo, A., Churkin, A., Barash, D.: RNAexinv: an extended inverse RNA folding from shape and physical attributes to sequences. BMC Bioinform. 12(1), 319 (2011). doi: 10.1186\/1471-2105-12-319","journal-title":"BMC Bioinform."},{"key":"196_CR3","unstructured":"Bau, A., Waldmann, J., Will, S.: RNA design by program inversion via SAT solving. In: Palu, A.D., Dovier, A. (eds.) Proceedings of Workshop on Constraint Based Methods for Bioinformatics (WCB 2013), pp. 85\u201394 (2013)"},{"issue":"15","key":"196_CR4","doi-asserted-by":"publisher","first-page":"1823","DOI":"10.1093\/bioinformatics\/btl194","volume":"22","author":"A Busch","year":"2006","unstructured":"Busch, A., Backofen, R.: INFO-RNA\u2014a fast approach to inverse RNA folding. Bioinformatics 22(15), 1823\u20131831 (2006). doi: 10.1093\/bioinformatics\/btl194","journal-title":"Bioinformatics"},{"key":"196_CR5","doi-asserted-by":"crossref","unstructured":"Dai, D.C., Tsang, H.H., Wiese, K.C.: RNADesign: local search for RNA secondary structure design. In: IEEE Symposium on Computational Intelligence in Bioinformatics and Computational Biology (CIBCB) (2009)","DOI":"10.1109\/CIBCB.2009.4925700"},{"issue":"9","key":"196_CR6","doi-asserted-by":"publisher","first-page":"1250","DOI":"10.1093\/bioinformatics\/btu001","volume":"30","author":"A Esmaili-Taheri","year":"2014","unstructured":"Esmaili-Taheri, A., Ganjtabesh, M., Mohammad-Noori, M.: Evolutionary solution for the RNA design problem. Bioinformatics 30(9), 1250\u20131258 (2014). doi: 10.1093\/bioinformatics\/btu001","journal-title":"Bioinformatics"},{"key":"196_CR7","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1186\/1748-7188-5-13","volume":"5","author":"Y Frid","year":"2010","unstructured":"Frid, Y., Gusfield, D.: A simple, practical and complete $$o(n^3\/\\log n)$$ o ( n 3 \/ log n ) -time algorithm for RNA folding using the Four-Russians speedup. Algorithms Mol. Biol. 5, 13 (2010). doi: 10.1186\/1748-7188-5-13","journal-title":"Algorithms Mol. Biol."},{"issue":"2","key":"196_CR8","doi-asserted-by":"publisher","first-page":"1350001","DOI":"10.1142\/S0219720013500017","volume":"11","author":"JA Garcia-Martin","year":"2013","unstructured":"Garcia-Martin, J.A., Clote, P., Dotu, I.: RNAiFOLD: a constraint programming algorithm for RNA inverse folding and molecular design. J. Bioinform. Comput. Biol. 11(2), 1350001 (2013). doi: 10.1142\/S0219720013500017","journal-title":"J. Bioinform. Comput. Biol."},{"issue":"1","key":"196_CR9","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1093\/nar\/gkg006","volume":"31","author":"S Griffiths-Jones","year":"2003","unstructured":"Griffiths-Jones, S., Bateman, A., Marshall, M., Khanna, A., Eddy, S.R.: RFAM: an RNA family database. Nucleic Acids Res. 31(1), 439\u2013441 (2003)","journal-title":"Nucleic Acids Res."},{"issue":"2","key":"196_CR10","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/BF00818163","volume":"125","author":"IL Hofacker","year":"1994","unstructured":"Hofacker, I.L., Fontana, W., Stadler, P., Bonhoeffer, L., Tacker, M., Schuster, P.: Fast folding and comparison of RNA secondary structures. Chem. Mon. 125(2), 167\u2013188 (1994). doi: 10.1007\/BF00818163","journal-title":"Chem. Mon."},{"issue":"12","key":"196_CR11","doi-asserted-by":"publisher","first-page":"1124","DOI":"10.1002\/bip.22337","volume":"99","author":"C H\u00f6ner Zu Siederdissen","year":"2013","unstructured":"H\u00f6ner Zu Siederdissen, C., Hammer, S., Abfalter, I., Hofacker, I.L., Flamm, C., Stadler, P.F.: Computational design of RNAs with complex energy landscapes. Biopolymers 99(12), 1124\u20131136 (2013). doi: 10.1002\/bip.22337","journal-title":"Biopolymers"},{"key":"196_CR12","first-page":"104","volume":"34","author":"D K\u0151nig","year":"1916","unstructured":"K\u0151nig, D.: Gr\u00e1fok \u00e9s alkalmaz\u00e1suk a determin\u00e1nsok \u00e9s a halmazok elm\u00e9let\u00e9re. Matematikai \u00e9s Term\u00e9szettudom\u00e1nyi \u00c9rtes\u00edt\u0151 34, 104\u2013119 (1916)","journal-title":"Matematikai \u00e9s Term\u00e9szettudom\u00e1nyi \u00c9rtes\u00edt\u0151"},{"issue":"20","key":"196_CR13","doi-asserted-by":"publisher","first-page":"10041","DOI":"10.1093\/nar\/gks768","volume":"40","author":"A Levin","year":"2012","unstructured":"Levin, A., Lis, M., Ponty, Y., O\u2019Donnell, C.W., Devadas, S., Berger, B., Waldisp\u00fchl, J.: A global sampling approach to designing and reengineering RNA secondary structures. Nucleic Acids Res. 40(20), 10041\u201310052 (2012). doi: 10.1093\/nar\/gks768","journal-title":"Nucleic Acids Res."},{"key":"196_CR14","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1186\/1471-2105-13-260","volume":"13","author":"RB Lyngs\u00f8","year":"2012","unstructured":"Lyngs\u00f8, R.B., Anderson, J.W., Sizikova, E., Badugu, A., Hyland, T., Hein, J.: FRNAkenstein: multiple target inverse RNA folding. BMC Bioinform. 13, 260 (2012). doi: 10.1186\/1471-2105-13-260","journal-title":"BMC Bioinform."},{"issue":"5","key":"196_CR15","doi-asserted-by":"crossref","first-page":"911","DOI":"10.1006\/jmbi.1999.2700","volume":"288","author":"DH Mathews","year":"1999","unstructured":"Mathews, D.H., Sabina, J., Zuker, M., Turner, D.H.: Expanded sequence dependence of thermodynamic parameters improves prediction of RNA secondary structure. J. Mol. Biol. 288(5), 911\u2013940 (1999)","journal-title":"J. Mol. Biol."},{"key":"196_CR16","doi-asserted-by":"crossref","first-page":"6903","DOI":"10.1073\/pnas.77.11.6309","volume":"77","author":"R Nussinov","year":"1980","unstructured":"Nussinov, R., Jacobson, A.: Fast algorithm for predicting the secondary structure of single-stranded RNA. Proc. Natl. Acad. Sci. USA 77, 6903\u20136913 (1980)","journal-title":"Proc. Natl. Acad. Sci. USA"},{"issue":"13","key":"196_CR17","doi-asserted-by":"publisher","first-page":"i308","DOI":"10.1093\/bioinformatics\/btt217","volume":"29","author":"V Reinharz","year":"2013","unstructured":"Reinharz, V., Ponty, Y., Waldisp\u00fchl, J.: A weighted sampling algorithm for the design of RNA sequences with targeted secondary structure and nucleotide distribution. Bioinformatics 29(13), i308\u2013i315 (2013). doi: 10.1093\/bioinformatics\/btt217","journal-title":"Bioinformatics"},{"issue":"8","key":"196_CR18","doi-asserted-by":"publisher","first-page":"e1003,172","DOI":"10.1371\/journal.pcbi.1003172","volume":"9","author":"G Rodrigo","year":"2013","unstructured":"Rodrigo, G., Landrain, T.E., Majer, E., Dar\u00f2s, J.A., Jaramillo, A.: Full design automation of multi-state RNA devices to program gene expression using energy-based optimization. PLoS Comput. Biol. 9(8), e1003,172 (2013). doi: 10.1371\/journal.pcbi.1003172","journal-title":"PLoS Comput. Biol."},{"key":"196_CR19","doi-asserted-by":"publisher","unstructured":"Schnall-Levin, M., Chindelevitch, L., Berger, B.: Inverting the Viterbi algorithm: an abstract framework for structure design. In: Proceedings of the Twenty-Fifth International Conference on Machine Learning (ICML 2008), Helsinki, Finland, June 5\u20139, 2008, pp. 904\u2013911 (2008). doi: 10.1145\/1390156.1390270","DOI":"10.1145\/1390156.1390270"},{"issue":"15","key":"196_CR20","doi-asserted-by":"publisher","first-page":"7577","DOI":"10.1093\/nar\/gkt452","volume":"41","author":"MK Takahashi","year":"2013","unstructured":"Takahashi, M.K., Lucks, J.B.: A modular strategy for engineering orthogonal chimeric RNA transcription regulators. Nucleic Acids Res. 41(15), 7577\u20137588 (2013). doi: 10.1093\/nar\/gkt452","journal-title":"Nucleic Acids Res."},{"key":"196_CR21","first-page":"1","volume":"4","author":"A Taneda","year":"2011","unstructured":"Taneda, A.: MODENA: a multi-objective RNA inverse folding. Adv. Appl. Bioinform. Chem. 4, 1\u201312 (2011)","journal-title":"Adv. Appl. Bioinform. Chem."},{"issue":"Database issue","key":"196_CR22","doi-asserted-by":"publisher","first-page":"D280","DOI":"10.1093\/nar\/gkp892","volume":"38","author":"DH Turner","year":"2010","unstructured":"Turner, D.H., Mathews, D.H.: NNDB: the nearest neighbor parameter database for predicting stability of nucleic acid secondary structure. Nucleic Acids Res. 38(Database issue), D280\u2013D282 (2010). doi: 10.1093\/nar\/gkp892","journal-title":"Nucleic Acids Res."},{"key":"196_CR23","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198510611.001.0001","volume-title":"Graphs, Colourings and the Four-colour Theorem","author":"RA Wilson","year":"2002","unstructured":"Wilson, R.A.: Graphs, Colourings and the Four-colour Theorem. Oxford University Press, Oxford (2002)"},{"issue":"240","key":"196_CR24","doi-asserted-by":"publisher","first-page":"240ps7","DOI":"10.1126\/scitranslmed.3008362","volume":"6","author":"SY Wu","year":"2014","unstructured":"Wu, S.Y., Lopez-Berestein, G., Calin, G.A., Sood, A.K.: RNAi therapies: drugging the undruggable. Sci. Transl. Med. 6(240), 240ps7 (2014). doi: 10.1126\/scitranslmed.3008362","journal-title":"Sci. Transl. Med."},{"issue":"3","key":"196_CR25","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1002\/jcc.21633","volume":"32","author":"JN Zadeh","year":"2011","unstructured":"Zadeh, J.N., Wolfe, B.R., Pierce, N.A.: Nucleic acid sequence design via efficient ensemble defect optimization. J. Comput. Chem. 32(3), 439\u2013452 (2011). doi: 10.1002\/jcc.21633","journal-title":"J. Comput. Chem."},{"issue":"1","key":"196_CR26","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1186\/1748-7188-6-20","volume":"6","author":"S Zakov","year":"2011","unstructured":"Zakov, S., Tsur, D., Ziv-Ukelson, M.: Reducing the worst case running times of a family of RNA and CFG problems, using Valiant\u2019s approach. Algorithms Mol. Biol. 6(1), 20 (2011). doi: 10.1186\/1748-7188-6-20","journal-title":"Algorithms Mol. Biol."},{"key":"196_CR27","doi-asserted-by":"publisher","unstructured":"Zhou, Y., Ponty, Y., Vialette, S., Waldispuhl, J., Zhang, Y., Denise, A.: Flexible RNA design under structure and sequence constraints using formal languages. In: Proceedings of the International Conference on Bioinformatics, Computational Biology and Biomedical Informatics (ACM-BCB), BCB\u201913, pp. 229\u2013238. ACM (2013). doi: 10.1145\/2506583.2506623","DOI":"10.1145\/2506583.2506623"},{"key":"196_CR28","doi-asserted-by":"crossref","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":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0196-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0196-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0196-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0196-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,19]],"date-time":"2024-06-19T03:17:08Z","timestamp":1718767028000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0196-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,8,29]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,11]]}},"alternative-id":["196"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0196-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,8,29]]}}}