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

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

BLEND is a mechanism that can efficiently find fuzzy seed matches between sequences to significantly improve the performance and accuracy while reducing the memory space usage of two important applications: 1) finding overlapping reads and 2) read mapping. Finding fuzzy seed matches enable BLEND to find both 1) exact-matching seeds and 2) highly similar seeds. We integrate the BLEND mechanism into Minimap2. We make the following changes in the original Minimap2 implementation:

  • We enable the Minimap2 implementation so that it can find fuzzy seed matches using the BLEND mechanism as the original implementation can only find the exact-matching seeds between sequences. To this end, we change the sketch.c implementation of Minimap2 so that 1) we can generate the seeds that BLEND finds and 2) generate the hash values for seeds to find fuzzy seed matches.
  • We enable the Minimap2 implementation to use seeds longer than 256 bases so that it can store longer seeds when using BLEND by combining the minimizer k-mer with many neighbor k-mers (e.g., hundreds), if necessary. The current implementation of Minimap2 allocates 8-bits to store seed lengths up to 256 characters. We change this requirement in various places of the implementation (e.g., line 112 in sketch.c and line 239 in index.c) so that BLEND can use 14 bits to store seed lengths up to 16384 characters. We do this because BLEND merges many k-mers into a single seed, which may be much larger than a 256 character-long sequence.
  • We disable filtering out the minimizer k-mers (i.e., seeds in BLEND's case) based on their number of maximum occurence. We do this because BLEND enables generating the same hash value for similar seeds, which may lead to many hash values above the maximum threshold. We do not oppose enabling this filtering mechanism, but it requires further investigation on how to set this threshold value for different parameter settings in BLEND. Thus, filtering out the seeds that occur more than X times is a future work for BLEND so that we can define the value X without reducing the accuracy of BLEND.

Cloning the source code

  • Download the code from its GitHub repository:
git clone https://github.com/CMU-SAFARI/BLEND.git blend
  • Alternatively, if you would like to compile the SIMD-compatible version of BLEND, you can clone BLEND with its simde submodule:
git clone --recurse-submodules https://github.com/CMU-SAFARI/BLEND.git blend

Compiling from the source code

Compilation process is similar to Minimap2's compilation as also explained in more detail here. We keep the support for using the SIMD instructions that Minimap2 implements.

Before compiling BLEND:

  • Make sure you have a C compiler and GNU make,

To compile:

cd blend && make

To compile the SIMD-compatible version:

cd blend && make simd

If the compilation is successful, the binary called blend will be located under bin.

Usage

You can print the help message to learn how to use blend:

blend -h

Below we show how to use blend for 1) finding overlapping reads and 2) read mapping when using the default preset parameters for each use application and genome.

BLEND provides the preset parameters depending on:

  • The application: 1) Finding overlapping reads and 2) read mapping.
  • Sequencing Technology: 1) Accurate long reads (e.g., PacBio HiFi reads), 2) erroneous long reads (e.g., PacBio CLR reads), and 2) short reads (i.e., Illumina paired-end reads).
  • Genome: 1) Human, 2) eukaryotic, and 3) bacterial genomes.

Finding Overlapping Reads

Assume that you would like to perform all-vs-all overlapping between all pairs of HiFi reads from a human genome located in file reads.fastq. To find overlapping reads and store them in the PAF file output.paf:

blend -x ava-hifi --genome human reads.fastq reads.fastq > output.paf

Read Mapping

Assume that you would like to map PacBio CLR reads in file reads.fastq to a reference genome in file ref.fasta. To generate the read mapping with the CIGAR output in the SAM file output.sam:

blend -ax map-pb ref.fasta reads.fastq > output.sam

Getting Help

Since we integrate the BLEND mechanism into Minimap2, most portion of the parameters are the same as explained in the man page of Minimap2 or as explained in the public page of minimap2.1, which is subject to change as the new versions of Minamp2 role out. We explain the parameters unique to the BLEND implementation below.

