Reportable Shortcuts with RLBWTs

Abstract

Backward search over a run-length compressed Burrows--Wheeler transform (RLBWT) takes one step per pattern character, even when long stretches of the pattern match material that recurs throughout a highly repetitive collection. We describe \emph{shortcuts}: for a precomputed set of pairs $(\alpha ,\beta )$ of strings, a backward search that has just matched $\beta$ and finds $\alpha$ immediately to its left in the pattern can cross $\alpha$ in one step. Since a shortcut is taken only after its pair has been recognized in the pattern, the search can record it, and it returns a report of the shortcuts it took along with the usual BWT interval. Our motivation is pangenome graphs, where such pairs mark the places where a pattern passes through a vertex. We work out the case of a single linear reference $\Rref$, in which $\beta$ ranges over the length-$\ell$ windows of $\Rref$ starting at multiples of $\ell$, and $\alpha$ over the $2^t\ell$ characters of $\Rref$ preceding such a window. We show that the resulting search counts correctly; that it crosses a stretch of the pattern matching $m$ consecutive windows of $\Rref$, whose anchors were all kept, with $O(\log m+m/2^{\tau })$ shortcuts, where $2^{\tau }\ell$ is the longest shortcut, provided the stretch and the rest of the pattern to its right occur together in the collection; and that the shortcuts can be built from the RLBWT in $O(|\Rref| (τ+ 1) \log r)$ time plus $O(\log n)$ time per BWT row they cover, plus the time to sort the anchors. On the 461-megabyte Pizza\&Chili \texttt{cere} collection of 37 genomes, shortcuts make backward search $2.3$ to $4.2$ times faster on exact patterns of length 200 to 1000, and $1.7$ to $2.0$ times faster on patterns with 1\% of their characters substituted, for 86\% more space than the RLBWT.