Minimum Parent-Offspring Recombination Haplotype Inference in Pedigrees

  • Qiangfeng Zhang
  • Francis Y. L. Chin
  • Hong Shen
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3680)


The problem of haplotype inference under the Mendelian law of inheritance on pedigree genotype data is studied. The minimum recombination principle states that genetic recombinations are rare and haplotypes with fewer recombinations are more likely to exist. Given genotype data on a pedigree, the problem of Minimum Recombination Haplotype Inference (MRHI) is to find a set of haplotype configurations consistent with the genotype data having the minimum number of recombinations. In this paper, we focus on a variation of the MRHI problem that gives more realistic solutions, namely the k-MRHI problem, which has the additional constraint that the number of recombinations in each parent-offspring pair is at most k. Although the k-MRHI problem is NP-hard even for k = 1, the k-MRHI problem with k > 1 can be solved efficiently by dynamic programming in \(O(nm^{3k+1}_{0}2^{m0})\) time by adopting an approach similar to the one used by Doi, Li and Jiang on pedigrees with n nodes and at most m 0 heterozygous loci in each node. In particular, the 1-MRHI problem can be solved in \(O(nm^{4}_{0}2^{m0})\) time. We propose an O(n 2 m 0) algorithm to find a node as the root of the pedigree tree so as to further reduce the time complexity to O(m 0 min(t R )), where t R is the number of feasible haplotype configuration combinations in all trios in the pedigree tree when R is the root. If the pedigree has few generations, the 1-MRHI problem can be solved in \(O(min\{nm^{4}_{0}2^{m0}, nm^{l+1}_{0}2^{\mu R+l}\})\) time, where μ R is the number of heterozygous loci in the root, and l is the maximum path length from the root to the leaves in the pedigree tree. Experiments on both real and simulated data confirm the out-performance of our algorithm when compared with other popular algorithms. In most real cases, our algorithm gives the same haplotyping results but runs much faster. In some real cases, other algorithms give an answer which has the least number of recombinations, while our algorithm gives a more credible solution and runs faster.


Time Complexity Nuclear Family Dynamic Programming Algorithm Heterozygous Locus Haplotype Inference 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    The CEPH genotype database,
  2. 2.
    Clark, A.G.: Inference of haplotypes from PCR-amplified samples of diploid populations. Mol. Biol. Evol. 7(2), 111–122 (1990)Google Scholar
  3. 3.
    Dausset, J., Cann, H., Cohen, D., Lathrop, M., Lalouel, J.M., White, R.: Centre d’etude du polymorphisme humain (ceph): collaborative genetic mapping of the human genome. Genomics 5, 575–577 (1990)CrossRefGoogle Scholar
  4. 4.
    Doi, K., Li, J., Jiang, T.: Minimum recombinant haplotype configuration on tree pedigree. In: Benson, G., Page, R.D.M. (eds.) WABI 2003. LNCS (LNBI), vol. 2812, pp. 339–353. Springer, Heidelberg (2003)CrossRefGoogle Scholar
  5. 5.
    Griffiths, A., Gelbart, W., Lewontin, R., Miller, J.: Modern Genetic Analysis: Integrating Genes and Genomes. W.H. Freeman and Company, N.Y. (2002)Google Scholar
  6. 6.
    Gusfield, D.: Inference of haplotypes from samples of diploid populations: complexity and algorithms. J. Computational Biology 8, 305–323 (2001)CrossRefGoogle Scholar
  7. 7.
    Li, J., Jiang, T.: Efficient inference of haplotypes from genotypes on a pedigree. J. Bioinfo Comp. Biol. 1(1) (2003)Google Scholar
  8. 8.
    Li, J., Jiang, T.: Efficient inference of haplotypes from genotypes on a pedigree. In: Proc. of RECOMB 2003, pp. 197–206 (2003)Google Scholar
  9. 9.
    Litt, M., Kramer, P., Browne, D., Gancher, S., Brunt, E.R.P., Root, D., et al.: A gene for episodic ataxia/myokymia maps to chromosome 12p13. Am. J. Hum. Genet. 55, 702–709 (1994)Google Scholar
  10. 10.
    Murray, J.C., et al.: A comprehensive human linkage map with centimorgan density. Science 265, 2049–2054 (1994)CrossRefGoogle Scholar
  11. 11.
    O’Connell, J.R.: Zero-recombinant haplotyping: applications to fine mapping using snps. Genet. Epidemiol. 19 (2000)Google Scholar
  12. 12.
    Qian, D., Beckmann, L.: Minimum-recombinant haplotyping in pedigrees. Am J. Hum. Genet. 70(6), 1434–1445 (2002)CrossRefGoogle Scholar
  13. 13.
    Russo, E., et al.: Single nucleotide polymorphism: Big pharma hedges its bets. The Scientist 13 (1999)Google Scholar
  14. 14.
    Stephens, M., Smith, N.J., Donnelly, P.: A new statistical method for haplotype reconstruction for population data. Am. J. Hum. Genet. 68, 978–989 (2001)CrossRefGoogle Scholar
  15. 15.
    Tapadar, P., Ghosh, S., Majumder, P.P.: Haplotyping in pedigrees via a genetic algorithm. Hum. Hered. 50(1), 43–56 (2000)CrossRefGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Qiangfeng Zhang
    • 1
  • Francis Y. L. Chin
    • 2
  • Hong Shen
    • 3
  1. 1.Department of Computer ScienceUniversity of Science and Technology of ChinaHefeiChina
  2. 2.Department of Computer ScienceThe University of Hong KongPokfulam, Hong Kong
  3. 3.Graduate School of Information ScienceJAISTIshikawaJapan

Personalised recommendations