genCRC32: collision-free CRC32-based hashing of DNA sequences

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Efficient and collision-free hashing of DNA sequences is critical for bioinformatics tools like genome assembly and sequence alignment.
• Traditional hashing methods often lead to collisions, compromising the accuracy and performance of downstream analyses.
• The practical limits of 32-bit hashing are reached for DNA k-mers up to length 16, necessitating improved hashing strategies.

Purpose of the Study:

• To evaluate genCRC32 as a hashing primitive for DNA sequences.
• To assess its collision behavior, bucket balance, sensitivity to single-base changes, and speed.
• To determine its suitability for collision-free mapping of DNA k-mers up to length 16.

Main Methods:

• Developed genCRC32 by combining a gen32 preprocessing step with CRC32 hashing.
• Identified eight specific CRC32 polynomials that guarantee collision-free hashing for DNA k-mers up to length 16.
• Conducted extensive empirical evaluations and benchmark tests comparing genCRC32 with established hashing methods.

Main Results:

• genCRC32 achieved zero collisions for all DNA k-mers up to length 16, ensuring a one-to-one mapping.
• The preprocessing step introduced minimal computational overhead, maintaining hashing performance comparable to MurmurHash3 and xxHash32.
• The method demonstrated good bucket balance and sensitivity to single-base changes.

Conclusions:

• genCRC32 is an effective and efficient hashing method for DNA sequences, particularly for k-mers up to length 16.
• Its collision-free nature and comparable performance make it a valuable primitive for bioinformatics applications.
• The publicly available Go implementation facilitates integration into existing bioinformatics workflows.