An approximation algorithm for haplotype inference by maximum parsimony.

Abstract excerpt

This paper studies haplotype inference by maximum parsimony using population data. We 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. We prove that OHI is NP-hard and can be formulated as an integer quadratic programming (IQP) problem. To solve the IQP problem, we propose an...

Topics

Share this publication in a Topic to start or enrich a Post.

• Share to Algorithms
• Share to Computational Biology
• Share to Cystic Fibrosis