SDPHapInfer

SDPHapInfer formulates haplotype inference as an integer quadratic programming problem and applies an iterative semidefinite programming-based approximation to minimize the number of haplotypes required to explain genotype data.

Key Features:

• Problem Formulation: Defines the optimal haplotype inference (OHI) problem as NP-hard and formulates it as an integer quadratic programming (IQP) problem.
• Approximation Algorithm: Employs an iterative semidefinite programming-based approximation algorithm to address the IQP formulation.
• Performance Guarantee: Provides an approximation guarantee within a factor of O(log n) of the optimal, where n is the number of genotypes.
• Comparative Performance: Shows competitive error rates on simulated and biological datasets compared with HAPLOTYPER (expectation-maximization) and exhibits variable performance relative to PHASE.
• Scalability: Demonstrates greater efficiency than HAPAR, which uses a branching and bound algorithm, particularly as the number of genotypes increases.

Scientific Applications:

• Population Genetics: Enables haplotype reconstruction for analyses of genetic diversity and evolutionary relationships.
• Disease Association Studies: Supports inference of haplotype structures used in linking genetic variation to phenotypic and disease associations.
• Large-scale Genomic Studies: Applicable to studies requiring inference from large numbers of genotypes due to its comparative computational efficiency.

Methodology:

Formulates OHI as an IQP and solves it using an iterative semidefinite programming-based approximation algorithm with an O(log n) approximation guarantee.