{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T18:08:39Z","timestamp":1778609319885,"version":"3.51.4"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2019,4,25]],"date-time":"2019-04-25T00:00:00Z","timestamp":1556150400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"crossref","award":["ANR-14-CE34-0011"],"award-info":[{"award-number":["ANR-14-CE34-0011"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2019,12]]},"DOI":"10.1186\/s12859-019-2784-7","type":"journal-article","created":{"date-parts":[[2019,4,25]],"date-time":"2019-04-25T10:03:36Z","timestamp":1556186616000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":27,"title":["Fixed-parameter tractable sampling for RNA design with multiple target structures"],"prefix":"10.1186","volume":"20","author":[{"given":"Stefan","family":"Hammer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wei","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2376-9205","authenticated-orcid":false,"given":"Sebastian","family":"Will","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yann","family":"Ponty","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,4,25]]},"reference":[{"issue":"8","key":"2784_CR1","doi-asserted-by":"publisher","first-page":"795","DOI":"10.1021\/acssynbio.5b00297","volume":"5","author":"M Kushwaha","year":"2016","unstructured":"Kushwaha M, Rostain W, Prakash S, Duncan JN, Jaramillo A. Using RNA as molecular code for programming cellular function. ACS Synth Biol. 2016; 5(8):795\u2013809. https:\/\/doi.org\/10.1021\/acssynbio.5b00297 .","journal-title":"ACS Synth Biol"},{"issue":"17","key":"2784_CR2","doi-asserted-by":"publisher","first-page":"2508","DOI":"10.1093\/bioinformatics\/btu335","volume":"30","author":"G Rodrigo","year":"2014","unstructured":"Rodrigo G, Jaramillo A. RiboMaker: computational design of conformation-based riboregulation. Bioinformatics. 2014; 30(17):2508\u201310. https:\/\/doi.org\/10.1093\/bioinformatics\/btu335 .","journal-title":"Bioinformatics"},{"key":"2784_CR3","doi-asserted-by":"publisher","first-page":"1105","DOI":"10.1002\/bip.360290621","volume":"29","author":"JS McCaskill","year":"1990","unstructured":"McCaskill JS. The equilibrium partition function and base pair binding probabilities for RNA secondary structure. Biopolymers. 1990; 29:1105\u201319. https:\/\/doi.org\/10.1002\/bip.360290621 .","journal-title":"Biopolymers"},{"key":"2784_CR4","doi-asserted-by":"publisher","first-page":"480","DOI":"10.1093\/nar\/gkt461","volume":"41","author":"Y Zhang","year":"2013","unstructured":"Zhang Y, Ponty Y, Blanchette M, L\u00e9cuyer E, Waldisp\u00fchl J. SPARCS: a web server to analyze (un)structured regions in coding RNA sequences. Nucleic Acids Res. 2013; 41:480\u20135. https:\/\/doi.org\/10.1093\/nar\/gkt461 .","journal-title":"Nucleic Acids Res"},{"issue":"4","key":"2784_CR5","doi-asserted-by":"publisher","first-page":"2541","DOI":"10.1093\/nar\/gks1330","volume":"41","author":"M Wachsmuth","year":"2013","unstructured":"Wachsmuth M, Findei\u00df S, Weissheimer N, Stadler PF, M\u00f6rl M. De novo design of a synthetic riboswitch that regulates transcription termination. Nucleic Acids Res. 2013; 41(4):2541\u201351. https:\/\/doi.org\/10.1093\/nar\/gks1330 .","journal-title":"Nucleic Acids Res"},{"issue":"7","key":"2784_CR6","doi-asserted-by":"publisher","first-page":"4108","DOI":"10.1093\/nar\/gkw1267","volume":"45","author":"G Domin","year":"2017","unstructured":"Domin G, Findei\u00df S, Wachsmuth M, Will S, Stadler PF, M\u00f6rl M. Applicability of a computational design approach for synthetic riboswitches. Nucleic Acids Res. 2017; 45(7):4108\u20134119. https:\/\/doi.org\/10.1093\/nar\/gkw1267 .","journal-title":"Nucleic Acids Res"},{"issue":"9","key":"2784_CR7","doi-asserted-by":"publisher","first-page":"1990","DOI":"10.3390\/s17091990","volume":"17","author":"Sven Findei\u00df","year":"2017","unstructured":"Findei\u00df S, Etzel M, Will S, M\u00f6rl M, Stadler PF. Design of artificial riboswitches as biosensors. Sensors (Basel, Switzerland). 2017; 17. https:\/\/doi.org\/10.3390\/s17091990 .","journal-title":"Sensors"},{"key":"2784_CR8","doi-asserted-by":"publisher","first-page":"6273","DOI":"10.1093\/nar\/gkt319","volume":"41","author":"JYA Zhu","year":"2013","unstructured":"Zhu JYA, Steif A, Proctor JR, Meyer IM. Transient RNA structure features are evolutionarily conserved and can be computationally predicted. Nucleic Acids Res. 2013; 41:6273\u201385. https:\/\/doi.org\/10.1093\/nar\/gkt319 .","journal-title":"Nucleic Acids Res"},{"key":"2784_CR9","doi-asserted-by":"publisher","first-page":"308","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 (Oxford, England). 2013; 29:308\u201315. https:\/\/doi.org\/10.1093\/bioinformatics\/btt217 .","journal-title":"Bioinformatics (Oxford, England)"},{"key":"2784_CR10","doi-asserted-by":"publisher","unstructured":"Zhou Y, Ponty Y, Vialette S, Waldisp\u00fchl J, Zhang Y, Denise A. Flexible RNA design under structure and sequence constraints using formal languages In: Gao J., editor. ACM Conference on Bioinformatics, Computational Biology and Biomedical Informatics. ACM-BCB 2013, Washington, DC, USA, September 22-25, 2013. ACM: 2013. p. 229. https:\/\/doi.org\/10.1145\/2506583.2506623 .","DOI":"10.1145\/2506583.2506623"},{"issue":"20","key":"2784_CR11","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 CW, Devadas S, Berger B, Waldisp\u00fchl J. A global sampling approach to designing and reengineering RNA secondary structures. Nucleic Acids Res. 2012; 40(20):10041\u201352.","journal-title":"Nucleic Acids Res"},{"key":"2784_CR12","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\u2013a fast approach to inverse RNA folding. Bioinformatics (Oxford, England). 2006; 22:1823\u201331. https:\/\/doi.org\/10.1093\/bioinformatics\/btl194 .","journal-title":"Bioinformatics (Oxford, England)"},{"issue":"2","key":"2784_CR13","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/BF00818163","volume":"125","author":"IL Hofacker","year":"1994","unstructured":"Hofacker IL, Fontana W, Stadler PF, Bonhoeffer LS, Tacker M, Schuster P. Fast folding and comparison of RNA secondary structures. Monatshefte f\u00fcr Chemie\/Chemical Monthly. 1994; 125(2):167\u201388.","journal-title":"Monatshefte f\u00fcr Chemie\/Chemical Monthly"},{"issue":"1","key":"2784_CR14","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1186\/s12859-015-0815-6","volume":"16","author":"R Kleinkauf","year":"2015","unstructured":"Kleinkauf R, Houwaart T, Backofen R, Mann M. antarna \u2013 multi-objective inverse folding of pseudoknot rna using ant-colony optimization. BMC Bioinformatics. 2015; 16(1):389. https:\/\/doi.org\/10.1186\/s12859-015-0815-6 .","journal-title":"BMC Bioinformatics"},{"key":"2784_CR15","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 RB, Anderson JWJ, Sizikova E, Badugu A, Hyland T, Hein J. Frnakenstein: multiple target inverse RNA folding. BMC Bioinformatics. 2012; 13:260. https:\/\/doi.org\/10.1186\/1471-2105-13-260 .","journal-title":"BMC Bioinformatics"},{"key":"2784_CR16","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 IL, Flamm C, Stadler PF. Computational design of RNAs with complex energy landscapes. Biopolymers. 2013; 99:1124\u201336. https:\/\/doi.org\/10.1002\/bip.22337 .","journal-title":"Biopolymers"},{"key":"2784_CR17","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1186\/s12859-015-0706-x","volume":"16","author":"A Taneda","year":"2015","unstructured":"Taneda A. Multi-objective optimization for RNA design with multiple target secondary structures. BMC Bioinformatics. 2015; 16:280. https:\/\/doi.org\/10.1186\/s12859-015-0706-x .","journal-title":"BMC Bioinformatics"},{"key":"2784_CR18","doi-asserted-by":"publisher","first-page":"2850","DOI":"10.1093\/bioinformatics\/btx263","volume":"33","author":"S Hammer","year":"2017","unstructured":"Hammer S, Tschiatschek B, Flamm C, Hofacker IL, Findei\u00df S. RNAblueprint: flexible multiple target nucleic acid sequence design. Bioinformatics (Oxford, England). 2017; 33:2850\u20138. https:\/\/doi.org\/10.1093\/bioinformatics\/btx263 .","journal-title":"Bioinformatics (Oxford, England)"},{"key":"2784_CR19","doi-asserted-by":"publisher","first-page":"7280","DOI":"10.1093\/nar\/gkg938","volume":"31","author":"Y Ding","year":"2003","unstructured":"Ding Y, Lawrence CE. A statistical sampling algorithm for RNA secondary structure prediction. Nucleic Acids Res. 2003; 31:7280\u2013301.","journal-title":"Nucleic Acids Res"},{"issue":"5","key":"2784_CR20","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1145\/2528401","volume":"60","author":"AA Bulatov","year":"2013","unstructured":"Bulatov AA, Dyer M, Goldberg LA, Jerrum M, Mcquillan C. The expressibility of functions on the boolean domain, with applications to counting CSPs. J ACM. 2013; 60(5):32\u201313236. https:\/\/doi.org\/10.1145\/2528401 .","journal-title":"J ACM"},{"issue":"5","key":"2784_CR21","doi-asserted-by":"publisher","first-page":"690","DOI":"10.1016\/j.jcss.2015.11.009","volume":"82","author":"J-Y Cai","year":"2016","unstructured":"Cai J-Y, Galanis A, Goldberg LA, Guo H, Jerrum M, \u0160tefankovi\u010d D, Vigoda E. # BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region. J Comput Syst Sci. 2016; 82(5):690\u2013711.","journal-title":"J Comput Syst Sci"},{"issue":"3","key":"2784_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.2200\/S00529ED1V01Y201308AIM023","volume":"7","author":"Rina Dechter","year":"2013","unstructured":"Dechter R. Reasoning with Probabilistic and Deterministic Graphical Models: Exact Algorithms.Morgan & Claypool; 2013, p. 191. https:\/\/doi.org\/10.2200\/S00529ED1V01Y201308AIM023 .","journal-title":"Synthesis Lectures on Artificial Intelligence and Machine Learning"},{"key":"2784_CR23","unstructured":"van Dijk T, van den Heuvel J-P, Slob W. Computing treewidth with LibTW. Technical report, University of Utrecht. 2006. http:\/\/treewidth.com\/treewidth\/docs\/LibTW.pdf ."},{"key":"2784_CR24","doi-asserted-by":"publisher","first-page":"1494","DOI":"10.1261\/rna.7284905","volume":"11","author":"J Ren","year":"2005","unstructured":"Ren J, Rastegari B, Condon A, Hoos HH. Hotknots: heuristic prediction of RNA secondary structures including pseudoknots. RNA (New York, N.Y.) 2005; 11:1494\u2013504. https:\/\/doi.org\/10.1261\/rna.7284905 .","journal-title":"RNA (New York, N.Y.)"},{"issue":"suppl_1","key":"2784_CR25","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1093\/nar\/gkp892","volume":"38","author":"DH Turner","year":"2009","unstructured":"Turner DH, Mathews DH. NNDB: the nearest neighbor parameter database for predicting stability of nucleic acid secondary structure. Nucleic Acids Res. 2009; 38(suppl_1):280\u20132.","journal-title":"Nucleic Acids Res"},{"key":"2784_CR26","doi-asserted-by":"crossref","unstructured":"Bodini O, Ponty Y. Multi-dimensional Boltzmann sampling of languages. In: Proceedings of the 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA\u201910). DMTCS: 2010. p. 49\u201364.","DOI":"10.46298\/dmtcs.2793"},{"key":"2784_CR27","doi-asserted-by":"publisher","first-page":"1465","DOI":"10.1089\/cmb.2011.0181","volume":"18","author":"J Waldisp\u00fchl","year":"2011","unstructured":"Waldisp\u00fchl J, Ponty Y. An unbiased adaptive sampling algorithm for the exploration of RNA mutational landscapes under evolutionary pressure. J Comput Biol J Comput Mol Cell Biol. 2011; 18:1465\u201379. https:\/\/doi.org\/10.1089\/cmb.2011.0181 .","journal-title":"J Comput Biol J Comput Mol Cell Biol"},{"issue":"40-42","key":"2784_CR28","doi-asserted-by":"publisher","first-page":"3527","DOI":"10.1016\/j.tcs.2010.05.010","volume":"411","author":"A Denise","year":"2010","unstructured":"Denise A, Ponty Y, Termier M. Controlled non-uniform random generation of decomposable structures. Theor Comput Sci. 2010; 411(40-42):3527\u201352.","journal-title":"Theor Comput Sci"},{"key":"2784_CR29","doi-asserted-by":"crossref","unstructured":"Bendkowski M, Bodini O, Dovgal S. Polynomial tuning of multiparametric combinatorial samplers. 2017. arXiv preprint arXiv:1708.01212.","DOI":"10.1137\/1.9781611975062.9"},{"key":"2784_CR30","unstructured":"Cupal J, Hofacker IL, Stadler PF. Dynamic programming algorithm for the density of states of RNA secondary structures In: Hofstaedt R, Lengauer T, Loeffler M, Schomburg D, editors. German Conference on Bioinformatics. Leipzig: 1996. p. 184\u20136."},{"issue":"3","key":"2784_CR31","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/0097-3165(83)90012-2","volume":"35","author":"EA Bender","year":"1983","unstructured":"Bender EA, Richmond LB, Williamson S. Central and local limit theorems applied to asymptotic enumeration. iii. matrix recursions. J Comb Theory Ser A. 1983; 35(3):263\u201378.","journal-title":"J Comb Theory Ser A"},{"issue":"1-2","key":"2784_CR32","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1002\/(SICI)1098-2418(199701\/03)10:1\/2<103::AID-RSA5>3.0.CO;2-Z","volume":"10","author":"M Drmota","year":"1997","unstructured":"Drmota M. Systems of functional equations. Random Struct Algoritm. 1997; 10(1-2):103\u201324.","journal-title":"Random Struct Algoritm"},{"issue":"05","key":"2784_CR33","doi-asserted-by":"publisher","first-page":"695","DOI":"10.1017\/S0963548312000296","volume":"21","author":"Q Ge","year":"2012","unstructured":"Ge Q, \u0160tefankovi\u010d D. A graph polynomial for independent sets of bipartite graphs. Comb Probab Comput. 2012; 21(05):695\u2013714.","journal-title":"Comb Probab Comput"},{"issue":"1","key":"2784_CR34","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1186\/1748-7188-6-26","volume":"6","author":"R Lorenz","year":"2011","unstructured":"Lorenz R, Bernhart SH, zu Siederdissen CH, Tafer H, Flamm C, Stadler PF, Hofacker IL. ViennaRNA Package 2.0. Algorithms Mol Biol. 2011; 6(1):26. https:\/\/doi.org\/10.1186\/1748-7188-6-26 .","journal-title":"Algorithms Mol Biol"},{"key":"2784_CR35","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1017\/S1355838201000863","volume":"7","author":"C Flamm","year":"2001","unstructured":"Flamm C, Hofacker IL, Maurer-Stroh S, Stadler PF, Zehl M. Design of multistable RNA molecules. RNA (New York, N.Y.) 2001; 7:254\u201365.","journal-title":"RNA (New York, N.Y.)"},{"issue":"13","key":"2784_CR36","doi-asserted-by":"publisher","first-page":"1664","DOI":"10.1002\/jcc.10296","volume":"24","author":"RM Dirks","year":"2003","unstructured":"Dirks RM, Pierce NA. A partition function algorithm for nucleic acid secondary structure including pseudoknots. J Comput Chem. 2003; 24(13):1664\u201377. https:\/\/doi.org\/10.1002\/jcc.10296 .","journal-title":"J Comput Chem"},{"key":"2784_CR37","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/978-3-642-31265-6_26","volume-title":"Combinatorial Pattern Matching","author":"Saad Sheikh","year":"2012","unstructured":"Sheikh S, Backofen R, Ponty Y. Impact of the energy model on the complexity of RNA folding with pseudoknots In: K\u00e4rkk\u00e4inen J, Stoye J, editors. Combinatorial Pattern Matching - 23rd Annual Symposium, CPM 2012, Helsinki, Finland, July 3-5, 2012. Proceedings. Lecture Notes in Computer Science. Springer: 2012. p. 321\u201333. https:\/\/doi.org\/10.1007\/978-3-642-31265-6_26 ."},{"key":"2784_CR38","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1038\/nmeth.4066","volume":"14","author":"E Rivas","year":"2017","unstructured":"Rivas E, Clements J, Eddy SR. A statistical test for conserved rna structure shows lack of evidence for structure in lncrnas. Nat Methods. 2017; 14:45\u20138. https:\/\/doi.org\/10.1038\/nmeth.4066 .","journal-title":"Nat Methods"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-019-2784-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1186\/s12859-019-2784-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-019-2784-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,16]],"date-time":"2022-09-16T21:09:40Z","timestamp":1663362580000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/s12859-019-2784-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,25]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,12]]}},"alternative-id":["2784"],"URL":"https:\/\/doi.org\/10.1186\/s12859-019-2784-7","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,4,25]]},"assertion":[{"value":"25 October 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 March 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 April 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Not applicable.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"The authors declare that they have no competing interests.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}},{"value":"Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Publisher\u2019s Note"}}],"article-number":"209"}}