Output details

Linear-time Haplotype Inference on Pedigrees without Recombinations and Mating Loops

<12>Haplotyping is an important problem in bioinformatics: it requires an international consortium (the International HapMap Project). This paper was the first to give an optimal linear-time algorithm for zero-recombinant tree pedigrees. The efficiency is essential for algorithms that consider recombinations (e.g. Xiao et al Algorithmica 2012). Prior work (e.g. Li and Jiang RECOMB 2003, Xiao et al SODA 2007) all relied on Gaussian elimination which limits the time complexity improvement; here we instead represent the equations on auxiliary graph structures and then employ graph traversal. This idea was adopted by subsequent work (Liu and Jiang, J. Comb. Opt. 2010).