{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,21]],"date-time":"2026-03-21T04:52:13Z","timestamp":1774068733650,"version":"3.50.1"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,8,12]],"date-time":"2025-08-12T00:00:00Z","timestamp":1754956800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0"},{"start":{"date-parts":[[2025,8,12]],"date-time":"2025-08-12T00:00:00Z","timestamp":1754956800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0"}],"funder":[{"DOI":"10.13039\/501100003130","name":"Fonds Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["1117322N"],"award-info":[{"award-number":["1117322N"]}],"id":[{"id":"10.13039\/501100003130","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003130","name":"Fonds Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["1SE7822N"],"award-info":[{"award-number":["1SE7822N"]}],"id":[{"id":"10.13039\/501100003130","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["RGPIN-07185-2020"],"award-info":[{"award-number":["RGPIN-07185-2020"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000002","name":"National Institutes of Health","doi-asserted-by":"publisher","award":["R01HG011392"],"award-info":[{"award-number":["R01HG011392"]}],"id":[{"id":"10.13039\/100000002","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-00281-x","type":"journal-article","created":{"date-parts":[[2025,8,12]],"date-time":"2025-08-12T15:12:52Z","timestamp":1755011572000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["b-move: faster lossless approximate pattern matching in a run-length compressed index"],"prefix":"10.1186","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8517-0479","authenticated-orcid":false,"given":"Lore","family":"Depuydt","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2244-1427","authenticated-orcid":false,"given":"Luca","family":"Renders","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-7810-2174","authenticated-orcid":false,"given":"Simon","family":"Van de Vyver","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lennart","family":"Veys","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3689-327X","authenticated-orcid":false,"given":"Travis","family":"Gagie","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9994-8269","authenticated-orcid":false,"given":"Jan","family":"Fostier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,8,12]]},"reference":[{"key":"281_CR1","doi-asserted-by":"publisher","unstructured":"The Computational Pan-Genomics Consortium. Computational pan-genomics: status, promises and challenges. Briefings Bioinform. 2016;19(1):118\u201335. https:\/\/doi.org\/10.1093\/bib\/bbw089.","DOI":"10.1093\/bib\/bbw089"},{"issue":"14","key":"281_CR2","doi-asserted-by":"publisher","first-page":"1754","DOI":"10.1093\/bioinformatics\/btp324","volume":"25","author":"H Li","year":"2009","unstructured":"Li H, Durbin R. Fast and accurate short read alignment with Burrows\u2013Wheeler transform. Bioinformatics. 2009;25(14):1754\u201360. https:\/\/doi.org\/10.1093\/bioinformatics\/btp324.","journal-title":"Bioinformatics"},{"issue":"4","key":"281_CR3","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1038\/nmeth.1923","volume":"9","author":"B Langmead","year":"2012","unstructured":"Langmead B, Salzberg SL. Fast gapped-read alignment with Bowtie 2. Nat Methods. 2012;9(4):357\u20139. https:\/\/doi.org\/10.1038\/nmeth.1923.","journal-title":"Nat Methods."},{"key":"281_CR4","doi-asserted-by":"publisher","unstructured":"Ferragina P, Manzini G. Opportunistic data structures with applications. In: Proceedings 41st annual symposium on Foundations of Computer Science; 2000. p. 390-8. https:\/\/doi.org\/10.1109\/SFCS.2000.892127.","DOI":"10.1109\/SFCS.2000.892127"},{"key":"281_CR5","unstructured":"Burrows M, Wheeler D. A Block-sorting lossless data compression algorithm. 130 Lytton Avenue, Palo Alto, California 94301: Digital Equipment Corporation Systems Research Center; 1994. p. 124."},{"issue":"5","key":"281_CR6","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0222058","volume":"22","author":"U Manber","year":"1993","unstructured":"Manber U, Myers G. Suffix arrays: a new method for on-line string searches. SIAM J Comput. 1993;22(5):935\u201348. https:\/\/doi.org\/10.1137\/0222058.","journal-title":"SIAM J Comput"},{"key":"281_CR7","doi-asserted-by":"publisher","unstructured":"Kempa D, Kociumaka T. Resolution of the Burrows\u2013Wheeler transform conjecture. In: 2020 IEEE 61st annual symposium on Foundations of Computer Science (FOCS); 2020. p. 1002\u201313. https:\/\/doi.org\/10.1109\/FOCS46700.2020.00097.","DOI":"10.1109\/FOCS46700.2020.00097"},{"key":"281_CR8","unstructured":"Seward J. bzip2 and libbzip2\u2014a program and library for data compression. available at http:\/\/wwwbziporg. 1996."},{"key":"281_CR9","doi-asserted-by":"publisher","unstructured":"M\u00e4kinen V, Navarro G. Succinct suffix arrays based on run-length encoding. In: Combinatorial pattern matching. Berlin, Heidelberg: Springer Berlin Heidelberg; 2005. p. 45\u201356. https:\/\/doi.org\/10.1007\/11496656_5.","DOI":"10.1007\/11496656_5"},{"key":"281_CR10","doi-asserted-by":"publisher","unstructured":"Gagie T, Navarro G, Prezza N. Optimal-time text indexing in BWT-runs bounded space. In: Proceedings of the twenty-ninth annual ACM-SIAM symposium on discrete algorithms, SODA 2018, New Orleans, LA, USA, January 7\u201310, 2018. SIAM; 2018. p. 1459\u201377. https:\/\/doi.org\/10.1137\/1.9781611975031.96.","DOI":"10.1137\/1.9781611975031.96"},{"key":"281_CR11","doi-asserted-by":"publisher","DOI":"10.1145\/3375890","author":"T Gagie","year":"2020","unstructured":"Gagie T, Navarro G, Prezza N. Fully functional suffix trees and optimal text searching in BWT-runs bounded space. J ACM. 2020. https:\/\/doi.org\/10.1145\/3375890.","journal-title":"J ACM."},{"issue":"2","key":"281_CR12","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1089\/cmb.2021.0290","volume":"29","author":"M Rossi","year":"2022","unstructured":"Rossi M, Oliva M, Langmead B, Gagie T, Boucher C. MONI: a pangenomic index for finding maximal exact matches. J Comput Biol. 2022;29(2):169\u201387. https:\/\/doi.org\/10.1089\/cmb.2021.0290. (PMID:35041495).","journal-title":"J Comput Biol."},{"key":"281_CR13","doi-asserted-by":"publisher","unstructured":"Boucher C, Gagie T, Tomohiro I, K\u00f6ppl D, Langmead B, Manzini G, et\u00a0al. PHONI: streamed matching statistics with multi-genome references. In: 2021 data compression conference (DCC); 2021. p. 193\u2013202. https:\/\/doi.org\/10.1109\/DCC50243.2021.00027.","DOI":"10.1109\/DCC50243.2021.00027"},{"issue":"6","key":"281_CR14","doi-asserted-by":"publisher","DOI":"10.1016\/j.isci.2021.102696","volume":"24","author":"O Ahmed","year":"2021","unstructured":"Ahmed O, Rossi M, Kovaka S, Schatz MC, Gagie T, Boucher C, et al. Pan-genomic matching statistics for targeted nanopore sequencing. iScience. 2021;24(6): 102696. https:\/\/doi.org\/10.1016\/j.isci.2021.102696.","journal-title":"iScience."},{"issue":"1","key":"281_CR15","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1186\/s13059-023-02958-1","volume":"24","author":"OY Ahmed","year":"2023","unstructured":"Ahmed OY, Rossi M, Gagie T, Boucher C, Langmead B. SPUMONI 2: improved classification using a pangenome index of minimizer digests. Genome Biol. 2023;24(1):122. https:\/\/doi.org\/10.1186\/s13059-023-02958-1.","journal-title":"Genome Biol."},{"key":"281_CR16","doi-asserted-by":"publisher","unstructured":"Nishimoto T, Tabei Y. Optimal-time queries on BWT-runs compressed indexes. In: 48th international colloquium on automata, languages, and programming, ICALP 2021, July 12\u201316, 2021, Glasgow, Scotland (virtual conference). vol. 198 of LIPIcs. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik; 2021. p. 101:1\u2013101:15. https:\/\/doi.org\/10.4230\/LIPICS.ICALP.2021.101.","DOI":"10.4230\/LIPICS.ICALP.2021.101"},{"key":"281_CR17","doi-asserted-by":"publisher","DOI":"10.1016\/j.isci.2024.111464","author":"M Zakeri","year":"2024","unstructured":"Zakeri M, Brown NK, Ahmed OY, Gagie T, Langmead B. Movi: a fast and cache-efficient full-text pangenome index. iScience. 2024. https:\/\/doi.org\/10.1016\/j.isci.2024.111464.","journal-title":"iScience."},{"key":"281_CR18","doi-asserted-by":"publisher","unstructured":"Bertram N, Fischer J, Nalbach L. Move-r: optimizing the r-index. In: Liberti L, editor. 22nd international symposium on experimental algorithms (SEA 2024). vol. 301 of Leibniz international Proceedings in informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik; 2024. p. 1:1\u20131:19. https:\/\/doi.org\/10.4230\/LIPIcs.SEA.2024.1.","DOI":"10.4230\/LIPIcs.SEA.2024.1"},{"key":"281_CR19","doi-asserted-by":"publisher","unstructured":"Bal\u00e1\u017e A, Gagie T, Goga A, Heumos S, Navarro G, Petescia A, et\u00a0al. Wheeler maps. In: LATIN 2024: theoretical informatics. Cham: Springer Nature Switzerland; 2024. p. 178\u201392. https:\/\/doi.org\/10.1007\/978-3-031-55598-5_12.","DOI":"10.1007\/978-3-031-55598-5_12"},{"key":"281_CR20","doi-asserted-by":"publisher","unstructured":"Arakawa Y, Navarro G, Sadakane K. Bi-directional r-indexes. In: 33rd annual symposium on combinatorial pattern matching (CPM 2022). vol. 223 of Leibniz international Proceedings in informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik; 2022. p. 11:1\u201311:14. https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2022.11.","DOI":"10.4230\/LIPIcs.CPM.2022.11"},{"key":"281_CR21","doi-asserted-by":"publisher","unstructured":"Kucherov G, Salikhov K, Tsur D. Approximate string matching using a bidirectional index. In: Combinatorial pattern matching. Cham: Springer International Publishing; 2014. p. 222\u201331. https:\/\/doi.org\/10.1007\/978-3-319-07566-2_23.","DOI":"10.1007\/978-3-319-07566-2_23"},{"key":"281_CR22","doi-asserted-by":"publisher","unstructured":"Depuydt L, Renders L, Van\u00a0de Vyver S, Veys L, Gagie T, Fostier J. b-move: faster bidirectional character extensions in a run-length compressed index. In: Pissis SP, Sung WK, editors. 24th international workshop on algorithms in bioinformatics (WABI 2024). vol. 312 of Leibniz international Proceedings in informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik; 2024. p. 10:1\u201310:18. https:\/\/doi.org\/10.4230\/LIPIcs.WABI.2024.10.","DOI":"10.4230\/LIPIcs.WABI.2024.10"},{"key":"281_CR23","doi-asserted-by":"publisher","unstructured":"Pockrandt CM. Approximate string matching: improving data structures and algorithms [dissertation]. Free University of Berlin, Dahlem, Germany; 2019. https:\/\/doi.org\/10.17169\/refubium-2185.","DOI":"10.17169\/refubium-2185"},{"key":"281_CR24","doi-asserted-by":"publisher","unstructured":"Lam TW, Li R, Tam A, Wong S, Wu E, Yiu SM. High throughput short read alignment via bi-directional BWT. In: 2009 IEEE international conference on bioinformatics and biomedicine; 2009. p. 31\u20136. https:\/\/doi.org\/10.1109\/BIBM.2009.42.","DOI":"10.1109\/BIBM.2009.42"},{"key":"281_CR25","doi-asserted-by":"publisher","unstructured":"Kianfar K, Pockrandt C, Torkamandi B, Luo H, Reinert K. Optimum search schemes for approximate string matching using bidirectional FM-index. bioRxiv. 2018. https:\/\/doi.org\/10.1101\/301085.","DOI":"10.1101\/301085"},{"key":"281_CR26","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2024.0664","author":"L Renders","year":"2024","unstructured":"Renders L, Depuydt L, Rahmann S, Fostier J. Lossless approximate pattern matching: automated design of efficient search schemes. J Comput Biol. 2024. https:\/\/doi.org\/10.1089\/cmb.2024.0664. (PMID:39344875).","journal-title":"J Comput Biol."},{"issue":"7","key":"281_CR27","doi-asserted-by":"publisher","DOI":"10.1016\/j.isci.2021.102687","volume":"24","author":"L Renders","year":"2021","unstructured":"Renders L, Marchal K, Fostier J. Dynamic partitioning of search patterns for approximate pattern matching using search schemes. iScience. 2021;24(7): 102687. https:\/\/doi.org\/10.1016\/j.isci.2021.102687.","journal-title":"iScience."},{"key":"281_CR28","doi-asserted-by":"publisher","unstructured":"Renders L, Depuydt L, Fostier J. Approximate pattern matching using search schemes and in-text verification. In: Bioinformatics and biomedical engineering. Cham: Springer International Publishing; 2022. p. 419\u201335. https:\/\/doi.org\/10.1007\/978-3-031-07802-6_36.","DOI":"10.1007\/978-3-031-07802-6_36"},{"key":"281_CR29","doi-asserted-by":"publisher","unstructured":"Renders L, Depuydt L, Rahmann S, Fostier J. Automated design of efficient search schemes for lossless approximate pattern matching. In: Research in computational molecular biology. Cham: Springer Nature Switzerland; 2024. p. 164\u201384. https:\/\/doi.org\/10.1007\/978-1-0716-3989-4_11.","DOI":"10.1007\/978-1-0716-3989-4_11"},{"key":"281_CR30","doi-asserted-by":"publisher","unstructured":"Renders L, Depuydt L, Gagie T, Fostier J. Columba: fast approximate pattern matching with optimized search schemes. bioRxiv. 2025. https:\/\/doi.org\/10.1101\/2025.03.26.645543.","DOI":"10.1101\/2025.03.26.645543"},{"issue":"1","key":"281_CR31","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1186\/S12859-023-05531-6","volume":"24","author":"L Depuydt","year":"2023","unstructured":"Depuydt L, Renders L, Abeel T, Fostier J. Pan-genome de Bruijn graph using the bidirectional FM-index. BMC Bioinform. 2023;24(1):400. https:\/\/doi.org\/10.1186\/S12859-023-05531-6.","journal-title":"BMC Bioinform."},{"key":"281_CR32","doi-asserted-by":"publisher","unstructured":"Brown NK, Gagie T, Rossi M. RLBWT tricks. In: Data compression conference, DCC 2022, Snowbird, UT, USA, March 22\u201325, 2022. IEEE; 2022. p. 444. https:\/\/doi.org\/10.1109\/DCC52660.2022.00055.","DOI":"10.1109\/DCC52660.2022.00055"},{"key":"281_CR33","doi-asserted-by":"publisher","unstructured":"The 1000 Genomes Project Consortium. A global reference for human genetic variation. Nature. 2015;526(7571):68\u201374. https:\/\/doi.org\/10.1038\/nature15393.","DOI":"10.1038\/nature15393"},{"issue":"1","key":"281_CR34","doi-asserted-by":"publisher","first-page":"13:1","DOI":"10.1186\/S13015-019-0148-5","volume":"14","author":"C Boucher","year":"2019","unstructured":"Boucher C, Gagie T, Kuhnle A, Langmead B, Manzini G, Mun T. Prefix-free parsing for building big BWTs. Algorithms Mol Biol. 2019;14(1):13:1-13:15. https:\/\/doi.org\/10.1186\/S13015-019-0148-5.","journal-title":"Algorithms Mol Biol."},{"key":"281_CR35","doi-asserted-by":"publisher","unstructured":"Cobas D, Gagie T, Navarro G. A fast and small subsampled R-index. In: 32nd annual symposium on combinatorial pattern matching (CPM 2021). vol. 191 of Leibniz international Proceedings in informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik; 2021. p. 13:1\u201313:16. https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2021.13.","DOI":"10.4230\/LIPIcs.CPM.2021.13"},{"key":"281_CR36","doi-asserted-by":"publisher","unstructured":"Goga A, Depuydt L, Brown NK, Fostier J, Gagie T, Navarro G. Faster maximal exact matches with lazy LCP evaluation. In: 2024 data compression conference (DCC); 2024. p. 123\u201332. https:\/\/doi.org\/10.1109\/DCC58796.2024.00020.","DOI":"10.1109\/DCC58796.2024.00020"}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-025-00281-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s13015-025-00281-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-025-00281-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,12]],"date-time":"2025-08-12T15:12:57Z","timestamp":1755011577000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/s13015-025-00281-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,12]]},"references-count":36,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2025,12]]}},"alternative-id":["281"],"URL":"https:\/\/doi.org\/10.1186\/s13015-025-00281-x","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-5367343\/v1","asserted-by":"object"}]},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,8,12]]},"assertion":[{"value":"31 October 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 May 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 August 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":"Ethics Approval and Consent to Participate"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for Publication"}},{"value":"The authors declare that they have no Conflict of interest.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing Interests"}}],"article-number":"15"}}