Can I read MONI can find k-MEMs on EtoBox?

MONI can find k-MEMs by Tatarnikov, Igor; Farahani, Ardavan Shahrabi; Kashgouli, Sana; Gagie, Travis is a scholarly article available to read on EtoBox.

What is MONI can find k-MEMs about?

Suppose we are asked to index a text $T [0..n - 1]$ such that, given a pattern $P [0..m - 1]$, we can quickly report the maximal substrings of $P$ that each occur in $T$ at least $k$ times. We first show how we can add $O (r \log n)$ bits to Rossi et al.'s recent MONI index, where $r$ is the number of runs in the Burrows-Wheeler Transform of $T$, such that it supports such queries in $O (k m \log n)$ time. We then show how, if we are given $k$ at construction time, we can reduce the query time to $O (m \log n)$.

Author

Tatarnikov, Igor; Farahani, Ardavan Shahrabi; Kashgouli, Sana; Gagie, Travis

Published

2022

Language

EN