biHash: bisulfite-aware recursive nucleotide hashing
- 1The University of British Columbia
Abstract
Bisulfite sequencing (BS-seq) measures cytosine methylation on the DNA at single-base resolution, but converts unmethylated cytosines to thymines, disrupting conventional strand complementarity and reducing sequence complexity. These pose a fundamental challenge to efficient sequence comparison and indexing tasks. Although k-mer hashing is foundational to bioinformatics for enabling such high-throughput operations, generic algorithms for string hashing are poorly equipped to handle the reduced-complexity alphabet and sequence ambiguity created by this conversion. We therefore require fast k-mer hashing that directly recognizes bisulfite-compatible sequence states. Here, we present biHash, a rolling hash algorithm tailored for bisulfite-sequenced data. Using context-specific dinucleotide encodings, biHash maps designated bisulfite-compatible sequence variants to the same hash value while retaining context-specific specificity. When hashing adjacent k-mers, biHash performs ~13 times faster than generic string hashing algorithms.
Related
- A Connectome Test of the Fly Hashing Algorithm
- A Multidimensional Arithmetical Ontology for High-Parameter Cytometry: Gaussian Primes and Cryptographic Hashing for Cell Population Standardization
- Analysis of single nucleotide substitution in CYP21A2 gene using Alphagenome
- A curated genome-scale nucleotide diversity panel of non-human primates
- Single-nucleotide genome editing uncovers the biological impact of rs16944 in the IL1B promoter
BibTeX
@misc{wong2026bihash,
title = {{biHash: bisulfite-aware recursive nucleotide hashing}},
author = {j. wong and I. Birol},
howpublished = {bioRxiv},
year = {2026},
month = oct,
doi = {10.64898/2026.10.19.760264},
url = {https://www.biorxiv.org/content/10.64898/2026.10.19.760264v1},
note = {CC BY-NC},
}
RIS
TY - UNPB
TI - biHash: bisulfite-aware recursive nucleotide hashing
AU - j. wong
AU - I. Birol
PY - 2026
DA - 2026/10/19
PB - bioRxiv
DO - 10.64898/2026.10.19.760264
UR - https://www.biorxiv.org/content/10.64898/2026.10.19.760264v1
AB - Bisulfite sequencing (BS-seq) measures cytosine methylation on the DNA at single-base resolution, but converts unmethylated cytosines to thymines, disrupting conventional strand complementarity and reducing sequence complexity. These pose a fundamental challenge to efficient sequence comparison and indexing tasks. Although k-mer hashing is foundational to bioinformatics for enabling such high-throughput operations, generic algorithms for string hashing are poorly equipped to handle the reduced-complexity alphabet and sequence ambiguity created by this conversion. We therefore require fast k-mer hashing that directly recognizes bisulfite-compatible sequence states. Here, we present biHash, a rolling hash algorithm tailored for bisulfite-sequenced data. Using context-specific dinucleotide encodings, biHash maps designated bisulfite-compatible sequence variants to the same hash value while retaining context-specific specificity. When hashing adjacent k-mers, biHash performs ~13 times faster than generic string hashing algorithms.
ER -