• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of Bioinformatics and Computational Biology >EFFECTIVE ALGORITHMS FOR TAG SNP SELECTION
【24h】

EFFECTIVE ALGORITHMS FOR TAG SNP SELECTION

机译：标签SNP选择的有效算法

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Single nucleotide polymorphisms (SNPs), due to their abundance and low mutation rate, are very useful genetic markers for genetic association studies. However, the current genotyping technology cannot afford to genotype all common SNPs in all the genes. By making use of linkage disequilibrium, we can reduce the experiment cost by genotyping a subset of SNPs, called Tag SNPs, which have a strong association with the ungenotyped SNPs, while are as independent from each other as possible. The problem of selecting Tag SNPs is NP-complete; when there are large number of SNPs, in order to avoid extremely long computational time, most of the existing Tag SNP selection methods first partition the SNPs into blocks based on certain block definitions, then Tag SNPs are selected in each block by brute-force search. The size of the Tag SNP set obtained in this way may usually be reduced further due to the inter-dependency among blocks. This paper proposes two algorithms, TSSA and TSSD, to tackle the block-independent Tag SNP selection problem. TSSA is based on A* search algorithm, and TSSD is a heuristic algorithm. Experiments show that TSSA can find the optimal solutions for medium-sized in reasonable time, while TSSD can handle very large problems and report approximate solutions very close to the optimal ones.
机译：由于其丰度和低突变率，单核苷酸多态性（SNP）是遗传关联研究的非常有用的遗传标记。然而，目前的基因分型技术不能在所有基因中基因型所有常见的SNP。通过利用连锁不平衡，我们可以通过基因分型SNP的子集来降低实验成本，称为标签SNP，其具有与未键入的SNP具有强烈关联的，同时尽可能独立。选择标签SNPS的问题是NP-Complete;当有大量的SNP时，为了避免极长的计算时间，大多数现有的标签SNP选择方法首先将SNPS基于某些块定义分区，然后通过Brute-Force搜索在每个块中选择标记SNPS 。由于块之间的依赖性，通常可以进一步减少以这种方式获得的标签SNP集的大小。本文提出了两个算法，TSSA和TSSD，解决了独立于块的标签SNP选择问题。 TSSA基于*搜索算法，TSSD是一种启发式算法。实验表明，TSSA可以在合理的时间内找到最佳解决方案，而TSSD可以处理非常大的问题，并报告非常接近最佳的解决方案。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号