Haplotype-based Parallel PBWT for Biobank Scale Data

Kecong Tang, Ahsan Sanaullah, Degui Zhi, Shaojie ZhangbioRxiv 2025 · DOI

TL;DR

This paper introduces HP-PBWT, a parallelized version of the Positional Burrows-Wheeler Transform (PBWT), designed to efficiently find all-vs-all haplotype matches in massive biobank-scale datasets. By parallelizing key PBWT computations, HP-PBWT achieves significant speedups, making it feasible to analyze datasets with billions of haplotypes.

What Problem Does This Paper Address?

The Positional Burrows-Wheeler Transform (PBWT) is a powerful tool for identifying haplotype matches and compressing genetic data. Its optimal time complexity of O(MN) (where M is the number of haplotypes and N is the number of variant sites) is excellent for many applications like IBD segment detection and genotype imputation. However, as biobanks grow and the number of genotyped individuals approaches millions, or even billions in the future, this O(MN) complexity becomes a bottleneck. Existing parallel PBWT approaches often struggle with memory constraints or are not designed for the sheer scale of modern biobanks, necessitating a more efficient and scalable parallel solution.

Methods

The core innovation of HP-PBWT lies in its parallelization strategy, which focuses on splitting the haplotype panel into blocks. This allows for parallel execution of several key PBWT operations:

  • PBWT Construction: The prefix array computation, which was previously sequential, is transformed into a parallel prefix sum problem. The divergence array computation is also parallelized by dividing the Yk array into blocks and processing them concurrently.
  • Reporting Matches: Two efficient parallel algorithms are introduced for reporting:
  • All-vs-all L-long matches: This involves identifying matches of at least a specified length L.
  • All-vs-all set-maximal matches: This identifies the longest possible matches that cannot be extended.

These parallel algorithms aim to maintain memory efficiency and the characteristic sweeping behavior of the original PBWT. The paper details optimizations to handle inter-block dependencies and reduce the overhead of parallel processing.

Datasets

The authors evaluated HP-PBWT using two types of datasets:

  • Real Datasets:
    • Chromosome 20 from the 1000 Genomes Project (sequencing data).
  • Chromosome 20 from the UK Biobank (genotyping array data).
  • Randomly Generated Datasets: VCF files were used to create synthetic datasets with varying numbers of haplotypes (M) and sites (N). These were crucial for testing scalability beyond available real-world datasets, particularly for the IO-excluded benchmarks where M could reach up to 8 million.

The benchmarks were designed to be either "IO-included" (simulating real-world scenarios with disk I/O) or "IO-excluded" (removing I/O to focus purely on computational performance).

Key Insights and Ideas

  • Haplotype Dimension Parallelization is Key: The paper strongly advocates for parallelizing along the haplotype dimension (M) rather than the site dimension (N), especially for large biobank-scale datasets where M is orders of magnitude larger than N.
  • Prefix Sums for Parallel Prefix Array: Transforming the prefix array construction into a parallel prefix sum problem is a clever way to break sequential dependencies and enable efficient parallel computation.
  • Block-Based Divergence Computation: Dividing the divergence array computation into blocks and carefully managing inter-block dependencies (via "upper search" and optimizations) is crucial for achieving parallel speedup.
  • Scalability for Genotyping Data: HP-PBWT shows significant promise for genotyping array data, which typically has a large number of haplotypes and sparser sites, aligning well with the algorithm's strengths.
  • Sequencing Data Challenges: The current parallelization strategy might introduce too much overhead for sequencing data, which often has fewer haplotypes but denser information. This suggests a need for different parallelization approaches for such data.

Key Results

  • Significant Speedups:
    • In IO-included benchmarks on UK Biobank data, HP-PBWT achieved a 4-fold speedup with 30 threads.
  • In IO-excluded benchmarks on 8 million randomized haplotypes, HP-PBWT achieved a 22-fold speedup with 60 cores.
  • Scalability: The performance scales well with an increasing number of haplotypes, demonstrating its suitability for biobank-scale data.
  • Memory Efficiency: HP-PBWT maintains memory efficiency, requiring only O(M) memory space.
  • Comparison to Existing Methods: HP-PBWT outperformed Durbin's original PBWT and Wertenbroek et al.'s parallel PBWT, especially on larger datasets. For instance, Wertenbroek et al.'s method showed no speedup on UK Biobank data compared to Durbin's, while HP-PBWT did.

