https://scholars.lib.ntu.edu.tw/handle/123456789/339644
標題: | A new framework for the selection of tag SNPs by multimarker haplotypes | 作者: | Huang, Yao-Ting KUN-MAO CHAO |
關鍵字: | Algorithm; Haplotype; Linkage disequilibrium; NP-hardness; SNP | 公開日期: | 2008 | 卷: | 41 | 期: | 6 | 起(迄)頁: | 953-961 | 來源出版物: | Journal of Biomedical Informatics | 摘要: | This paper proposes a new framework for the selection of tag SNPs based on haplotypes instead of on a single SNP. The tag SNPs found by this framework form a set of haplotypes completely predictive of the alleles of all untyped SNPs. We refer to this problem as MTMH, which is defined as follows: given a set of SNPs, find a minimum subset of SNPs (called tag SNPs) which defines a set of haplotypes completely predictive of the alleles of all untyped SNPs. The MTMH problem is solved by dividing into three subproblems, two of which are shown to be NP-hard. Several exact and approximation algorithms are proposed to solve these subproblems. We describe a framework which integrates these algorithms and develop a program called HapTagger for finding tag SNPs. HapTagger is compared with existing methods as well as the official tagging tool (called Haploview) of the International HapMap project using a variety of real data sets. Our theoretical analysis and experimental results indicate that HapTagger consistently identifies a smaller set of tag SNPs and runs much faster than existing methods. HapTagger avoids the need of incorporating a linkage disequilibrium statistic and thus significantly improves the computational efficiency. We also present an algorithm (specific to HapTagger) for reconstructing alleles of untyped SNPs. It is worth mentioning that these predictive haplotypes selected by HapTagger can be used as signatures of recent positive selection or co-evolution. HapTagger is available at http://www.csie.ntu.edu.tw/~kmchao/tools/HapTagger/. © 2008 Elsevier Inc. All rights reserved. |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-55549139479&doi=10.1016%2fj.jbi.2008.04.003&partnerID=40&md5=82ea07cb257b257c2c422d294b9e3b56 http://scholars.lib.ntu.edu.tw/handle/123456789/339644 |
ISSN: | 15320464 | DOI: | 10.1016/j.jbi.2008.04.003 |
顯示於: | 生醫電子與資訊學研究所 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。