ntHash2

ntHash2 implements spaced-seed hashing for nucleotide sequences to compute canonical hash values of k-mers, increasing sensitivity in the presence of base mismatches while accelerating sequence comparison and reducing hash collisions.

Key Features:

• Spaced-seed support: Uses spaced seeds (gapped seed patterns) as an alternative to contiguous k-mers to improve sensitivity and specificity when base mismatch rates are high.
• Efficiency: Achieves up to 2.1× speed improvement over its predecessor and up to 3.8× speed improvement over conventional hashing algorithms naively adapted for spaced seeds.
• Collision reduction: Refines the canonical hashing mechanism to produce a more uniform hash distribution and reduce hash collisions, particularly for longer k-mer lengths.
• Integration capability: Provides a hashing approach intended for incorporation into other bioinformatics tools and workflows for nucleotide sequence analysis.

Scientific Applications:

• Genome research: Accelerates large-scale nucleotide sequence comparison and indexing in genome-scale analyses.
• Comparative genomics: Improves sensitivity when aligning or comparing sequences with substitutions by leveraging spaced seeds.
• Metagenomics: Enhances sequence-level comparisons in mixed-community datasets where high mismatch rates and sequence diversity are common.
• Sequence alignment and hashing-based analyses: Serves hashing and indexing steps in alignment, assembly, and k-mer–based comparative analyses.

Methodology:

Computes spaced-seed hashes over nucleotide k-mers using a refined canonical hashing mechanism to optimize hash distribution, reduce collisions, and improve computational performance.