File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Minimum parent-offspring recombination haplotype inference in pedigrees

TitleMinimum parent-offspring recombination haplotype inference in pedigrees
Authors
Issue Date2005
PublisherSpringer 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. 100-112 How to Cite?
AbstractThe 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(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 1-MRHI 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 1-MRHI 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 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. © Springer-Verlag Berlin Heidelberg 2005.
Persistent Identifierhttp://hdl.handle.net/10722/89042
ISSN
2005 Impact Factor: 0.402
2015 SCImago Journal Rankings: 0.252
References

 

DC FieldValueLanguage
dc.contributor.authorZhang, Qen_HK
dc.contributor.authorChin, FYLen_HK
dc.contributor.authorShen, Hen_HK
dc.date.accessioned2010-09-06T09:51:40Z-
dc.date.available2010-09-06T09:51:40Z-
dc.date.issued2005en_HK
dc.identifier.citationLecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2005, v. 3680 LNBI, p. 100-112en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/89042-
dc.description.abstractThe 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(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 1-MRHI 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 1-MRHI 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 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. © Springer-Verlag Berlin Heidelberg 2005.en_HK
dc.languageengen_HK
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_HK
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)en_HK
dc.titleMinimum parent-offspring recombination haplotype inference in pedigreesen_HK
dc.typeArticleen_HK
dc.identifier.emailChin, FYL:chin@cs.hku.hken_HK
dc.identifier.authorityChin, FYL=rp00105en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.scopuseid_2-s2.0-33646181254en_HK
dc.identifier.hkuros117569en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-33646181254&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume3680 LNBIen_HK
dc.identifier.spage100en_HK
dc.identifier.epage112en_HK
dc.publisher.placeGermanyen_HK
dc.identifier.scopusauthoridZhang, Q=8901546900en_HK
dc.identifier.scopusauthoridChin, FYL=7005101915en_HK
dc.identifier.scopusauthoridShen, H=7404522601en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats