File Download
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1137/080680990
- Scopus: eid_2-s2.0-65949111055
- WOS: WOS:000266018400004
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: Linear-time haplotype inference on pedigrees without recombinations and mating loops
Title | Linear-time haplotype inference on pedigrees without recombinations and mating loops | ||||||
---|---|---|---|---|---|---|---|
Authors | |||||||
Keywords | Computational biology Haplotype inference Pedigree Recombination | ||||||
Issue Date | 2009 | ||||||
Publisher | Society 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? | ||||||
Abstract | In 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 Identifier | http://hdl.handle.net/10722/60605 | ||||||
ISSN | 2023 Impact Factor: 1.2 2023 SCImago Journal Rankings: 2.143 | ||||||
ISI Accession Number ID |
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 Field | Value | Language |
---|---|---|
dc.contributor.author | Chan, MY | en_HK |
dc.contributor.author | Chan, WT | en_HK |
dc.contributor.author | Chin, FYL | en_HK |
dc.contributor.author | Fung, SPY | en_HK |
dc.contributor.author | Kao, MY | en_HK |
dc.date.accessioned | 2010-05-31T04:14:50Z | - |
dc.date.available | 2010-05-31T04:14:50Z | - |
dc.date.issued | 2009 | en_HK |
dc.identifier.citation | SIAM Journal On Computing, 2009, v. 38 n. 6, p. 2179-2197 | en_HK |
dc.identifier.issn | 0097-5397 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/60605 | - |
dc.description.abstract | In 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.language | eng | en_HK |
dc.publisher | Society for Industrial and Applied Mathematics. The Journal's web site is located at http://www.siam.org/journals/sicomp.php | - |
dc.relation.ispartof | SIAM Journal on Computing | en_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.subject | Computational biology | en_HK |
dc.subject | Haplotype inference | en_HK |
dc.subject | Pedigree | en_HK |
dc.subject | Recombination | en_HK |
dc.title | Linear-time haplotype inference on pedigrees without recombinations and mating loops | 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 | published_or_final_version | - |
dc.identifier.doi | 10.1137/080680990 | en_HK |
dc.identifier.scopus | eid_2-s2.0-65949111055 | en_HK |
dc.identifier.hkuros | 166275 | en_HK |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-65949111055&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.volume | 38 | en_HK |
dc.identifier.issue | 6 | en_HK |
dc.identifier.spage | 2179 | en_HK |
dc.identifier.epage | 2197 | en_HK |
dc.identifier.eissn | 1095-7111 | - |
dc.identifier.isi | WOS:000266018400004 | - |
dc.publisher.place | United States | en_HK |
dc.identifier.scopusauthorid | Chan, MY=7402597863 | en_HK |
dc.identifier.scopusauthorid | Chan, WT=7403918060 | en_HK |
dc.identifier.scopusauthorid | Chin, FYL=7005101915 | en_HK |
dc.identifier.scopusauthorid | Fung, SPY=7201970079 | en_HK |
dc.identifier.scopusauthorid | Kao, MY=7202198147 | en_HK |
dc.identifier.issnl | 0097-5397 | - |