{
  "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.",
  "abstract_shown": true,
  "affiliations": [
    "Cleveland Clinic Foundation"
  ],
  "article_type": "New results",
  "arxiv": null,
  "author_total": 5,
  "authors": [
    {
      "name": "F. Cumbo"
    },
    {
      "name": "K. Dhillon"
    },
    {
      "name": "M. H. Najafi"
    },
    {
      "name": "S. Aygun"
    },
    {
      "affs": [
        0
      ],
      "name": "D. Blankenberg"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/6x2136fz4e24b.bib",
  "cited_by": 0,
  "doi": "10.64898/2026.09.01.748726",
  "fulltext_url": "https://www.biorxiv.org/content/10.64898/2026.09.01.748726v1.full",
  "id": "6x2136fz4e24b",
  "issns": [],
  "landing_url": "https://www.biorxiv.org/content/10.64898/2026.09.01.748726v1",
  "language": null,
  "licence": "CC-BY",
  "licence_label": "CC BY",
  "licence_source": "article",
  "licence_url": "https://creativecommons.org/licenses/by/4.0/",
  "metadata_licence": null,
  "native_subjects": [
    [
      "biorxiv",
      "bioinformatics"
    ],
    [
      "openalex",
      "1312|Genomics and Phylogenetic Studies"
    ]
  ],
  "openalex": "W7211916529",
  "pdf_url": "https://www.biorxiv.org/content/10.64898/2026.09.01.748726v1.full.pdf",
  "pmcid": null,
  "pmid": null,
  "published": "2026-09-01",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/6x2136fz4e24b.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:19:47Z",
      "native_id": "10.64898/2026.09.01.748726",
      "source": "biorxiv",
      "url": "https://www.biorxiv.org/content/10.64898/2026.09.01.748726v1"
    }
  ],
  "subjects": [
    {
      "field": "biology",
      "origin": "biorxiv:bioinformatics",
      "subfield": "bioinformatics"
    }
  ],
  "title": "HyperSketch: de Bruijn graph sketching for genomic similarity estimation with Hyperdimensional Computing",
  "title_text": "HyperSketch: de Bruijn graph sketching for genomic similarity estimation with Hyperdimensional Computing",
  "type": "preprint",
  "updated_at": "2026-10-30T12:19:47Z",
  "url": "https://research.draconitic.com/paper/6x2136fz4e24b",
  "venue": "bioRxiv",
  "versions": []
}