2026-07-23T22:21:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23251 2025-10-27T10:36:16Z ddc:004 open_access

Pangenome Graph Indexing via the Multidollar-BWT Cozzi, Davide Riccardi, Brian Denti, Luca Ciccolella, Simone Sadakane, Kunihiko Bonizzoni, Paola Multidollar-BWT Graph Index Graph Pattern Matching Pangenome Graph Indexing pangenome graphs is a major algorithmic challenge in computational pangenomics, a recent and active research field that seeks to use graphs as representations of multiple genomes. Since these graphs are constructed from whole genome sequences of a species population, they can become very large, making indexing one of the most challenging problems. In this paper, we propose gindex, a novel indexing approach to solve the Graph Pattern Matching Problem based on the multidollar-BWT. Specifically, gindex aims to find all occurrences of a pattern in a sequence-labeled graph by overcoming two main limitations of GCSA2, one of the most widely used graph indexes: handling queries of arbitrary length and scaling to large graphs without pruning any complex regions. Moreover, we show how a smart preprocessing step can optimize the use of multidollar-BWT to skip small redundant sub-patterns and enhance gindex’s querying capabilities. We demonstrate the effectiveness of our approach by comparing it to GCSA2 in terms of index construction and query time, using different preprocessing modes on three pangenome graphs: one built from Drosophila genomes and two produced by the Human Pangenome Reference Consortium. The results show that gindex can scale on human pangenome graphs - which GCSA2 cannot index using large amounts of RAM - with acceptable memory and time requirements. Moreover, gindex achieves fast query times, although not as fast as GCSA2, which may produce false positives. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Davide Cozzi and Brian Riccardi and Luca Denti and Simone Ciccolella and Kunihiko Sadakane and Paola Bonizzoni 2025 Is Part Of LIPIcs, Volume 338, 23rd International Symposium on Experimental Algorithms (SEA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2025.13 urn:nbn:de:0030-drops-232515 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2025.13 eng https://creativecommons.org/licenses/by/4.0/legalcode