The following option (i.e., neighbors) defines the number of consecutive k-mers that BLEND uses to generate a seed. Thus, if the k-mer length is k, the seed length is neighbors + k - 1. Default value is 10.

--neighbors INT Combines INT amount of k-mers to generate a seed. [10]

The following option (i.e., fixed-bits) defines the number of bits that BLEND uses for a hash value of a seed. By default, it uses 2 bits per character of a k-mer and, thus, 2*k bits for a hash value of a seed. This value can be decreased to increase the collision rate for assigning the same hash values for similar seeds, but also may start assigning the same hash value for slightly dissimilar seeds.

--fixed-bits INT BLEND uses INT number of bits when generating hash values of seeds rather than using 2*k number of bits. Useful when collision rate needs to be decreased than 2*k bits. Setting this option to 0 uses 2*k bits for hash values. [0].

BLEND also provides preset options. Some of these preset options also depend on the genome type as shown below:

-x map-ont (-k15 -w10 --fixed-bits=30 --neighbors=3)
-x ava-ont (-k15 -w20 --fixed-bits=30 --neighbors=3 -e0 -m100 -r2k)
-x map-pb (-Hk15 -w20 --fixed-bits=30 --neighbors=3)
-x ava-pb (-Hk19 -Xw20 --fixed-bits=32 --neighbors=3 -e0 -m100)
-x map-hifi --genome human (-k15 -w500 --fixed-bits=38 --neighbors=100 -U50,500 -g10k -A1 -B4 -O6,26 -E2,1 -s200)
-x map-hifi --genome eukaryote (-k15 -w500 --fixed-bits=30 --neighbors=5 -U50,500 -g10k -A1 -B4 -O6,26 -E2,1 -s200)
-x map-hifi --genome bacteria (-k15 -w500 --fixed-bits=30 --neighbors=3 -U50,500 -g10k -A1 -B4 -O6,26 -E2,1 -s200)
-x ava-hifi --genome human (-k15 -Xw500 --fixed-bits=38 --neighbors=10 -e0 -m100)
-x ava-hifi --genome eukaryote (-k15 -Xw500 --fixed-bits=30 --neighbors=10 -e0 -m100)
-x ava-hifi --genome bacteria (-k15 -Xw500 --fixed-bits=30 --neighbors=5 -e0 -m100)

Replicating the results in the paper

We explain how to replicate the results we produce in the BLEND paper in the test directory.

Owner
SAFARI Research Group at ETH Zurich and Carnegie Mellon University
Site for source code and tools distribution from SAFARI Research Group at ETH Zurich and Carnegie Mellon University.
SAFARI Research Group at ETH Zurich and Carnegie Mellon University
Similar Resources

VID-Fusion: Robust Visual-Inertial-Dynamics Odometry for Accurate External Force Estimation

VID-Fusion: Robust Visual-Inertial-Dynamics Odometry for Accurate External Force Estimation

VID-Fusion VID-Fusion: Robust Visual-Inertial-Dynamics Odometry for Accurate External Force Estimation Authors: Ziming Ding , Tiankai Yang, Kunyi Zhan

Nov 18, 2022

Accurate C port of AHX's Amiga replayer

ahx2play Aims to be an accurate C port of AHX 2.3d-sp3's internal replayer. The project contains example code in the ahx2play folder on how to interfa

Dec 2, 2022

Aims to be an accurate C port of Impulse Tracker 2.15's IT replayer (with selectable IT2 sound drivers)

it2play Aims to be an accurate C port of Impulse Tracker 2.15's IT replayer (with selectable IT2 sound drivers). This is a direct port of the original

Sep 27, 2022

A simple PoC to demonstrate that is possible to write Non writable memory and execute Non executable memory on Windows

WindowsPermsPoC A simple PoC to demonstrate that is possible to write Non writable memory and execute Non executable memory on Windows You can build i

Jul 21, 2022

Memory Process File System (MemProcFS) is an easy and convenient way of viewing physical memory as files in a virtual file system

Memory Process File System (MemProcFS) is an easy and convenient way of viewing physical memory as files in a virtual file system

