%0 Journal Article
%T Haplotypes versus genotypes on pedigrees
%A Bonnie B Kirkpatrick
%J Algorithms for Molecular Biology
%D 2011
%I BioMed Central
%R 10.1186/1748-7188-6-10
%X To answer these questions, a reduction is given from genotype problem instances to haplotype problem instances, and it is shown that solving the haplotype problem yields the solution to the genotype problem, up to constant factors or coefficients. The pedigree analysis problems we will consider are the likelihood, maximum probability haplotype, and minimum recombination haplotype problems.Two algorithms are introduced: an exponential-time hidden Markov model (HMM) for haplotype data where some individuals are untyped, and a linear-time algorithm for pedigrees having haplotype data for all individuals. Recombination estimates from the general haplotype HMM algorithm are compared to recombination estimates produced by a genotype HMM. Having haplotype data on all individuals produces better estimates. However, having several untyped individuals can drastically reduce the utility of haplotype data.Pedigree analysis, both linkage and association studies, has a long history of important contributions to genetics, including disease-gene finding and some of the first genetic maps for humans. Recent contributions include fine-scale recombination maps in humans [1], regions linked to Schizophrenia that might be missed by genome-wide association studies [2], and insights into the relationship between cystic fibrosis and fertility [3]. Algorithms for pedigree problems are of great interest to the computer science community, in part because of connections to machine learning algorithms, optimization methods, and combinatorics [4-8].Single-molecule sequencing is an attractive alternative to genotyping and would yield haplotypes for individuals in a pedigree [9]. Such technologies are being developed and may become commercial within five to ten years. Sequencing methods would apparently yield more information from the same set of sampled individuals, which is critical due to the limited availability of individuals for sampling in multi-generational pedigrees (i.e. individuals usua
%U http://www.almob.org/content/6/1/10