HAPLOFREQ - Estimating haplotype frequencies efficiently

Eran Halperin, Elad Hazan

Research output: Contribution to journalConference articlepeer-review

4 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)553-568
Number of pages16
JournalLecture Notes in Bioinformatics (Subseries of Lecture Notes in Computer Science)
Volume3500
DOIs
StatePublished - 2005
Event9th Annual International Conference on Research in Computational Molecular Biology, RECOMB 2005 - Cambridge, MA, United States
Duration: May 14 2005May 18 2005

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'HAPLOFREQ - Estimating haplotype frequencies efficiently'. Together they form a unique fingerprint.

Cite this