The Memory Process File System (MemProcFS) is an easy and convenient way of viewing physical memory as files in a virtual file system.

Dec 2, 2022

Thread Stack Spoofing - PoC for an advanced In-Memory evasion technique allowing to better hide injected shellcode's memory allocation from scanners and analysts.

Thread Stack Spoofing - PoC for an advanced In-Memory evasion technique allowing to better hide injected shellcode's memory allocation from scanners and analysts.

Thread Stack Spoofing PoC A PoC implementation for an advanced in-memory evasion technique that spoofs Thread Call Stack. This technique allows to byp

Nov 26, 2022

An advanced in-memory evasion technique fluctuating shellcode's memory protection between RW/NoAccess & RX and then encrypting/decrypting its contents

An advanced in-memory evasion technique fluctuating shellcode's memory protection between RW/NoAccess & RX and then encrypting/decrypting its contents

Shellcode Fluctuation PoC A PoC implementation for an another in-memory evasion technique that cyclically encrypts and decrypts shellcode's contents t

Nov 26, 2022

Upload arbitrary data via Apple's Find My network.

Upload arbitrary data via Apple's Find My network.

Send My Send My allows you to to upload abritrary data from devices without an internet connection by (ab)using Apple's Find My network. The data is b

Nov 23, 2022

find likely coding segments in DNA using composition-normalised hexamer tables

hextable makes files of statistics that hexamer uses to scan for likely coding regions

