LIPIcs.WABI.2021.19.pdf
- Filesize: 2.4 MB
- 13 pages
Document
Efficient Haplotype Block Matching in Bi-Directional PBWT
Authors
-
Part of:
Volume:
21st International Workshop on Algorithms in Bioinformatics (WABI 2021)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Workshop on Algorithms in Bioinformatics (WABI) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2021-07-22
File
Document Identifiers
Acknowledgements
This research has been conducted using the UK Biobank Resource under Application Number 24247.
Cite AsGet 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
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)
0PDF Downloads
References
-
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.
-
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.
-
1000 Genomes Project Consortium et al. A global reference for human genetic variation. Nature, 526(7571):68, 2015.
-
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.
-
Richard Durbin. Efficient haplotype matching and storage using the positional Burrows-Wheeler transform (pbwt). Bioinformatics, 30(9):1266-1272, 2014.
-
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.
-
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.
-
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.
-
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.
-
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.
- 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.
-
Simone Rubinacci, Olivier Delaneau, and Jonathan Marchini. Genotype imputation using the positional burrows wheeler transform. PLoS Genetics, 16(11):e1009049, 2020.
-
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.
-
Elizabeth A Thompson. Identity by Descent: Variation in Meiosis, Across Genomes, and in Populations. Genetics, 194(2):301-326, 2013.
-
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.