## Abstract

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(nm_{0} ^{3k+1}2^{m0}) time on pedigrees with n nodes and at most m_{0} 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 language | English |
---|---|

Pages (from-to) | 985-993 |

Number of pages | 9 |

Journal | Lecture Notes in Computer Science |

Volume | 3515 |

Issue number | II |

DOIs | |

Publication status | Published - 2005 |

Externally published | Yes |

Event | 5th International Conference on Computational Science - ICCS 2005 - Atlanta, GA, United States Duration: 22 May 2005 → 25 May 2005 |