Dept. of Comput. Sci. & Inf. Eng., National Taiwan Univ.Huang, Yao-TingYao-TingHuangKUN-MAO CHAO2018-09-102018-09-102005https://www.scopus.com/inward/record.uri?eid=2-s2.0-33751175840&doi=10.1109%2fEITC.2005.1544359&partnerID=40&md5=5a87677f7768e5531cd9fe04831a3b65http://scholars.lib.ntu.edu.tw/handle/123456789/315311This 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. © 2005 IEEE.application/pdf96833 bytesapplication/pdfAlgorithms; Approximation theory; Computer simulation; Genes; Optimal systems; Optimization; Approximation algorithms; Biological data; Haplotypes; Optimal solutions; Problem solvingconference paper10.1109/EITC.2005.15443592-s2.0-33751175840