| Since the introduction of the Perfect Phylogeny Haplotyping (PPH) Problem in RECOMB 2002 [27], the problem of finding a linear-time (deterministic, worst-case) solution for it has remained open, despite broad interest in the PPH problem and a series of papers on various aspects of it. In this dissertation we solve the open problem, giving a practical, deterministic linear-time algorithm based on a simple data-structure and simple operations on it. Simulations show that the algorithm is much faster in practice than prior methods. The value of a linear-time solution to the PPH problem is partly conceptual and partly for use in the inner-loop of algorithms for more complex problems, where the PPH problem must be solved repeatedly.;Combining the linear-time algorithm for phasing genotypes on trees with a recently proposed tree-based method for association mapping, we devise an efficient method for scanning unphased whole-genome data for association. From unphased genotype data, our algorithm builds local phylogenies along the genome, and scores each tree according to the clustering of cases and controls. We assess the performance of our new method on both simulated and real biological data sets. |
