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 shortcuts: for a precomputed set of pairs $(α,β)$ of strings, a backward search that has just matched $β$ and finds $α$ immediately to its left in the pattern can cross $α$ in one step. Since a shortcut is taken only after its pair has been recognized in the pattern, the search 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, so the report gives the path a match takes through the graph. We work out the case of a single linear reference $R$, with $β$ ranging over the length-$\ell$ windows of $R$ starting at multiples of $\ell$, and $α$ over the $2^t \ell$ characters preceding such a window. We show that the search counts correctly, that under stated conditions it crosses a stretch of the pattern matching $m$ consecutive windows of $R$ with $O(\log m + m / 2^τ)$ shortcuts, where $2^τ\ell$ is the longest shortcut, and that the shortcuts can be built efficiently from the RLBWT. On the Pizza&Chili 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 with 1% of the characters substituted, for 86% more space. On 11 gigabases of genomes of seven bacterial species, they make it 1.6 to 1.9 times faster on exact patterns for 32% more space. On whole chromosome 19 haplotypes against 16 to 64 others from the Human Pangenome Reference Consortium, shortcuts in both directions make Boyer-Moore-Li search for maximal exact matches of length at least 1000 about 8 times faster.