Approximation algorithms for the optimization problems of SNPs and haplotypes
Resource
Emerging Information Technology Conference, 2005.
Journal
Emerging Information Technology Conference 2005
Journal Volume
2005
Pages
105-107
Date Issued
2005
Author(s)
Huang, Yao-Ting
Abstract
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. © 2005 IEEE.
Event(s)
Emerging Information Technology Conference 2005
Other Subjects
Algorithms; Approximation theory; Computer simulation; Genes; Optimal systems; Optimization; Approximation algorithms; Biological data; Haplotypes; Optimal solutions; Problem solving
Type
conference paper
File(s)![Thumbnail Image]()
Loading...
Name
01544359.pdf
Size
94.56 KB
Format
Adobe PDF
Checksum
(MD5):ce3a5f1628c800453139c9894ff2eaa8