Fractional Hitting Sets Accelerate Genomic Multiset Sketching While Slashing Memory Use

A new computational framework based on fractional hitting sets enables researchers to compress massive genomic sequencing datasets into compact sketches that use an order of magnitude less space and memory than state-of-the-art tools while operating several times faster. Developed to address the computational bottlenecks associated with analyzing massive microbial collections, the method has been implemented in an open-source tool called supersampler. In formal evaluations conducted on extensive collections of bacterial genomes, supersampler achieved similarity estimations comparable to those of sourmash while reducing random-access memory requirements by a factor of five and disk storage by up to fifty-fold. By encoding sampled sub-sequences as super-k-mers partitioned by shared minimizers, the software provides an exact plain-text representation of sampled sequence space rather than relying on hashed integer fingerprints. This design eliminates false-positive matching errors and allows bioinformaticians to retrieve specific sequences of interest directly from compressed sketches, providing a scalable algorithmic solution for querying repositories that currently hold millions of microbial assemblies.

The exponential expansion of public sequencing repositories, including the Sequence Read Archive and the GenBank database, has created an urgent need for data structures capable of querying terabase-scale collections. GenBank alone hosts more than 1.2 million bacterial genomes totaling over five terabases of nucleotide sequence, making traditional pairwise alignment algorithms such as BLAST computationally prohibitive for large-scale metagenomic characterization. While exact k-mer indexing structures offer linear query times, their memory footprints become unsustainable when applied to extensive reference collections. Probabilistic data structures mitigate memory constraints by accepting bounded false-positive rates on large queries, but fixed-size sketches such as MinHash, HyperLogLog, and HyperMinHash degrade in accuracy when comparing divergent documents whose sequence content differs by multiple orders of magnitude. Scaled sketches, exemplified by sourmash through scaled MinHash and FracMinHash, address divergent dataset sizes by selecting a fraction of k-mers whose sketch size scales linearly with input volume. However, because sourmash represents selected k-mers as generic thirty-two-bit integer fingerprints stored in flat dictionaries, it incurs substantial memory overhead and fails to exploit sequence redundancies specific to biological strings.

To overcome the limitations of generic fingerprint dictionaries, the authors formulated the theoretical concept of Fractional Hitting Sets as a practical relaxation of Universal Hitting Sets. In genomic algorithms, a Universal Hitting Set is defined over an alphabet of size four as a set of small sub-strings of length m, known as minimizers, such that every sequence of w consecutive m-mers contains at least one element from the set, where w equals k minus m plus one. Universal Hitting Sets guarantee total coverage across the k-mer space, but sketching applications require only a representative fraction f of the k-mer space rather than complete coverage. The authors designed Fractional Hitting Sets to encompass at least a target fraction f of consecutive m-mer windows in expectation by employing a random hash function that uniformly distributes m-mers across an integer range up to four to the power of m. By selecting small minimizers whose hash values fall below a calculated threshold, the scheme ensures that each k-mer possessing distinct constituent m-mers has an independent probability of containing a selected small minimizer, guaranteeing unbiased, uniform sampling across the entire sequence space.

The mathematical analysis of Fractional Hitting Sets reveals fundamental improvements in minimizer density, which measures the sparsity of selected positions. Whereas classical random minimizer schemes achieve an expected density of two divided by w plus one, and Universal Hitting Sets cannot theoretically breach a density barrier of one point five divided by w plus one, Fractional Hitting Sets achieve significantly lower densities by leaving non-selected regions uncovered. The authors demonstrated that the expected density of small minimizers across an entire random sequence is upper bounded by two times f divided by w plus one, plus a negligible asymptotic term. When evaluating the restricted density over only the covered sequence fraction, the bound takes the form of two multiplied by f plus one minus f times the natural logarithm of one minus f, all divided by f squared times w plus one. This restricted density factor transitions smoothly from two when f equals one down to the optimal value of one as f approaches zero, enabling the indexing of substantially longer overlapping sequence blocks than classical schemes permit.

By capitalizing on low selection densities, supersampler organizes covered k-mers into super-k-mers, which are maximal sub-strings in which every consecutive k-mer shares the exact same minimizer. Super-k-mers function as Spectrum Preserving String Sets, which compactly spell out k-mer collections by avoiding the redundant repetition of shared nucleotide bases. While an isolated k-mer typically requires two k bits of storage, a super-k-mer containing x k-mers spans k plus x minus one bases and requires only two times k plus x minus one divided by x bits per constituent k-mer. Space efficiency reaches its theoretical peak in maximal super-k-mers, which span two k minus m bases, contain exactly w k-mers, and require two times two k minus m divided by k minus m plus one bits per k-mer. The authors proved mathematically that the proportion of maximal super-k-mers among all formed super-k-mers approaches one hundred percent as the sampling fraction f declines toward zero. In practical evaluations, the fraction of maximal super-k-mers reached ninety percent at a subsampling rate of ten, ninety-nine percent at a rate of one hundred, and ninety-nine point nine percent at the standard rate of one thousand.

