Speaker: Jin Jun
Day:  Wednesday, 3/29/2006
Room: ITEB 336
Time: 3:30pm
Title: An Approximation Algorithm for Haplotype Inference by Maximum
Parsimony

This paper studies haplotype inference by maximum parsimony. 
They define the optimal haplotype inference (OHI) problem as 
given a set of genotypes and a set of related haplotypes, 
find a minimum subset of haplotypes that can resolve all the genotypes. 
They prove that OHI is NP-hard and can be formulated as 
an integer quadratic programming (IQP) problem. 
To solve the IQP problem, they propose an iterative semidefinite 
programming-based approximation algorithm, (called SDPHapInfer).
They show that this algorithm finds a solution within a factor of O(log n) 
of the optimal solution, where n is the number of genotypes.

From : Journal of Computational Biology, Vol. 12, No. 10, Pp. 1261-1274,
2005.