HyperSketch: de Bruijn graph sketching for genomic similarity estimation with Hyperdimensional Computing
Listed in
This article is not in any list yet, why not save it to one of your lists.Abstract
Background
The exponential growth of genomic databases necessitates alignment-free methods for comparing genomes. While MinHash-based tools have revolutionized this field by efficiently estimating the Average Nucleotide Identity based on k-mer sets, they inherently discard structural genomic information.
Methods
We introduce HyperSketch, a novel sketching tool that encodes the de Bruijn graph structure of a genome into a fixed-size, topology-aware vector using Hyperdimensional Computing (HDC). Unlike set-based sketches, HyperSketch encodes the transitions between adjacent k-mers into a superposition of orthogonal hypervectors. To formalize parameter selection, we also propose an analytical framework proving that graph-based sketches fundamentally require a smaller k-mer size than set-based models due to their expanded k+1 biological footprint.
Results
We benchmarked HyperSketch against Mash and HyperGen using a dataset of ∼26 thousand viral reference genomes from NCBI GenBank. Under optimal parameters, we demonstrate a strong linear correlation (>99%) between HyperSketch’s graph-based similarity and standard MinHash distance estimates. Crucially, we show that the mathematical formulation of HyperSketch introduces a distance scaling effect that expands the dynamic range of estimates for closely related strains, providing a higher-resolution metric for sub-lineage clustering than purely compositional estimators.
Conclusions
HyperSketch provides a computationally efficient, structure-aware alternative to traditional sketching. By natively encoding genomic syntax, it offers a new dimension of genomic comparison that excels at both high-resolution strain differentiation and deep evolutionary scaling, complementing existing nucleotide identity metrics without requiring sequence alignment.
