A commonly used tool in disease association studies is the search for discrepancies between
the haplotype distribution in the case and control populations. In order to find this discrepancy,
the haplotypes frequency in each of the populations is estimated from the genotypes.
We present a new method HAPLOFREQ to estimate haplotype frequencies over a short genomic
region given the genotypes or haplotypes with missing data or sequencing errors. Our
approach incorporates a maximum likelihood model based on a simple random generative
model which assumes that the genotypes are independently sampled from the population.
We first show that if the phased haplotypes are given, possibly with missing data, we can
estimate the frequency of the haplotypes in the population by finding the global optimum
of the likelihood function in polynomial time. If the haplotypes are not phased, finding the
maximum value of the likelihood function is NP-hard. In this case, we define an alternative
likelihood function which can be thought of as a relaxed likelihood function. We show
that the maximum relaxed likelihood can be found in polynomial time and that the optimal
solution of the relaxed likelihood approaches asymptotically to the haplotype frequencies
in the population. In contrast to previous approaches, our algorithms are guaranteed to
converge in polynomial time to a global maximum of the different likelihood functions.
We compared the performance of our algorithm to the widely used program PHASE, and
we found that our estimates are at least 10% more accurate than PHASE and about ten
times faster than PHASE. Our techniques involve new algorithms in convex optimization.
These algorithms may be of independent interest. Particularly, they may be helpful in other
maximum likelihood problems arising from survey sampling.
