Syllable-PBWT

Syllable-PBWT performs space-efficient long-match haplotype queries between a query haplotype and large reference panels to enable scalable matching in biobank-scale genomic analyses.

Key Features:

• Segmentation into syllables: Divides each haplotype into smaller units called "syllables" to enable compact representation.
• Compressed positional prefix arrays: Constructs compressed positional prefix arrays from syllable-segmented haplotypes to reduce storage.
• Positional Burrows-Wheeler Transform (PBWT) variation: Implements a PBWT variation that preserves PBWT benefits while lowering memory demands.
• Polynomial rolling hash functions: Applies polynomial rolling hash functions for efficient positional substring comparisons within compressed structures.
• Syllable-Query algorithm: Provides the Syllable-Query long-match algorithm that operates on Syllable-PBWT data structures to perform long-match queries.
• Memory reduction: Achieves memory usage reductions reported as over 100 times compared to previous solutions.
• Runtime and CPU cache utilization: Improves runtime performance through enhanced CPU cache utilization of the compressed data structures.

Scientific Applications:

• Genetic genealogical searches: Detects long haplotype matches relevant to genetic genealogy and relatedness inference.
• Biobank-scale haplotype matching: Enables matching and long-match queries across millions of haplotypes in biobank-scale datasets.
• Demonstrated datasets: Has been evaluated on datasets including UK Biobank genotype data and 1000 Genomes Project sequence data.

Methodology:

Segments haplotypes into syllables, builds compressed positional prefix arrays from those syllables, uses polynomial rolling hash functions for rapid positional substring comparisons, and executes the Syllable-Query long-match algorithm on the resulting data structures.