{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T12:54:53Z","timestamp":1774356893990,"version":"3.50.1"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,12,10]],"date-time":"2025-12-10T00:00:00Z","timestamp":1765324800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T00:00:00Z","timestamp":1774310400000},"content-version":"vor","delay-in-days":104,"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-23-CE44-0027"],"award-info":[{"award-number":["ANR-23-CE44-0027"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-23-CE44-0027"],"award-info":[{"award-number":["ANR-23-CE44-0027"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100007601","name":"Horizon 2020","doi-asserted-by":"publisher","award":["101029676"],"award-info":[{"award-number":["101029676"]}],"id":[{"id":"10.13039\/501100007601","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>RNAs composed of Triplet Repeats (TR) have recently attracted much attention in the field of synthetic biology. We study the mimimum free energy (MFE) secondary structures of such RNAs and give improved algorithms to compute the MFE and the partition function. Furthermore, we study the interaction of multiple RNAs and design a new algorithm for computing MFE and partition function for RNA-RNA interactions, improving the previously known factorial running time to exponential. In the case of TR, we show computational hardness but still obtain a parameterized algorithm. Finally, we propose a polynomial-time algorithm for computing interactions from a base set of RNA strands and conduct experiments on the interaction of TR based on this algorithm. For instance, we study the probability that a base pair is formed between two strands with the same triplet pattern, allowing an assessment of a notion of orthogonality between TR.<\/jats:p>","DOI":"10.1186\/s13015-025-00292-8","type":"journal-article","created":{"date-parts":[[2025,12,10]],"date-time":"2025-12-10T18:45:24Z","timestamp":1765392324000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["RNA triplet repeats: improved algorithms for structure prediction and interactions"],"prefix":"10.1186","volume":"21","author":[{"given":"Kimon","family":"Boehmer","sequence":"first","affiliation":[]},{"given":"Sarah J.","family":"Berkemer","sequence":"additional","affiliation":[]},{"given":"Sebastian","family":"Will","sequence":"additional","affiliation":[]},{"given":"Yann","family":"Ponty","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,12,10]]},"reference":[{"issue":"11","key":"292_CR1","doi-asserted-by":"publisher","DOI":"10.1016\/j.crmeth.2022.100334","volume":"2","author":"AU Isiktas","year":"2022","unstructured":"Isiktas AU, Eshov A, Yang S, Guo JU. Systematic generation and imaging of tandem repeats reveal base-pairing properties that promote RNA aggregation. Cell Reports Methods. 2022;2(11):100334.","journal-title":"Cell Reports Methods"},{"issue":"20","key":"292_CR2","doi-asserted-by":"publisher","first-page":"3823","DOI":"10.1016\/j.cell.2022.09.016","volume":"185","author":"H Guo","year":"2022","unstructured":"Guo H, Ryan JC, Song X, Mallet A, Zhang M, Pabst V, et al. Spatial engineering of E. coli with addressable phase-separated RNAs. Cell. 2022;185(20):3823\u201337.","journal-title":"Cell"},{"key":"292_CR3","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/B978-0-323-85654-6.00048-4","volume-title":"Neurobiology of Brain Disorders","author":"SR Srinivasan","year":"2023","unstructured":"Srinivasan SR, MelodeGusmao C, Korecka JA, Khurana V. Chapter 18 - repeat expansion disorders. In: Zigmond MJ, Wiley CA, Chesselet M-F, editors. Neurobiology of Brain Disorders. 2nd ed. New York: Academic Press; 2023. p. 293\u2013312. https:\/\/doi.org\/10.1016\/B978-0-323-85654-6.00048-4.","edition":"2"},{"issue":"2","key":"292_CR4","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/s11604-022-01343-5","volume":"41","author":"R Kurokawa","year":"2023","unstructured":"Kurokawa R, Kurokawa M, Mitsutake A, Nakaya M, Baba A, Nakata Y, et al. Clinical and neuroimaging review of triplet repeat diseases. Jpn J Radiol. 2023;41(2):115\u201330.","journal-title":"Jpn J Radiol"},{"issue":"24","key":"292_CR5","doi-asserted-by":"publisher","first-page":"2301409120","DOI":"10.1073\/pnas.2301409120","volume":"120","author":"H Maity","year":"2023","unstructured":"Maity H, Nguyen HT, Hori N, Thirumalai D. Odd-even disparity in the population of slipped hairpins in rna repeat sequences with implications for phase separation. Proc Natl Acad Sci. 2023;120(24):2301409120.","journal-title":"Proc Natl Acad Sci"},{"key":"292_CR6","doi-asserted-by":"crossref","unstructured":"Aierken D, Joseph JA. Accelerated simulations of rna phase separation: a systematic study of non-redundant tandem repeats. bioRxiv, 2023\u201312 (2023)","DOI":"10.1101\/2023.12.23.573204"},{"issue":"11","key":"292_CR7","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"},{"issue":"1","key":"292_CR8","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1093\/nar\/9.1.133","volume":"9","author":"M Zuker","year":"1981","unstructured":"Zuker M, Stiegler P. Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information. Nucleic Acids Res. 1981;9(1):133\u201348. https:\/\/doi.org\/10.1093\/nar\/9.1.133.","journal-title":"Nucleic Acids Res"},{"issue":"14","key":"292_CR9","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1093\/bioinformatics\/btz375","volume":"35","author":"L Huang","year":"2019","unstructured":"Huang L, Zhang H, Deng D, Zhao K, Liu K, Hendrix DA, et al. LinearFold: linear-time approximate RNA folding by 5\u2019-to-3\u2019 dynamic programming and beam search. Bioinformatics. 2019;35(14):295\u2013304. https:\/\/doi.org\/10.1093\/bioinformatics\/btz375.","journal-title":"Bioinformatics"},{"issue":"2","key":"292_CR10","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1137\/17M112720X","volume":"48","author":"K Bringmann","year":"2019","unstructured":"Bringmann K, Grandoni F, Saha B, Williams VV. Truly subcubic algorithms for language edit distance and rna folding via fast bounded-difference min-plus product. SIAM J Comput. 2019;48(2):481\u2013512. https:\/\/doi.org\/10.1137\/17M112720X.","journal-title":"SIAM J Comput"},{"key":"292_CR11","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/j.tcs.2018.07.010","volume":"757","author":"Y-J Chang","year":"2019","unstructured":"Chang Y-J. Hardness of rna folding problem with four symbols. Theor Comput Sci. 2019;757:11\u201326. https:\/\/doi.org\/10.1016\/j.tcs.2018.07.010.","journal-title":"Theor Comput Sci"},{"issue":"2","key":"292_CR12","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1089\/cmb.2006.13.267","volume":"13","author":"C Alkan","year":"2006","unstructured":"Alkan C, Karakoc E, Nadeau JH, Sahinalp SC, Zhang K. Rna-rna interaction prediction and antisense rna target search. J Comput Biol. 2006;13(2):267\u201382.","journal-title":"J Comput Biol"},{"issue":"1","key":"292_CR13","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"},{"key":"292_CR14","unstructured":"Condon A, Hajiaghayi M, Thachuk C. Predicting minimum free energy structures of multi-stranded nucleic acid complexes is apx-hard. In: 27th International Conference on DNA Computing and Molecular Programming (DNA 27)(2021) (2021). Schloss-Dagstuhl-Leibniz Zentrum f\u00fcr Informatik"},{"key":"292_CR15","unstructured":"Demaine ED, Gomez T, Grizzell E, Hecher M, Lynch J, Schweller R, Shalaby A, Woods D. Domain-based nucleic-acid minimum free energy: Algorithmic hardness and parameterized bounds. In: 30th International Conference on DNA Computing and Molecular Programming (DNA 30)(2024) (2024). Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik"},{"issue":"suppl\u20131","key":"292_CR16","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\u20131):280\u20132. https:\/\/doi.org\/10.1093\/nar\/gkp892.","journal-title":"Nucleic Acids Res"},{"issue":"40","key":"292_CR17","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. Theoret Comput Sci. 2010;411(40):3527\u201352. https:\/\/doi.org\/10.1016\/j.tcs.2010.05.010.","journal-title":"Theoret Comput Sci"},{"issue":"2","key":"292_CR18","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1016\/0021-8693(89)90222-6","volume":"122","author":"L Lipshitz","year":"1989","unstructured":"Lipshitz L. $$D$$-finite power series. J Algebra. 1989;122(2):353\u201373.","journal-title":"J Algebra"},{"key":"292_CR19","doi-asserted-by":"crossref","unstructured":"Bostan A, Chyzak F, Lecerf Ge, Salvy B, Schost E. Differential equations for algebraic functions. In: Brown, C.W. (ed.) ISSAC\u201907: Proceedings of the 2007 International Symposium on Symbolic and Algebraic Computation. ISSAC\u201907, pp. 25\u201332. ACM Press, New York (2007)","DOI":"10.1145\/1277548.1277553"},{"issue":"2","key":"292_CR20","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1145\/178365.178368","volume":"20","author":"B Salvy","year":"1994","unstructured":"Salvy B, Zimmerman P. GFUN: a Maple package for the manipulation of generating and holonomic functions in one variable. ACM Trans Math Softw. 1994;20(2):163\u201377.","journal-title":"ACM Trans Math Softw"},{"issue":"1\u20132","key":"292_CR21","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/S0166-218X(99)00112-2","volume":"98","author":"C McDiarmid","year":"1999","unstructured":"McDiarmid C. Pattern minimisation in cutting stock problems. Discret Appl Math. 1999;98(1\u20132):121\u201330.","journal-title":"Discret Appl Math"},{"key":"292_CR22","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, H\u00f6ner Zu Siederdissen C, Tafer H, Flamm C, Stadler PF, et al. ViennaRNA package 2.0. Algorithms Molec Biol AMB. 2011;6:26. https:\/\/doi.org\/10.1186\/1748-7188-6-26.","journal-title":"Algorithms Molec Biol AMB"},{"issue":"24","key":"292_CR23","doi-asserted-by":"publisher","first-page":"4297","DOI":"10.1093\/bioinformatics\/bty468","volume":"34","author":"JS Lu","year":"2018","unstructured":"Lu JS, Bindewald E, Kasprzak WK, Shapiro BA. RiboSketch: versatile visualization of multi-stranded RNA and DNA secondary structure. Bioinformatics. 2018;34(24):4297\u20139. https:\/\/doi.org\/10.1093\/bioinformatics\/bty468.","journal-title":"Bioinformatics"},{"key":"292_CR24","volume-title":"Clique Cover Based Vertex Cover Solver","author":"F Hauser","year":"2024","unstructured":"Hauser F, Ermel F, Boehmer K. Clique Cover Based Vertex Cover Solver. New York: GitHub; 2024."}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-025-00292-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s13015-025-00292-8","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-025-00292-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T12:05:48Z","timestamp":1774353948000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1186\/s13015-025-00292-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,10]]},"references-count":24,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2026,12]]}},"alternative-id":["292"],"URL":"https:\/\/doi.org\/10.1186\/s13015-025-00292-8","relation":{},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,10]]},"assertion":[{"value":"4 November 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 November 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 December 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":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest\/Conflict of interest"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"Not applicable.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Materials availability"}},{"order":6,"name":"Ethics","group":{"name":"EthicsHeading","label":"Code availability"}},{"value":"The authors declare no Conflict of interest.","order":7,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"4"}}