KeBaB: k-mer based breaking for finding long MEMs.

Long maximal exact matches (MEMs) are used in many genomics applications such as read classification and sequence alignment. Li's ropebwt3 finds long MEMs quickly because it can often ignore much of its input, skipping matching steps which are redundant to the final output. In this paper we propose KeBaB, a fast and space efficient k-mer filtration step using a Bloom filter. This approach speeds up MEM-finders such as ropebwt3 even further by letting them ignore even more, breaking the input into substrings called "pseudo-MEMs" which are guaranteed to contain all long MEMs. We also show experimentally that KeBaB can accelerate metagenomic classification without significantly reducing accuracy, either by finding all long MEMs or by leveraging the filter to find only the long MEMs present in the t longest pseudo-MEMs.