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

ABSTRACT:

Motivation

The Positional Burrows-Wheeler Transform (PBWT) 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 O(hw) 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 metho

SUBMITTER: Cozzi D 

PROVIDER: S-EPMC10502237 | biostudies-literature | 2023 Sep

REPOSITORIES: biostudies-literature