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 Scopus citations

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 - 2009

Keywords

  • Computational biology
  • Haplotype inference
  • Pedigree
  • Recombination

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Linear-time haplotype inference on pedigrees without recombinations and mating loops'. Together they form a unique fingerprint.

  • Cite this