Parse indexing for choosing pseudo-MEMs
For researchers needing fast and safe MEM searches in repetitive texts, this improves on KeBaB by guaranteeing no MEMs are lost.
Brown et al. (2025) introduced KeBaB, a method using k-mer based breaking to speed up MEM searches by filtering pseudo-MEMs, but with risk of discarding all MEMs. This paper uses parse indexing to eliminate that risk and removes the need to choose k.
Brown et al.\ (2025) recently proposed a pre-processing step, called $k$-mer based breaking (KeBaB), to speed up searches for long maximal exact matches (MEMs) between patterns and an indexed repetitive text. They fix a parameter $k$ and build a Bloom filter for the distinct $k$-mers in the text. When given a pattern, they quickly separate the $k$-mers in it into those that probably occur in the text and those that certainly do not. They call the maximal substrings of the pattern consisting only of the former $k$-mers {\em pseudo-MEMs}. These pseudo-MEMs are guaranteed to contain all the MEMs of length at least $k$ of the pattern with respect to the text, and it is usually much faster to find the pseudo-MEMs and then find the MEMs in them than to find the MEMs in the pattern directly. KeBaB is particularly effective when we choose a threshold $L > k$ and discard the pseudo-MEMs of length less than $L$, or discard all but the $t$ longest pseudo-MEMs. These filtering steps are risky, however, since all the MEMs could be in the discarded pseudo-MEMs. In this paper we show how to use parse indexing to choose pseudo-MEMs to eliminate this risk, with the added benefit that we need not choose $k$.