mattheww95 / blend

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. Described by Firtina et al. (preliminary version at https://arxiv.org/abs/2112.08687)

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

BLEND is a mechanism that can generate the same hash value for highly similar seeds to find fuzzy (approximate) seed matches between sequences with a single lookup from their hash values. By replacing their hash functions with BLEND, any seeding technique can integrate BLEND to generate the hash values of seeds. By efficiently finding fuzzy seed matches with a single lookup, BLEND can significantly improve the performance and accuracy while reducing the memory footprint of two important applications: 1) read overlapping and 2) read mapping. Apart from these two applications, we envision that any application that uses seeds can exploit BLEND. BLEND is described in arXiv.

For proof of work, we integrate the BLEND mechanism into minimap2. We show the benefits of BLEND when used with the minimizer and strobemer seeding techniques. We make the following changes in the original minimap2 implementation:

• We modify the original minimap2 implementation so that minimap2 can assign the same hash values for highly similar seeds it finds. To this end, we change the sketch.c implementation of minimap2 to 1) generate the hash values of k-mers and 2) decide the minimizer k-mer based on the hash values BLEND generates.
• We implement a simple version of the strobemer seeds in minimap2 in three steps. First, we find minimizer k-mers using the original hash function that minimap2 uses. Second, we link each n consecutive minimizer k-mer in a strobemer seeds. Third, we use the BLEND mechanism for generating the hash value of the strobemer seed based on the hash values of linked k-mers.
• We enable the minimap2 implementation to use seeds longer than 256 characters so that it can store longer seeds when using BLEND. 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 can be much larger than a 256 character-long seed.

Cloning the source code

• Download the code from its GitHub repository:

git clone 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.

Before compiling BLEND:

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

To compile:

cd blend && make

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).

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 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 minimap2 role out. We explain the parameters unique to the BLEND implementation below.

The following option (i.e., neighbors) defines the number of k-mers that BLEND uses to generate a seed.

--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 when generating the hash values of seeds. 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]

The following option (i.e., --strobemers) tells BLEND that it should link consecutive neighbors many minimizer k-mers to generate a strobemer sequence as seed and use the hash values of these minimizer k-mers to generate a hash value for the strobemer sequence using the SimHash hashing strategy as suggested in the BLEND paper.

----strobemers link minimizers rather than the preceding k-mers of a single minimizer. (Number of minimizers to link is defined by --neighbors.)

The following option (i.e., immediate) tells BLEND that it should link consecutive neighbors many overlapping k-mers to generate a seed sequence and use the hash values of these k-mers to generate a hash value for the seed sequence using the SimHash hashing strategy as suggested in the BLEND paper.

--immediate use the hash values of consecutive k-mers to generate the hash values of seeds (defualt behavior).

BLEND provides the following preset options:

-x map-ont (-k7 -w10 --fixed-bits=32 --neighbors=11)
-x ava-ont (-k15 -w10 --fixed-bits=30 --neighbors=5 -e0 -m100 -r2k)
-x map-pb (-Hk7 -w10 --fixed-bits=32 --neighbors=15)
-x ava-pb (-Hk19 -Xw10 --fixed-bits=38 --neighbors=5 -e0 -m100)
-x map-hifi (--strobemers -k19 -w50 --fixed-bits=38 --neighbors=5 -U50,500 -g10k -A1 -B4 -O6,26 -E2,1 -s200)
-x ava-hifi (--strobemers -k25 -Xw200 --fixed-bits=50 --neighbors=7 -e0 -m100)

Reproducing the results in the paper

We explain how to reproduce the results we show in the BLEND paper in the test directory.

Citing BLEND

If you use BLEND in your work, please cite:

Can Firtina, Jisung Park, Mohammed Alser, Jeremie S. Kim, Damla Senol Cali, Taha Shahroodi, Nika Mansouri Ghiasi, Gagandeep Singh, Konstantinos Kanellopoulos, Can Alkan, and Onur Mutlu "BLEND: A Fast, Memory-Efficient, and Accurate Mechanism to Find Fuzzy Seed Matches in Genome Analysis" arXiv preprint arXiv:2112.08687 (2021). DOI