Limitations and Future Work

  • Sequencing Data Performance: HP-PBWT does not currently show speedups on sequencing data with a small number of haplotypes. The authors suggest that the partition mechanisms might introduce too much overhead for such datasets.
  • Future Work:
    • Researching new algorithms and optimizations specifically for sequencing datasets.
  • Exploring the simultaneous application of both haplotype-based (like HP-PBWT) and site-based parallel PBWT algorithms to further accelerate the process.
  • The paper suggests that with further hardware optimization, HP-PBWT is expected to handle billions of haplotypes efficiently.

Summary updated

Abstract

Durbin's positional Burrows-Wheeler transform (PBWT) enables algorithms with the optimal time complexity of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>O</mml:mi> <mml:mfenced><mml:mrow><mml:mi>M</mml:mi> <mml:mspace></mml:mspace> <mml:mi>N</mml:mi></mml:mrow> </mml:mfenced> </mml:mrow> </mml:math> for reporting all vs all haplotype matches in a population panel with <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>M</mml:mi></mml:math> haplotypes and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>N</mml:mi></mml:math> variant sites. However, even this efficiency may still be too slow when the number of haplotypes reaches millions. To further reduce the run time, in this paper, a parallel version of the PBWT algorithms is introduced for all versus all haplotype matching, which is called HP-PBWT (haplotype-based parallel PBWT). HP-PBWT parallelly executes the PBWT by splitting a haplotype panel into blocks of haplotypes. HP-PBWT algorithms achieve parallelization for PBWT construction, reporting all versus all L-long matches, and reporting all versus all set-maximal matches while maintaining memory efficiency. HP-PBWT has an <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>O</mml:mi> <mml:mfenced> <mml:mrow> <mml:mfenced> <mml:mrow><mml:mfrac><mml:mi>M</mml:mi> <mml:mi>T</mml:mi></mml:mfrac> <mml:mo>+</mml:mo> <mml:mi>T</mml:mi></mml:mrow> </mml:mfenced> <mml:mi>N</mml:mi></mml:mrow> </mml:mfenced> </mml:mrow> </mml:math> time complexity in PBWT construction, and an <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>O</mml:mi> <mml:mfenced> <mml:mrow> <mml:mfenced> <mml:mrow><mml:mfrac><mml:mi>M</mml:mi> <mml:mi>T</mml:mi></mml:mfrac> <mml:mo>+</mml:mo> <mml:mi>T</mml:mi> <mml:mo>+</mml:mo> <mml:msup><mml:mi>c</mml:mi> <mml:mo>∗</mml:mo></mml:msup> </mml:mrow> </mml:mfenced> <mml:mi>N</mml:mi></mml:mrow> </mml:mfenced> </mml:mrow> </mml:math> time complexity for reporting all versus all L-long matches and reporting all versus all set-maximal matches, where <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>T</mml:mi></mml:math> is the number of threads and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow><mml:msup><mml:mi>c</mml:mi> <mml:mo>∗</mml:mo></mml:msup> </mml:mrow> </mml:math> is the maximum number of matches (of length L or maximum divergence value for L-long matches and set-maximal matches, respectively) per haplotype per site. HP-PBWT achieves 4-fold speed-up in UK Biobank genotyping array data with 30 threads in the IO-included benchmarks. When applying HP-PBWT to a dataset of 8 million randomized haplotypes (random binary strings of equal length) in the IO-excluded benchmarks, it can achieve a 22-fold speed-up with 60 cores on the Amazon EC2 server. With further hardware optimization, HP-PBWT is expected to handle billions of haplotypes efficiently.
BibTeX
@misc{tang2025haplotype,
  author = {Kecong Tang and Ahsan Sanaullah and Degui Zhi and Shaojie Zhang},
  title = {{Haplotype-based Parallel PBWT for Biobank Scale Data}},
  year = {2025},
  doi = {10.1101/2025.02.04.636317},
  howpublished = {bioRxiv},
}
Figure