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 journalArticlepeer-review

1 Scopus citations


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
Issue number6
StatePublished - 2009


  • Computational biology
  • Haplotype inference
  • Pedigree
  • Recombination

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)


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