Approximation algorithms for the optimization problems of SNPs and haplotypes

This paper studies two optimization problems in the SNP and haplotype research. The first problem asks for a minimum set of SNPs that can tolerate a certain number of missing data. The second problem asks for a minimum set of haplotypes that can explain a given set of genotypes. We show that both problems are NP-hard and design several approximation algorithms to solve them efficiently. These algorithms have been implemented and tested on both simulated and biological data. Our theoretical analysis and experimental results indicate that these algorithms are able to find solutions close to the optimal solutions.