μ- PBWT: a lightweight r-indexing of the PBWT for storing and querying UK Biobank data

MOTIVATION: The Positional Burrows–Wheeler Transform ([Formula: see text]) is a data structure that indexes haplotype sequences in a manner that enables finding maximal haplotype matches in h sequences containing w variation sites in [Formula: see text] time. This represents a significant improvement over classical quadratic-time approaches. However, the original PBWT data structure does not allow for queries over Biobank panels that consist of several millions of haplotypes, if an index of the haplotypes must be kept entirely in memory. RESULTS: In this article, we leverage the notion of r-index proposed for the BWT to present a memory-efficient method for constructing and storing the run-length encoded PBWT, and computing set maximal matches (SMEMs) queries in haplotype sequences. We implement our method, which we refer to as [Formula: see text] , and evaluate it on datasets of 1000 Genome Project and UK Biobank data. Our experiments demonstrate that the [Formula: see text] reduces the memory usage up to a factor of 20% compared to the best current PBWT-based indexing. In particular, [Formula: see text] produces an index that stores high-coverage whole genome sequencing data of chromosome 20 in about a third of the space of its BCF file. [Formula: see text] is an adaptation of techniques for the run-length compressed [Formula: see text] for the PBWT (RLPBWT) and it is based on keeping in memory only a succinct representation of the RLPBWT that still allows the efficient computation of set maximal matches (SMEMs) over the original panel. AVAILABILITY AND IMPLEMENTATION: Our implementation is open source and available at https://github.com/dlcgold/muPBWT. The binary is available at https://bioconda.github.io/recipes/mupbwt/README.html.