Haplotype inference and block partitioning in mixed population samples.

Multi-population haplotype inference and block partitioning is a difficult task when dealing with mixed genotype samples. A number of studies have shown that the haplotype block structures, as well as the collections of common haplotypes and their frequencies, vary significantly among world populations. These differences are more extreme when the geographical locations for the populations are more distant. Some of the previous studies performed haplotype inference in multi-population samples with known population assignment. Others developed algorithms for clustering of the mixed haplotype or genotype samples with different block structures or genetic marker profiles. We present a new algorithm that performs haplotype inference and block partitioning in a mixed sample of genotypes from two populations when the population assignments are not known. Given a mixed genotype sample, the proposed algorithm (HAPLOCLUST) extracts two clusters of genotypes with different block structures in addition to performing haplotype inference on each of these clusters. When tested on a set of unrelated individuals, our algorithm provides correct assignments comparable to those of two state-of-the-art algorithms for population stratification. The contribution of HAPLOCLUST consists of performing haplotype/block-based population stratification and simultaneously finding the haplotype resolution and block partitioning for the extracted clusters.