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