d-PBWT

d-PBWT implements a dynamic positional Burrows-Wheeler transform to enable dynamic haplotype matching and maintenance of haplotype panels for identifying identical-by-descent (IBD) segments and supporting genotype imputation.

Key Features:

• Dynamic Data Structure: Uses linked lists to store reverse prefix sorting at each genomic position, enabling insertion and deletion of individual haplotypes without reconstructing the entire structure.
• Efficient Algorithms: Implements insertion and deletion algorithms that maintain high performance while preserving existing PBWT functionalities.
• Comprehensive Query Support: Retrieves long shared segments (long matches) and supports queries between an external haplotype and a panel.
• Algorithmic Analysis: Includes systematic investigation of set maximal match and long match query algorithm variations, with average-case time complexity independent of database size and differing worst-case complexities and auxiliary data-structure dependencies.

Scientific Applications:

• IBD Segment Identification: Detects shared genetic segments (identical-by-descent) among individuals for studies of linkage and ancestry.
• Genotype Imputation: Supports prediction of unobserved genotypes in a population using haplotype panel comparisons.

Methodology:

Generalizes the static PBWT by using linked lists for reverse prefix sorting at each position and implements insertion and deletion algorithms, with analysis of set maximal match and long match query algorithms and their time-complexity properties.