| Title: | P-smoother: Efficient PBWT smoothing of large haplotype panels |
| Journal: | Bioinformatics Advances |
| Published: | 10 Jan 2022 |
| Pubmed: | https://pubmed.ncbi.nlm.nih.gov/35785021/ |
| DOI: | https://doi.org/10.1093/bioadv/vbac045 |
| URL: | https://academic.oup.com/bioinformaticsadvances/article-pdf/2/1/vbac045/44329660/vbac045.pdf |
Publication 7213
WARNING: the interactive features of this website use CSS3, which your browser does not support. To use the full features of this website, please update your browser.
Abstract
Motivation: As large haplotype panels become increasingly available, efficient string matching algorithms such as positional Burrows-Wheeler transformation (PBWT) are promising for identifying shared haplotypes. However, recent mutations and genotyping errors create occasional mismatches, presenting challenges for exact haplotype matching. Previous solutions are based on probabilistic models or seed-and-extension algorithms that passively tolerate mismatches.Results: Here, we propose a PBWT-based smoothing algorithm, P-smoother, to actively 'correct' these mismatches and thus 'smooth' the panel. P-smoother runs a bidirectional PBWT-based panel scanning that flips mismatching alleles based on the overall haplotype matching context, which we call the IBD (identical-by-descent) prior. In a simulated panel with 4000 haplotypes and a 0.2% error rate, we show it can reliably correct 85% of errors. As a result, PBWT algorithms running over the smoothed panel can identify more pairwise IBD segments than that over the unsmoothed panel. Most strikingly, a PBWT-cluster algorithm running over the smoothed panel, which we call PS-cluster, achieves state-of-the-art performance for identifying multiway IBD segments, a challenging problem in the computational community for years. We also showed that PS-cluster is adequately efficient for UK Biobank data. Therefore, P-smoother opens up new possibilities for efficient error-tolerating algorithms for biobank-scale haplotype panels.
Availability and implementation: Source code is available at github.com/ZhiGroup/P-smoother.
6 Authors
- William Yue
- Ardalan Naseri
- Victor Wang
- Pramesh Shakya
- Shaojie Zhang
- Degui Zhi
Enabling scientific discoveries that improve human health