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

Mee Yee Chan, Wun Tat Chan, Francis Y.L. Chin, Stanley P.Y. Fung, Ming-Yang Kao

Research output: Contribution to journalArticle

1 Citation (Scopus)

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.

Original languageEnglish (US)
Pages (from-to)2179-2197
Number of pages19
JournalSIAM Journal on Computing
Volume38
Issue number6
DOIs
StatePublished - Jun 1 2009

Fingerprint

Pedigree
Haplotype
Linear equations
Recombination
Linear Time
Parity
Graph in graph theory
Linear-time Algorithm
System of Linear Equations
Optimal Algorithm
Resolve

Keywords

  • Computational biology
  • Haplotype inference
  • Pedigree
  • Recombination

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Cite this

Chan, Mee Yee ; Chan, Wun Tat ; Chin, Francis Y.L. ; Fung, Stanley P.Y. ; Kao, Ming-Yang. / Linear-time haplotype inference on pedigrees without recombinations and mating loops. In: SIAM Journal on Computing. 2009 ; Vol. 38, No. 6. pp. 2179-2197.
@article{9f818165ab504c26b2d2332e61565d6e,
title = "Linear-time haplotype inference on pedigrees without recombinations and mating loops",
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.",
keywords = "Computational biology, Haplotype inference, Pedigree, Recombination",
author = "Chan, {Mee Yee} and Chan, {Wun Tat} and Chin, {Francis Y.L.} and Fung, {Stanley P.Y.} and Ming-Yang Kao",
year = "2009",
month = "6",
day = "1",
doi = "10.1137/080680990",
language = "English (US)",
volume = "38",
pages = "2179--2197",
journal = "SIAM Journal on Computing",
issn = "0097-5397",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "6",

}

Linear-time haplotype inference on pedigrees without recombinations and mating loops. / Chan, Mee Yee; Chan, Wun Tat; Chin, Francis Y.L.; Fung, Stanley P.Y.; Kao, Ming-Yang.

In: SIAM Journal on Computing, Vol. 38, No. 6, 01.06.2009, p. 2179-2197.

Research output: Contribution to journalArticle

TY - JOUR

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

AU - Chan, Mee Yee

AU - Chan, Wun Tat

AU - Chin, Francis Y.L.

AU - Fung, Stanley P.Y.

AU - Kao, Ming-Yang

PY - 2009/6/1

Y1 - 2009/6/1

N2 - 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.

AB - 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.

KW - Computational biology

KW - Haplotype inference

KW - Pedigree

KW - Recombination

UR - http://www.scopus.com/inward/record.url?scp=65949111055&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=65949111055&partnerID=8YFLogxK

U2 - 10.1137/080680990

DO - 10.1137/080680990

M3 - Article

AN - SCOPUS:65949111055

VL - 38

SP - 2179

EP - 2197

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

SN - 0097-5397

IS - 6

ER -