BWT-runs Compressed Data Structures for Pan-Genomics Text Indexing

Abstract

The FM-index is used in many bioinformatics applications; however, it cannot handle large text collections. This is of particular concern due to reference bias; references fail to capture the required genetic diversity. A recently successful solution has been FM-indexes using the RLBWT and many references, but these traditionally rely on worst case logarithmic time rank operations. Nishimoto and Tabei improved this result to answer queries by computing last-to-first (LF) steps in constant-time. We show that this result can be made practical for LF using “table-lookup” on permutations. We show how to compress columns of the table to support count queries, competitive in time/space with the best existing implementations. Matching statistics describe exact matching substrings of a pattern, and computing them relies on LF, thresholds, and LCE queries. We show how storing additional LCE information alongside thresholds allows us to improve the speed of computing matching statistic for pan-genomic datasets.