Haplotyping for disease association: a combinatorial approach

Area of Science:

• Computational Biology
• Genetics
• Bioinformatics

Background:

• Haplotyping is crucial for understanding genetic disease transmission.
• Distinguishing between healthy and diseased individuals based on genotypes is complex.
• Inferring haplotype contributions to disease status requires robust methods.

Purpose of the Study:

• To formulate and solve a combinatorial problem for inferring disease-associated haplotypes.
• To determine the computational complexity of haplotype inference for genetic diseases.
• To identify conditions under which a simple solution for haplotyping is feasible.

Main Methods:

• Formulation of a combinatorial problem based on population genotype data and disease status.
• Analysis of the decision problem associated with inferring "good" and "bad" haplotypes.
• Proof of NP-completeness for the general problem.
• Development of a simple solution under specific data constraints.

Main Results:

• The problem of inferring disease-related haplotypes is proven to be NP-complete.
• A straightforward algorithm can solve the haplotyping problem.
• The solution is contingent upon a minimal, weak data requirement.

Conclusions:

• Despite the NP-complete nature of the general problem, efficient haplotyping is achievable.
• The findings provide a practical approach for genetic disease analysis using population data.
• This work contributes to the understanding of genotype-phenotype relationships in inherited diseases.