Approximate $k$ -Mer Matching Using Fuzzy Hash Maps
John Healy, Desmond Chambers · IEEE Transactions on Computational Biology and Bioinformatics · 2014
We present a fuzzy technique for approximate k-mer matching that combines the speed of hashing with the sensitivity of dynamic programming. Our approach exploits the collision detection mechanism used by hash maps, unifying the two phases of "seed and extend" into a single operation that executes in close to O(1) average time.