Heu-MCHC

Heu-MCHC solves the Minimum-Change Haplotype Configuration (MCHC) problem by inferring haplotypes in pedigree data while minimizing the total number of recombinations and point mutations.

Key Features:

• Problem Definition: Formulates MCHC as an extension of the Minimum-Recombinant Haplotype Configuration (MRHC) problem that incorporates both recombination and mutation events.
• Computational Efficiency: Implements a heuristic algorithm grounded in an L-reduction to a coding problem to enable efficient computation.
• Approximation Guarantees: Provably O(nm/(log nm))-approximable for both MCHC and MRHC on general pedigrees, where n is the pedigree size and m is the genotype length.
• Flexibility and Adaptability: Adapts the heuristic to solve the original MRHC problem and can leverage additional knowledge about input genotypes.

Scientific Applications:

• Haplotype inference in pedigrees: Infers haplotype configurations from pedigree genotype data while accounting for recombinations and point mutations.
• Analysis of genetic variation events: Enables studies that quantify and minimize recombination and mutation events in inheritance patterns.
• Genetic studies of complex traits and diseases: Supports research into inheritance patterns relevant to complex trait and disease genetics by providing more precise haplotype reconstructions.

Methodology:

The approach defines MCHC (shown APX-hard under several restrictions) and applies a heuristic algorithm based on an L-reduction to a coding problem to obtain an O(nm/(log nm))-approximation.