Introduction
Overview
The Positional Burrows-Wheeler Transform (PBWT), introduced by Richard Durbin in 2014 (Durbin 2014), is an efficient and scalable data structure for handling large haplotype datasets. It has been applied in many important genomic tasks:
- Phasing haplotypes (Browning et al. 2021)
- Genotype imputation (Rubinacci et al. 2023, 2020)
- Identifying identical-by-descent (IBD) segments (Naseri et al. 2019)
- Pangenomic haplotype analysis (Baaijens et al. 2022)
Motivation
The PBWT algorithm is powerful, yet it can be challenging for newcomers to grasp. I am grateful for Alistair Miles’s insightful blog post, which provides a practical bridge between Richard Durbin’s original paper and a working implementation.
However, there is still a need for a deeper intuition of the underlying processes and how they were implemented in practice. I created this blog to provide mental models of how PBWT algorithms function. By analyzing Richard Durbin’s source code, I have developed simplified pseudo-code that captures the core logic and created illustrative algorithmic diagrams to visualize how the algorithms are implemented with a specific example.
Content covered
- Construction: How to build prefix and divergence arrays (Algorithms 1&2).
- Internal Matching: Identifying shared segments and maximal matches within a population:
- Algorithms 2&3: Report matches longer than \(L\)
- Algorithms 2&4: Report set maximal matches
- External Querying: Mapping a new haplotype against a PBWT database (Algorithm 2&5).