Haplotyping for Disease Association: A Combinatorial Approach

ABSTRACT

We consider a combinatorial problem derived from haplotyping a population with respect to a genetic disease, 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 e.g. the disease is recessive. Then, the resolving haplotypes must consist of \emph{bad} and \emph{good} haplotypes, so that (i) each genotype belonging to a diseased individual is explained by a pair of bad haplotypes and (ii) 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 the data satisfy a very weak requirement.

REFERENCES

• 1: V. Bafna, D. Gusfield, G. Lancia, and S. Yooseph, "Haplotyping as Perfect Phylogeny: A Direct Approach," J. Computational Biology, vol. 10, nos. 3-4, pp. 323-340, 2003.
• 2: D.G. Brown and J.M. Harrower, "A New Integer Programming Formulation for the Pure Parsimony Problem in Haplotype Analysis," Proc. Fourth Int'l Workshop Algorithms in Bioinformatics, pp. 254-265, 2004.
• 3: A. Clark, "Inference of Haplotypes from PCR-Amplified Samples of Diploid Populations," Molecular Biology Evolution, vol. 7, pp. 111-122, 1990.
• 4: Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
• 5: Z. Ding, V. Filkov, and D. Gusfield, "A Linear-Time Algorithm for the Perfect Phylogeny Haplotyping Problem," Proc. Ninth Ann. Int'l Conf. Research in Computational Molecular Biology, 2005.
• 6: E. Eskin, E. Halperin, and R. Karp, "Efficient Reconstruction of Haplotype Structure via Perfect Phylogeny," J. Bioinformatics and Computational Biology, vol. 1, no. 1, pp. 1-20, 2003.
• 7: Harvey J. Greenberg , William E. Hart , Giuseppe Lancia, Opportunities for Combinatorial Optimization in Computational Biology, INFORMS Journal on Computing, v.16 n.3, p.211-231, June 2004 [doi>10.1287/ijoc.1040.0073]
• 8: D. Gusfield, "Haplotype Inference by Pure Parsimony," Proc. 14th Ann. Symp. Combinatorial Pattern Matching, pp. 144-155, 2003.
• 9: D. Gusfield and S.H. Orzack, "Haplotype Inference," Handbook of Computational Molecular Biology, pp. 1-28, Chapman and Hall/ CRC Press, 2005.
• 10: L. Helmuth, "Genome Research: Map of the Human Genome 3.0," Science, vol. 293, no. 5530, pp. 583-585, 2001.
• 11: Yao-Ting Huang , Kun-Mao Chao , Ting Chen, An approximation algorithm for haplotype inference by maximum parsimony, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico [doi>10.1145/1066677.1066714]
• 12: Giuseppe Lancia , Maria Cristina Pinotti , Romeo Rizzi, Haplotyping Populations by Pure Parsimony: Complexity of Exact and Approximation Algorithms, INFORMS Journal on Computing, v.16 n.4, p.348-359, Fall 2004 [doi>10.1287/ijoc.1040.0085]
• 13: E. Marshall, "Drug Firms to Create Public Database of Genetic Mutations," Science, vol. 284, no. 5413, pp. 406-407, 1999.
• 14: L. Wang and Y. Xu, "Haplotype Inference by Maximum Parsimony," Bioinformatics, vol. 19, no. 14, pp. 1773-1780, 2003.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES
      Subjects: Biology and genetics

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Pattern analysis; Classifier design and evaluation
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis

General Terms:
Algorithms, Design

Keywords:
Combinatorics, Discrete Mathematics, Biology and genetics