PedPhase

PedPhase infers haplotypes from genotypic data in pedigrees using algorithms for the minimum-recombinant haplotype configuration (MRHC) problem to support analysis of linkage and inheritance patterns.

Key Features:

• Zero Recombination Assumption: Operates under the zero recombination assumption appropriate for closely linked single nucleotide polymorphisms (SNPs) across chromosomal segments.
• Mathematical Formulation and Constraint Encoding: Formulates genotype constraints as a linear system of inheritance variables and encodes connectivity information with disjoint-set data structures for consistency checking.
• Algorithm Performance: On tree pedigrees without missing data, outputs general solutions and enumerates specific solutions in nearly linear time O(mn . alpha(n)), where m is the number of loci, n is the number of individuals, and alpha is the inverse Ackermann function.
• Extension to Complex Pedigrees: Extends applicability to looped pedigrees and pedigrees with missing data by incorporating partial constraints on inheritance variables.
• Implementation and Efficiency: Implemented in C++ and optimized to identify all 0-recombinant solutions, with experimental speed improvements reported from 10- to 100,000-fold over other algorithms across parameter settings.
• Empirical Validation: Empirical results corroborate the theoretical complexity bounds and reported performance.

Scientific Applications:

• Pedigree-based haplotype inference: Inferring haplotypes from pedigree genotypes for linkage and inheritance analyses.
• Population genetics: Analyzing tightly linked SNP haplotype structure and linkage across chromosome segments.
• Genealogical research: Reconstructing familial haplotype relationships in genealogical studies.
• Hereditary disease studies: Mapping inherited variants and haplotype segregation in investigations of hereditary diseases.

Methodology:

Solves the MRHC problem by formulating genotype constraints as a linear system of inheritance variables, encoding connectivity with disjoint-set structures, enumerating 0-recombinant solutions with nearly linear-time algorithms (O(mn . alpha(n))) and extending to looped pedigrees and missing data via partial inheritance-variable constraints; implemented in C++.