PBWT-Query

PBWT-Query performs efficient haplotype matching between a query and a panel of millions of haplotypes using the Positional Burrows-Wheeler Transform (PBWT) to identify shared DNA segments for genetic genealogical searches.

Key Features:

• PBWT indexing: Pre-computes a PBWT index of the panel to enable constant-time matching at each genomic position.
• Durbin's Algorithm 5 foundation: Builds on Durbin's Algorithm 5 for identification of set-maximal matches within the panel.
• Virtual insertion: Integrates a query into the PBWT matrix via virtual insertion to allow scanning of PBWT match blocks both upwards and downwards.
• Length-threshold matching (L): Identifies matches that are longer than or equal to a specified length L rather than only the longest set-maximal matches.
• L-PBWT-Query acceleration: Introduces additional data structures to bypass blocks of incomplete matches and accelerate search throughput.
• Large-cohort scale: Designed to operate on panels containing millions of haplotypes for large-cohort analyses.
• Empirical validation: Evaluated on simulated datasets and real-world data from the UK Biobank.

Scientific Applications:

• Genetic genealogy: Detects shared DNA segments to support genealogical searches and identification of matches between individuals.
• Relatedness detection: Identifies related individuals for a given query within very large cohorts.
• Large-cohort haplotype matching: Enables rapid haplotype matching across extensive genomic datasets containing millions of haplotypes.
• Method benchmarking: Provides a framework validated on simulated data and UK Biobank for benchmarking match-detection performance.

Methodology:

Pre-compute a PBWT index of the panel to enable constant-time per-position matching; apply Durbin's Algorithm 5 to detect set-maximal matches; use virtual insertion to integrate the query and scan PBWT match blocks upward and downward to find matches ≥ L; in L-PBWT-Query, employ additional data structures to bypass incomplete-match blocks and accelerate the search.