K-recombination haplotype inference in pedigrees

Francis Y.L. Chin, Qiangfeng Zhang, Hong Shen

Research output: Contribution to journalConference articlepeer-review

5 Citations (Scopus)


Haplotyping under the Mendelian law of inheritance on pedigree genotype data is studied. Because genetic recombinations are rare, research has focused on Minimum Recombination Haplotype Inference (MRHI), i.e. finding the haplotype configuration consistent with the genotype data having the minimum number of recombinations. We focus here on the more realistic k-MRHI, which has the additional constraint that the number of recombinations on each parent-offspring pair is at most k. Although k-MRHI is NP-hard even for k = 1, we give an algorithm to solve k-MRHI efficiently by dynamic programming in 0(nm0 3k+12m0) time on pedigrees with n nodes and at most m0 heterozygous loci in each node. Experiments on real and simulated data show that, in most cases, our algorithm gives the same haplotyping results but runs much faster than other popular algorithms.

Original languageEnglish
Pages (from-to)985-993
Number of pages9
JournalLecture Notes in Computer Science
Issue numberII
Publication statusPublished - 2005
Externally publishedYes
Event5th International Conference on Computational Science - ICCS 2005 - Atlanta, GA, United States
Duration: 22 May 200525 May 2005


Dive into the research topics of 'K-recombination haplotype inference in pedigrees'. Together they form a unique fingerprint.

Cite this