Jan 21, 2022
Comments
  • A test of BLEND on two real datasets of PacBio CLR and Nanopore reads

    A test of BLEND on two real datasets of PacBio CLR and Nanopore reads

    In the paper https://arxiv.org/abs/2112.08687 BLEND was tested on only one non-HiFi read dataset. That was a simulated read dataset for one of the smallest eukaryotic genomes — the genome of Saccharomyces cerevisiae.

    To test how well BLEND performs on real (non-simulated) datasets of genomes which have more typical sizes, I used it to assemble genomes from these two sets of reads:

    1. Caenorhabditis elegans, PacBio CLR reads used in the article https://www.sciencedirect.com/science/article/pii/S2589004220305770 . For polishing I also used Illumina reads from that article. The nematode genome size is approximately 100 Mbp.
    2. Arabidopsis thaliana, Nanopore reads https://www.ncbi.nlm.nih.gov/sra/?term=ERR5530736 . For polishing I also used Illumina reads https://www.ncbi.nlm.nih.gov/sra/?term=ERR2173372 . The size of arabidopsis' genome is approximately 120 Mbp.

    I searched for overlaps, then assembled the genomes with Miniasm using default parameters, then polished the assemblies using long reads with Racon, and then polished the assemblies using both long and short reads with HyPo. The assemblies were compared with references using QUAST.

    The search for overlaps was performed with Blend 1.0 and, for comparison, with Minimap 2.22, using 22 threads of Intel Xeon X5670.

    For the nematode, results are as follows: | | Minimap2 | BLEND | | --- | --- | --- | | Time to find overlaps | 10m | 3h 37m | | Maximum RAM consumption | 20G | 44G | | N50 | 2,056,511 | 1,915,190 | | NGA50 | 589,675 | 563,498 | | misassemblies | 740 | 707 | | Genome fraction | 99.692% | 99.683% | | Total length | 109,516,352 | 108,958,103 |

    So, the assemblies of the nematode genome made with Minimap2 and with BLEND are similar. However, Blend required 20x more time to find overlaps and 2x more RAM.

    For arabidopsis Minimap found overlaps in 30 minutes using 29G RAM. I terminated BLEND because it didn't finish in 24 hours. At the moment I terminated it, BLEND was using 300G RAM.

    So, it seems that on non-HiFi datasets for genomes not as small as the genome of Saccharomyces cerevisiae BLEND is slower than Minimap2 and uses more RAM. This may be so because BLEND doesn't deal efficiently with repetitive seeds.

  • Some questions about the article

    Some questions about the article

    Could you please answer some questions about the article (https://arxiv.org/pdf/2112.08687.pdf):

    1. For HiFi reads you used Minimap2 with the option --ava-pb that is intended for PacBio CLR reads and not PacBio HiFi reads (Table S1). Why didn't you try Minimap2 with some other parameters? For example you could have increased the window size and the minimizer size. I suppose this will make Minimap2 faster and decrease its RAM consumption, thus reducing the difference between BLEND and Minimap2 on HiFi reads.
    2. Why did you use N50 and not NGA50 (Table 2)? N50 may be inflated due to misassemblies that result in improper sequence junctions.
    3. Why did you measure k-mer completeness and average identity using unpolished assemblies (Table 3)? Miniasm assemblies require polishing, because the accuracy of its contigs is the same as the accuracy of the reads used for the assembly. The higher accuracy of BLEND in Table 3 means that contigs made with BLEND are composed of slightly more accurate reads than contigs made with Minimap2, but the difference in accuracy may disappear after polishing.
    4. Taking into account that you used only one non-HiFi long read dataset and BLEND performed on it worse than Minimap2 (N50 in Table 2), is it correct to say that BLEND is probably fit only for HiFi long reads, and not PacBio CLR or Nanopore reads?

    With best wishes, Mikhail Schelkunov

Related tags
fuzzy matching selection gui

fm === fm provides a gui to select an item from a list using a fuzzy matching algorithm. When an item is selected, it is sent to the plumber `send` po

Nov 1, 2022
American fuzzy lop - a security-oriented fuzzer

american fuzzy lop Originally developed by Michal Zalewski [email protected] See QuickStartGuide.txt if you don't have time to read this file. 1) Ch

Nov 28, 2022
A perfect blend of C, Java, and Python tailored for those who desire a simple yet powerful programming language.

Fastcode A perfect blend of C, Java, and Python tailored for those who desire a simple yet powerful programming language. FastCode is a procedural/str

Aug 19, 2022
Mnemonic seed library for Monero and other CryptoNote-based currencies.

Features 16 mnemonic words (36% shorter than the original 25-word seed) embedded wallet birthday to optimize restoring from the seed supports encrypti

Oct 19, 2022
Fast and Accurate Extrinsic Calibration for Multiple LiDARs and Cameras
Fast and Accurate Extrinsic Calibration for Multiple LiDARs and Cameras

Fast and Accurate Extrinsic Calibration for Multiple LiDARs and Cameras The pre-print version of our paper is available here. The pre-release code has

Nov 24, 2022
The artifact associated with our ISSTA 2021 paper "Seed Selection for Successful Fuzzing"

Seed Selection for Successful Fuzzing The artifact associated with our ISSTA 2021 paper "Seed Selection for Successful Fuzzing". While our primary art

Nov 5, 2022
Solve 20 simple math questions and see how accurate/fast you are!
Solve 20 simple math questions and see how accurate/fast you are!

Math-Quiz Solve 20 simple math questions and see how accurate/fast you are! Want to try? Clone this repository $ git clone https://github.com/Mini-War

Sep 11, 2022
An unidentifiable mechanism that helps you bypass GFW.

trojan An unidentifiable mechanism that helps you bypass GFW. Trojan features multiple protocols over TLS to avoid both active/passive detections and

Nov 28, 2022
Fuses IMU readings with a complementary filter to achieve accurate pitch and roll readings.
Fuses IMU readings with a complementary filter to achieve accurate pitch and roll readings.

SimpleFusion A library that fuses accelerometer and gyroscope readings quickly and easily with a complementary filter. Overview This library combines

Aug 22, 2022
RRxIO - Robust Radar Visual/Thermal Inertial Odometry: Robust and accurate state estimation even in challenging visual conditions.
RRxIO - Robust Radar Visual/Thermal Inertial Odometry: Robust and accurate state estimation even in challenging visual conditions.

RRxIO - Robust Radar Visual/Thermal Inertial Odometry RRxIO offers robust and accurate state estimation even in challenging visual conditions. RRxIO c

Nov 30, 2022