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
KeywordsComputational biology
Haplotype inference
Pedigree
Recombination
Issue Date2009
PublisherSociety for Industrial and Applied Mathematics. The Journal's web site is located at http://epubs.siam.org/sam-bin/dbq/toclist/SICOMP
Citation
SIAM Journal On Computing, 2009, v. 38 n. 6, p. 2179-2197 How to Cite?
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
2015 Impact Factor: 0.841
2015 SCImago Journal Rankings: 1.808
ISI Accession Number ID
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

 

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://epubs.siam.org/sam-bin/dbq/toclist/SICOMPen_HK
dc.relation.ispartofSIAM Journal on Computingen_HK
dc.rightsSIAM Journal of Computing. Copyright © Society for Industrial and Applied Mathematics .en_HK
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
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

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats