Efficient haplotype matching between a query and a panel for genealogical search.

ABSTRACT:

Motivation

With the wide availability of whole-genome genotype data, there is an increasing need for conducting genetic genealogical searches efficiently. Computationally, this task amounts to identifying shared DNA segments between a query individual and a very large panel containing millions of haplotypes. The celebrated Positional Burrows-Wheeler Transform (PBWT) data structure is a pre-computed index of the panel that enables constant time matching at each position between one haplotype and an arbitrarily large panel. However, the existing algorithm (Durbin's Algorithm 5) can only identify set-maximal matches, the longest matches ending at any location in a panel, while in real genealogical search scenarios, multiple 'good enough' matches are desired.

Results

In this wor

SUBMITTER: Naseri A 

PROVIDER: S-EPMC6612857 | biostudies-literature | 2019 Jul

REPOSITORIES: biostudies-literature