Document Open Access Logo

Efficient Haplotype Block Matching in Bi-Directional PBWT

Authors Ardalan Naseri, William Yue, Shaojie Zhang, Degui Zhi

PDF
Thumbnail PDF

File

LIPIcs.WABI.2021.19.pdf
  • Filesize: 2.4 MB
  • 13 pages

Document Identifiers

Author Details

Ardalan Naseri
  • School of Biomedical Informatics, University of Texas Health Science Center at Houston, TX, USA
William Yue
  • School of Biomedical Informatics, University of Texas Health Science Center at Houston, TX, USA
Shaojie Zhang
  • Department of Computer Science, University of Central Florida, Orlando, FL, USA
Degui Zhi
  • School of Biomedical Informatics, University of Texas Health Science Center at Houston, TX, USA

Funding

This work was supported by the National Institutes of Health R01HG010086.

Acknowledgements

This research has been conducted using the UK Biobank Resource under Application Number 24247.

Cite As Get BibTex

Ardalan Naseri, William Yue, Shaojie Zhang, and Degui Zhi. Efficient Haplotype Block Matching in Bi-Directional PBWT. In 21st International Workshop on Algorithms in Bioinformatics (WABI 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 201, pp. 19:1-19:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.WABI.2021.19

Abstract

Efficient haplotype matching search is of great interest when large genotyped cohorts are becoming available. Positional Burrows-Wheeler Transform (PBWT) enables efficient searching for blocks of haplotype matches. However, existing efficient PBWT algorithms sweep across the haplotype panel from left to right, capturing all exact matches. As a result, PBWT does not account for mismatches. It is also not easy to investigate the patterns of changes between the matching blocks. Here, we present an extension to PBWT, called bi-directional PBWT that allows the information about the blocks of matches to be present at both sides of each site. We also present a set of algorithms to efficiently merge the matching blocks or examine the patterns of changes on both sides of each site. The time complexity of the algorithms to find and merge matching blocks using bi-directional PBWT is linear to the input size.
Using real data from the UK Biobank, we demonstrate the run time and memory efficiency of our algorithms. More importantly, our algorithms can identify more blocks by enabling tolerance of mismatches. Moreover, by using mutual information (MI) between the forward and the reverse PBWT matching block sets as a measure of haplotype consistency, we found the MI derived from European samples in the 1000 Genomes Project is highly correlated (Spearman correlation r=0.87) with the deCODE recombination map.

Subject Classification

ACM Subject Classification
  • Applied computing → Genetics
  • Applied computing → Computational genomics
Keywords
  • PBWT
  • Bi-directional
  • Haplotype Matching

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. Jarno Alanko, Hideo Bannai, Bastien Cazaux, Pierre Peterlongo, and Jens Stoye. Finding all maximal perfect haplotype blocks in linear time. Algorithms for Molecular Biology, 15(1):2, 2020. Google Scholar
  2. Clare Bycroft, Colin Freeman, Desislava Petkova, Gavin Band, Lloyd T Elliott, Kevin Sharp, Allan Motyer, Damjan Vukcevic, Olivier Delaneau, Jared O’Connell, et al. The UK Biobank resource with deep phenotyping and genomic data. Nature, 562(7726):203-209, 2018. Google Scholar
  3. 1000 Genomes Project Consortium et al. A global reference for human genetic variation. Nature, 526(7571):68, 2015. Google Scholar
  4. Luís Cunha, Yoan Diekmann, Luis Kowada, and Jens Stoye. Identifying maximal perfect haplotype blocks. In Brazilian Symposium on Bioinformatics, pages 26-37. Springer, 2018. Google Scholar
  5. Richard Durbin. Efficient haplotype matching and storage using the positional Burrows-Wheeler transform (pbwt). Bioinformatics, 30(9):1266-1272, 2014. Google Scholar
  6. William A Freyman, Kimberly F McManus, Suyash S Shringarpure, Ethan M Jewett, Katarzyna Bryc, The 23, Me Research Team, and Adam Auton. Fast and Robust Identity-by-Descent Inference with the Templated Positional Burrows–Wheeler Transform. Molecular Biology and Evolution, 38(5):2131-2151, 2021. Google Scholar
  7. Bjarni V Halldorsson, Gunnar Palsson, Olafur A Stefansson, Hakon Jonsson, Marteinn T Hardarson, Hannes P Eggertsson, Bjarni Gunnarsson, Asmundur Oddsson, Gisli H Halldorsson, Florian Zink, et al. Characterizing mutagenic effects of recombination through a sequence-level genetic map. Science, 363(6425), 2019. Google Scholar
  8. Po-Ru Loh, Petr Danecek, Pier Francesco Palamara, Christian Fuchsberger, Yakir A Reshef, Hilary K Finucane, Sebastian Schoenherr, Lukas Forer, Shane McCarthy, Goncalo R Abecasis, et al. Reference-based phasing using the haplotype reference consortium panel. Nature Genetics, 48(11):1443, 2016. Google Scholar
  9. Ardalan Naseri, Erwin Holzhauser, Degui Zhi, and Shaojie Zhang. Efficient haplotype matching between a query and a panel for genealogical search. Bioinformatics, 35(14):i233-i241, 2019. Google Scholar
  10. Ardalan Naseri, Xiaoming Liu, Kecong Tang, Shaojie Zhang, and Degui Zhi. RaPID: ultra-fast, powerful, and accurate detection of segments identical by descent (IBD) in biobank-scale cohorts. Genome Biology, 20(1):1-15, 2019. Google Scholar
  11. Ardalan Naseri, Degui Zhi, and Shaojie Zhang. Discovery of runs-of-homozygosity diplotype clusters and their associations with diseases in UK Biobank. medRxiv, 2020. URL: https://doi.org/10.1101/2020.10.26.20220004.
  12. Simone Rubinacci, Olivier Delaneau, and Jonathan Marchini. Genotype imputation using the positional burrows wheeler transform. PLoS Genetics, 16(11):e1009049, 2020. Google Scholar
  13. Vladimir Shchur, Liliia Ziganurova, and Richard Durbin. Fast and scalable genome-wide inference of local tree topologies from large number of haplotypes based on tree consistent pbwt data structure. bioRxiv, page 542035, 2019. Google Scholar
  14. Elizabeth A Thompson. Identity by Descent: Variation in Meiosis, Across Genomes, and in Populations. Genetics, 194(2):301-326, 2013. Google Scholar
  15. Ying Zhou, Sharon R Browning, and Brian L Browning. A fast and simple method for detecting identity-by-descent segments in large-scale data. The American Journal of Human Genetics, 106(4):426-437, 2020. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact