biHash: bisulfite-aware recursive nucleotide hashing

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.