Exploiting parallelization in positional Burrows-Wheeler transform (PBWT) algorithms for efficient haplotype matching and compression

Rick Wertenbroek; Ioannis Xenarios; Yann Thoma; Olivier Delaneau

doi:10.1093/bioadv/vbad021

Exploiting parallelization in positional Burrows-Wheeler transform (PBWT) algorithms for efficient haplotype matching and compression

Bioinform Adv. 2023 Mar 2;3(1):vbad021. doi: 10.1093/bioadv/vbad021. eCollection 2023.

Authors

Rick Wertenbroek^{1

2}, Ioannis Xenarios², Yann Thoma¹, Olivier Delaneau²

Affiliations

¹ School of Engineering and Management Vaud (HEIG-VD), HES-SO University of Applied Sciences and Arts Western Switzerland, Yverdon-les-Bains 1401, Switzerland.
² Department of Computational Biology, University of Lausanne, Lausanne 1015, Switzerland.

Abstract

Summary: The positional Burrows-Wheeler transform (PBWT) data structure allows for efficient haplotype data matching and compression. Its performance makes it a powerful tool for bioinformatics. However, existing algorithms do not exploit parallelism due to inner dependencies. We introduce a new method to break the dependencies and show how to fully exploit modern multi-core processors.

Availability and implementation: Source code and applications are available at https://github.com/rwk-unil/parallel_pbwt.

Supplementary information: Supplementary data are available at Bioinformatics Advances online.