BLEND: A Fast, Memory-Efficient, and Accurate Mechanism to Find Fuzzy Seed Matches in Genome Analysis

Abstract

Generating the hash values of short subsequences, called seeds, enables quickly identifying similarities between genomic sequences by matching seeds with a single lookup of their hash values. However, these hash values can be used only for finding exact-matching seeds as the conventional hashing methods assign distinct hash values for different seeds, including highly similar seeds. Finding only exact-matching seeds causes either 1) increasing the use of the costly sequence alignment or 2) limited sensitivity. We introduce BLEND, the first efficient and accurate mechanism that can identify both exact-matching and highly similar seeds with a single lookup of their hash values, called fuzzy seed matches. BLEND 1) utilizes a technique called SimHash, that can generate the same hash value for similar sets, and 2) provides the proper mechanisms for using seeds as sets with the SimHash technique to find fuzzy seed matches efficiently. We show the benefits of BLEND when used in read overlapping and read mapping. For read overlapping, BLEND is faster by 2.4x - 83.9x (on average 19.3x), has a lower memory footprint by 0.9x - 14.1x (on average 3.8x), and finds higher quality overlaps leading to accurate de novo assemblies than the state-of-the-art tool, minimap2. For read mapping, BLEND is faster by 0.8x - 4.1x (on average 1.7x) than minimap2. Source code is available at https://github.com/CMU-SAFARI/BLEND.

arXiv commentPublished in NARGAB

References in corpus (13)

• Minimap2: pairwise alignment for nucleotide sequences
• Haplotype-resolved de novo assembly with phased assembly graphs
• Minimap and miniasm: fast mapping and de novo assembly for noisy long sequences
• Nanopore Sequencing Technology and Tools for Genome Assembly: Computational Analysis of the Current State, Bottlenecks and Future Directions
• Technology dictates algorithms: Recent developments in read alignment
• GRIM-Filter: Fast Seed Location Filtering in DNA Read Mapping Using Processing-in-Memory Technologies
• FPGA-Based Near-Memory Acceleration of Modern Data-Intensive Applications
• Apollo: A Sequencing-Technology-Independent, Scalable, and Accurate Assembly Polishing Algorithm
• SneakySnake: A Fast and Accurate Universal Genome Pre-Alignment Filter for CPUs, GPUs, and FPGAs
• FiltPIM: In-Memory Filter for DNA Sequencing
• Improving Similarity Search with High-dimensional Locality-sensitive Hashing
• FastRemap: A Tool for Quickly Remapping Reads between Genome Assemblies
• AirLift: A Fast and Comprehensive Technique for Remapping Alignments between Reference Genomes

Cited by in corpus (4)

• RawHash: Enabling Fast and Accurate Real-Time Analysis of Raw Nanopore Signals for Large Genomes
• RawHash2: Mapping Raw Nanopore Signals Using Hash-Based Seeding and Adaptive Quantization
• TargetCall: Eliminating the Wasted Computation in Basecalling via Pre-Basecalling Filtering
• AirLift: A Fast and Comprehensive Technique for Remapping Alignments between Reference Genomes