{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T22:05:48Z","timestamp":1779141948663,"version":"3.51.4"},"reference-count":89,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T00:00:00Z","timestamp":1777334400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0"},{"start":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T00:00:00Z","timestamp":1779062400000},"content-version":"vor","delay-in-days":20,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0"}],"funder":[{"DOI":"10.13039\/501100021856","name":"Ministero dell'Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["MUR - FSE REACT EU - PON R\\&I 2014-2020"],"award-info":[{"award-number":["MUR - FSE REACT EU - PON R\\&I 2014-2020"]}],"id":[{"id":"10.13039\/501100021856","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100021856","name":"Ministero dell'Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["PRIN 2022 YRB97K PINC"],"award-info":[{"award-number":["PRIN 2022 YRB97K PINC"]}],"id":[{"id":"10.13039\/501100021856","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100017142","name":"Gruppo Nazionale per il Calcolo Scientifico","doi-asserted-by":"publisher","award":["CUP_E53C24001950001"],"award-info":[{"award-number":["CUP_E53C24001950001"]}],"id":[{"id":"10.13039\/100017142","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010661","name":"Horizon 2020 Framework Programme","doi-asserted-by":"publisher","award":["956229"],"award-info":[{"award-number":["956229"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010661","name":"Horizon 2020 Framework Programme","doi-asserted-by":"publisher","award":["872539"],"award-info":[{"award-number":["872539"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100031478","name":"NextGenerationEU","doi-asserted-by":"publisher","award":["ECS00000017"],"award-info":[{"award-number":["ECS00000017"]}],"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"],"DOI":"10.1186\/s13015-025-00289-3","type":"journal-article","created":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T06:24:15Z","timestamp":1777357455000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Pattern matching with Elastic-Degenerate strings and Elastic-Founder graphs"],"prefix":"10.1186","volume":"21","author":[{"given":"Rocco","family":"Ascone","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giulia","family":"Bernardini","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alessio","family":"Conte","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Massimo","family":"Equi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Esteban","family":"Gabory","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roberto","family":"Grossi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nadia","family":"Pisanti","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,4,28]]},"reference":[{"issue":"6","key":"289_CR1","doi-asserted-by":"publisher","first-page":"1039","DOI":"10.1137\/0216067","volume":"16","author":"KR Abrahamson","year":"1987","unstructured":"Abrahamson KR. Generalized string matching. SIAM J Comput. 1987;16(6):1039\u201351.","journal-title":"SIAM J Comput"},{"key":"289_CR2","unstructured":"Alanko JN, Biagi E, Puglisi SJ, Vuohtoniemi J. Subset wavelet trees. In: 21st International Symposium on Experimental Algorithms (SEA), volume 265 of LIPIcs, pages 4:1\u20134:14, 2023."},{"key":"289_CR3","unstructured":"Alzamel M, Bernardini G, Grossi RP, Iliopoulos CS, Pisanti NP, Pissis SP, Rosone G. Degenerate string comparison and applications. In: 18th International Workshop on Algorithms in Bioinformatics (WABI), volume 113 of LIPIcs, pages 21:1\u201321:14, 2018."},{"issue":"1\u20134","key":"289_CR4","doi-asserted-by":"publisher","first-page":"41","DOI":"10.3233\/FI-2020-1947","volume":"175","author":"M Alzamel","year":"2020","unstructured":"Alzamel M, Ayad LAK, Bernardini G, Grossi R, Iliopoulos CS, Pisanti N, Pissis SP, Rosone G. Comparing degenerate strings. Fundam Informaticae. 2020;175(1\u20134):41\u201358.","journal-title":"Fundam Informaticae"},{"key":"289_CR5","unstructured":"Amir A, Itzhaki M. Reconstructing General Matching Graphs. In 35th Annual Symposium on Combinatorial Pattern Matching (CPM 2024), volume 296 of Leibniz International Proceedings in Informatics (LIPIcs), pages 2:1\u20132:15, Dagstuhl, Germany, 2024. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik."},{"key":"289_CR6","unstructured":"Antoniou P, Crochemore M, Iliopoulos CS, Jayasekera I, Landau GM. Conservative string covering of indeterminate strings. In: Proceedings of the Prague Stringology Conference, pages 2008;108\u2013115."},{"key":"289_CR7","unstructured":"Aoyama K, Nakashima Y, Tomohiro I, Inenaga S, Bannai H, Takeda M. Faster online elastic degenerate string matching. In: 29th Annual Symposium on Combinatorial Pattern Matching (CPM), volume 105 of LIPIcs, pages 9:1\u20139:10. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2018."},{"key":"289_CR8","doi-asserted-by":"crossref","unstructured":"Ascone R, Bernardini G, Conte A, Equi M, Gabory E, Grossi R, Pisanti N. A unifying taxonomy of pattern matching in degenerate strings and founder graphs. In: 24th International Workshop on Algorithms in Bioinformatics, (WABI), volume 312 of LIPIcs, pages 14:1\u201314:21. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2024.","DOI":"10.1186\/s13015-025-00289-3"},{"issue":"1","key":"289_CR9","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/s11047-022-09882-6","volume":"21","author":"JA Baaijens","year":"2022","unstructured":"Baaijens JA, Bonizzoni P, Boucher C, Vedova GD, Pirola Y, Rizzi R, Sir\u00e9n J. Computational graph pangenomics: a tutorial on data structures and their applications. Nat Comput. 2022;21(1):81\u2013108.","journal-title":"Nat Comput"},{"key":"289_CR10","doi-asserted-by":"crossref","unstructured":"Backurs A, Indyk P. Which regular expression patterns are hard to match? CoRR, arXiv:1511.07070, 2015.","DOI":"10.1109\/FOCS.2016.56"},{"key":"289_CR11","doi-asserted-by":"crossref","unstructured":"Backurs A, Indyk P. Which regular expression patterns are hard to match? In: 57th IEEE Annual Symposium on Foundations of Computer Science (FOCS), 457\u2013466, 2016.","DOI":"10.1109\/FOCS.2016.56"},{"key":"289_CR12","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/j.tcs.2022.04.009","volume":"922","author":"C Barton","year":"2022","unstructured":"Barton C. On the average-case complexity of pattern matching with wildcards. Theor Comput Sci. 2022;922:37\u201345.","journal-title":"Theor Comput Sci"},{"key":"289_CR13","unstructured":"Bathie G, Charalampopoulos P, Starikovskaya T. Pattern matching with mismatches and wildcards. In: Timothy\u00a0M. Chan, Johannes Fischer, John Iacono, and Grzegorz Herman, editors, 32nd Annual European Symposium on Algorithms, ESA 2024, September 2-4, 2024, Royal Holloway, London, United Kingdom, volume 308 of LIPIcs, 20:1\u201320:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2024."},{"issue":"43","key":"289_CR14","doi-asserted-by":"publisher","first-page":"4327","DOI":"10.1016\/j.tcs.2009.07.014","volume":"410","author":"G Battaglia","year":"2009","unstructured":"Battaglia G, Cangelosi D, Grossi R, Pisanti N. Masking patterns in sequences: a new class of motif discovery with don\u2019t cares. Theor Comput Sci. 2009;410(43):4327\u201340.","journal-title":"Theor Comput Sci"},{"key":"289_CR15","doi-asserted-by":"crossref","unstructured":"Bernardini G, Gabory E, Pissis SP, Stougie L, Sweering M, Zuba W. Elastic-degenerate string matching with 1 error. In: 15th Latin American Symposium on Theoretical Informatics (LATIN), volume 13568 of Lecture Notes in Computer Science, 20\u201337. Springer, 2022.","DOI":"10.1007\/978-3-031-20624-5_2"},{"key":"289_CR16","unstructured":"Bernardini G, Gawrychowski P, Pisanti N, Pissis SP, Rosone G. Even faster elastic-degenerate string matching via fast matrix multiplication. In: 46th International Colloquium on Automata, Languages, and Programming (ICALP), volume 132 of LIPIcs, 2019;21:1\u201321:15."},{"issue":"3","key":"289_CR17","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1137\/20M1368033","volume":"51","author":"G Bernardini","year":"2022","unstructured":"Bernardini G, Gawrychowski P, Pisanti N, Pissis SP, Rosone G. Elastic-degenerate string matching via fast matrix multiplication. SIAM J Comput. 2022;51(3):549\u201376.","journal-title":"SIAM J Comput"},{"key":"289_CR18","doi-asserted-by":"crossref","unstructured":"Bernardini G, Pisanti N, Pissis SP, Rosone G. Pattern matching on elastic-degenerate text with errors. In: 24th International Symposium on String Processing and Information Retrieval (SPIRE), volume 10508 of Lecture Notes in Computer Science, 74\u201390. Springer, 2017.","DOI":"10.1007\/978-3-319-67428-5_7"},{"key":"289_CR19","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/j.tcs.2019.08.012","volume":"812","author":"G Bernardini","year":"2020","unstructured":"Bernardini G, Pisanti N, Pissis SP, Rosone G. Approximate pattern matching on elastic-degenerate text. Theor Comput Sci. 2020;812:109\u201322.","journal-title":"Theor Comput Sci"},{"key":"289_CR20","doi-asserted-by":"crossref","unstructured":"Bille P, Li\u00a0G\u00f8rtz I, Stordalen T. Rank and select on degenerate strings. In: 2024 Data Compression Conference (DCC), 2024;283\u2013292.","DOI":"10.1109\/DCC58796.2024.00036"},{"issue":"5","key":"289_CR21","doi-asserted-by":"publisher","first-page":"btad320","DOI":"10.1093\/bioinformatics\/btad320","volume":"39","author":"T B\u00fcchler","year":"2023","unstructured":"B\u00fcchler T, Olbrich J, Ohlebusch E. Efficient short read mapping to a pangenome that is represented by a graph of ED strings. Bioinformatics. 2023;39(5):btad320.","journal-title":"Bioinformatics"},{"key":"289_CR22","doi-asserted-by":"crossref","unstructured":"Cicherski A, Lisiecka A, Dojer N. Alfapang: Alignment free algorithm for pangenome graph construction. In: 24th International Workshop on Algorithms in Bioinformatics, WABI, volume 312 of LIPIcs, 2024;23:1\u201323:18.","DOI":"10.1186\/s13015-025-00277-7"},{"issue":"24","key":"289_CR23","doi-asserted-by":"publisher","first-page":"4290","DOI":"10.1093\/bioinformatics\/bty506","volume":"34","author":"A Cislak","year":"2018","unstructured":"Cislak A, Grabowski S, Holub J. Sopang: online text searching over a pan-genome. Bioinform. 2018;34(24):4290\u20132.","journal-title":"Bioinform"},{"issue":"2","key":"289_CR24","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.ipl.2006.08.002","volume":"101","author":"P Clifford","year":"2007","unstructured":"Clifford P, Clifford R. Simple deterministic wildcard matching. Inf Process Lett. 2007;101(2):53\u20134.","journal-title":"Inf Process Lett"},{"key":"289_CR25","doi-asserted-by":"crossref","unstructured":"Cole R, Hariharan R. Tree pattern matching and subset matching in randomized o(n log$$ ^{\\text{3}}$$m) time. In Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing (STOC), 66\u201375. ACM, 1997.","DOI":"10.1145\/258533.258553"},{"key":"289_CR26","doi-asserted-by":"crossref","unstructured":"Cole R, Hariharan R. Verifying candidate matches in sparse and wildcard matching. In: Proceedings on 34th Annual ACM Symposium on Theory of Computing (STOC), 592\u2013601. ACM, 2002.","DOI":"10.1145\/509907.509992"},{"issue":"4","key":"289_CR27","doi-asserted-by":"publisher","first-page":"1056","DOI":"10.1137\/S0097539700382704","volume":"32","author":"R Cole","year":"2003","unstructured":"Cole R, Hariharan R. Tree pattern matching to subset matching in linear time. SIAM J Comput. 2003;32(4):1056\u201366.","journal-title":"SIAM J Comput"},{"key":"289_CR28","unstructured":"The Computational\u00a0Pan-Genomics Consortium. Computational pan-genomics: status, promises and challenges. Brief Bioinformatics 2018;19(1):118\u2013135."},{"key":"289_CR29","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546853","volume-title":"Algorithms on strings","author":"M Crochemore","year":"2007","unstructured":"Crochemore M, Hancart C, Lecroq T. Algorithms on strings. Cambridge: Cambridge University Press; 2007."},{"key":"289_CR30","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.tcs.2017.05.026","volume":"698","author":"M Crochemore","year":"2017","unstructured":"Crochemore M, Iliopoulos CS, Kociumaka T, Radoszewski J, Rytter W, Walen T. Covering problems for partial words and for indeterminate strings. Theor Comput Sci. 2017;698:25\u201339.","journal-title":"Theor Comput Sci"},{"issue":"15","key":"289_CR31","doi-asserted-by":"publisher","first-page":"2156","DOI":"10.1093\/bioinformatics\/btr330","volume":"27","author":"P Danecek","year":"2011","unstructured":"Danecek P, Auton A, Abecasis GR, Albers CA, Banks E, DePristo MA, Handsaker RE, Lunter G, Marth GT, Sherry ST, McVean G, Durbin R. The variant call format and vcftools. Bioinform. 2011;27(15):2156\u20138.","journal-title":"Bioinform"},{"key":"289_CR32","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1016\/j.ipl.2019.03.003","volume":"147","author":"JW Daykin","year":"2019","unstructured":"Daykin JW, Groult R, Guesnet Y, Lecroq T, Lefebvre A, L\u00e9onard M, Mouchard L, Prieur \u00c9, Watson BW. Efficient pattern matching in degenerate strings with the burrows-wheeler transform. Inf Process Lett. 2019;147:82\u20137.","journal-title":"Inf Process Lett"},{"issue":"2","key":"289_CR33","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/s11786-016-0285-x","volume":"11","author":"JW Daykin","year":"2017","unstructured":"Daykin JW, Watson BW. Indeterminate string factorizations and degenerate text transformations. Math Comput Sci. 2017;11(2):209\u201318.","journal-title":"Math Comput Sci"},{"issue":"Suppl 6","key":"289_CR34","doi-asserted-by":"publisher","first-page":"S2","DOI":"10.1186\/1471-2164-15-S6-S2","volume":"15","author":"D Doerr","year":"2014","unstructured":"Doerr D, Stoye J, B\u00f6cker S, Jahn K. Identifying gene clusters by discovering common intervals in indeterminate strings. BMC Genomics. 2014;15(Suppl 6):S2.","journal-title":"BMC Genomics"},{"issue":"1","key":"289_CR35","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1186\/s12859-023-05624-2","volume":"24","author":"D Dorey-Robinson","year":"2023","unstructured":"Dorey-Robinson D, Maccari G, Hammond JA. Igmat: immunoglobulin sequence multi-species annotation tool for any species including those with incomplete antibody annotation or unusual characteristics. BMC Bioinform. 2023;24(1):491.","journal-title":"BMC Bioinform"},{"issue":"21","key":"289_CR36","doi-asserted-by":"publisher","first-page":"5139","DOI":"10.1093\/bioinformatics\/btaa640","volume":"36","author":"JM Eizenga","year":"2021","unstructured":"Eizenga JM, Novak AM, Kobayashi E, Villani F, Cisar C, Heumos S, Hickey G, Colonna V, Paten B, Garrison E. Efficient dynamic variation graphs. Bioinform. 2021;36(21):5139\u201344.","journal-title":"Bioinform"},{"key":"289_CR37","doi-asserted-by":"crossref","unstructured":"Equi M, M\u00e4kinen V, Tomescu AI. Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails. In: 47th International Conference on Current Trends in Theory and Practice of Computer Science, (SOFSEM), volume 12607 of Lecture Notes in Computer Science, pages 608\u2013622. Springer, 2021.","DOI":"10.1007\/978-3-030-67731-2_44"},{"key":"289_CR38","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2023.114128","volume":"975","author":"M Equi","year":"2023","unstructured":"Equi M, M\u00e4kinen V, Tomescu AI. Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails. Theor Comput Sci. 2023;975: 114128.","journal-title":"Theor Comput Sci"},{"issue":"3","key":"289_CR39","doi-asserted-by":"publisher","first-page":"21:1","DOI":"10.1145\/3588334","volume":"19","author":"M Equi","year":"2023","unstructured":"Equi M, M\u00e4kinen V, Tomescu AI, Grossi R. On the complexity of string matching for graphs. ACM Trans Algorithms. 2023;19(3):21:1-21:25.","journal-title":"ACM Trans Algorithms"},{"key":"289_CR40","unstructured":"Equi M, Norri T, Alanko J, Cazaux B, Tomescu AI, M\u00e4kinen V. Algorithms and complexity on indexing elastic founder graphs. In: 32nd International Symposium on Algorithms and Computation (ISAAC), volume 212 of LIPIcs, 2021;20:1\u201320:18."},{"issue":"6","key":"289_CR41","doi-asserted-by":"publisher","first-page":"1586","DOI":"10.1007\/s00453-022-01007-w","volume":"85","author":"M Equi","year":"2023","unstructured":"Equi M, Norri T, Alanko J, Cazaux B, Tomescu AI, M\u00e4kinen V. Algorithms and complexity on indexing founder graphs. Algorithmica. 2023;85(6):1586\u2013623.","journal-title":"Algorithmica"},{"issue":"7960","key":"289_CR42","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1038\/s41586-023-05896-x","volume":"617","author":"Liao","year":"2023","unstructured":"Liao, et al. A draft human pangenome reference. Nature. 2023;617(7960):312\u201324.","journal-title":"Nature"},{"key":"289_CR43","doi-asserted-by":"crossref","unstructured":"Farach M. Optimal suffix tree construction with large alphabets. In: 38th Annual Symposium on Foundations of Computer Science, FOCS \u201997, Miami Beach, Florida, USA, October 19-22, 1997, 137\u2013143, 1997.","DOI":"10.1109\/SFCS.1997.646102"},{"issue":"43","key":"289_CR44","doi-asserted-by":"publisher","first-page":"4391","DOI":"10.1016\/j.tcs.2009.07.020","volume":"410","author":"M Federico","year":"2009","unstructured":"Federico M, Pisanti N. Suffix tree characterization of maximal motifs in biological sequences. Theor Comput Sci. 2009;410(43):4391\u2013401.","journal-title":"Theor Comput Sci"},{"key":"289_CR45","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2025.105296","volume":"304","author":"E Gabory","year":"2025","unstructured":"Gabory E, Mwaniki MN, Pisanti N, Pissis SP, Radoszewski J, Sweering M, Zuba W. Elastic-degenerate string comparison. Inf Comput. 2025;304: 105296.","journal-title":"Inf Comput"},{"key":"289_CR46","unstructured":"Gabory E, Mwaniki NM, Pisanti N, Pissis SP, Radoszewski J, Sweering M, Zuba W. Comparing elastic-degenerate strings: Algorithms, lower bounds, and applications. In: 34th Annual Symposium on Combinatorial Pattern Matching (CPM), volume 259 of LIPIcs, 11:1\u201311:20, 2023."},{"key":"289_CR47","doi-asserted-by":"publisher","first-page":"11:1","DOI":"10.3389\/fbinf.2024.1397036","volume":"4","author":"E Gabory","year":"2024","unstructured":"Gabory E, Mwaniki NM, Pisanti N, Pissis SP, Radoszewski J, Sweering M, Zuba W. Pangenome comparison via ED strings. Front Bioinformatics. 2024;4:11:1-11:20.","journal-title":"Front Bioinformatics"},{"issue":"9","key":"289_CR48","doi-asserted-by":"publisher","first-page":"875","DOI":"10.1038\/nbt.4227","volume":"36","author":"E Garrison","year":"2018","unstructured":"Garrison E, Sir\u00e9n J, Novak AM, Hickey G, Eizenga JM, Dawson ET, Jones W, Garg S, Markello C, Lin MF, Paten B, Durbin R. Variation graph toolkit improves read mapping by representing genetic variation in the reference. Nat Biotechnol. 2018;36(9):875\u20139.","journal-title":"Nat Biotechnol"},{"key":"289_CR49","unstructured":"Gawrychowski P, Ghazawi S, Landau GM. On indeterminate strings matching. In: 31st Annual Symposium on Combinatorial Pattern Matching (CPM), volume 161 of LIPIcs, 2020;14:1\u201314:14."},{"key":"289_CR50","doi-asserted-by":"crossref","unstructured":"Gibney D. An efficient elastic-degenerate text index? not likely. In: 27th International Symposium on String Processing and Information Retrieval, volume 12303 of Lecture Notes in Computer Science, 76\u201388. Springer, 2020.","DOI":"10.1007\/978-3-030-59212-7_6"},{"key":"289_CR51","doi-asserted-by":"crossref","unstructured":"Gibney D, Hoppenworth G, Thankachan SV. Simple reductions from formula-sat to pattern matching on labeled graphs and subtree isomorphism. In: 4th SIAM Symposium on Simplicity in Algorithms (SOSA), 2021;232\u2013242.","DOI":"10.1137\/1.9781611976496.26"},{"key":"289_CR52","unstructured":"Koerkamp RG. A*PA2: Up to 19$$\\times $$ faster exact global alignment. In 24th International Workshop on Algorithms in Bioinformatics (WABI), volume 312 of LIPIcs, 17:1\u201317:25. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2024."},{"key":"289_CR53","unstructured":"Grossi R, Iliopoulos CS, Liu C, Pisanti N, Pissis SP, Retha A, Rosone G, Vayani F, Versari L. On-line pattern matching on similar texts. In 28th Annual Symposium on Combinatorial Pattern Matching (CPM), volume\u00a078 of LIPIcs, 2017;9:1\u20139:14."},{"key":"289_CR54","doi-asserted-by":"crossref","unstructured":"Grossi R, Pietracaprina A, Pisanti N, Pucci G, Upfal E, Vandin F. MADMX: A novel strategy for maximal dense motif extraction. In Steven Salzberg and Tandy\u00a0J. Warnow, editors, Algorithms in Bioinformatics, 9th International Workshop, WABI 2009, Philadelphia, PA, USA, September 12-13, 2009. Proceedings, volume 5724 of Lecture Notes in Computer Science, 362\u2013374. Springer, 2009.","DOI":"10.1007\/978-3-642-04241-6_30"},{"issue":"4","key":"289_CR55","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1089\/cmb.2010.0177","volume":"18","author":"R Grossi","year":"2011","unstructured":"Grossi R, Pietracaprina A, Pisanti N, Pucci G, Upfal E, Vandin F. MADMX: a strategy for maximal dense motif extraction. J Comput Biol. 2011;18(4):535\u201345.","journal-title":"J Comput Biol"},{"key":"289_CR56","unstructured":"Gu M, Farach M, Beigel R. An efficient algorithm for dynamic text indexing. In: Proceedings of the 5th annual ACM-SIAM symposium on Discrete algorithms (SODA), 1994;697\u2013704."},{"issue":"1","key":"289_CR57","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/j.jda.2006.10.003","volume":"6","author":"J Holub","year":"2008","unstructured":"Holub J, Smyth WF, Wang S. Fast pattern-matching on indeterminate strings. J Discrete Algorithms. 2008;6(1):37\u201350.","journal-title":"J Discrete Algorithms"},{"key":"289_CR58","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2020.104616","volume":"279","author":"CS Iliopoulos","year":"2021","unstructured":"Iliopoulos CS, Kundu R, Pissis SP. Efficient pattern matching in elastic-degenerate strings. Inf Comput. 2021;279: 104616.","journal-title":"Inf Comput"},{"issue":"4","key":"289_CR59","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1007\/s11786-007-0029-z","volume":"1","author":"CS Iliopoulos","year":"2008","unstructured":"Iliopoulos CS, Mouchard L, Rahman MS. A new approach to pattern matching in degenerate DNA\/RNA sequences and distributed pattern matching. Math Comput Sci. 2008;1(4):557\u201369.","journal-title":"Math Comput Sci"},{"key":"289_CR60","unstructured":"Iliopoulos CS, Radoszewski J. Truly subquadratic-time extension queries and periodicity detection in strings with uncertainties. In: 27th Annual Symposium on Combinatorial Pattern Matching (CPM), volume\u00a054 of LIPIcs, 2016;8:1\u20138:12."},{"issue":"2","key":"289_CR61","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo R, Paturi R. On the complexity of k-sat. J Comput Syst Sci. 2001;62(2):367\u201375.","journal-title":"J Comput Syst Sci"},{"key":"289_CR62","doi-asserted-by":"crossref","unstructured":"IUPAC-IUB Commission on Biochemical Nomenclature. Abbreviations and symbols for nucleic acids, polynucleotides, and their constituents. Biochemistry, 9(20):4022\u20134027, 1970.","DOI":"10.1021\/bi00822a023"},{"issue":"2","key":"289_CR63","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"DE Knuth","year":"1977","unstructured":"Knuth DE, Morris Jr JH, Pratt VR. Fast pattern matching in strings. SIAM J Comput. 1977;6(2):323\u201350.","journal-title":"SIAM J Comput"},{"issue":"24","key":"289_CR64","doi-asserted-by":"publisher","first-page":"5443","DOI":"10.1093\/bioinformatics\/btac689","volume":"38","author":"T Lemane","year":"2022","unstructured":"Lemane T, Chikhi R, Peterlongo P. KMDIFF: large-scale and user-friendly differential k-mer analyses. Bioinform. 2022;38(24):5443\u20135.","journal-title":"Bioinform"},{"key":"289_CR65","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/j.tcs.2020.12.007","volume":"854","author":"FA Louza","year":"2021","unstructured":"Louza FA, Mhaskar N, Smyth WF. A new approach to regular & indeterminate strings. Theor Comput Sci. 2021;854:105\u201315.","journal-title":"Theor Comput Sci"},{"key":"289_CR66","unstructured":"M\u00e4kinen V, Cazaux B, Equi M, Norri T, Tomescu AI. Linear time construction of indexable founder block graphs. In:20th International Workshop on Algorithms in Bioinformatics (WABI), volume 172 of LIPIcs, 2020;7:1\u20137:18."},{"key":"289_CR67","doi-asserted-by":"crossref","unstructured":"Mwaniki NM, Garrison E, Pisanti N. Fast exact string to D-texts alignments. In 16th International Joint Conference on Biomedical Engineering Systems and Technologies (BIOSTEC), 70\u201379. SCITEPRESS, 2023.","DOI":"10.5220\/0011666900003414"},{"key":"289_CR68","doi-asserted-by":"crossref","unstructured":"Mwaniki NM, Pisanti N. Optimal sequence alignment to ED-strings. In: 18th International Symposium Bioinformatics Research and Applications (ISBRA), volume 13760 of Lecture Notes in Computer Science, pages 204\u2013216. Springer, 2022.","DOI":"10.1007\/978-3-031-23198-8_19"},{"issue":"5","key":"289_CR69","doi-asserted-by":"publisher","first-page":"665","DOI":"10.1101\/gr.214155.116","volume":"27","author":"B Paten","year":"2017","unstructured":"Paten B, Novak AM, Eizenga JM, Garrison E. Genome graphs and the evolution of genome inference. Genome Res. 2017;27(5):665\u201376.","journal-title":"Genome Res"},{"issue":"3","key":"289_CR70","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1016\/j.jda.2007.03.003","volume":"6","author":"P Peterlongo","year":"2008","unstructured":"Peterlongo P, Pisanti N, Boyer F, do Lago AP, Sagot M-F. Lossless filter for multiple repetitions with hamming distance. J Discrete Algorithms. 2008;6(3):497\u2013509.","journal-title":"J Discrete Algorithms."},{"key":"289_CR71","doi-asserted-by":"crossref","unstructured":"Peterlongo P, Pisanti N, Boyer F, Sagot M-F. Lossless filter for finding long multiple approximate repetitions using a new data structure, the bi-factor array. In Mariano\u00a0P. Consens and Gonzalo Navarro, editors, String Processing and Information Retrieval, 12th International Conference, SPIRE 2005, Buenos Aires, Argentina, November 2-4, 2005, Proceedings, volume 3772 of Lecture Notes in Computer Science, 179\u2013190. Springer, 2005.","DOI":"10.1007\/11575832_20"},{"key":"289_CR72","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/1748-7188-4-3","volume":"4","author":"P Peterlongo","year":"2009","unstructured":"Peterlongo P, Sacomoto GAT, do Lago AP, Pisanti N, Sagot M-F. Lossless filter for multiple repeats with bounded edit distance. Algorithms Mol Biol. 2009;4:1\u201320.","journal-title":"Algorithms Mol Biol"},{"key":"289_CR73","doi-asserted-by":"crossref","unstructured":"Pisanti N, Soldano H, Carpentier M. Incremental inference of relational motifs with a degenerate alphabet. In 16th Annual Symposium on Combinatorial Pattern Matching (CPM), volume 3537 of Lecture Notes in Computer Science, 229\u2013240. Springer, 2005.","DOI":"10.1007\/11496656_20"},{"issue":"12","key":"289_CR74","doi-asserted-by":"publisher","first-page":"1635","DOI":"10.1089\/cmb.2008.0019","volume":"16","author":"N Pisanti","year":"2009","unstructured":"Pisanti N, Soldano H, Carpentier M, Pothier J. A relational extension of the notion of motifs: application to the common 3d protein substructures searching problem. J Computut Biol. 2009;16(12):1635\u201360.","journal-title":"J Computut Biol"},{"key":"289_CR75","doi-asserted-by":"crossref","unstructured":"Pissis SP. Optimal prefix-suffix queries with applications. In: 2025 Symposium on Simplicity in Algorithms (SOSA), 166\u2013171. SIAM, 2025.","DOI":"10.1137\/1.9781611978315.13"},{"key":"289_CR76","unstructured":"Pissis SP, Retha A. Dictionary matching in elastic-degenerate texts with applications in searching VCF files on-line. In: 17th International Symposium on Experimental Algorithms (SEA), volume 103 of LIPIcs, 2018;16:1\u201316:14."},{"issue":"5","key":"289_CR77","doi-asserted-by":"publisher","first-page":"442","DOI":"10.1007\/s42979-023-01760-x","volume":"4","author":"P Proch\u00e1zka","year":"2023","unstructured":"Proch\u00e1zka P, Cvacho O, Krc\u00e1l L, Holub J. Backward pattern matching on elastic-degenerate strings. SN Comput Sci. 2023;4(5):442.","journal-title":"SN Comput Sci"},{"key":"289_CR78","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1038\/s41588-018-0316-4","volume":"51","author":"G Rakocevic","year":"2019","unstructured":"Rakocevic G, Semenyuk V, Lee W-P, Spencer J, Browning J, Johnson IJ, Arsenijevic V, Nadj J, Ghose K, Suciu MC, Ji S-G, Demir G, Li L, Topta\u015f B\u00c7, Dolgoborodov A, Pollex B, Spulber I, Glotova I, K\u00f3m\u00e1r P, Stachyra AL, Li Y, Popovic M, K\u00e4llberg M, Jain A, Kural D. Fast and accurate genomic analyses using genome graphs. Nat Genet. 2019;51:354\u201362.","journal-title":"Nat Genet"},{"key":"289_CR79","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2023.114269","volume":"982","author":"N Rizzo","year":"2024","unstructured":"Rizzo N, Equi M, Norri T, M\u00e4kinen V. Elastic founder graphs improved and enhanced. Theor Comput Sci. 2024;982: 114269.","journal-title":"Theor Comput Sci"},{"key":"289_CR80","unstructured":"Rizzo N, M\u00e4kinen V. Indexable elastic founder graphs of minimum height. In: 33rd Annual Symposium on Combinatorial Pattern Matching (CPM), volume 223 of LIPIcs, 2022;19:1\u201319:19."},{"key":"289_CR81","doi-asserted-by":"crossref","unstructured":"Rizzo N, M\u00e4kinen V. Linear time construction of indexable elastic founder graphs. In 33rd International Workshop on Combinatorial Algorithms (IWOCA), volume 13270 of Lecture Notes in Computer Science, 480\u2013493. Springer, 2022.","DOI":"10.1007\/978-3-031-06678-8_35"},{"key":"289_CR82","doi-asserted-by":"crossref","unstructured":"Sagot M-F, Viari A, Soldano H. Multiple sequence comparison: A peptide matching approach. In: 6th Annual Symposium on Combinatorial Pattern Matching (CPM), volume 937 of Lecture Notes in Computer Science, pages 366\u2013385. Springer, 1995.","DOI":"10.1007\/3-540-60044-2_55"},{"issue":"1\u20132","key":"289_CR83","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/S0304-3975(96)00137-5","volume":"180","author":"M-F Sagot","year":"1997","unstructured":"Sagot M-F, Viari A, Soldano H. Multiple sequence comparison\u2013a peptide matching approach. Theor Comput Sci. 1997;180(1\u20132):115\u201337.","journal-title":"Theor Comput Sci"},{"key":"289_CR84","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.tcs.2016.01.003","volume":"638","author":"A Shiftan","year":"2016","unstructured":"Shiftan A, Porat E. Set intersection and sequence matching with mismatch counting. Theor Comput Sci. 2016;638:3\u201310.","journal-title":"Theor Comput Sci"},{"key":"289_CR85","unstructured":"Sir\u00e9n J, Garrison E, Novak AM, Paten B, Durbin R. Haplotype-aware graph indexes. In: 18th International Workshop on Algorithms in Bioinformatics (WABI), volume 113 of LIPIcs, pages 2018;4:1\u20134:13."},{"issue":"3","key":"289_CR86","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/0167-8655(94)00095-K","volume":"16","author":"H Soldano","year":"1995","unstructured":"Soldano H, Viari A, Champesme M. Searching for flexible repeated patterns using a non-transitive similarity relation. Pattern Recognit Lett. 1995;16(3):233\u201346.","journal-title":"Pattern Recognit Lett"},{"key":"289_CR87","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/j.jda.2012.10.001","volume":"18","author":"C Thachuk","year":"2013","unstructured":"Thachuk C. Indexing hypertext. J Discrete Algorithms. 2013;18:113\u201322.","journal-title":"J Discrete Algorithms"},{"key":"289_CR88","doi-asserted-by":"crossref","unstructured":"Weiner P. Linear pattern matching algorithms. In: 14th Annual Symposium on Switching and Automata Theory, Iowa City, Iowa, USA, October 15-17, 1973, 1\u201311, 1973.","DOI":"10.1109\/SWAT.1973.13"},{"issue":"2\u20133","key":"289_CR89","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1016\/j.tcs.2005.09.023","volume":"348","author":"R Williams","year":"2005","unstructured":"Williams R. A new algorithm for optimal 2-constraint satisfaction and its implications. Theor Comput Sci. 2005;348(2\u20133):357\u201365.","journal-title":"Theor Comput Sci"}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s13015-025-00289-3","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-025-00289-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-025-00289-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T10:04:09Z","timestamp":1779098649000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1186\/s13015-025-00289-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,28]]},"references-count":89,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2026,12]]}},"alternative-id":["289"],"URL":"https:\/\/doi.org\/10.1186\/s13015-025-00289-3","relation":{},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,28]]},"assertion":[{"value":"1 November 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 June 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 April 2026","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":"8"}}