Haplotyping for Disease Association: A Combinatorial Approach

We consider a combinatorial problem derived from haplotyping a population with respect to a , either recessive or dominant. Given a set of individuals, partitioned into healthy and diseased, and the corresponding sets of genotypes, we want to infer "bad" and "good" haplotypes to account for these genotypes and for the disease. Assume, for example, that the disease is recessive. Then, the resolving haplotypes must consist of bad and good haplotypes so that 1) each genotype belonging to a diseased individual is explained by a pair of bad haplotypes and 2) each genotype belonging to a healthy individual is explained by a pair of haplotypes of which at least one is good. We prove that the associated decision problem is NP-complete. However, we also prove that there is a simple solution, provided that the data satisfy a very weak requirement.

1 Introduction

A single nucleotide polymorphism (SNP, pronounced “snip”) is a site of the human genome showing a statistically significant variability within a population. Apart from very rare exceptions, at each SNP, only two nucleotides (out of A, T, C, and G) are observed and they are called the SNP alleles. SNPs are the predominant form of human polymorphism and their importance can hardly be overestimated. They are widely used in therapeutic, diagnostic, and forensic applications and a SNP consortium exists with the goal of designing a detailed SNP map for the human genome [13], [10].