| Title: | μ- PBWT: a lightweight r-indexing of the PBWT for storing and querying UK Biobank data |
| Journal: | Bioinformatics |
| Published: | 2 Sep 2023 |
| Pubmed: | https://pubmed.ncbi.nlm.nih.gov/37688560/ |
| DOI: | https://doi.org/10.1093/bioinformatics/btad552 |
| URL: | https://academic.oup.com/bioinformatics/advance-article-pdf/doi/10.1093/bioinformatics/btad552/51472749/btad552.pdf |
Publication 9647
WARNING: the interactive features of this website use CSS3, which your browser does not support. To use the full features of this website, please update your browser.
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.</p>
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 μ-PBWT, and evaluate it on datasets of 1000 Genome Project and UK Biobank data. Our experiments demonstrate that the μ-PBWT reduces the memory usage up to a factor of 20% compared to the best current PBWT-based indexing. In particular, μ-PBWT 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. μ-PBWT is an adaptation of techniques for the run-length compressed BWT 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.</p>
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.</p>
7 Authors
- Davide Cozzi
- Massimiliano Rossi
- Simone Rubinacci
- Travis Gagie
- Dominik Köppl
- Christina Boucher
- Paola Bonizzoni
1 Application
| Application ID | Title |
|---|---|
| 66995 | Prediction of haplotypes, genotypes, parental-of-origin and applications in biobanks. |
Enabling scientific discoveries that improve human health