2026-07-23T19:12:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18644 2024-03-06T11:02:20Z ddc:004 open_access

Fulgor: A Fast and Compact {k-mer} Index for Large-Scale Matching and Color Queries Fan, Jason Singh, Noor Pratap Khan, Jamshed Pibiri, Giulio Ermanno Patro, Rob k-mers Colored de Bruijn Graph Compression Read-mapping The problem of sequence identification or matching - determining the subset of reference sequences from a given collection that are likely to contain a short, queried nucleotide sequence - is relevant for many important tasks in Computational Biology, such as metagenomics and pan-genome analysis. Due to the complex nature of such analyses and the large scale of the reference collections a resource-efficient solution to this problem is of utmost importance. This poses the threefold challenge of representing the reference collection with a data structure that is efficient to query, has light memory usage, and scales well to large collections. To solve this problem, we describe how recent advancements in associative, order-preserving, k-mer dictionaries can be combined with a compressed inverted index to implement a fast and compact colored de Bruijn graph data structure. This index takes full advantage of the fact that unitigs in the colored de Bruijn graph are monochromatic (all k-mers in a unitig have the same set of references of origin, or "color"), leveraging the order-preserving property of its dictionary. In fact, k-mers are kept in unitig order by the dictionary, thereby allowing for the encoding of the map from k-mers to their inverted lists in as little as 1+o(1) bits per unitig. Hence, one inverted list per unitig is stored in the index with almost no space/time overhead. By combining this property with simple but effective compression methods for inverted lists, the index achieves very small space. We implement these methods in a tool called Fulgor. Compared to Themisto, the prior state of the art, Fulgor indexes a heterogeneous collection of 30,691 bacterial genomes in 3.8× less space, a collection of 150,000 Salmonella enterica genomes in approximately 2× less space, is at least twice as fast for color queries, and is 2-6 × faster to construct. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jason Fan and Noor Pratap Singh and Jamshed Khan and Giulio Ermanno Pibiri and Rob Patro 2023 Is Part Of LIPIcs, Volume 273, 23rd International Workshop on Algorithms in Bioinformatics (WABI 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WABI.2023.18 urn:nbn:de:0030-drops-186446 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2023.18 eng https://creativecommons.org/licenses/by/4.0/legalcode