Algorithms for Molecular Biology · 2024 · 37 citations · 34 references
Life SciencesBioinformaticsComputer ScienceData StructuresGenomicsMetagenomicsGenomic DatabasesSequence AlignmentSequence Similarity SearchColored De Bruijn GraphsCompressionIndexing Data StructuresInverted Index StructuresInverted IndexesK-mer IndexingPangenome AnalysisSequence Similarity
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.
34
Basic local alignment search tool
Stephen F. Altschul, Warren Gish, Webb Miller et al. · Journal of Molecular Biology · 1990 · 94.5K citations
Near-optimal probabilistic RNA-seq quantification
Nicolas Bray, Harold Pimentel, Páll Melsted et al. · Nature Biotechnology · 2016 · 11K citations · Full text
Improved metagenomic analysis with Kraken 2
Derrick E. Wood, Jennifer Lu, Ben Langmead · Genome biology · 2019 · 7.1K citations · Full text
The complete sequence of a human genome
Sergey Nurk, Sergey Koren, Arang Rhie et al. · Science · 2022 · 3.3K citations · Full text