{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,21]],"date-time":"2026-05-21T16:42:54Z","timestamp":1779381774209,"version":"3.53.1"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,12,1]],"date-time":"2023-12-01T00:00:00Z","timestamp":1701388800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,12,1]],"date-time":"2023-12-01T00:00:00Z","timestamp":1701388800000},"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-CE45-0023"],"award-info":[{"award-number":["ANR-19-CE45-0023"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010665","name":"H2020 Marie Sk\u0142odowska-Curie Actions","doi-asserted-by":"publisher","award":["101029676"],"award-info":[{"award-number":["101029676"]}],"id":[{"id":"10.13039\/100010665","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><jats:p>Although RNA secondary structure prediction is a textbook application of dynamic programming (DP) and routine task in RNA structure analysis, it remains challenging whenever pseudoknots come into play. Since the prediction of pseudoknotted structures by minimizing (realistically modelled) energy is NP-hard, specialized algorithms have been proposed for restricted conformation classes that capture the most frequently observed configurations. To achieve good performance, these methods rely on specific and carefully hand-crafted DP schemes. In contrast, we generalize and fully automatize the design of DP pseudoknot prediction algorithms. For this purpose, we formalize the problem of designing DP algorithms for an (infinite) class of conformations, modeled by (a finite number of) fatgraphs, and automatically build DP schemes minimizing their algorithmic complexity. We propose an algorithm for the problem, based on the tree-decomposition of a well-chosen representative structure, which we simplify and reinterpret as a DP scheme. The algorithm is fixed-parameter tractable for the treewidth <jats:italic>tw<\/jats:italic> of the fatgraph, and its output represents a <jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathcal {O}}(n^{tw+1})$$<\/jats:tex-math><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:msup>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mrow>\n                        <mml:mi>t<\/mml:mi>\n                        <mml:mi>w<\/mml:mi>\n                        <mml:mo>+<\/mml:mo>\n                        <mml:mn>1<\/mml:mn>\n                      <\/mml:mrow>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> algorithm (and even possibly <jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathcal {O}}(n^{tw})$$<\/jats:tex-math><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:msup>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mrow>\n                        <mml:mi>tw<\/mml:mi>\n                      <\/mml:mrow>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> in simple energy models) for predicting the MFE folding of an RNA of length <jats:italic>n<\/jats:italic>. We demonstrate, for the most common pseudoknot classes, that our automatically generated algorithms achieve the same complexities as reported in the literature for hand-crafted schemes. Our framework supports general energy models, partition function computations, recursive substructures and partial folding, and could pave the way for algebraic dynamic programming beyond the context-free case.<\/jats:p>","DOI":"10.1186\/s13015-023-00229-z","type":"journal-article","created":{"date-parts":[[2023,12,1]],"date-time":"2023-12-01T05:02:57Z","timestamp":1701406977000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Automated design of dynamic programming schemes for RNA folding with pseudoknots"],"prefix":"10.1186","volume":"18","author":[{"given":"Bertrand","family":"Marchand","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sebastian","family":"Will","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sarah J.","family":"Berkemer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yann","family":"Ponty","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Laurent","family":"Bulteau","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,12,1]]},"reference":[{"issue":"13","key":"229_CR1","doi-asserted-by":"publisher","first-page":"3406","DOI":"10.1093\/nar\/gkg595","volume":"31","author":"M Zuker","year":"2003","unstructured":"Zuker M. Mfold web server for nucleic acid folding and hybridization prediction. Nucleic Acids Res. 2003;31(13):3406\u201315.","journal-title":"Nucleic Acids Res"},{"key":"229_CR2","doi-asserted-by":"publisher","DOI":"10.1186\/1748-7188-6-26","author":"R Lorenz","year":"2011","unstructured":"Lorenz R, H\u00f6ner Bernhart S, Zu Siederdissen C, Tafer H, Flamm C, Stadler P, Hofacker I. ViennaRNA Package 2.0. Algorithms Mol Biol. 2011. https:\/\/doi.org\/10.1186\/1748-7188-6-26.","journal-title":"Algorithms Mol Biol"},{"issue":"1","key":"229_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/1471-2105-11-129","volume":"11","author":"JS Reuter","year":"2010","unstructured":"Reuter JS, Mathews DH. RNAstructure: software for rna secondary structure prediction and analysis. BMC Bioinform. 2010;11(1):1\u20139.","journal-title":"BMC Bioinform"},{"issue":"14","key":"229_CR4","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1093\/bioinformatics\/btl246","volume":"22","author":"CB Do","year":"2006","unstructured":"Do CB, Woods DA, Batzoglou S. CONTRAfold: RNA secondary structure prediction without physics-based models. Bioinformatics. 2006;22(14):90\u20138.","journal-title":"Bioinformatics"},{"issue":"11","key":"229_CR5","doi-asserted-by":"publisher","first-page":"1525","DOI":"10.1089\/cmb.2011.0184","volume":"18","author":"S Zakov","year":"2011","unstructured":"Zakov S, Goldberg Y, Elhadad M, Ziv-Ukelson M. Rich parameterization improves RNA structure prediction. J Comput Biol. 2011;18(11):1525\u201342.","journal-title":"J Comput Biol"},{"issue":"1","key":"229_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1038\/s41467-021-21194-4","volume":"12","author":"K Sato","year":"2021","unstructured":"Sato K, Akiyama M, Sakakibara Y. RNA secondary structure prediction using deep learning with thermodynamic integration. Nature Commun. 2021;12(1):1\u20139.","journal-title":"Nature Commun"},{"issue":"47","key":"229_CR7","doi-asserted-by":"publisher","first-page":"11665","DOI":"10.1021\/bi00162a001","volume":"31","author":"E Ten Dam","year":"1992","unstructured":"Ten Dam E, Pleij K, Draper D. Structural and functional aspects of RNA pseudoknots. Biochemistry. 1992;31(47):11665\u201376.","journal-title":"Biochemistry"},{"issue":"1\u20133","key":"229_CR8","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/S0166-218X(00)00186-4","volume":"104","author":"T Akutsu","year":"2000","unstructured":"Akutsu T. Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots. Discrete Appl Mathemat. 2000;104(1\u20133):45\u201362.","journal-title":"Discrete Appl Mathemat"},{"issue":"9","key":"229_CR9","doi-asserted-by":"publisher","first-page":"2634","DOI":"10.1093\/nar\/gkl346","volume":"34","author":"S Cao","year":"2006","unstructured":"Cao S, Chen S-J. Predicting RNA pseudoknot folding thermodynamics. Nucleic Acids Res. 2006;34(9):2634\u201352. https:\/\/doi.org\/10.1093\/nar\/gkl346.","journal-title":"Nucleic Acids Res"},{"issue":"5","key":"229_CR10","doi-asserted-by":"publisher","first-page":"2053","DOI":"10.1006\/jmbi.1998.2436","volume":"285","author":"E Rivas","year":"1999","unstructured":"Rivas E, Eddy SR. A dynamic programming algorithm for RNA structure prediction including pseudoknots. J Mol Biol. 1999;285(5):2053\u201368.","journal-title":"J Mol Biol"},{"issue":"13","key":"229_CR11","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.","journal-title":"J Comput Chem"},{"issue":"8","key":"229_CR12","doi-asserted-by":"publisher","first-page":"1076","DOI":"10.1093\/bioinformatics\/btr090","volume":"27","author":"CM Reidys","year":"2011","unstructured":"Reidys CM, Huang FW, Andersen JE, Penner RC, Stadler PF, Nebel ME. Topology and prediction of RNA pseudoknots. Bioinformatics. 2011;27(8):1076\u201385.","journal-title":"Bioinformatics"},{"issue":"22","key":"229_CR13","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.","journal-title":"Bioinformatics"},{"issue":"10","key":"229_CR14","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. 2005;11(10):1494\u2013504.","journal-title":"RNA"},{"issue":"13","key":"229_CR15","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1093\/bioinformatics\/btr215","volume":"27","author":"K Sato","year":"2011","unstructured":"Sato K, Kato Y, Hamada M, Akutsu T, Asai K. IPknot: fast and accurate prediction of RNA secondary structures with pseudoknots using integer programming. Bioinformatics. 2011;27(13):85\u201393.","journal-title":"Bioinformatics"},{"issue":"1","key":"229_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/1471-2105-15-147","volume":"15","author":"H Jabbari","year":"2014","unstructured":"Jabbari H, Condon A. A fast and robust iterative algorithm for prediction of RNA pseudoknotted secondary structures. BMC Bioinform. 2014;15(1):1\u201317.","journal-title":"BMC Bioinform"},{"issue":"11","key":"229_CR17","doi-asserted-by":"publisher","first-page":"1575","DOI":"10.1089\/cmb.2010.0006","volume":"17","author":"CM Reidys","year":"2010","unstructured":"Reidys CM, Wang RR. Shapes of RNA pseudoknot structures. J Comput Biol. 2010;17(11):1575\u201390.","journal-title":"J Comput Biol"},{"issue":"3","key":"229_CR18","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1089\/cmb.2009.0168","volume":"17","author":"M M\u00f6hl","year":"2010","unstructured":"M\u00f6hl M, Will S, Backofen R. Lifting prediction to alignment of RNA pseudoknots. J Comput Biol. 2010;17(3):429\u201342.","journal-title":"J Comput Biol"},{"issue":"2","key":"229_CR19","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1089\/cmb.2006.13.267","volume":"13","author":"C Alkan","year":"2006","unstructured":"Alkan C, Karako\u00e7 E, Nadeau JH, Sahinalp SC, Zhang K. RNA-RNA interaction prediction and antisense RNA target search. J Comput Biol. 2006;13(2):267\u201382. https:\/\/doi.org\/10.1089\/cmb.2006.13.267.","journal-title":"J Comput Biol"},{"issue":"10","key":"229_CR20","doi-asserted-by":"publisher","first-page":"2665","DOI":"10.1021\/acssynbio.9b00523","volume":"9","author":"ME Fornace","year":"2020","unstructured":"Fornace ME, Porubsky NJ, Pierce NA. A unified dynamic programming framework for the analysis of interacting nucleic acid strands: enhanced models, scalability, and speed. ACS Synt Biol. 2020;9(10):2665\u201378. https:\/\/doi.org\/10.1021\/acssynbio.9b00523.","journal-title":"ACS Synt Biol"},{"issue":"3","key":"229_CR21","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. Comp J. 2008;51(3):255\u201369.","journal-title":"Comp J"},{"key":"229_CR22","doi-asserted-by":"crossref","unstructured":"Rinaudo P, Ponty Y, Barth D, Denise A Tree decomposition and parameterized algorithms for RNA structure-sequence alignment including tertiary interactions and pseudoknots. In: International Workshop on Algorithms in Bioinformatics, 149\u2013164 (2012). Springer","DOI":"10.1007\/978-3-642-33122-0_12"},{"issue":"6","key":"229_CR23","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender HL. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J Comput. 1996;25(6):1305\u201317.","journal-title":"SIAM J Comput"},{"issue":"1","key":"229_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1515\/mlbmb-2017-0001","volume":"5","author":"F Huang","year":"2017","unstructured":"Huang F, Reidys C, Rezazadegan R. Fatgraph models of RNA structure. Comput Mathemat Biophy. 2017;5(1):1\u201320.","journal-title":"Comput Mathemat Biophy"},{"issue":"4","key":"229_CR25","doi-asserted-by":"publisher","first-page":"1558","DOI":"10.1016\/j.aim.2007.11.016","volume":"217","author":"M Loebl","year":"2008","unstructured":"Loebl M, Moffatt I. The chromatic polynomial of fatgraphs and its categorification. Adv Mathemat. 2008;217(4):1558\u201387.","journal-title":"Adv Mathemat"},{"issue":"10","key":"229_CR26","doi-asserted-by":"publisher","first-page":"1249","DOI":"10.1002\/cpa.20340","volume":"63","author":"RC Penner","year":"2010","unstructured":"Penner RC, Knudsen M, Wiuf C, Andersen JE. Fatgraph models of proteins. Commun Pure Appl Mathemat. 2010;63(10):1249\u201397.","journal-title":"Commun Pure Appl Mathemat"},{"issue":"16","key":"229_CR27","doi-asserted-by":"publisher","first-page":"4843","DOI":"10.1093\/nar\/gkh779","volume":"32","author":"R Giegerich","year":"2004","unstructured":"Giegerich R, Vo\u00df B, Rehmsmeier M. Abstract shapes of rna. Nucleic Acids Res. 2004;32(16):4843\u201351.","journal-title":"Nucleic Acids Res"},{"key":"229_CR28","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."},{"issue":"2","key":"229_CR29","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 ak-tree. SIAM J Algeb Discrete Meth. 1987;8(2):277\u201384.","journal-title":"SIAM J Algeb Discrete Meth"},{"issue":"3","key":"229_CR30","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 AM. Treewidth computations i. upper bounds. Inform Comput. 2010;208(3):259\u201375.","journal-title":"Inform Comput"},{"issue":"4","key":"229_CR31","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 Comb Optim. 2019;37(4):1283\u2013311.","journal-title":"J Comb Optim"},{"key":"229_CR32","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1207.4109","author":"V Gogate","year":"2012","unstructured":"Gogate V, Dechter R. A complete anytime algorithm for treewidth. arXiv. 2012. https:\/\/doi.org\/10.48550\/arXiv.1207.4109.","journal-title":"arXiv"},{"key":"229_CR33","unstructured":"Yao H-T, Waldisp\u00fchl J, Ponty Y, Will S. 2021. Taming Disruptive Base Pairs to Reconcile Positive and Negative Structural Design of RNA. In: RECOMB 2021-25th International Conference on Research in Computational Molecular Biology."},{"key":"229_CR34","doi-asserted-by":"publisher","DOI":"10.1186\/s13015-022-00216-w","author":"C Scornavacca","year":"2021","unstructured":"Scornavacca C, Weller M. Treewidth-based algorithms for the small parsimony problem on networks. Algorit Mole Biol. 2021. https:\/\/doi.org\/10.1186\/s13015-022-00216-w.","journal-title":"Algorit Mole Biol"},{"issue":"1","key":"229_CR35","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1090\/S0273-0979-05-01088-8","volume":"43","author":"L Lov\u00e1sz","year":"2006","unstructured":"Lov\u00e1sz L. Graph minor theory. Bull Am Mathemat Soc. 2006;43(1):75\u201386.","journal-title":"Bull Am Mathemat Soc"},{"issue":"3","key":"229_CR36","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/j.disc.2005.12.017","volume":"306","author":"HL Bodlaender","year":"2006","unstructured":"Bodlaender HL, Koster AM. Safe separators for treewidth. Discrete Mathemat. 2006;306(3):337\u201350.","journal-title":"Discrete Mathemat"},{"issue":"1","key":"229_CR37","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1137\/S0097539799359683","volume":"31","author":"V Bouchitt\u00e9","year":"2001","unstructured":"Bouchitt\u00e9 V, Todinca I. Treewidth and minimum fill-in: grouping the minimal separators. SIAM J Comput. 2001;31(1):212\u201332.","journal-title":"SIAM J Comput"},{"issue":"11","key":"229_CR38","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 Nat Acad Sci. 1980;77(11):6309\u201313.","journal-title":"Proc Nat Acad Sci"},{"issue":"6","key":"229_CR39","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1093\/bioinformatics\/15.6.440","volume":"15","author":"RB Lyngs\u00f8","year":"1999","unstructured":"Lyngs\u00f8 RB, Zuker M, Pedersen CN. Fast evaluation of internal loops in RNA secondary structure prediction. Bioinformatics. 1999;15(6):440\u20135. https:\/\/doi.org\/10.1093\/bioinformatics\/15.6.440.","journal-title":"Bioinformatics"},{"issue":"6\u20137","key":"229_CR40","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"},{"issue":"24","key":"229_CR41","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(24):7280\u2013301. https:\/\/doi.org\/10.1093\/nar\/gkg938.","journal-title":"Nucleic Acids Res"},{"key":"229_CR42","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1007\/978-3-642-23038-7_22","volume-title":"Algorit Bioinform","author":"Y Ponty","year":"2011","unstructured":"Ponty Y, Saule C. A combinatorial framework for designing (pseudoknotted) RNA algorithms. In: Przytycka TM, Sagot M-F, editors. Algorit Bioinform. Berlin, Heidelberg: Springer; 2011. p. 250\u201369."},{"key":"229_CR43","doi-asserted-by":"publisher","DOI":"10.12688\/f1000research.29032.2","author":"F M\u00f6lder","year":"2021","unstructured":"M\u00f6lder F, Jablonski KP, Letcher B, Hall MB, Tomkins-Tinch CH, Sochat V, Forster J, Lee S, Twardziok SO, Kanitz A, et al. Sustainable data analysis with snakemake. F1000Research. 2021. https:\/\/doi.org\/10.12688\/f1000research.29032.2.","journal-title":"F1000Research"},{"key":"229_CR44","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, Stadler PF. Algebraic dynamic programming for multiple context-free grammars. Theoret Comp Sci. 2016;639:91\u2013109. https:\/\/doi.org\/10.1016\/j.tcs.2016.05.032.","journal-title":"Theoret Comp Sci"},{"issue":"6","key":"229_CR45","doi-asserted-by":"publisher","first-page":"803","DOI":"10.1089\/cmb.2008.0219","volume":"16","author":"H-L Chen","year":"2009","unstructured":"Chen H-L, Condon A, Jabbari H. An O$$(n^5)$$ algorithm for MFE prediction of kissing hairpins and 4-chains in nucleic acids. J Comput Biol. 2009;16(6):803\u201315.","journal-title":"J Comput Biol"},{"issue":"4","key":"229_CR46","first-page":"1","volume":"20","author":"M Quadrini","year":"2019","unstructured":"Quadrini M, Tesei L, Merelli E. An algebraic language for RNA pseudoknots comparison. BMC Bioinform. 2019;20(4):1\u201318.","journal-title":"BMC Bioinform"},{"issue":"4","key":"229_CR47","doi-asserted-by":"publisher","first-page":"135","DOI":"10.3390\/a10040135","volume":"10","author":"SJ Berkemer","year":"2017","unstructured":"Berkemer SJ, Siederdissen C, Stadler PF. Algebraic dynamic programming on trees. Algorithms. 2017;10(4):135.","journal-title":"Algorithms"},{"issue":"1","key":"229_CR48","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1137\/060651100","volume":"49","author":"RM Dirks","year":"2007","unstructured":"Dirks RM, Bois JS, Schaeffer JM, Winfree E, Pierce NA. Thermodynamic analysis of interacting nucleic acid strands. SIAM Rev. 2007;49(1):65\u201388.","journal-title":"SIAM Rev"}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-023-00229-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s13015-023-00229-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-023-00229-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,1]],"date-time":"2023-12-01T05:03:13Z","timestamp":1701406993000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/s13015-023-00229-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,1]]},"references-count":48,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2023,12]]}},"alternative-id":["229"],"URL":"https:\/\/doi.org\/10.1186\/s13015-023-00229-z","relation":{},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,1]]},"assertion":[{"value":"1 April 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 June 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 December 2023","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":"18"}}