https://scholars.lib.ntu.edu.tw/handle/123456789/315311
標題: | Approximation algorithms for the optimization problems of SNPs and haplotypes | 作者: | Huang, Yao-Ting KUN-MAO CHAO |
公開日期: | 2005 | 卷: | 2005 | 起(迄)頁: | 105-107 | 來源出版物: | Emerging Information Technology Conference 2005 | 會議論文: | Emerging Information Technology Conference 2005 | 摘要: | 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. |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-33751175840&doi=10.1109%2fEITC.2005.1544359&partnerID=40&md5=5a87677f7768e5531cd9fe04831a3b65 http://scholars.lib.ntu.edu.tw/handle/123456789/315311 |
DOI: | 10.1109/EITC.2005.1544359 | SDG/關鍵字: | Algorithms; Approximation theory; Computer simulation; Genes; Optimal systems; Optimization; Approximation algorithms; Biological data; Haplotypes; Optimal solutions; Problem solving |
顯示於: | 生醫電子與資訊學研究所 |
檔案 | 描述 | 大小 | 格式 | |
---|---|---|---|---|
01544359.pdf | 94.56 kB | Adobe PDF | 檢視/開啟 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。