Related Experiment Video
Updated: May 19, 2026
12:39
A Novel Bayesian Change-point Algorithm for Genome-wide Analysis of Diverse ChIPseq Data Types
Published on: December 10, 2012
Haplotype-based Parallel PBWT for Biobank Scale Data
Kecong Tang1, Ahsan Sanaullah1, Degui Zhi2
1Department of Computer Science, University of Central Florida, Orlando, FL 32826, USA.
IEEE ... International Conference on Computational Advances in Bio and Medical Sciences : [Proceedings]. IEEE International Conference on Computational Advances in Bio and Medical Sciences
|May 18, 2026
Summary
A new parallel algorithm, HP-PBWT, speeds up haplotype matching for large population panels. This method significantly reduces computation time for analyzing millions of haplotypes, making large-scale genetic analysis more efficient.
Area of Science:
- Bioinformatics
- Computational Biology
- Genetics
Background:
- Durbin's positional Burrows-Wheeler transform (PBWT) offers optimal O(MN) time complexity for all-vs-all haplotype matching.
- PBWT's efficiency becomes a bottleneck for population panels with millions of haplotypes.
- Large-scale haplotype analysis is crucial for genetic studies but computationally demanding.
Purpose of the Study:
- To introduce a parallel version of PBWT algorithms, termed HP-PBWT (haplotype-based parallel PBWT).
- To significantly reduce runtime for all-vs-all haplotype matching in large-scale datasets.
- To maintain memory efficiency while achieving parallelization.
Main Methods:
- HP-PBWT parallelizes PBWT by partitioning the haplotype panel into blocks.
- Parallel execution is applied to PBWT construction, L-long match reporting, and set-maximal match reporting.
- The algorithm achieves a time complexity of O(((M/T) + T)N) for construction and O(((M/T) + T + c*)N) for matching, where T is the number of threads.
Main Results:
- HP-PBWT demonstrated a 4-fold speed-up on UK Biobank data with 30 threads.
- A 22-fold speed-up was achieved on 8 million randomized haplotypes using 60 cores.
- The algorithm maintains memory efficiency across parallelized operations.
Conclusions:
- HP-PBWT offers substantial performance improvements for all-vs-all haplotype matching.
- The parallel approach effectively handles large-scale genomic datasets.
- HP-PBWT is poised to efficiently manage analyses involving billions of haplotypes with further optimization.
Related Concept Videos
01:11Genome-wide Association Studies-GWAS
Genome-wide association studies or GWAS are used to identify whether common SNPs are associated with certain diseases. Suppose specific SNPs are more frequently observed in individuals with a particular disease than those without the disease. In that case, those SNPs are said to be associated with the disease. Chi-square analysis is performed to check the probability of the allele likely to be associated with the disease.
GWAS does not require the identification of the target gene involved in...
GWAS does not require the identification of the target gene involved in...
02:54Evolutionary Relationships through Genome Comparisons
Genome comparison is one of the excellent ways to interpret the evolutionary relationships between organisms. The basic principle of genome comparison is that if two species share a common feature, it is likely encoded by the DNA sequence conserved between both species. The advent of genome sequencing technologies in the late 20th century enabled scientists to understand the concept of conservation of domains between species and helped them to deduce evolutionary relationships across diverse...