More Like this

1. Fulgor: A Fast and Compact k-mer Index for Large-Scale Matching and Color Queries

   https://doi.org/10.4230/LIPIcs.WABI.2023.18  

   Fan, Jason; Singh, Noor Pratap; Khan, Jamshed; Pibiri, Giulio Ermanno; Patro, Rob (August 2023, 23rd International Workshop on Algorithms in Bioinformatics (WABI 2023))

   Belazzougui, Djamal; Ouangraoua, Aïda (Ed.)

   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. 

   more » « less
2. Compression algorithm for colored de Bruijn graphs

   https://doi.org/10.1186/s13015-024-00254-6  

   Rahman, Amatur; Dufresne, Yoann; Medvedev, Paul (December 2024, Algorithms for Molecular Biology)

   Abstract A colored de Bruijn graph (also called a set of k-mer sets), is a set of k-mers with every k-mer assigned a set of colors. Colored de Bruijn graphs are used in a variety of applications, including variant calling, genome assembly, and database search. However, their size has posed a scalability challenge to algorithm developers and users. There have been numerous indexing data structures proposed that allow to store the graph compactly while supporting fast query operations. However, disk compression algorithms, which do not need to support queries on the compressed data and can thus be more space-efficient, have received little attention. The dearth of specialized compression tools has been a detriment to tool developers, tool users, and reproducibility efforts. In this paper, we develop a new tool that compresses colored de Bruijn graphs to disk, building on previous ideas for compression of k-mer sets and indexing colored de Bruijn graphs. We test our tool, called ESS-color, on various datasets, including both sequencing data and whole genomes. ESS-color achieves better compression than all evaluated tools and all datasets, with no other tool able to consistently achieve less than 44% space overhead. The software is available athttp://github.com/medvedevgroup/ESSColor. 

   more » « less
3. ESKEMAP: exact sketch-based read mapping

   https://doi.org/10.1186/s13015-024-00261-7  

   Schulz, Tizian; Medvedev, Paul (December 2024, Algorithms for Molecular Biology)

   Abstract BackgroundGiven a sequencing read, the broad goal of read mapping is to find the location(s) in the reference genome that have a “similar sequence”. Traditionally, “similar sequence” was defined as having a high alignment score and read mappers were viewed as heuristic solutions to this well-defined problem. For sketch-based mappers, however, there has not been a problem formulation to capture what problem an exact sketch-based mapping algorithm should solve. Moreover, there is no sketch-based method that can find all possible mapping positions for a read above a certain score threshold. ResultsIn this paper, we formulate the problem of read mapping at the level of sequence sketches. We give an exact dynamic programming algorithm that finds all hits above a given similarity threshold. It runs in$$\mathcal {O} (|t| + |p| + \ell ^2)$$ $O\left(\right|t|+|p|+{\ell }^2)$time and$$\mathcal {O} (\ell \log \ell )$$ $O(\ell log\ell )$space, where |t| is the number of$$k$$ $k$-mers inside the sketch of the reference, |p| is the number of$$k$$ $k$-mers inside the read’s sketch and$$\ell$$ $\ell$is the number of times that$$k$$ $k$-mers from the pattern sketch occur in the sketch of the text. We evaluate our algorithm’s performance in mapping long reads to the T2T assembly of human chromosome Y, where ampliconic regions make it desirable to find all good mapping positions. For an equivalent level of precision as minimap2, the recall of our algorithm is 0.88, compared to only 0.76 of minimap2. 

   more » « less
4. Cuttlefish: fast, parallel and low-memory compaction of de Bruijn graphs from large-scale genome collections

   https://doi.org/10.1093/bioinformatics/btab309  

   Khan, Jamshed; Patro, Rob (July 2021, Bioinformatics)

   null (Ed.)

   Abstract Motivation The construction of the compacted de Bruijn graph from collections of reference genomes is a task of increasing interest in genomic analyses. These graphs are increasingly used as sequence indices for short- and long-read alignment. Also, as we sequence and assemble a greater diversity of genomes, the colored compacted de Bruijn graph is being used more and more as the basis for efficient methods to perform comparative genomic analyses on these genomes. Therefore, time- and memory-efficient construction of the graph from reference sequences is an important problem. Results We introduce a new algorithm, implemented in the tool Cuttlefish, to construct the (colored) compacted de Bruijn graph from a collection of one or more genome references. Cuttlefish introduces a novel approach of modeling de Bruijn graph vertices as finite-state automata, and constrains these automata’s state-space to enable tracking their transitioning states with very low memory usage. Cuttlefish is also fast and highly parallelizable. Experimental results demonstrate that it scales much better than existing approaches, especially as the number and the scale of the input references grow. On a typical shared-memory machine, Cuttlefish constructed the graph for 100 human genomes in under 9 h, using ∼29 GB of memory. On 11 diverse conifer plant genomes, the compacted graph was constructed by Cuttlefish in under 9 h, using ∼84 GB of memory. The only other tool completing these tasks on the hardware took over 23 h using ∼126 GB of memory, and over 16 h using ∼289 GB of memory, respectively. Availability and implementation Cuttlefish is implemented in C++14, and is available under an open source license at https://github.com/COMBINE-lab/cuttlefish. Supplementary information Supplementary data are available at Bioinformatics online. 

   more » « less
5. Better Hardness Results for the Minimum Spanning Tree Congestion Problem

   https://doi.org/10.1007/s00453-024-01278-5  

   Luu, Huong; Chrobak, Marek (January 2025, Algorithmica)

   Abstract In the spanning tree congestion problem, given a connected graphG, the objective is to compute a spanning treeTinGthat minimizes its maximum edge congestion, where the congestion of an edgeeofTis the number of edges inGfor which the unique path inTbetween their endpoints traversese. The problem is known to be$$\mathbb{N}\mathbb{P}$$ $NP$-hard, but its approximability is still poorly understood, and it is not even known whether the optimum solution can be efficiently approximated with ratioo(n). In the decision version of this problem, denoted$${\varvec{K}-\textsf {STC}}$$ $K-\mathrm{STC}$, we need to determine ifGhas a spanning tree with congestion at mostK. It is known that$${\varvec{K}-\textsf {STC}}$$ $K-\mathrm{STC}$is$$\mathbb{N}\mathbb{P}$$ $NP$-complete for$$K\ge 8$$ $K\ge 8$, and this implies a lower bound of 1.125 on the approximation ratio of minimizing congestion. On the other hand,$${\varvec{3}-\textsf {STC}}$$ $3-\mathrm{STC}$can be solved in polynomial time, with the complexity status of this problem for$$K\in { \left\{ 4,5,6,7 \right\} }$$ $K\in \left(4,,,5,,,6,,,7\right)$remaining an open problem. We substantially improve the earlier hardness results by proving that$${\varvec{K}-\textsf {STC}}$$ $K-\mathrm{STC}$is$$\mathbb{N}\mathbb{P}$$ $NP$-complete for$$K\ge 5$$ $K\ge 5$. This leaves only the case$$K=4$$ $K=4$open, and improves the lower bound on the approximation ratio to 1.2. Motivated by evidence that minimizing congestion is hard even for graphs of small constant radius, we also consider$${\varvec{K}-\textsf {STC}}$$ $K-\mathrm{STC}$restricted to graphs of radius 2, and we prove that this variant is$$\mathbb{N}\mathbb{P}$$ $NP$-complete for all$$K\ge 6$$ $K\ge 6$. 

   more » « less