The underlying data architecture of supersampler partitions sketches into distinct buckets according to their shared minimizer sequences, mimicking the natural division of super-k-mer space into four to the power of m partitions. Because the sketching process retains only small minimizers whose hashes fall below the sampling threshold, only a small subset of non-empty partitions are materialized on disk. Within each partition, the minimizer sequence is stored a single time and omitted from all associated maximal super-k-mers, driving the theoretical encoding cost down to four times k minus m divided by k minus m plus one bits per k-mer. When executing all-versus-all document comparisons, supersampler evaluates only matching partitions between query and reference sets, bypassing entire sub-files whose minimizers do not appear in the query document. Storing compact partitions in memory eliminates the pervasive cache misses suffered by sourmash, which must query a monolithic thirty-two-bit integer hash dictionary for every sampled element, thereby accelerating comparison routines across large collections.

To support noisy real-world sequencing experiments, supersampler incorporates an abundance filtering module that purges low-frequency k-mers generated by sequencing errors. Unlike sourmash, which lacks native abundance filtering and forces users to pre-process raw datasets with separate k-mer counting utilities, supersampler records abundances directly for sampled fingerprints with minimal computational overhead. Because filtering individual erroneous k-mers can fracture contiguous super-k-mers, the algorithm initiates a greedy assembly routine across broken sequences. The assembly phase identifies k-mers that terminate with a minimizer suffix and extends them greedily along neighboring k-mers until maximal super-k-mers are reconstituted. Any residual k-mers that cannot form maximal structures are joined into the longest possible string representations, following simplitig compact encoding paradigms to minimize total base counts. This integrated filtering workflow prevents sequencing noise from inflating sketch sizes while maintaining high fidelity in downstream similarity estimations.

Beyond binary presence-absence comparisons using traditional Jaccard and containment indices, supersampler provides dedicated routines for multiset comparisons via angular similarity. While the cosine similarity between k-mer abundance vectors reflects taxonomic relatedness, the conventional cosine distance metric violates the triangle inequality and therefore does not constitute a true mathematical metric. Supersampler resolves this limitation by computing the angular distance, defined as the arccosine of cosine similarity divided by pi, and subtracting it from one to yield a proper metric space. To track k-mer multiplicities without exhausting system memory, the tool employs an efficient hashmap based on Robin Hood hashing techniques. Furthermore, supersampler implements two heuristic compression strategies to mitigate disk overhead: a logarithmic abundance encoding mode that compresses wide abundance variations, and a super-k-mer average abundance mode that assigns a single mean frequency integer to entire super-k-mer blocks, reducing stored abundance integers by a significant factor.

Rigorous benchmarking on dedicated high-performance hardware validated the empirical advantages of the Fractional Hitting Set implementation over sourmash. Hardware testing on an Intel Xeon Gold 6130 processor with 128 gigabytes of memory demonstrated that for a k-mer length of thirty-one, supersampler utilized five times less random-access memory and sixteen times less disk space than sourmash when indexing 1024 RefSeq bacterial genomes. On dissimilar genomes with Jaccard indices near zero, supersampler executed comparisons fifty times faster due to its partition-skipping mechanics. When testing a larger k-mer length of sixty-three, supersampler reduced disk space consumption by fifty-fold compared to sourmash. In simulated Caenorhabditis elegans sequencing runs at one-hundred-fold coverage with a subsampling rate of one thousand, an abundance-encoded sketch in sourmash required sixteen megabytes of memory, whereas the equivalent supersampler sketch consumed approximately one megabyte. Reference Jaccard and containment metrics calculated using the exact k-mer counting tool Simka confirmed that supersampler maintained approximation accuracy closely aligned with sourmash, exhibiting only a minor variance stemming from localized k-mer clustering around small minimizers.

In extensive scalability trials involving growing cohorts of RefSeq bacterial assemblies ranging from one hundred up to 128,000 distinct genomes, supersampler successfully completed all-versus-all comparisons across the entire 128,000-genome cohort in twenty-five central processing unit hours. Sourmash could only be evaluated up to 32,000 genomes before computational execution times became prohibitive. Although supersampler displayed a slight accuracy dip due to the non-independent clustering of overlapping k-mers, this trade-off is offset by its ability to index substantially larger volumes of sequence data within identical hardware constraints. Furthermore, because supersampler stores exact nucleotide sequences rather than irreversible hash fingerprints, investigators can extract shared sequences directly from compressed sketches for downstream microbiological validation. The authors noted that future enhancements will include benchmarking against Average Nucleotide Identity metrics, exploring sorted fingerprint layouts to reduce comparison complexity, and deriving refined theoretical bounds for restricted density across variable sampling fractions.

Subject of Research: Genomic multiset sketching and sequence comparison algorithms using fractional hitting sets

Article Title: Fractional hitting sets for efficient multiset sketching

Article References: Rouzé, T., Martayan, I., Marchet, C., & Limasset, A. (2025). Fractional hitting sets for efficient multiset sketching. Algorithms for Molecular Biology, 20(1), Article 1. https://doi.org/10.1186/s13015-024-00268-0

Image Credits: AI Generated

DOI: 10.1186/s13015-024-00268-0

Keywords: Fractional Hitting Sets, supersampler, sourmash, super-k-mers, genomic sketching, k-mer indexing, Universal Hitting Sets, metagenomics, Jaccard similarity, containment index, angular distance, Spectrum Preserving String Sets, minimizer schemes, abundance filtering, RefSeq bacterial genomes, Salmonella comparative genomics, cosine similarity