ArticleAlgorithms for molecular biology : AMB2024
Fulgor: a fast and compact k-mer index for large-scale matching and color queries.
Article in Algorithms for molecular biology : AMB, 2024. The graph could read no effect estimate from its abstract, so it casts no vote on the map. Cited by 21 papers.
What it found
Each row is one number read from the abstract, on the scale the paper reported it, with its interval. Left of the dashed line favours the treatment, right favours the comparator. Under each row is the sentence it came from. New to these charts? A ten-minute tutorial.
The abstract states no effect estimate the extractor could read, or names no intervention and outcome on the map, so this paper lights no cell and moves no belief. It is still indexed, cited and linked below.
The trial behind it
Trials whose registry record cites this paper, or whose number appears in the abstract. A trial that started after this paper was published is citing it as background, not reporting it.
Neither the registry nor the abstract names a trial number. If this is a trial report, that itself is worth knowing.
Who cites it
21 citing papers in PubMed.
- Article
- Optimizing sparse and skew hashing: faster k-mer dictionaries.Bioinformatics (Oxford, England) · 2026Article
- krepp: a k-mer-based maximum pseudo-likelihood method for estimating read distances and genome-wide phylogenetic placement.Genome biology · 2026Article
- Optimizing sparse and skew hashing: fasterbioRxiv : the preprint server for biology · 2026Article
- Kaminari: a frugal colored index for approximateBioinformatics advances · 2026Article
- Robust 16S rRNA classification based on a compressed LCA index.Genome research · 2025Article
- BioSet2Vec: extraction of k-mer dictionaries from multiple sets of biological sequences via big data technologies.BMC bioinformatics · 2025Article
- Alevin-fry-atac enables rapid and memory frugal mapping of single-cell ATAC-seq data using virtual colors for accurate genomic pseudoalignment.Bioinformatics (Oxford, England) · 2025Article
- The open-closed mod-minimizer algorithm.Algorithms for molecular biology : AMB · 2025Article
- Fast and Scalable Parallel External-Memory Construction of Colored Compacted de Bruijn Graphs with Cuttlefish 3.bioRxiv : the preprint server for biology · 2025Article
- Movi Color: fast and accurate taxonomic classification with the move structure.ACM-BCB ... ... : the ... ACM Conference on Bioinformatics, Computational Biology and Biomedicine. ACM Conference on Bioinformatics, Computational Biology and Biomedicine · 2025Article
- K2R: Tinted de Bruijn graphs implementation for efficient read extraction from sequencing datasets.Bioinformatics advances · 2025Article
- Movi: A fast and cache-efficient full-text pangenome index.iScience · 2024Article
- kmerDB: A database encompassing the set of genomic and proteomic sequence information for each species.Computational and structural biotechnology journal · 2024Article
- BWT construction and search at the terabase scale.Bioinformatics (Oxford, England) · 2024Article
- When less is more: sketching with minimizers in genomics.Genome biology · 2024Review
- Where the Patterns Are: Repetition-Aware Compression for Colored de Bruijn GraphsJournal of computational biology : a journal of computational molecular cell biology · 2024Article
- Conway-Bromage-Lyndon (CBL): an exact, dynamic representation of k-mer sets.Bioinformatics (Oxford, England) · 2024Article
- Label-guided seed-chain-extend alignment on annotated De Bruijn graphs.Bioinformatics (Oxford, England) · 2024Article
- Designing efficient randstrobes for sequence similarity analyses.Bioinformatics (Oxford, England) · 2024Article
Corrections and comments
- Update of
Authors and funding
5 authors.
Funding
Abstract
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 pangenome 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 an efficient colored de Bruijn graph index, arising as the combination of a k-mer dictionary with a compressed inverted index. The proposed index takes full advantage of the fact that unitigs in the colored compacted de Bruijn graph are monochromatic (i.e., all k-mers in a unitig have the same set of references of origin, or color). Specifically, the unitigs are kept in the dictionary in color order, thereby allowing for the encoding of the map from k-mers to their colors in as little as 1 + o(1) bits per unitig. Hence, one color per unitig is stored in the index with almost no space/time overhead. By combining this property with simple but effective compression methods for integer lists, the index achieves very small space. We implement these methods in a tool called Fulgor, and conduct an extensive experimental analysis to demonstrate the improvement of our tool over previous solutions. For example, compared to Themisto-the strongest competitor in terms of index space vs. query time trade-off-Fulgor requires significantly less space (up to 43% less space for a collection of 150,000 Salmonella enterica genomes), is at least twice as fast for color queries, and is 2-6[Formula: see text] faster to construct.
Indexed as
Identifiers
What OpenQuestion holds
Registered trials
Read under generation 80e0d062 · epoch 390. Bibliography from PubMed, PubMed Central and OpenAlex; grants from NIH RePORTER; trial links from ClinicalTrials.gov; estimates, votes and beliefs from the OpenQuestion graph.