{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,20]],"date-time":"2025-04-20T04:10:28Z","timestamp":1745122228072,"version":"3.40.4"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,4,19]],"date-time":"2025-04-19T00:00:00Z","timestamp":1745020800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,4,19]],"date-time":"2025-04-19T00:00:00Z","timestamp":1745020800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003407","name":"Ministero dell\u2019Istruzione, dell\u2019Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["PRIN Project, 2022TS4Y3N","PRIN Project, 2022TS4Y3N","PRIN Project, 2022TS4Y3N","\u201cFit4MedRob - Fit for Medical Robotics\u201d, #PNC0000007"],"award-info":[{"award-number":["PRIN Project, 2022TS4Y3N","PRIN Project, 2022TS4Y3N","PRIN Project, 2022TS4Y3N","\u201cFit4MedRob - Fit for Medical Robotics\u201d, #PNC0000007"]}],"id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100007601","name":"Horizon 2020","doi-asserted-by":"publisher","award":["PANGAIA project - Marie Sk\u0142odowska-Curie grant agreement No. 872539","PANGAIA project - Marie Sk\u0142odowska-Curie grant agreement No. 872539","PANGAIA project - Marie Sk\u0142odowska-Curie grant agreement No. 872539"],"award-info":[{"award-number":["PANGAIA project - Marie Sk\u0142odowska-Curie grant agreement No. 872539","PANGAIA project - Marie Sk\u0142odowska-Curie grant agreement No. 872539","PANGAIA project - Marie Sk\u0142odowska-Curie grant agreement No. 872539"]}],"id":[{"id":"10.13039\/501100007601","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100031478","name":"NextGenerationEU","doi-asserted-by":"publisher","award":["PNRR ECS00000017 Tuscany Health Ecosystem"],"award-info":[{"award-number":["PNRR ECS00000017 Tuscany Health Ecosystem"]}],"id":[{"id":"10.13039\/100031478","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>Analyzing and comparing sequences of symbols is among the most fundamental problems in computer science, possibly even more so in bioinformatics. Maximal Common Subsequences (MCSs), i.e., inclusion-maximal sequences of non-contiguous symbols common to two or more strings, have only recently received attention in this area, despite being a basic notion and a natural generalization of more common tools like Longest Common Substrings\/Subsequences. In this paper we simplify and engineer recent advancements in MCSs into a practical tool called <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\textsc {McDag}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>M<\/mml:mi>\n                    <mml:mstyle>\n                      <mml:mi>C<\/mml:mi>\n                      <mml:mi>D<\/mml:mi>\n                      <mml:mi>A<\/mml:mi>\n                      <mml:mi>G<\/mml:mi>\n                    <\/mml:mstyle>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>, the first publicly available tool that can index MCSs of real genomic data, and show that its definition can be generalized to multiple strings. We demonstrate that our tool can index pairs of sequences exceeding 10,000 base pairs within minutes, utilizing only 4-7% more than the minimum required nodes. For three or more sequences, we observe experimentally that the minimum index may exhibit a significant increase in the number of nodes.<\/jats:p>","DOI":"10.1186\/s13015-025-00271-z","type":"journal-article","created":{"date-parts":[[2025,4,19]],"date-time":"2025-04-19T10:50:16Z","timestamp":1745059816000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["$$\\textsc {McDag}$$: indexing maximal common subsequences for k strings"],"prefix":"10.1186","volume":"20","author":[{"given":"Giovanni","family":"Buzzega","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alessio","family":"Conte","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roberto","family":"Grossi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giulia","family":"Punzi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,4,19]]},"reference":[{"issue":"1","key":"271_CR1","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","volume":"147","author":"TF Smith","year":"1981","unstructured":"Smith TF, Waterman MS, et al. Identification of common molecular subsequences. J Mol Biol. 1981;147(1):195\u20137.","journal-title":"J Mol Biol"},{"issue":"2","key":"271_CR2","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1145\/322063.322075","volume":"25","author":"D Maier","year":"1978","unstructured":"Maier D. The complexity of some problems on subsequences and supersequences. J ACM (JACM). 1978;25(2):322\u201336. https:\/\/doi.org\/10.1145\/322063.322075.","journal-title":"J ACM (JACM)"},{"key":"271_CR3","doi-asserted-by":"publisher","unstructured":"Abboud A, Backurs A, Williams VV. Tight Hardness Results for LCS and Other Sequence Similarity Measures. In: Guruswami V, editor. IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015. IEEE. IEEE Computer Society; 2015;p. 59\u201378. Available from: https:\/\/doi.org\/10.1109\/FOCS.2015.14.","DOI":"10.1109\/FOCS.2015.14"},{"key":"271_CR4","doi-asserted-by":"crossref","unstructured":"Bringmann K, K\u00fcnnemann M. Quadratic conditional lower bounds for string problems and dynamic time warping. In: Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE; 2015;p. 79\u201397.","DOI":"10.1109\/FOCS.2015.15"},{"issue":"3\u20134","key":"271_CR5","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/S1570-8667(03)00029-7","volume":"1","author":"M Crochemore","year":"2003","unstructured":"Crochemore M, Melichar B, Tron\u00edcek Z. Directed acyclic subsequence graph - Overview. J Discrete Algorith. 2003;1(3\u20134):255\u201380. https:\/\/doi.org\/10.1016\/S1570-8667(03)00029-7.","journal-title":"J Discrete Algorith"},{"issue":"3","key":"271_CR6","doi-asserted-by":"publisher","first-page":"757","DOI":"10.1007\/s00453-021-00898-5","volume":"84","author":"A Conte","year":"2022","unstructured":"Conte A, Grossi R, Punzi G, Uno T. Enumeration of maximal common subsequences between two strings. Algorithmica. 2022;84(3):757\u201383. https:\/\/doi.org\/10.1007\/s00453-021-00898-5.","journal-title":"Algorithmica"},{"key":"271_CR7","unstructured":"Greenberg RI. Bounds on the Number of Longest Common Subsequences. CoRR. 2003;cs.DM\/0301030."},{"key":"271_CR8","doi-asserted-by":"publisher","unstructured":"Conte A, Grossi R, Punzi G, Uno T. A Compact DAG for Storing and Searching Maximal Common Subsequences. In: Iwata S, Kakimura N, editors. 34th International Symposium on Algorithms and Computation, ISAAC 2023, December 3-6, 2023, Kyoto, Japan. vol. 283 of LIPIcs. Schloss-Dagstuhl-Leibniz Zentrum f\u00fcr Informatik. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik; 2023;p. 21:1\u201321:15. Available from: https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2023.21.","DOI":"10.4230\/LIPIcs.ISAAC.2023.21"},{"key":"271_CR9","doi-asserted-by":"publisher","unstructured":"Hirota M, Sakai Y. Efficient algorithms for enumerating maximal common subsequences of two strings. CoRR. 2023;abs\/2307.10552. https:\/\/doi.org\/10.48550\/arXiv.2307.10552. arXiv:2307.10552.","DOI":"10.48550\/arXiv.2307.10552"},{"key":"271_CR10","doi-asserted-by":"publisher","unstructured":"Buzzega G, Conte A, Grossi R, Punzi G. McDag: Indexing Maximal Common Subsequences in Practice. In: Pissis SP, Sung W, editors. 24th International Workshop on Algorithms in Bioinformatics, WABI 2024, September 2-4, 2024, Royal Holloway, London, United Kingdom. vol. 312 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik; 2024; p. 21:1\u201321:18. Available from: https:\/\/doi.org\/10.4230\/LIPIcs.WABI.2024.21.","DOI":"10.4230\/LIPIcs.WABI.2024.21"},{"key":"271_CR11","doi-asserted-by":"crossref","unstructured":"Agrawal R, Srikant R. Mining sequential patterns. In: Proceedings of the eleventh international conference on data engineering. IEEE; 1995;p. 3\u201314.","DOI":"10.1109\/ICDE.1995.380415"},{"issue":"2","key":"271_CR12","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1006\/inco.1996.0011","volume":"124","author":"C Fraser","year":"1996","unstructured":"Fraser C, Irving RW, Middendorf M. Maximal Common Subsequences and Minimal Common Supersequences. Inf Comput. 1996;124(2):145\u201353. https:\/\/doi.org\/10.1006\/inco.1996.0011.","journal-title":"Inf Comput"},{"key":"271_CR13","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1016\/j.tcs.2019.06.020","volume":"793","author":"Y Sakai","year":"2019","unstructured":"Sakai Y. Maximal common subsequence algorithms. Theor Comput Sci. 2019;793:132\u20139. https:\/\/doi.org\/10.1016\/j.tcs.2019.06.020.","journal-title":"Theor Comput Sci"},{"key":"271_CR14","doi-asserted-by":"publisher","unstructured":"Bulteau L, Jones M, Niedermeier R, Tantau T. An FPT-algorithm for longest common subsequence parameterized by the maximum number of deletions. In: Bannai H, Holub J, editors. 33rd Annual Symposium on Combinatorial Pattern Matching, CPM 2022, June 27-29, 2022, Prague, Czech Republic. vol. 223 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik; 2022;p. 6:1\u20136:11. Available from: https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2022.6.","DOI":"10.4230\/LIPIcs.CPM.2022.6"},{"issue":"9","key":"271_CR15","doi-asserted-by":"publisher","first-page":"1191","DOI":"10.1587\/transfun.2022dml0002","volume":"106","author":"M Hirota","year":"2023","unstructured":"Hirota M, Sakai Y. A fast algorithm for finding a maximal common subsequence of multiple strings. IEICE Trans Fundam Electron Commun Comput Sci. 2023;106(9):1191\u20134. https:\/\/doi.org\/10.1587\/transfun.2022dml0002.","journal-title":"IEICE Trans Fundam Electron Commun Comput Sci"},{"issue":"2","key":"271_CR16","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1016\/0304-3975(91)90358-9","volume":"78","author":"RA Baeza-Yates","year":"1991","unstructured":"Baeza-Yates RA. Searching subsequences. Theoret Comput Sci. 1991;78(2):363\u201376. https:\/\/doi.org\/10.1016\/0304-3975(91)90358-9.","journal-title":"Theoret Comput Sci"},{"key":"271_CR17","unstructured":"Crochemore M, Tron\u00ed\u010dek Z. Directed acyclic subsequence graph for multiple texts. Rapport IGM. 1999;p. 99\u201313."},{"key":"271_CR18","doi-asserted-by":"publisher","unstructured":"Tron\u00edcek Z. Common Subsequence Automaton. In: Champarnaud J, Maurel D, editors. Implementation and Application of Automata, 7th International Conference, CIAA 2002, Tours, France, July 3-5, 2002, Revised Papers. vol. 2608 of Lecture Notes in Computer Science. Springer. Springer; 2002;p. 270\u2013275. Available from: https:\/\/doi.org\/10.1007\/3-540-44977-9_28.","DOI":"10.1007\/3-540-44977-9_28"},{"issue":"1","key":"271_CR19","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/BF01934514","volume":"24","author":"WJ Hsu","year":"1984","unstructured":"Hsu WJ, Du MW. Computing a longest common subsequence for a set of strings. BIT Num Mathe. 1984;24(1):45\u201359. https:\/\/doi.org\/10.1007\/BF01934514.","journal-title":"BIT Num Mathe"},{"key":"271_CR20","doi-asserted-by":"publisher","unstructured":"Melichar B, Polcar T. The Longest Common Subsequence Problem A Finite Automata Approach. In: Ibarra OH, Dang Z, editors. Implementation and Application of Automata, 8th International Conference, CIAA 2003, Santa Barbara, California, USA, July 16-18, 2003, Proceedings. vol. 2759 of Lecture Notes in Computer Science. Springer. Springer; 2003;p. 294\u2013296. Available from: https:\/\/doi.org\/10.1007\/3-540-45089-0_27.","DOI":"10.1007\/3-540-45089-0_27"},{"key":"271_CR21","doi-asserted-by":"publisher","unstructured":"Minato S. Zero-Suppressed BDDs for Set Manipulation in Combinatorial Problems. In: Dunlop AE, editor. Proceedings of the 30th Design Automation Conference. Dallas, Texas, USA, June 14-18, 1993. DAC \u201993. New York, NY, USA: ACM Press; 1993; p. 272\u2013277. Available from: https:\/\/doi.org\/10.1145\/157485.164890.","DOI":"10.1145\/157485.164890"},{"issue":"2","key":"271_CR22","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/s10115-009-0252-9","volume":"24","author":"E Loekito","year":"2010","unstructured":"Loekito E, Bailey J, Pei J. A binary decision diagram based approach for mining frequent subsequences. Knowl Inf Syst. 2010;24(2):235\u201368. https:\/\/doi.org\/10.1007\/s10115-009-0252-9.","journal-title":"Knowl Inf Syst"},{"key":"271_CR23","doi-asserted-by":"crossref","unstructured":"Irving RW, Fraser CB. Two algorithms for the longest common subsequence of three (or more) strings. In: Combinatorial Pattern Matching: Third Annual Symposium Tucson, Arizona, USA, April 29\u2013May 1, 1992 Proceedings 3. Springer; 1992;p. 214\u2013229.","DOI":"10.1007\/3-540-56024-6_18"},{"issue":"8","key":"271_CR24","doi-asserted-by":"publisher","first-page":"835","DOI":"10.1109\/71.298210","volume":"5","author":"M Lu","year":"1994","unstructured":"Lu M, Lin H. Parallel algorithms for the longest common subsequence problem. IEEE Trans Parall Distrib Syst. 1994;5(8):835\u201348. https:\/\/doi.org\/10.1109\/71.298210.","journal-title":"IEEE Trans Parall Distrib Syst"},{"key":"271_CR25","doi-asserted-by":"publisher","unstructured":"Shida Y, Punzi G, Kobayashi Y, Uno T, Arimura H. Finding Diverse Strings and Longest Common Subsequences in a Graph. CoRR. 2024;abs\/2405.00131. https:\/\/doi.org\/10.48550\/arXiv.2405.00131. arXiv:2405.00131.","DOI":"10.48550\/arXiv.2405.00131"},{"key":"271_CR26","unstructured":"Brzozowski J A. Canonical regular expressions and minimal state graphs for definite events. In: Proc. Symposium of Mathematical Theory of Automata; 1962;p. 529\u2013561."},{"key":"271_CR27","first-page":"96","volume":"2002","author":"JM Champarnaud","year":"2002","unstructured":"Champarnaud JM, Khorsi A, Parantho\u00ebn T. Split and join for minimizing: Brzozowski\u2019s algorithm. Stringology. 2002;2002:96\u2013104.","journal-title":"Stringology"},{"issue":"14","key":"271_CR28","doi-asserted-by":"publisher","first-page":"1744","DOI":"10.1093\/bioinformatics\/btm248","volume":"23","author":"X Wu","year":"2007","unstructured":"Wu X, Cai Z, Wan XF, Hoang T, Goebel R, Lin G. Nucleotide composition string selection in HIV-1 subtyping using whole genomes. Bioinformatics. 2007;23(14):1744\u201352. https:\/\/doi.org\/10.1093\/bioinformatics\/btm248.","journal-title":"Bioinformatics"},{"issue":"1","key":"271_CR29","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/0304-3975(92)90142-3","volume":"92","author":"D Revuz","year":"1992","unstructured":"Revuz D. Minimisation of acyclic deterministic automata in linear time. Theoretical Comput Sci. 1992;92(1):181\u20139. https:\/\/doi.org\/10.1016\/0304-3975(92)90142-3.","journal-title":"Theoretical Comput Sci"}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-025-00271-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s13015-025-00271-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-025-00271-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,19]],"date-time":"2025-04-19T10:50:20Z","timestamp":1745059820000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/s13015-025-00271-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,19]]},"references-count":29,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2025,12]]}},"alternative-id":["271"],"URL":"https:\/\/doi.org\/10.1186\/s13015-025-00271-z","relation":{},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,4,19]]},"assertion":[{"value":"1 November 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 February 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 April 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":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"6"}}