{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T16:05:07Z","timestamp":1761321907774,"version":"build-2065373602"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T00:00:00Z","timestamp":1761264000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T00:00:00Z","timestamp":1761264000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-19-CE30-0021"],"award-info":[{"award-number":["ANR-19-CE30-0021"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    Inverse folding is a classic instance of negative RNA design which consists in finding a sequence that uniquely folds into a target secondary structure with respect to energy minimization. A breakthrough result of Bonnet\u00a0\n                    <jats:italic>et al.<\/jats:italic>\n                    shows that, even in simple base pairs-based (BP) models, the decision version of a mildly constrained version of inverse folding is NP-hard. In this work, we show that inverse folding can be solved in linear time for a large collection of targets, including every structure that contains no isolated BP and no isolated stack (or, equivalently, when all helices consist of\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$3^{+}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:msup>\n                            <mml:mn>3<\/mml:mn>\n                            <mml:mo>+<\/mml:mo>\n                          <\/mml:msup>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    base pairs). For structures featuring shorter helices, our linear algorithm is no longer guaranteed to produce a solution, but still does so for a large proportion of instances. Our approach introduces a notion of modulo\n                    <jats:italic>m<\/jats:italic>\n                    -separability, generalizing a property pioneered by Hales\n                    <jats:italic>et al<\/jats:italic>\n                    . Separability is a sufficient condition for the existence of a solution to the inverse folding problem. We show that, for any input secondary structure of length\n                    <jats:italic>n<\/jats:italic>\n                    , a modulo\n                    <jats:italic>m<\/jats:italic>\n                    -separated sequence can be produced in time\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\mathcal {O}(n\\,m\\, 2^m)$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>O<\/mml:mi>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mspace\/>\n                            <mml:mi>m<\/mml:mi>\n                            <mml:mspace\/>\n                            <mml:msup>\n                              <mml:mn>2<\/mml:mn>\n                              <mml:mi>m<\/mml:mi>\n                            <\/mml:msup>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    anytime such a sequence exists. Meanwhile, we show that any structure consisting of\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$3^{+}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:msup>\n                            <mml:mn>3<\/mml:mn>\n                            <mml:mo>+<\/mml:mo>\n                          <\/mml:msup>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    base pairs is either trivially non-designable, or always admits a modulo-2 separated solution. Solution sequences can thus be produced in linear time, and even be uniformly generated within the set of modulo-2 separable sequences.\n                  <\/jats:p>","DOI":"10.1186\/s13015-025-00278-6","type":"journal-article","created":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T15:56:52Z","timestamp":1761321412000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["RNA inverse folding can be solved in linear time for structures without isolated stacks or base pairs"],"prefix":"10.1186","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-0553-4789","authenticated-orcid":false,"given":"Th\u00e9o","family":"Boury","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-6766-2383","authenticated-orcid":false,"given":"Samuel","family":"Gardelle","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1645-9345","authenticated-orcid":false,"given":"Laurent","family":"Bulteau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7615-3930","authenticated-orcid":false,"given":"Yann","family":"Ponty","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,10,24]]},"reference":[{"issue":"2","key":"278_CR1","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 Chem Chem Mon. 1994;125(2):167\u201388.","journal-title":"Monatshefte f\u00fcr Chem Chem Mon"},{"key":"278_CR2","doi-asserted-by":"crossref","unstructured":"Schnall-Levin M, Chindelevitch L, Berger B. Inverting the viterbi algorithm: an abstract framework for structure design. In: ICML. ACM International Conference Proceeding Series, 2008;307: 904\u2013911. ACM","DOI":"10.1145\/1390156.1390270"},{"issue":"3","key":"278_CR3","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1089\/cmb.2019.0420","volume":"27","author":"E Bonnet","year":"2020","unstructured":"Bonnet E, Rzazewski P, Sikora F. Designing rna secondary structures is hard. J Comput Biol. 2020;27(3):302\u201316. https:\/\/doi.org\/10.1089\/cmb.2019.0420. (PMID:32160034).","journal-title":"J Comput Biol"},{"issue":"15","key":"278_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-a fast approach to inverse RNA folding. Bioinformatics. 2006;22(15):1823\u201331.","journal-title":"Bioinformatics"},{"issue":"3","key":"278_CR5","doi-asserted-by":"publisher","first-page":"607","DOI":"10.1016\/j.jmb.2003.12.041","volume":"336","author":"M Andronescu","year":"2004","unstructured":"Andronescu M, Fejes AP, Hutter F, Hoos HH, Condon A. A new algorithm for RNA secondary structure design. J Mol Biol. 2004;336(3):607\u201324. https:\/\/doi.org\/10.1016\/j.jmb.2003.12.041.","journal-title":"J Mol Biol"},{"issue":"3","key":"278_CR6","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1002\/jcc.21633","volume":"32","author":"JN Zadeh","year":"2011","unstructured":"Zadeh JN, Wolfe BR, Pierce NA. Nucleic acid sequence design via efficient ensemble defect optimization. J Comput Chem. 2011;32(3):439\u201352. https:\/\/doi.org\/10.1002\/jcc.21633.","journal-title":"J Comput Chem"},{"issue":"9","key":"278_CR7","doi-asserted-by":"publisher","first-page":"2920","DOI":"10.1093\/bioinformatics\/btaa039","volume":"36","author":"MD Retwitzer","year":"2020","unstructured":"Retwitzer MD, Reinharz V, Churkin A, Ponty Y, Waldisp\u00fchl J. Barash D incaRNAfbinv 2.0: a webserver and software with motif control for fragment-based design of RNAs. Bioinformatics. 2020;36(9):2920\u20132. https:\/\/doi.org\/10.1093\/bioinformatics\/btaa039.","journal-title":"Bioinformatics"},{"key":"278_CR8","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 Bioinform. 2012;13:260.","journal-title":"BMC Bioinform"},{"key":"278_CR9","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1186\/s12859-014-0444-5","volume":"16","author":"A Esmaili-Taheri","year":"2015","unstructured":"Esmaili-Taheri A, Ganjtabesh M. ERD: a fast and reliable tool for RNA design including constraints. BMC Bioinform. 2015;16:20\u201312011.","journal-title":"BMC Bioinform"},{"issue":"19","key":"278_CR10","doi-asserted-by":"publisher","first-page":"3114","DOI":"10.1093\/bioinformatics\/btv319","volume":"31","author":"R Kleinkauf","year":"2015","unstructured":"Kleinkauf R, Mann M, Backofen R. antaRNA: ant colony-based RNA sequence design. Bioinformatics. 2015;31(19):3114\u201321. https:\/\/doi.org\/10.1093\/bioinformatics\/btv319.","journal-title":"Bioinformatics"},{"issue":"1","key":"278_CR11","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1186\/s12859-022-04866-w","volume":"23","author":"NSC Merleau","year":"2022","unstructured":"Merleau NSC, Smerlak M. arnaque: an evolutionary algorithm for inverse pseudoknotted RNA folding inspired by l\u00e9vy flights. BMC Bioinform. 2022;23(1):335.","journal-title":"BMC Bioinform"},{"issue":"13","key":"278_CR12","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. 2013;29(13):308\u201315. https:\/\/doi.org\/10.1093\/bioinformatics\/btt217.","journal-title":"Bioinformatics"},{"key":"278_CR13","unstructured":"Yao H-T, Waldisp\u00fchl J, Ponty Y, Will S. Taming Disruptive Base Pairs to Reconcile Positive and Negative Structural Design of RNA. In: Proc. of the 25th Annual International Conferences on Computational Molecular Biology (RECOMB\u201921) 2021. https:\/\/inria.hal.science\/hal-02987566"},{"issue":"W1","key":"278_CR14","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1093\/nar\/gkv460","volume":"43","author":"JA Garcia-Martin","year":"2015","unstructured":"Garcia-Martin JA, Dotu I, Clote P. RNAiFold 2.0: a web server and software to design custom and Rfam-based RNA molecules. Nucleic Acids Res. 2015;43(W1):513\u201321. https:\/\/doi.org\/10.1093\/nar\/gkv460.","journal-title":"Nucleic Acids Res"},{"key":"278_CR15","doi-asserted-by":"publisher","DOI":"10.1186\/s12859-019-2784-7","author":"S Hammer","year":"2019","unstructured":"Hammer S, Wang W, Will S, Ponty Y. Fixed-parameter tractable sampling for RNA design with multiple target structures. BMC Bioinform. 2019. https:\/\/doi.org\/10.1186\/s12859-019-2784-7.","journal-title":"BMC Bioinform"},{"key":"278_CR16","unstructured":"Runge F, Stoll D, Falkner S, Hutter F. Learning to design RNA. In: Proceedings of ICLR 2019 2019."},{"issue":"3","key":"278_CR17","doi-asserted-by":"publisher","first-page":"835","DOI":"10.1007\/s00453-016-0196-x","volume":"79","author":"J Hales","year":"2017","unstructured":"Hales J, H\u00e9liou A, Manuch J, Ponty Y, Stacho L. Combinatorial RNA design: Designability and structure-approximating algorithm in Watson-Crick and Nussinov-Jacobson energy models. Algorithmica. 2017;79(3):835\u201356.","journal-title":"Algorithmica"},{"issue":"11","key":"278_CR18","doi-asserted-by":"publisher","first-page":"6309","DOI":"10.1073\/pnas.77.11.6309","volume":"77","author":"R Nussinov","year":"1980","unstructured":"Nussinov R, Jacobson AB. Fast algorithm for predicting the secondary structure of single-stranded RNA. Proc Natl Acad Sci. 1980;77(11):6309\u201313. https:\/\/doi.org\/10.1073\/pnas.77.11.6309.","journal-title":"Proc Natl Acad Sci"},{"key":"278_CR19","doi-asserted-by":"publisher","unstructured":"Yao H-T, Chauve C, Regnier M, Ponty Y. Exponentially few RNA structures are designable. In: Conference on Bioinformatics, Computational Biology, and Health Informatics ACM-BCB, 2019;289\u2013298. ACM Press, Niagara-Falls, United States. https:\/\/doi.org\/10.1145\/3307339.3342163 . https:\/\/inria.hal.science\/hal-02141853","DOI":"10.1145\/3307339.3342163"},{"key":"278_CR20","unstructured":"Ponty Y. Ensemble Algorithms and Analytic Combinatorics in RNA Bioinformatics and Beyond. Habilitation \u00e0 diriger des recherches, Universit\u00e9 Paris-Saclay 2020. https:\/\/theses.hal.science\/tel-03219977"},{"key":"278_CR21","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/j.tcs.2013.01.006","volume":"502","author":"WA Lorenz","year":"2013","unstructured":"Lorenz WA, Ponty Y. Non-redundant random generation algorithms for weighted context-free grammars. Theor Comput Sci. 2013;502:177\u201394. https:\/\/doi.org\/10.1016\/j.tcs.2013.01.006.","journal-title":"Theor Comput Sci"},{"key":"278_CR22","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:280\u20132. https:\/\/doi.org\/10.1093\/nar\/gkp892.","journal-title":"Nucleic Acids Res"},{"issue":"4\u20135","key":"278_CR23","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1017\/S0963548304006315","volume":"13","author":"P Duchon","year":"2004","unstructured":"Duchon P, Flajolet P, Louchard G, Schaeffer G. Boltzmann samplers for the random generation of combinatorial structures. Comb Probab Comput. 2004;13(4\u20135):577\u2013625. https:\/\/doi.org\/10.1017\/S0963548304006315.","journal-title":"Comb Probab Comput"},{"key":"278_CR24","doi-asserted-by":"publisher","unstructured":"Bodini O, Ponty Y. Multi-dimensional Boltzmann Sampling of Languages. Discrete Mathematics & Theoretical Computer Science DMTCS Proceedings vol. AM 21st International Meeting on Probabilistic Combinatorial and Asymptotic Methods in the Analysis of Algorithms (AofA\u201910) 2010. https:\/\/doi.org\/10.46298\/dmtcs.2793","DOI":"10.46298\/dmtcs.2793"},{"issue":"11","key":"278_CR25","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. 2011;18(11):1465\u201379. https:\/\/doi.org\/10.1089\/cmb.2011.0181.","journal-title":"J Comput Biol"},{"key":"278_CR26","doi-asserted-by":"publisher","DOI":"10.1186\/s13015-024-00258-2","author":"H-T Yao","year":"2024","unstructured":"Yao H-T, Marchand B, Berkemer SJ, Ponty Y, Will S. Infrared: a declarative tree decomposition-powered framework for bioinformatics. Algorithm Mol Biol. 2024. https:\/\/doi.org\/10.1186\/s13015-024-00258-2.","journal-title":"Algorithm Mol Biol"},{"key":"278_CR27","doi-asserted-by":"crossref","unstructured":"Boury T, Sidl L, Hofacker IL, Ponty Y, Yao H-T. Old dog, new tricks: Exact seeding strategy improves RNA design performances. In: Proceedings of RECOMB\u201925 2025. https:\/\/hal.science\/hal-04756160","DOI":"10.1007\/978-3-031-90252-9_9"}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-025-00278-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s13015-025-00278-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-025-00278-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T15:56:54Z","timestamp":1761321414000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/s13015-025-00278-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,24]]},"references-count":27,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2025,12]]}},"alternative-id":["278"],"URL":"https:\/\/doi.org\/10.1186\/s13015-025-00278-6","relation":{},"ISSN":["1748-7188"],"issn-type":[{"type":"electronic","value":"1748-7188"}],"subject":[],"published":{"date-parts":[[2025,10,24]]},"assertion":[{"value":"31 October 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 April 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 October 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"This research does not involve experiments on living organisms. All authors approved the publication of this research.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"The authors declare no competing interests.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"20"}}