MONI-k: An index for efficient pangenome-to-pangenome comparison

Abstract

Maximal exact matches (MEMs) are widely used in bioinformatics, originally for genome-to-genome comparison but especially for DNA alignment ever since Li (2013) presented BWA-MEM. Building on work by Bannai, Gagie and I (2018) and again targeting alignment, Rossi et al. (2022) recently built an index called MONI that is based on the run-length compressed Burrows-Wheeler Transform and can find MEMs efficiently with respect to pangenomes. In this paper we define k-MEMs to be maximal substrings of a pattern that each occur exactly at least k times in a text (so a MEM is a 1-MEM) and briefly explain why computing k-MEMs could be useful for pangenome-to-pangenome comparison. We then show that, when k is given at construction time, MONI can easily be extended to find k-MEMs efficiently as well.