BLEND

BLEND identifies exact and highly similar (fuzzy) seeds in genomic sequences using SimHash to enable sensitive and memory-efficient read overlapping and mapping for improved de novo genome assemblies.

Key Features:

• Fuzzy seed matching: Identifies both exact-matching and highly similar seeds via fuzzy seed matches.
• SimHash-based hashing: Utilizes the SimHash technique to generate identical hash values for similar seed sets.
• Set representation of seeds: Treats seeds as sets before hashing to enable similarity-preserving hashes.
• Single-hash lookup: Performs a single lookup of hash values to efficiently identify fuzzy seed matches.
• Reduced reliance on alignment: Addresses limitations of conventional hashing that assign distinct hashes to similar seeds, reducing the need for costly sequence alignment and improving sensitivity.
• Read overlapping performance: Achieves speed improvements over minimap2 ranging from 2.4× to 83.9× (average 19.3×) and a lower memory footprint by 0.9× to 14.1× (average 3.8×) for read overlapping tasks.
• Read mapping performance: Outperforms minimap2 in read mapping with speed enhancements ranging from 0.8× to 4.1× (average 1.7×).
• Overlap quality: Produces higher-quality overlaps that are important for accurate de novo genome assemblies.

Scientific Applications:

• Read overlapping: Accelerates detection of overlaps between reads with measured speed gains of 2.4×–83.9× and reduced memory usage of 0.9×–14.1× versus minimap2.
• Read mapping: Improves mapping throughput with speed enhancements of 0.8×–4.1× compared to minimap2.
• De novo genome assembly: Enhances overlap quality used in de novo assembly pipelines, supporting more accurate assemblies.

Methodology:

BLEND treats seeds as sets, applies SimHash to produce similarity-preserving hash values, and performs single-lookups of those hashes to identify fuzzy seed matches.