Fast and flexible minimizer digestion with digest

Abstract

Summary: Minimizer digestion is an increasingly common component of bioinformatics tools, including tools for de Bruijn graph assembly and sequence classification. We describe a new open source tool and library to facilitate efficient digestion of genomic sequences. It can produce digests based on the related ideas of minimizers, modimizers or syncmers. Digest uses efficient data structures, scales well to many threads, and produces digests with expected spacings between digested elements.

Availability and implementation: Digest is implemented in C++17 with a Python API, and is available open-source at https://github.com/VeryAmazed/digest. The python library is available on Bioconda. Rust bindings are available as a public crate at https://crates.io/crates/digest-rs.

Figure 1.

(A) Comparison of min query speed for different data structures as a function of window size. In this benchmark, each data-structure performs 10 million queries on an array of uniformly distributed 32-bit hash values. (B) Shows the throughput of the different digestion schemes in Digest (using a segment tree data-structure) when computing the digest of a 62M human chromosome Y sequence consisting of only A/C/G/T characters. Benchmarking for both (A) and (B) were performed on a 48-core 3 GHz Intel Xeon Gold Cascade Lake 6248R CPU with 192 GB RAM.