{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T18:11:06Z","timestamp":1778609466186,"version":"3.51.4"},"reference-count":59,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,3,16]],"date-time":"2024-03-16T00:00:00Z","timestamp":1710547200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,3,16]],"date-time":"2024-03-16T00:00:00Z","timestamp":1710547200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["I 4520"],"award-info":[{"award-number":["I 4520"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-21-CE45-0034-01"],"award-info":[{"award-number":["ANR-21-CE45-0034-01"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100018694","name":"HORIZON EUROPE Marie Sklodowska-Curie Actions","doi-asserted-by":"publisher","award":["10102967"],"award-info":[{"award-number":["10102967"]}],"id":[{"id":"10.13039\/100018694","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003065","name":"University of Vienna","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100003065","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Motivation<\/jats:title>\n                    <jats:p>Many bioinformatics problems can be approached as optimization or controlled sampling tasks, and solved exactly and efficiently using Dynamic Programming (DP). However, such exact methods are typically tailored towards specific settings, complex to develop, and hard to implement and adapt to problem variations.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Methods<\/jats:title>\n                    <jats:p>We introduce the Infrared framework to overcome such hindrances for a large class of problems. Its underlying paradigm is tailored toward problems that can be declaratively formalized as sparse feature networks, a generalization of constraint networks. Classic Boolean constraints specify a search space, consisting of putative solutions whose evaluation is performed through a combination of features. Problems are then solved using generic cluster tree elimination algorithms over a tree decomposition of the feature network. Their overall complexities are linear on the number of variables, and only exponential in the treewidth of the feature network. For sparse feature networks, associated with low to moderate treewidths, these algorithms allow to find optimal solutions, or generate controlled samples, with practical empirical efficiency.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>Implementing these methods, the Infrared software allows Python programmers to rapidly develop exact optimization and sampling applications based on a tree decomposition-based efficient processing. Instead of directly coding specialized algorithms, problems are declaratively modeled as sets of variables over finite domains, whose dependencies are captured by constraints and functions. Such models are then automatically solved by generic DP algorithms. To illustrate the applicability of Infrared in bioinformatics and guide new users, we model and discuss variants of bioinformatics applications. We provide reimplementations and extensions of methods for RNA design, RNA sequence-structure alignment, parsimony-driven inference of ancestral traits in phylogenetic trees\/networks, and design of coding sequences. Moreover, we demonstrate multidimensional Boltzmann sampling. These applications of the framework\u2014together with our novel results\u2014underline the practical relevance of Infrared. Remarkably, the achieved complexities are typically equivalent to the ones of specialized algorithms and implementations.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Availability<\/jats:title>\n                    <jats:p>\n                      Infrared is available at\n                      <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"uri\" xlink:href=\"https:\/\/amibio.gitlabpages.inria.fr\/Infrared\">https:\/\/amibio.gitlabpages.inria.fr\/Infrared<\/jats:ext-link>\n                      with extensive documentation, including various usage examples and API reference; it can be installed using Conda or from source.\n                    <\/jats:p>\n                  <\/jats:sec>","DOI":"10.1186\/s13015-024-00258-2","type":"journal-article","created":{"date-parts":[[2024,3,16]],"date-time":"2024-03-16T08:01:39Z","timestamp":1710576099000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Infrared: a declarative tree decomposition-powered framework for bioinformatics"],"prefix":"10.1186","volume":"19","author":[{"given":"Hua-Ting","family":"Yao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bertrand","family":"Marchand","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sarah J.","family":"Berkemer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yann","family":"Ponty","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebastian","family":"Will","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,3,16]]},"reference":[{"issue":"2","key":"258_CR1","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1080\/15476286.2015.1017235","volume":"12","author":"M Wachsmuth","year":"2015","unstructured":"Wachsmuth M, Domin G, Lorenz R, Serfling R, Findei\u00df S, Stadler PF, M\u00f6rl M. Design criteria for synthetic riboswitches acting on transcription. RNA Biol. 2015;12(2):221\u201331. https:\/\/doi.org\/10.1080\/15476286.2015.1017235.","journal-title":"RNA Biol"},{"issue":"8","key":"258_CR2","doi-asserted-by":"publisher","first-page":"1838","DOI":"10.1021\/acssynbio.9b00142","volume":"8","author":"MJ Wu","year":"2019","unstructured":"Wu MJ, Andreasson JOL, Kladwang W, Greenleaf W, Das R. Automated design of diverse stand-alone riboswitches. ACS Synth Biol. 2019;8(8):1838\u201346. https:\/\/doi.org\/10.1021\/acssynbio.9b00142.","journal-title":"ACS Synth Biol"},{"key":"258_CR3","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33122-0_12","author":"P Rinaudo","year":"2012","unstructured":"Rinaudo P, Ponty Y, Barth D, Denise A. Tree decomposition and parameterized algorithms for RNA structure-sequence alignment including tertiary interactions and pseudoknots. Algorithms Bioinform. 2012. https:\/\/doi.org\/10.1007\/978-3-642-33122-0_12.","journal-title":"Algorithms Bioinform"},{"issue":"22","key":"258_CR4","doi-asserted-by":"publisher","first-page":"3849","DOI":"10.1093\/bioinformatics\/bty420","volume":"34","author":"H Jabbari","year":"2018","unstructured":"Jabbari H, Wark I, Montemagno C, Will S. Knotty: efficient and accurate prediction of complex RNA pseudoknot structures. Bioinformatics. 2018;34(22):3849\u201356. https:\/\/doi.org\/10.1093\/bioinformatics\/bty420.","journal-title":"Bioinformatics"},{"issue":"1","key":"258_CR5","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1186\/s13015-022-00216-w","volume":"17","author":"C Scornavacca","year":"2022","unstructured":"Scornavacca C, Weller M. Treewidth-based algorithms for the small parsimony problem on networks. Algorithms Mol Biol. 2022;17(1):15. https:\/\/doi.org\/10.1186\/s13015-022-00216-w.","journal-title":"Algorithms Mol Biol"},{"issue":"5","key":"258_CR6","doi-asserted-by":"publisher","first-page":"8091","DOI":"10.1007\/s11042-020-10139-6","volume":"80","author":"S Katoch","year":"2021","unstructured":"Katoch S, Chauhan SS, Kumar V. A review on genetic algorithm: past, present, and future. Multimed Tools Appl. 2021;80(5):8091\u2013126. https:\/\/doi.org\/10.1007\/s11042-020-10139-6.","journal-title":"Multimed Tools Appl"},{"key":"258_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/11851561_17","author":"I Mikl\u00f3s","year":"2006","unstructured":"Mikl\u00f3s I, Paige TB, Ligeti P. Efficient sampling of transpositions and inverted transpositions for bayesian MCMC. Algorithms Bioinform. 2006. https:\/\/doi.org\/10.1007\/11851561_17.","journal-title":"Algorithms Bioinform"},{"issue":"6","key":"258_CR8","doi-asserted-by":"publisher","first-page":"1770","DOI":"10.1093\/bioinformatics\/btac004","volume":"38","author":"J Neumann","year":"2022","unstructured":"Neumann J, Lin YT, Mallela A, Miller EF, Colvin J, Duprat AT, Chen Y, Hlavacek WS, Posner RG. Implementation of a practical Markov chain Monte Carlo sampling algorithm in PyBioNetFit. Bioinformatics. 2022;38(6):1770\u20132. https:\/\/doi.org\/10.1093\/bioinformatics\/btac004.","journal-title":"Bioinformatics"},{"key":"258_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"RG Downey","year":"1999","unstructured":"Downey RG, Fellows MR. Parameterized Complexity. New York: Springer; 1999. https:\/\/doi.org\/10.1007\/978-1-4612-0515-9."},{"key":"258_CR10","volume-title":"Handbook of constraint programming (Foundations of Artificial Intelligence)","author":"F Rossi","year":"2006","unstructured":"Rossi F, Beek P, Walsh T. Handbook of constraint programming (Foundations of Artificial Intelligence). Walthm: Elsevier Science; 2006."},{"key":"258_CR11","doi-asserted-by":"publisher","DOI":"10.1016\/B978-1-55860-890-0.X5000","volume-title":"Constraint Proc","author":"R Dechter","year":"2003","unstructured":"Dechter R. Constraint Proc. San Francisco: Morgan Kaufmann; 2003. https:\/\/doi.org\/10.1016\/B978-1-55860-890-0.X5000."},{"key":"258_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-01583-0","volume-title":"Reasoning with probabilistic and deterministic graphical models","author":"R Dechter","year":"2019","unstructured":"Dechter R. Reasoning with probabilistic and deterministic graphical models. Cham: Springer; 2019. https:\/\/doi.org\/10.1007\/978-3-031-01583-0."},{"issue":"3","key":"258_CR13","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1016\/j.ic.2009.03.008","volume":"208","author":"HL Bodlaender","year":"2010","unstructured":"Bodlaender HL, Koster AMCA. Treewidth computations i. upper bounds. Inform Comput. 2010;208(3):259\u201375. https:\/\/doi.org\/10.1016\/j.ic.2009.03.008.","journal-title":"Inform Comput"},{"key":"258_CR14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan M, Fomin FV, Kowalik \u0141, Lokshtanov D, Marx D, Pilipczuk M, Pilipczuk M, Saurabh S. Parameterized Algorithms. Cham: Springer; 2015."},{"key":"258_CR15","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 Proceedings, Vienna, Austria. 2010; 49\u201364.","DOI":"10.46298\/dmtcs.2793"},{"issue":"1","key":"258_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s12859-019-2784-7","volume":"20","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 Bioinf. 2019;20(1):1\u201313. https:\/\/doi.org\/10.1186\/s12859-019-2784-7.","journal-title":"BMC Bioinf"},{"key":"258_CR17","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: Research in Computational Molecular Biology - 25th Annual International Conference, RECOMB 2021. Lecture Notes in Computer Science. Springer, Padova, Italy 2021"},{"issue":"1","key":"258_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s13015-022-00213-z","volume":"17","author":"B Marchand","year":"2022","unstructured":"Marchand B, Ponty Y, Bulteau L. Tree diet: reducing the treewidth to unlock FPT algorithms in RNA bioinformatics. Algorithms Mol Biol. 2022;17(1):1\u201317. https:\/\/doi.org\/10.1186\/s13015-022-00213-z.","journal-title":"Algorithms Mol Biol"},{"key":"258_CR19","doi-asserted-by":"publisher","unstructured":"Marchand B, Will S, Berkemer SJ, Bulteau L, Ponty Y. Automated design of dynamic programming schemes for RNA folding with pseudoknots. In: Boucher, C., Rahmann, S. (eds.) 22nd nternational Workshop on Algorithms in Bioinformatics (WABI 2022). Leibniz International Proceedings in Informatics (LIPIcs), vol. 242, pp. 7\u20131724. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany 2022. https:\/\/doi.org\/10.4230\/LIPIcs.WABI.2022.7 . https:\/\/drops.dagstuhl.de\/opus\/volltexte\/2022\/17041","DOI":"10.4230\/LIPIcs.WABI.2022.7"},{"issue":"1","key":"258_CR20","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1007\/s10601-007-9032-x","volume":"13","author":"S Will","year":"2008","unstructured":"Will S, Busch A, Backofen R. Efficient sequence alignment with side-constraints by cluster tree elimination. Constraints. 2008;13(1):110\u201329. https:\/\/doi.org\/10.1007\/s10601-007-9032-x.","journal-title":"Constraints"},{"issue":"6\u20137","key":"258_CR21","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(6\u20137):1105\u201319. https:\/\/doi.org\/10.1002\/bip.360290621.","journal-title":"Biopolymers"},{"key":"258_CR22","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. https:\/\/doi.org\/10.1093\/nar\/gkg938.","journal-title":"Nucleic Acids Res"},{"issue":"1","key":"258_CR23","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1093\/biomet\/57.1.97","volume":"57","author":"WK Hastings","year":"1970","unstructured":"Hastings WK. Monte carlo sampling methods using markov chains and their applications. Biometrika. 1970;57(1):97\u2013109. https:\/\/doi.org\/10.1093\/biomet\/57.1.97.","journal-title":"Biometrika"},{"issue":"22","key":"258_CR24","doi-asserted-by":"publisher","first-page":"2715","DOI":"10.1093\/bioinformatics\/btl472","volume":"22","author":"U Roshan","year":"2006","unstructured":"Roshan U, Livesay DR. Probalign: multiple sequence alignment using partition function posterior probabilities. Bioinformatics. 2006;22(22):2715\u201321. https:\/\/doi.org\/10.1093\/bioinformatics\/btl472.","journal-title":"Bioinformatics"},{"issue":"5","key":"258_CR25","doi-asserted-by":"publisher","first-page":"900","DOI":"10.1261\/rna.029041.111","volume":"18","author":"S Will","year":"2012","unstructured":"Will S, Joshi T, Hofacker IL, Stadler PF, Backofen R. LocARNA-P: accurate boundary prediction and improved detection of structural RNAs. RNA. 2012;18(5):900\u201314. https:\/\/doi.org\/10.1261\/rna.029041.111.","journal-title":"RNA"},{"key":"258_CR26","unstructured":"Schulte C, Tack G, Lagerkvist MZ. Modeling and programming with Gecode. Schulte, Christian and Tack, Guido and Lagerkvist, Mikael 2010;1"},{"key":"258_CR27","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1016\/j.artint.2016.06.005","volume":"238","author":"D Allouche","year":"2016","unstructured":"Allouche D, Bessiere C, Boizumault P, Givry S, Gutierrez P, Lee JHM, Leung KL, Loudni S, M\u00e9tivier J-P, Schiex T, Wu Y. Tractability-preserving transformations of global cost functions. Artif Intell. 2016;238:166\u201389. https:\/\/doi.org\/10.1016\/j.artint.2016.06.005.","journal-title":"Artif Intell"},{"key":"258_CR28","unstructured":"Yao H-T, Ponty Y, Will S. Developing complex RNA design applications in the Infrared framework. (2022). preprint; to be published. https:\/\/hal.science\/hal-03711828"},{"issue":"3","key":"258_CR29","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1093\/comjnl\/bxm037","volume":"51","author":"HL Bodlaender","year":"2008","unstructured":"Bodlaender HL, Koster AM. Combinatorial optimization on graphs of bounded treewidth. Comput J. 2008;51(3):255\u201369.","journal-title":"Comput J"},{"key":"258_CR30","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/S1574-6526(06)80011-8","volume":"2","author":"R Dechter","year":"2006","unstructured":"Dechter R, Handbook of Constraint Programming. Tractable Structures for Constraint Satisfaction Problems. In. Found Artificial Intell. 2006;2:209\u201344. https:\/\/doi.org\/10.1016\/S1574-6526(06)80011-8.","journal-title":"Found Artificial Intell"},{"key":"258_CR31","doi-asserted-by":"publisher","first-page":"893","DOI":"10.1007\/978-3-540-77120-3_77","volume-title":"International symposium on algorithms and computation (ISAAC 2007)","author":"E Bachoore","year":"2007","unstructured":"Bachoore E, Bodlaender HL. Weighted treewidth algorithmic techniques and results. In: Tokuyama T, editor. International symposium on algorithms and computation (ISAAC 2007). Berlin: Springer; 2007. p. 893\u2013903. https:\/\/doi.org\/10.1007\/978-3-540-77120-3_77."},{"issue":"2","key":"258_CR32","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S Arnborg","year":"1987","unstructured":"Arnborg S, Corneil DG, Proskurowski A. Complexity of finding embeddings in a k-tree. SIAM J Algebraic Discrete Methods. 1987;8(2):277\u201384. https:\/\/doi.org\/10.1137\/0608024.","journal-title":"SIAM J Algebraic Discrete Methods"},{"issue":"4","key":"258_CR33","doi-asserted-by":"publisher","first-page":"1283","DOI":"10.1007\/s10878-018-0353-z","volume":"37","author":"H Tamaki","year":"2019","unstructured":"Tamaki H. Positive-instance driven dynamic programming for treewidth. J Combinatorial Optimizat. 2019;37(4):1283\u2013311.","journal-title":"J Combinatorial Optimizat"},{"key":"258_CR34","doi-asserted-by":"crossref","unstructured":"Bodlaender HL. A linear time algorithm for finding tree-decompositions of small treewidth. In: Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of Computing. 1993;226\u2013234.","DOI":"10.1145\/167088.167161"},{"issue":"5423","key":"258_CR35","doi-asserted-by":"publisher","first-page":"2124","DOI":"10.1126\/science.284.5423.2124","volume":"284","author":"WF Doolittle","year":"1999","unstructured":"Doolittle WF. Phylogenetic classification and the universal tree. Science. 1999;284(5423):2124\u20138. https:\/\/doi.org\/10.1126\/science.284.5423.2124.","journal-title":"Science"},{"issue":"4","key":"258_CR36","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1093\/sysbio\/20.4.406","volume":"20","author":"WM Fitch","year":"1971","unstructured":"Fitch WM. Toward defining the course of evolution: minimum change for a specific tree topology. Syst Biol. 1971;20(4):406\u201316. https:\/\/doi.org\/10.1093\/sysbio\/20.4.406.","journal-title":"Syst Biol"},{"issue":"1","key":"258_CR37","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1007\/BF01681346","volume":"9","author":"D Sankoff","year":"1975","unstructured":"Sankoff D, Rousseau P. Locating the vertices of a steiner tree in an arbitrary metric space. Math Program. 1975;9(1):240\u20136. https:\/\/doi.org\/10.1007\/BF01681346.","journal-title":"Math Program"},{"issue":"15","key":"258_CR38","doi-asserted-by":"publisher","first-page":"1974","DOI":"10.1093\/bioinformatics\/btp250","volume":"25","author":"K Darty","year":"2009","unstructured":"Darty K, Denise A, Ponty Y. VARNA: interactive drawing and editing of the RNA secondary structure. Bioinformatics. 2009;25(15):1974.","journal-title":"Bioinformatics"},{"key":"258_CR39","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 Bioinf. 2015;16:280. https:\/\/doi.org\/10.1186\/s12859-015-0706-x.","journal-title":"BMC Bioinf"},{"issue":"5","key":"258_CR40","doi-asserted-by":"publisher","first-page":"911","DOI":"10.1006\/jmbi.1999.2700","volume":"288","author":"DH Mathews","year":"1999","unstructured":"Mathews DH, Sabina J, Zuker M, Turner DH. Expanded sequence dependence of thermodynamic parameters improves prediction of RNA secondary structure. J Mol Biol. 1999;288(5):911\u201340. https:\/\/doi.org\/10.1006\/jmbi.1999.2700.","journal-title":"J Mol Biol"},{"issue":"Suppl\u20131","key":"258_CR41","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1093\/nar\/gkp892","volume":"38","author":"DH Turner","year":"2010","unstructured":"Turner DH, Mathews DH. NNDB: the nearest neighbor parameter database for predicting stability of nucleic acid secondary structure. Nucleic Acids Res. 2010;38(Suppl\u20131):280\u20132.","journal-title":"Nucleic Acids Res"},{"issue":"3","key":"258_CR42","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","volume":"48","author":"SB Needleman","year":"1970","unstructured":"Needleman SB, Wunsch CD. A general method applicable to the search for similarities in the amino acid sequence of two proteins. J Mol Biol. 1970;48(3):443\u201353. https:\/\/doi.org\/10.1016\/0022-2836(70)90057-4.","journal-title":"J Mol Biol"},{"issue":"3","key":"258_CR43","doi-asserted-by":"publisher","first-page":"705","DOI":"10.1016\/0022-2836(82)90398-9","volume":"162","author":"O Gotoh","year":"1982","unstructured":"Gotoh O. An improved algorithm for matching biological sequences. J Mol Biol. 1982;162(3):705\u20138. https:\/\/doi.org\/10.1016\/0022-2836(82)90398-9.","journal-title":"J Mol Biol"},{"issue":"5","key":"258_CR44","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1093\/bioinformatics\/8.5.481","volume":"8","author":"K-M Chao","year":"1992","unstructured":"Chao K-M, Pearson WR, Miller W. Aligning two sequences within a specified diagonal band. Bioinformatics. 1992;8(5):481\u20137.","journal-title":"Bioinformatics"},{"key":"258_CR45","first-page":"482","volume-title":"A regular language membership constraint for finite sequences of Variables. In: principles and practice of constraint programming - CP","author":"G Pesant","year":"2001","unstructured":"Pesant G. A regular language membership constraint for finite sequences of Variables. In: principles and practice of constraint programming - CP. Berlin: Springer; 2001. p. 482\u201395."},{"key":"258_CR46","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: BCB\u201913: Proceedings of the International Conference on Bioinformatics, Computational Biology and Biomedical Informatics, pp. 229\u2013238. Association for Computing Machinery, New York, NY, USA (2013). https:\/\/doi.org\/10.1145\/2506583.2506623","DOI":"10.1145\/2506583.2506623"},{"issue":"W1","key":"258_CR47","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(W1):480\u20135. https:\/\/doi.org\/10.1093\/nar\/gkt461.","journal-title":"Nucleic Acids Res"},{"issue":"13","key":"258_CR48","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":"258_CR49","volume-title":"Adv Design Struct RNAs RNA RedPrint: RNA Bioinformatics","author":"Y Ponty","year":"2020","unstructured":"Ponty Y, Hammer S, Yao H-T, Will S. Adv Design Struct RNAs RNA RedPrint: RNA Bioinformatics. Berlin: Springer; 2020."},{"key":"258_CR50","unstructured":"Boury, T., Ponty, Y., Reinharz, V.: Automatic exploration of the natural variability of RNA non-canonical geometric patterns with a parameterized sampling technique. In: 23nd International Workshop on Algorithms in Bioinformatics (WABI 2023). Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2023). https:\/\/hal.science\/hal-04094288"},{"issue":"18","key":"258_CR51","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. 2017;33(18):2850\u20138. https:\/\/doi.org\/10.1093\/bioinformatics\/btx263.","journal-title":"Bioinformatics"},{"key":"258_CR52","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1016\/j.dam.2017.07.015","volume":"246","author":"P Gambette","year":"2018","unstructured":"Gambette P, Gunawan AD, Labarre A, Vialette S, Zhang L. Solving the tree containment problem in linear time for nearly stable phylogenetic networks. Discrete Appl Math. 2018;246:62\u201379.","journal-title":"Discrete Appl Math"},{"key":"258_CR53","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1007\/978-3-540-24605-3_37","volume-title":"An extensible SAT-solver In Theory and Applications of Satisfiability Testing","author":"N E\u00e9n","year":"2004","unstructured":"E\u00e9n N, S\u00f6rensson N. An extensible SAT-solver In Theory and Applications of Satisfiability Testing. Berlin: Springer; 2004. p. 502\u201318. https:\/\/doi.org\/10.1007\/978-3-540-24605-3_37."},{"issue":"53","key":"258_CR54","first-page":"157","volume":"46","author":"II Cplex","year":"2009","unstructured":"Cplex II. V12. 1: User\u2019s manual for CPLEX. Int Business Mach Corporat. 2009;46(53):157.","journal-title":"Int Business Mach Corporat"},{"issue":"3","key":"258_CR55","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/j.scico.2003.12.005","volume":"51","author":"R Giegerich","year":"2004","unstructured":"Giegerich R, Meyer C, Steffen P. A discipline of dynamic programming over sequence data. Sci Comput Programming. 2004;51(3):215\u201363. https:\/\/doi.org\/10.1016\/j.scico.2003.12.005.","journal-title":"Sci Comput Programming"},{"issue":"5","key":"258_CR56","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1093\/bioinformatics\/btt022","volume":"29","author":"G Sauthoff","year":"2013","unstructured":"Sauthoff G, M\u00f6hl M, Janssen S, Giegerich R. Bellman\u2019s GAP\u2013a language and compiler for dynamic programming in sequence analysis. Bioinformatics. 2013;29(5):551\u201360. https:\/\/doi.org\/10.1093\/bioinformatics\/btt022.","journal-title":"Bioinformatics"},{"issue":"12","key":"258_CR57","doi-asserted-by":"publisher","first-page":"1124","DOI":"10.1002\/bip.22337","volume":"99","author":"SH Zu","year":"2013","unstructured":"Siederdissen H\u00f6ner Zu, C, Hammer S, Abfalter I, Hofacker IL, Flamm C, Stadler PF. Computational design of RNAs with complex energy landscapes. Biopolymers. 2013;99(12):1124\u201336. https:\/\/doi.org\/10.1002\/bip.22337.","journal-title":"Biopolymers"},{"key":"258_CR58","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/j.tcs.2016.05.032","volume":"639","author":"M Riechert","year":"2016","unstructured":"Riechert M, Siederdissen C, Stadler PF. Algebraic dynamic programming for multiple context-free grammars. Theoret Comput Sci. 2016;639:91\u2013109. https:\/\/doi.org\/10.1016\/j.tcs.2016.05.032.","journal-title":"Theoret Comput Sci"},{"key":"258_CR59","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1093\/bioinformatics\/btx269","volume":"33","author":"J Mich\u00e1lik","year":"2017","unstructured":"Mich\u00e1lik J, Touzet H, Ponty Y. Efficient approximations of RNA kinetics landscape using non-redundant sampling. Bioinformatics. 2017;33:283\u201392. https:\/\/doi.org\/10.1093\/bioinformatics\/btx269.","journal-title":"Bioinformatics"}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-024-00258-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s13015-024-00258-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-024-00258-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,16]],"date-time":"2024-03-16T08:01:52Z","timestamp":1710576112000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/s13015-024-00258-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,16]]},"references-count":59,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2024,12]]}},"alternative-id":["258"],"URL":"https:\/\/doi.org\/10.1186\/s13015-024-00258-2","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-3366298\/v1","asserted-by":"object"}]},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,16]]},"assertion":[{"value":"18 September 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 February 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 March 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"13"}}