KeBaB: k-mer based breaking for finding long MEMs

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Maximal exact matches (MEMs) are crucial for genomics tasks like read classification and sequence alignment.
• Existing tools like ropebwt3 efficiently find MEMs by skipping redundant matching steps.
• Further optimization is needed to accelerate these computationally intensive processes.

Purpose of the Study:

• To introduce KeBaB, a k-mer filtration method designed to enhance the speed and efficiency of MEM-finding algorithms.
• To reduce the computational load on tools such as ropebwt3 by pre-filtering input data.
• To improve the performance of metagenomic classification without compromising accuracy.

Main Methods:

• Development of KeBaB, a k-mer filtration step utilizing a Bloom filter.
• Integration of KeBaB with existing MEM-finders like ropebwt3.
• Breaking down input sequences into 'pseudo-MEMs' to guarantee the containment of all long MEMs.

Main Results:

• KeBaB significantly accelerates MEM-finding algorithms by enabling them to ignore larger portions of input data.
• Experimental results demonstrate KeBaB's ability to speed up metagenomic classification.
• The method achieves acceleration without a significant reduction in classification accuracy.

Conclusions:

• KeBaB offers a fast and space-efficient solution for k-mer filtration in genomics.
• The proposed method effectively enhances the performance of MEM-finding tools and downstream applications like metagenomic classification.
• KeBaB provides a flexible approach, allowing for either complete MEM identification or targeted identification within the longest pseudo-MEMs.