{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T01:52:28Z","timestamp":1773280348469,"version":"3.50.1"},"reference-count":54,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T00:00:00Z","timestamp":1648857600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T00:00:00Z","timestamp":1648857600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"published-print":{"date-parts":[[2022,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    Hard graph problems are ubiquitous in Bioinformatics, inspiring the design of specialized Fixed-Parameter Tractable algorithms, many of which rely on a combination of tree-decomposition and dynamic programming. The time\/space complexities of such approaches hinge critically on low values for the treewidth\n                    <jats:italic>tw<\/jats:italic>\n                    of the input graph. In order to extend their scope of applicability, we introduce the\n                    <jats:sc>Tree-Diet<\/jats:sc>\n                    problem,\n                    <jats:italic>i.e.<\/jats:italic>\n                    the removal of a minimal set of edges such that a given tree-decomposition can be slimmed down to a prescribed treewidth\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$tw'$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>t<\/mml:mi>\n                            <mml:msup>\n                              <mml:mi>w<\/mml:mi>\n                              <mml:mo>\u2032<\/mml:mo>\n                            <\/mml:msup>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    . Our rationale is that the time gained thanks to a smaller treewidth in a parameterized algorithm compensates the extra post-processing needed to take deleted edges into account. Our core result is an FPT dynamic programming algorithm for\n                    <jats:sc>Tree-Diet<\/jats:sc>\n                    , using\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$2^{O(tw)}n$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:msup>\n                              <mml:mn>2<\/mml:mn>\n                              <mml:mrow>\n                                <mml:mi>O<\/mml:mi>\n                                <mml:mo>(<\/mml:mo>\n                                <mml:mi>t<\/mml:mi>\n                                <mml:mi>w<\/mml:mi>\n                                <mml:mo>)<\/mml:mo>\n                              <\/mml:mrow>\n                            <\/mml:msup>\n                            <mml:mi>n<\/mml:mi>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    time and space. We complement this result with parameterized complexity lower-bounds for stronger variants (e.g., NP-hardness when\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$tw'$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>t<\/mml:mi>\n                            <mml:msup>\n                              <mml:mi>w<\/mml:mi>\n                              <mml:mo>\u2032<\/mml:mo>\n                            <\/mml:msup>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    or\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$tw-tw'$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>t<\/mml:mi>\n                            <mml:mi>w<\/mml:mi>\n                            <mml:mo>-<\/mml:mo>\n                            <mml:mi>t<\/mml:mi>\n                            <mml:msup>\n                              <mml:mi>w<\/mml:mi>\n                              <mml:mo>\u2032<\/mml:mo>\n                            <\/mml:msup>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    is constant). We propose a prototype implementation for our approach which we apply on difficult instances of selected RNA-based problems: RNA design, sequence-structure alignment, and search of pseudoknotted RNAs in genomes, revealing very encouraging results. This work paves the way for a wider adoption of tree-decomposition-based algorithms in Bioinformatics.\n                  <\/jats:p>","DOI":"10.1186\/s13015-022-00213-z","type":"journal-article","created":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T06:04:12Z","timestamp":1648879452000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Tree diet: reducing the treewidth to unlock FPT algorithms in RNA bioinformatics"],"prefix":"10.1186","volume":"17","author":[{"given":"Bertrand","family":"Marchand","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yann","family":"Ponty","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Laurent","family":"Bulteau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,4,2]]},"reference":[{"key":"213_CR1","doi-asserted-by":"publisher","unstructured":"Weller M, Chateau A, Giroudeau R. Exact approaches for scaffolding. BMC Bioinformatics. 2015; 16(S14). https:\/\/doi.org\/10.1186\/1471-2105-16-s14-s2","DOI":"10.1186\/1471-2105-16-s14-s2"},{"key":"213_CR2","doi-asserted-by":"publisher","unstructured":"Xu J. Rapid protein side-chain packing via tree decomposition. In: Research in Computational Molecular Biology (RECOMB 2005). Lecture Notes in Computer Science. 2005; vol. 3500, pp. 423\u2013439. Springer, Cambridge, USA. https:\/\/doi.org\/10.1007\/11415770_32.","DOI":"10.1007\/11415770_32"},{"key":"213_CR3","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/j.tcs.2012.04.034","volume":"440","author":"L Bulteau","year":"2012","unstructured":"Bulteau L, Fertin G, Jiang M, Rusu I. Tractability and approximability of maximal strip recovery. Theor Comput Sci. 2012;440:14\u201328.","journal-title":"Theor Comput Sci"},{"issue":"4","key":"213_CR4","doi-asserted-by":"publisher","first-page":"920","DOI":"10.1007\/s11538-017-0260-y","volume":"79","author":"J Baste","year":"2017","unstructured":"Baste J, Paul C, Sau I, Scornavacca C. Efficient FPT algorithms for (strict) compatibility of unrooted phylogenetic trees. Bull Math Biol. 2017;79(4):920\u201338. https:\/\/doi.org\/10.1007\/s11538-017-0260-y.","journal-title":"Bull Math Biol"},{"issue":"12","key":"213_CR5","doi-asserted-by":"publisher","first-page":"256","DOI":"10.3390\/a12120256","volume":"12","author":"L Bulteau","year":"2019","unstructured":"Bulteau L, Weller M. Parameterized algorithms in bioinformatics: an overview. Algorithms. 2019;12(12):256. https:\/\/doi.org\/10.3390\/a12120256.","journal-title":"Algorithms"},{"issue":"1","key":"213_CR6","first-page":"167","volume":"1","author":"MS Waterman","year":"1978","unstructured":"Waterman MS. Secondary structure of single stranded nucleic acids. Adv Math Suppl Stud. 1978;1(1):167\u2013212.","journal-title":"Adv Math Suppl Stud"},{"issue":"26","key":"213_CR7","doi-asserted-by":"publisher","first-page":"15310","DOI":"10.1073\/pnas.2536430100","volume":"100","author":"A Xayaphoummine","year":"2003","unstructured":"Xayaphoummine A, Bucher T, Thalmann F, Isambert H. Prediction and statistics of pseudoknots in RNA structures using exactly clustered stochastic simulations. Proc Natl Acad Sci USA. 2003;100(26):15310\u20135.","journal-title":"Proc Natl Acad Sci USA"},{"issue":"1\u20133","key":"213_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 Math. 2000;104(1\u20133):45\u201362. https:\/\/doi.org\/10.1016\/S0166-218X(00)00186-4.","journal-title":"Discrete Appl Math"},{"issue":"3\u20134","key":"213_CR9","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1089\/106652700750050862","volume":"7","author":"RB Lyngs\u00f8","year":"2000","unstructured":"Lyngs\u00f8 RB, Pedersen CNS. RNA pseudoknot prediction in energy-based models. J Comput Biol. 2000;7(3\u20134):409\u201327.","journal-title":"J Comput Biol"},{"key":"213_CR10","doi-asserted-by":"publisher","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. (eds.) CPM - 23rd Annual Symposium on Combinatorial Pattern Matching. Combinatorial Pattern Matching.2012; vol. 7354, pp. 321\u2013333. Springer, Helsinki, Finland . https:\/\/doi.org\/10.1007\/978-3-642-31265-6_26. Juha K\u00e4rkk\u00e4inen.","DOI":"10.1007\/978-3-642-31265-6_26"},{"issue":"2","key":"213_CR11","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1109\/tcbb.2008.28","volume":"7","author":"G Blin","year":"2010","unstructured":"Blin G, Denise A, Dulucq S, Herrbach C, Touzet H. Alignments of RNA structures. IEEE\/ACM Trans Comput Biol Bioinformat. 2010;7(2):309\u201322. https:\/\/doi.org\/10.1109\/tcbb.2008.28.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinformat"},{"key":"213_CR12","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/978-3-642-33122-0_12","volume-title":"Algorithms in Bioinformatics","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. In: Raphael B, Tang J, editors. Algorithms in Bioinformatics. Ljubljana, Slovenia: Springer; 2012. p. 149\u201364."},{"issue":"D1","key":"213_CR13","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1093\/nar\/gkaa1047","volume":"49","author":"I Kalvari","year":"2020","unstructured":"Kalvari I, Nawrocki EP, Ontiveros-Palacios N, Argasinska J, Lamkiewicz K, Marz M, Griffiths-Jones S, Toffano-Nioche C, Gautheret D, Weinberg Z, Rivas E, Eddy SR, Finn RD, Bateman A, Petrov AI. Rfam 14: expanded coverage of metagenomic, viral and microRNA families. Nucleic Acids Res. 2020;49(D1):192\u2013200. https:\/\/doi.org\/10.1093\/nar\/gkaa1047.","journal-title":"Nucleic Acids Res"},{"key":"213_CR14","doi-asserted-by":"publisher","unstructured":"Sarrazin-Gendron R, Yao H-T, Reinharz V, Oliver CG, Ponty Y, Waldisp\u00fchl J. Stochastic sampling of structural contexts improves the scalability and accuracy of RNA 3d module identification. In: Lecture Notes in Computer Science. 2020; pp. 186\u2013201. Springer, Padua, Italy. https:\/\/doi.org\/10.1007\/978-3-030-45257-5_12.","DOI":"10.1007\/978-3-030-45257-5_12"},{"issue":"4","key":"213_CR15","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1017\/S1355838201002515","volume":"7","author":"NB Leontis","year":"2001","unstructured":"Leontis NB, Westhof E. Geometric nomenclature and classification of RNA base pairs. RNA. 2001;7(4):499\u2013512.","journal-title":"RNA"},{"issue":"8","key":"213_CR16","doi-asserted-by":"publisher","first-page":"3841","DOI":"10.1093\/nar\/gky197","volume":"46","author":"V Reinharz","year":"2018","unstructured":"Reinharz V, Soul\u00e9 A, Westhof E, Waldisp\u00fchl J, Denise A. Mining for recurrent long-range interactions in RNA structures reveals embedded hierarchies in network families. Nucleic Acids Res. 2018;46(8):3841\u201351. https:\/\/doi.org\/10.1093\/nar\/gky197.","journal-title":"Nucleic Acids Res"},{"key":"213_CR17","unstructured":"Gogate V, Dechter R. A complete anytime algorithm for treewidth. 2012; arXiv preprint arXiv:1207.4109."},{"issue":"3","key":"213_CR18","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. Informat Comput. 2010;208(3):259\u201375.","journal-title":"Informat Comput."},{"key":"213_CR19","doi-asserted-by":"crossref","unstructured":"Song Y, Liu C, Malmberg R, Pan F, Cai L. Tree decomposition based fast search of RNA structures including pseudoknots in genomes. In: Computational Systems Bioinformatics Conference, 2005. Proceedings. 2005; 2005 IEEE, pp. 223\u2013234 . IEEE.","DOI":"10.1109\/CSB.2005.52"},{"issue":"5","key":"213_CR20","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1089\/cmb.2007.0214","volume":"15","author":"B Han","year":"2008","unstructured":"Han B, Dost B, Bafna V, Zhang S. Structural alignment of pseudoknotted RNA. J Comput Biol. 2008;15(5):489\u2013504. https:\/\/doi.org\/10.1089\/cmb.2007.0214.","journal-title":"J Comput Biol"},{"issue":"1","key":"213_CR21","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1093\/bioinformatics\/btz497","volume":"36","author":"J Vucinic","year":"2019","unstructured":"Vucinic J, Simoncini D, Ruffini M, Barbe S, Schiex T. Positive multistate protein design. Bioinformatics. 2019;36(1):122\u201330. https:\/\/doi.org\/10.1093\/bioinformatics\/btz497.","journal-title":"Bioinformatics"},{"key":"213_CR22","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 International Conference on Research in Computational Molecular Biology (RECOMB 2021), Padova, France.2021."},{"key":"213_CR23","doi-asserted-by":"publisher","unstructured":"Hammer S, Wang W, Will S, Ponty Y. Fixed-parameter tractable sampling for RNA design with multiple target structures. BMC Bioinformatics .2019;20(1). https:\/\/doi.org\/10.1186\/s12859-019-2784-7.","DOI":"10.1186\/s12859-019-2784-7"},{"key":"213_CR24","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1093\/nar\/28.1.235","volume":"28","author":"HM Berman","year":"2000","unstructured":"Berman HM, Westbrook J, Feng Z, Gilliland G, Bhat TN, Weissig H, Shindyalov IN, Bourne PE. The protein data bank. Nucleic Acids Res. 2000;28:235\u201342. https:\/\/doi.org\/10.1093\/nar\/28.1.235.","journal-title":"Nucleic Acids Res"},{"issue":"21","key":"213_CR25","first-page":"142","volume":"43","author":"X-J Lu","year":"2015","unstructured":"Lu X-J, Bussemaker HJ, Olson WK. Dssr: an integrated software tool for dissecting the spatial structure of rna. Nucleic Acids Res. 2015;43(21):142\u2013142.","journal-title":"Nucleic Acids Res"},{"key":"213_CR26","unstructured":"van Dijk T, van\u00a0den Heuvel J-P, Slob W. Computing treewidth with libtw. Citeseer. http:\/\/citeseerx.ist.psu.edu\/viewdoc\/download. 2006."},{"issue":"6","key":"213_CR27","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"},{"key":"213_CR28","volume-title":"Parameterized complexity","author":"RG Downey","year":"2012","unstructured":"Downey RG, Fellows MR. Parameterized complexity. Berlin: Springer; 2012."},{"key":"213_CR29","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, vol. 5. Cham: Springer; 2015."},{"issue":"3","key":"213_CR30","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1109\/31.1748","volume":"35","author":"ES El-Mallah","year":"1988","unstructured":"El-Mallah ES, Colbourn CJ. The complexity of some edge deletion problems. IEEE Trans Circ Syst. 1988;35(3):354\u201362.","journal-title":"IEEE Trans Circ Syst"},{"key":"213_CR31","unstructured":"Crespelle C, Drange PG, Fomin FV, Golovach PA. A survey of parameterized algorithms and the complexity of edge modification.2020; arXiv preprint arXiv:2001.06867."},{"issue":"3","key":"213_CR32","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1016\/S0166-218X(02)00242-1","volume":"127","author":"L Cai","year":"2003","unstructured":"Cai L. Parameterized complexity of vertex colouring. Discrete Appl Math. 2003;127(3):415\u201329.","journal-title":"Discrete Appl Math"},{"issue":"1","key":"213_CR33","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 Math Soc. 2006;43(1):75\u201386.","journal-title":"Bull Am Math Soc"},{"issue":"1","key":"213_CR34","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N Robertson","year":"1995","unstructured":"Robertson N, Seymour PD. Graph minors. xiii. the disjoint paths problem. J Combinat Theo Ser B. 1995;63(1):65\u2013110.","journal-title":"J Combinat Theo Ser B."},{"key":"213_CR35","doi-asserted-by":"crossref","unstructured":"Cygan M, Lokshtanov D, Pilipczuk M, Pilipczuk M, Saurabh S. On the hardness of losing width. In: International Symposium on Parameterized and Exact Computationl. 2011; pp. 159\u2013168. Springer","DOI":"10.1007\/978-3-642-28050-4_13"},{"issue":"3","key":"213_CR36","doi-asserted-by":"publisher","first-page":"1623","DOI":"10.1137\/19M1287146","volume":"34","author":"J Baste","year":"2020","unstructured":"Baste J, Sau I, Thilikos DM. Hitting minors on bounded treewidth graphs. i. general upper bounds. SIAM J Discret Math. 2020;34(3):1623\u201348. https:\/\/doi.org\/10.1137\/19M1287146.","journal-title":"SIAM J Discret Math"},{"issue":"3","key":"213_CR37","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1051\/ita\/1992260302571","volume":"26","author":"B Courcelle","year":"1992","unstructured":"Courcelle B. The monadic second-order logic of graphs iii: Tree-decompositions, minors and complexity issues. RAIRO-Theoretical Informatics and Applications-Informatique Th\u00e9orique et Applications. 1992;26(3):257\u201386.","journal-title":"RAIRO-Theoretical Informatics and Applications-Informatique Th\u00e9orique et Applications"},{"issue":"2","key":"213_CR38","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S Arnborg","year":"1991","unstructured":"Arnborg S, Lagergren J, Seese D. Easy problems for tree-decomposable graphs. J Algo. 1991;12(2):308\u201340.","journal-title":"J Algo"},{"key":"213_CR39","doi-asserted-by":"publisher","unstructured":"Saitoh T, Yoshinaka R, Bodlaender HL. Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes. In: Algorithms and Computation-15th International Conference and Workshops (WALCOM 2021). Lecture Notes in Computer Science. 2021; vol. 12635, pp. 142\u2013153. Springer, Yangon, Myanmar. https:\/\/doi.org\/10.1007\/978-3-030-68211-8_12.","DOI":"10.1007\/978-3-030-68211-8_12"},{"issue":"3","key":"213_CR40","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/s00453-007-0118-z","volume":"48","author":"J Tan","year":"2007","unstructured":"Tan J, Zhang L. The consecutive ones submatrix problem for sparse matrices. Algorithmica. 2007;48(3):287\u201399.","journal-title":"Algorithmica"},{"key":"213_CR41","doi-asserted-by":"crossref","unstructured":"Proskurowski A, Telle JA. Classes of graphs with restricted interval models. Discret Math Theor Comput Sci. 2006; 3(4)","DOI":"10.46298\/dmtcs.263"},{"issue":"3","key":"213_CR42","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":"213_CR43","doi-asserted-by":"crossref","unstructured":"Bodlaender HL. Discovering treewidth. In: International Conference on Current Trends in Theory and Practice of Computer Science. 2005; pp. 1\u201316. Springer","DOI":"10.1007\/978-3-540-30577-4_1"},{"key":"213_CR44","unstructured":"Jakob W, Rhinelander J, Moldovan D. pybind11\u2013Seamless operability between C++11 and Python. https:\/\/github.com\/pybind\/pybind11.2017."},{"issue":"1","key":"213_CR45","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1186\/1471-2105-4-44","volume":"4","author":"RJ Klein","year":"2003","unstructured":"Klein RJ, Eddy SR. Rsearch: finding homologs of single structured RNA sequences. BMC Bioinformat. 2003;4(1):44.","journal-title":"BMC Bioinformat"},{"issue":"1","key":"213_CR46","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1186\/s12859-015-0832-5","volume":"16","author":"E Rivas","year":"2015","unstructured":"Rivas E, Eddy SR. Parameterizing sequence alignment with an explicit evolutionary model. BMC Bioinformat. 2015;16(1):406.","journal-title":"BMC Bioinformat"},{"key":"213_CR47","unstructured":"Wang W. Practical sequence-structure alignment of rnas with pseudoknots. PhD thesis, Universit\u00e9 Paris-Saclay, School of Computer Science.2017."},{"key":"213_CR48","unstructured":"Wang W, Denise A, Ponty Y. LicoRNA: aLignment of Complex RNAs v1.0. 2017; https:\/\/licorna.lri.fr."},{"key":"213_CR49","doi-asserted-by":"publisher","unstructured":"Sudarsan N, Lee ER, Weinberg Z, Moy RH, Kim JN, Link KH, Breaker RR. Riboswitches in eubacteria sense the second messenger cyclic di-gmp. Science. 2008;321(5887):411\u20133. https:\/\/doi.org\/10.1126\/science.1159519.https:\/\/science.sciencemag.org\/content\/321\/5887\/411.full.pdf.","DOI":"10.1126\/science.1159519."},{"issue":"2","key":"213_CR50","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1371\/journal.ppat.1007529","volume":"15","author":"R Tamayo","year":"2019","unstructured":"Tamayo R. Cyclic diguanylate riboswitches control bacterial pathogenesis mechanisms. PLOS Pathogens. 2019;15(2):1\u20137. https:\/\/doi.org\/10.1371\/journal.ppat.1007529.","journal-title":"PLOS Pathogens"},{"key":"213_CR51","doi-asserted-by":"publisher","unstructured":"Smith KD, Shanahan CA, Moore EL, Simon AC, Strobel SA. Structural basis of differential ligand recognition by two classes of bis-(3\u2019-5\u2019)-cyclic dimeric guanosine monophosphate-binding riboswitches. Proc Nat Acad Sci. 2011;108(19):7757\u201362. https:\/\/doi.org\/10.1073\/pnas.1018857108.https:\/\/www.pnas.org\/content\/108\/19\/7757.full.pdf","DOI":"10.1073\/pnas.1018857108."},{"key":"213_CR52","doi-asserted-by":"publisher","unstructured":"Lu X-J, Bussemaker HJ, Olson WK. DSSR: an integrated software tool for dissecting the spatial structure of RNA. Nucleic Acids Res. 2015;43(21):142\u2013142. https:\/\/doi.org\/10.1093\/nar\/gkv716.https:\/\/academic.oup.com\/nar\/article-pdf\/43\/21\/e142\/17435026\/gkv716.pdf.","DOI":"10.1093\/nar\/gkv716."},{"issue":"1","key":"213_CR53","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1093\/bioinformatics\/15.1.87","volume":"15","author":"JD Thompson","year":"1999","unstructured":"Thompson JD, Plewniak F, Poch O. BAliBASE: a benchmark alignment database for the evaluation of multiple alignment programs. Bioinformatics. 1999;15(1):87\u20138.","journal-title":"Bioinformatics."},{"issue":"9","key":"213_CR54","doi-asserted-by":"publisher","first-page":"739","DOI":"10.1038\/nchembio.1587","volume":"10","author":"Y Liu","year":"2014","unstructured":"Liu Y, Wilson TJ, McPhee SA, Lilley DM. Crystal structure and mechanistic investigation of the twister ribozyme. Nat Chem Biol. 2014;10(9):739\u201344.","journal-title":"Nat Chem Biol"}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-022-00213-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s13015-022-00213-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-022-00213-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T06:04:56Z","timestamp":1648879496000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/s13015-022-00213-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,2]]},"references-count":54,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["213"],"URL":"https:\/\/doi.org\/10.1186\/s13015-022-00213-z","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-1082732\/v1","asserted-by":"object"},{"id-type":"doi","id":"10.1101\/2021.04.30.442158","asserted-by":"object"}]},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,4,2]]},"assertion":[{"value":"15 November 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 March 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 April 2022","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":"8"}}