HyperSketch: de Bruijn graph sketching for genomic similarity estimation with Hyperdimensional Computing
- 1Cleveland Clinic Foundation
Abstract
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. 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. 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 the graph-based similarity computed by HyperSketch 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. 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.
Related
- Sketching the SRA: experiment-wide similarity search across 4.8 million metagenomes
- Scale-dependent associations between genetic similarity and aggregation behaviour in three toad lineages
- Individualized morphometric-similarity deviations in autism linked to cortical hierarchy and microarchitecture
- Regional similarity to male-typical brain architecture links childhood ADHD to neurophysiological aging in later adulthood
- Regional Similarity to Sex-Typical Young Adult Brain Architecture is a Longitudinal Correlate of Neuroinflammation and Depression in Later Adulthood
BibTeX
@misc{cumbo2026hypersketch,
title = {{HyperSketch: de Bruijn graph sketching for genomic similarity estimation with Hyperdimensional Computing}},
author = {F. Cumbo and K. Dhillon and M. H. Najafi and S. Aygun and D. Blankenberg},
howpublished = {bioRxiv},
year = {2026},
month = sep,
doi = {10.64898/2026.09.01.748726},
url = {https://www.biorxiv.org/content/10.64898/2026.09.01.748726v1},
note = {CC BY},
}
RIS
TY - UNPB
TI - HyperSketch: de Bruijn graph sketching for genomic similarity estimation with Hyperdimensional Computing
AU - F. Cumbo
AU - K. Dhillon
AU - M. H. Najafi
AU - S. Aygun
AU - D. Blankenberg
PY - 2026
DA - 2026/09/01
PB - bioRxiv
DO - 10.64898/2026.09.01.748726
UR - https://www.biorxiv.org/content/10.64898/2026.09.01.748726v1
AB - 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. 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. 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 the graph-based similarity computed by HyperSketch 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. 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.
ER -