Here, we systematically evaluate the genotype imputation approach outlined in the paragraph above using our Markov Chain Haplotyping algorithm (MaCH 1.0; see Appendix for implementation details). To estimate haplotypes, our approach starts by randomly generating a pair of haplotypes that is compatible with observed genotypes for each sampled individual. These initial haplotype estimates are then refined through a series of iterations. In each iteration, a new pair of haplotypes is sampled for each individual in turn using a Hidden Markov Model (HMM) that describes the haplotype pair as an imperfect mosaic of the other haplotypes. Model parameters that characterize the probability of change in the mosaic pattern between every pair of consecutive markers and the probability of observing an imperfection in the mosaic at each specific point are also updated. After many iterations (typically 20–100), a consensus haplotype can be constructed by merging the haplotypes sampled in each round.
