File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Linear-time haplotype inference on pedigrees without recombinations and mating loops

TitleLinear-time haplotype inference on pedigrees without recombinations and mating loops
Authors
Chan, MYChan, WTChin, FYLFung, SPYKao, MY
KeywordsComputational biology
Haplotype inference
Pedigree
Recombination
Issue Date2009
PublisherSociety for Industrial and Applied Mathematics. The Journal's web site is located at http://www.siam.org/journals/sicomp.php
Citation
SIAM Journal On Computing, 2009, v. 38 n. 6, p. 2179-2197 How to Cite?
DOI: http://dx.doi.org/10.1137/080680990
AbstractIn this paper, an optimal linear-time algorithm is presented to solve the haplotype inference problem for pedigree data when there are no recombinations and the pedigree has no mating loops. The approach is based on the use of graphs to capture SNP, Mendelian, and parity constraints of the given pedigree. This representation allows us to capture the constraints as the edges in a graph, rather than as a system of linear equations as in previous approaches. Graph traversals are then used to resolve the parity of these edges, resulting in an optimal running time. © 2009 Society for Industrial and Applied Mathematics.
Persistent Identifierhttp://hdl.handle.net/10722/60605
ISSN
0097-5397
2021 Impact Factor: 1.475
2020 SCImago Journal Rankings: 1.533
ISI Accession Number ID
WOS:000266018400004
Funding AgencyGrant Number
Hong Kong RGCHKU-7119/05E
HKU Strategic Research Team Fund
Funding Information:

The third author's research was supported by Hong Kong RGC grant HKU-7119/05E and HKU Strategic Research Team Fund.

References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorChan, MYen_HK
dc.contributor.authorChan, WTen_HK
dc.contributor.authorChin, FYLen_HK
dc.contributor.authorFung, SPYen_HK
dc.contributor.authorKao, MYen_HK
dc.date.accessioned2010-05-31T04:14:50Z-
dc.date.available2010-05-31T04:14:50Z-
dc.date.issued2009en_HK
dc.identifier.citationSIAM Journal On Computing, 2009, v. 38 n. 6, p. 2179-2197en_HK
dc.identifier.issn0097-5397en_HK
dc.identifier.urihttp://hdl.handle.net/10722/60605-
dc.description.abstractIn this paper, an optimal linear-time algorithm is presented to solve the haplotype inference problem for pedigree data when there are no recombinations and the pedigree has no mating loops. The approach is based on the use of graphs to capture SNP, Mendelian, and parity constraints of the given pedigree. This representation allows us to capture the constraints as the edges in a graph, rather than as a system of linear equations as in previous approaches. Graph traversals are then used to resolve the parity of these edges, resulting in an optimal running time. © 2009 Society for Industrial and Applied Mathematics.en_HK
dc.languageengen_HK
dc.publisherSociety for Industrial and Applied Mathematics. The Journal's web site is located at http://www.siam.org/journals/sicomp.php-
dc.relation.ispartofSIAM Journal on Computingen_HK
dc.rights© 2009 Society for Industrial and Applied Mathematics. First Published in SIAM Journal on Computing in volume 38, issue 6, published by the Society for Industrial and Applied Mathematics (SIAM).-
dc.subjectComputational biologyen_HK
dc.subjectHaplotype inferenceen_HK
dc.subjectPedigreeen_HK
dc.subjectRecombinationen_HK
dc.titleLinear-time haplotype inference on pedigrees without recombinations and mating loopsen_HK
dc.typeArticleen_HK
dc.identifier.emailChin, FYL:chin@cs.hku.hken_HK
dc.identifier.authorityChin, FYL=rp00105en_HK
dc.description.naturepublished_or_final_version-
dc.identifier.doi10.1137/080680990en_HK
dc.identifier.scopuseid_2-s2.0-65949111055en_HK
dc.identifier.hkuros166275en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-65949111055&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume38en_HK
dc.identifier.issue6en_HK
dc.identifier.spage2179en_HK
dc.identifier.epage2197en_HK
dc.identifier.eissn1095-7111-
dc.identifier.isiWOS:000266018400004-
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridChan, MY=7402597863en_HK
dc.identifier.scopusauthoridChan, WT=7403918060en_HK
dc.identifier.scopusauthoridChin, FYL=7005101915en_HK
dc.identifier.scopusauthoridFung, SPY=7201970079en_HK
dc.identifier.scopusauthoridKao, MY=7202198147en_HK
dc.identifier.issnl0097-5397-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats