A fast haplotype inference method for large population genotype data

With the rapid progress of genotyping techniques, many large-scale, genome-wide disease studies are now under way. One of the challenges of large disease-association studies is developing a fast and accurate computing method for haplotype inference from genotype data. In this paper, a new computing method for population-based haplotype inference problem is proposed. The designed method does not assume haplotype blocks in the population and allows each individual haplotype to have its own structure, and thus is able to accommodate recombination and obtain higher adaptivity to the genotype data, specifically in the case of long marker maps. This method develops a dynamic programming algorithm, which is theoretically guaranteed to find exact maximum likelihood solutions of the variable order Markov chain model for haplotype inference problem within linear running time. Hence, it is fast and, as a result, practicable for large genotype datasets. Through extensive computational experiments on large-scale real genotype data, the proposed method is shown to be fast and efficient.