File Download
There are no files associated with this item.
Supplementary

Citations:
 Scopus: 0
 Appears in Collections:
Article: Minimum parentoffspring recombination haplotype inference in pedigrees
Title  Minimum parentoffspring recombination haplotype inference in pedigrees 

Authors  
Issue Date  2005 
Publisher  Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ 
Citation  Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2005, v. 3680 LNBI, p. 100112 How to Cite? 
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 O(nm0 3k+12m0) time by adopting an approach similar to the one used by Doi, Li and Jiang [4] on pedigrees with n nodes and at most mo heterozygous loci in each node. In particular, the 1MRHI problem can be solved in O(nm0 42m0) 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(momin(t R)), 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 O(min{nm0 42m0, nm0 l+12μR+l}) time, where μR is the number of heterozygous loci in the root, and 1 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. © SpringerVerlag Berlin Heidelberg 2005. 
Persistent Identifier  http://hdl.handle.net/10722/89042 
ISSN  2005 Impact Factor: 0.402 2015 SCImago Journal Rankings: 0.252 
References 
DC Field  Value  Language 

dc.contributor.author  Zhang, Q  en_HK 
dc.contributor.author  Chin, FYL  en_HK 
dc.contributor.author  Shen, H  en_HK 
dc.date.accessioned  20100906T09:51:40Z   
dc.date.available  20100906T09:51:40Z   
dc.date.issued  2005  en_HK 
dc.identifier.citation  Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2005, v. 3680 LNBI, p. 100112  en_HK 
dc.identifier.issn  03029743  en_HK 
dc.identifier.uri  http://hdl.handle.net/10722/89042   
dc.description.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 O(nm0 3k+12m0) time by adopting an approach similar to the one used by Doi, Li and Jiang [4] on pedigrees with n nodes and at most mo heterozygous loci in each node. In particular, the 1MRHI problem can be solved in O(nm0 42m0) 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(momin(t R)), 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 O(min{nm0 42m0, nm0 l+12μR+l}) time, where μR is the number of heterozygous loci in the root, and 1 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. © SpringerVerlag Berlin Heidelberg 2005.  en_HK 
dc.language  eng  en_HK 
dc.publisher  Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/  en_HK 
dc.relation.ispartof  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)  en_HK 
dc.title  Minimum parentoffspring recombination haplotype inference in pedigrees  en_HK 
dc.type  Article  en_HK 
dc.identifier.email  Chin, FYL:chin@cs.hku.hk  en_HK 
dc.identifier.authority  Chin, FYL=rp00105  en_HK 
dc.description.nature  link_to_subscribed_fulltext   
dc.identifier.scopus  eid_2s2.033646181254  en_HK 
dc.identifier.hkuros  117569  en_HK 
dc.relation.references  http://www.scopus.com/mlt/select.url?eid=2s2.033646181254&selection=ref&src=s&origin=recordpage  en_HK 
dc.identifier.volume  3680 LNBI  en_HK 
dc.identifier.spage  100  en_HK 
dc.identifier.epage  112  en_HK 
dc.publisher.place  Germany  en_HK 
dc.identifier.scopusauthorid  Zhang, Q=8901546900  en_HK 
dc.identifier.scopusauthorid  Chin, FYL=7005101915  en_HK 
dc.identifier.scopusauthorid  Shen, H=7404522601  en_HK 