Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/36746
Citations  
Scopus  Web of Science®  Altmetric 

?

?

Type:  Journal article 
Title:  Minimum parentoffspring recombination haplotype inference in pedigrees 
Author:  Zhang, Q. Chin, F. Shen, H. 
Citation:  Lecture Notes in Artificial Intelligence, 2005; 2:100112 
Publisher:  Springer 
Issue Date:  2005 
ISSN:  18612075 16113349 
Statement of Responsibility:  Qiangfeng Zhang, Francis Y.L. Chin and Hong Shen 
Abstract:  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 kMRHI problem, which has the additional constraint that the number of recombinations in each parentoffspring pair is at most k. Although the kMRHI problem is NPhard even for k = 1, the kMRHI problem with k > 1 can be solved efficiently by dynamic programming in time by adopting an approach similar to the one used by Doi, Li and Jiang on pedigrees with n nodes and at most m0 heterozygous loci in each node. In particular, the 1MRHI problem can be solved in time. We propose an O(n2m0) algorithm to find a node as the root of the pedigree tree so as to further reduce the time complexity to O(m0min(tR)), where tR 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 1MRHI problem can be solved in 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 outperformance 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. 
Description:  The original publication is available at www.springerlink.com 
DOI:  10.1007/11567752_7 
Published version:  http://www.springerlink.com/content/lkq286xq51uj8281/?p=232f2ec0d0a74bf69e492b1bd8482946&pi=6 
Appears in Collections:  Aurora harvest Computer Science publications 
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.