2 Search Results for "Zhi, Degui"

Document
DOI: 10.4230/LIPIcs.WABI.2022.4
Haplotype Threading Using the Positional Burrows-Wheeler Transform

Authors: Ahsan Sanaullah, Degui Zhi, and Shaoije Zhang

Published in: LIPIcs, Volume 242, 22nd International Workshop on Algorithms in Bioinformatics (WABI 2022)

Abstract
In the classic model of population genetics, one haplotype (query) is considered as a mosaic copy of segments from a number of haplotypes in a panel, or threading the haplotype through the panel. The Li and Stephens model parameterized this problem using a hidden Markov model (HMM). However, HMM algorithms are linear to the sample size, and can be very expensive for biobank-scale panels. Here, we formulate the haplotype threading problem as the Minimal Positional Substring Cover problem, where a query is represented by a mosaic of a minimal number of substring matches from the panel. We show that this problem can be solved by a sequential set of greedy set maximal matches. Moreover, the solution space can be bounded by the left-most and the right-most solutions by the greedy approach. Based on these results, we formulate and solve several variations of this problem. Although our results are yet to be generalized to the cases with mismatches, they offer a theoretical framework for designing methods for genotype imputation and haplotype phasing.
Cite as

Ahsan Sanaullah, Degui Zhi, and Shaoije Zhang. Haplotype Threading Using the Positional Burrows-Wheeler Transform. In 22nd International Workshop on Algorithms in Bioinformatics (WABI 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 242, pp. 4:1-4:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{sanaullah_et_al:LIPIcs.WABI.2022.4,
  author =	{Sanaullah, Ahsan and Zhi, Degui and Zhang, Shaoije},
  title =	{{Haplotype Threading Using the Positional Burrows-Wheeler Transform}},
  booktitle =	{22nd International Workshop on Algorithms in Bioinformatics (WABI 2022)},
  pages =	{4:1--4:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-243-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{242},
  editor =	{Boucher, Christina and Rahmann, Sven},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2022.4},
  URN =		{urn:nbn:de:0030-drops-170386},
  doi =		{10.4230/LIPIcs.WABI.2022.4},
  annote =	{Keywords: Substring Cover, PBWT, Haplotype Threading, Haplotype Matching}
}
Document
DOI: 10.4230/LIPIcs.WABI.2021.19
Efficient Haplotype Block Matching in Bi-Directional PBWT

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

Published in: LIPIcs, Volume 201, 21st International Workshop on Algorithms in Bioinformatics (WABI 2021)

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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{naseri_et_al:LIPIcs.WABI.2021.19,
  author =	{Naseri, Ardalan and Yue, William and Zhang, Shaojie and Zhi, Degui},
  title =	{{Efficient Haplotype Block Matching in Bi-Directional PBWT}},
  booktitle =	{21st International Workshop on Algorithms in Bioinformatics (WABI 2021)},
  pages =	{19:1--19:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-200-6},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{201},
  editor =	{Carbone, Alessandra and El-Kebir, Mohammed},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2021.19},
  URN =		{urn:nbn:de:0030-drops-143729},
  doi =		{10.4230/LIPIcs.WABI.2021.19},
  annote =	{Keywords: PBWT, Bi-directional, Haplotype Matching}
}
  • Refine by Author
  • 2 Zhi, Degui
  • 1 Naseri, Ardalan
  • 1 Sanaullah, Ahsan
  • 1 Yue, William
  • 1 Zhang, Shaoije
  • Show More...

  • Refine by Classification
  • 2 Applied computing → Genetics
  • 1 Applied computing → Computational biology
  • 1 Applied computing → Computational genomics

  • Refine by Keyword
  • 2 Haplotype Matching
  • 2 PBWT
  • 1 Bi-directional
  • 1 Haplotype Threading
  • 1 Substring Cover

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2021
  • 1 2022

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 Imprint Privacy Contact