Selecting additional tag SNPs for tolerating missing data in genotyping
Selecting additional tag SNPs for tolerating missing data in genotyping
复制标题
DOI：
10.1186/1471-2105-6-263
复制
发表时间：
2005-11-01
影响因子：
3
通讯作者：
Chao, KM
中科院分区：
文献类型：
--
作者：
Huang, YT;Zhang, K;Chao, KM
背景：最近的研究表明，在人群中观察到的连锁不平衡模式具有块状结构，并且一小部分SNP（称为标签SNP）足以区分块中的每对单倍型模式。实际上，一些标签SNP可能会缺失，并且由于缺失数据引起的歧义，我们可能无法区分两个不同的单倍型。结果：我们发现存在一个SNP子集（称为鲁棒标签SNP），即使在某些SNP缺失时，它仍然可以区分所有不同的单倍型。寻找最小鲁棒标签 SNP 的问题被证明是 NP 困难的。为了有效地找到鲁棒的标签 SNP，我们提出了两种贪婪算法和一种线性规划松弛算法。实验结果表明：（1）这些算法找到的解非常接近最优解； (2)使用标签SNP节省的基因分型成本可高达80%； (3) 对额外的标签 SNP 进行基因分型以容忍缺失数据仍然具有成本效益。结论：如果我们无法避免缺失数据的发生，对稳健标签 SNP 进行基因分型比仅对最小标签 SNP 进行基因分型更实用。我们的理论分析和实验结果表明，我们的算法不仅性能高效，而且找到的解也接近最优解。
Background: Recent studies have shown that the patterns of linkage disequilibrium observed in human populations have a block-like structure, and a small subset of SNPs ( called tag SNPs) is sufficient to distinguish each pair of haplotype patterns in the block. In reality, some tag SNPs may be missing, and we may fail to distinguish two distinct haplotypes due to the ambiguity caused by missing data.Results: We show there exists a subset of SNPs ( referred to as robust tag SNPs) which can still distinguish all distinct haplotypes even when some SNPs are missing. The problem of finding minimum robust tag SNPs is shown to be NP-hard. To find robust tag SNPs efficiently, we propose two greedy algorithms and one linear programming relaxation algorithm. The experimental results indicate that ( 1) the solutions found by these algorithms are quite close to the optimal solution; ( 2) the genotyping cost saved by using tag SNPs can be as high as 80%; and ( 3) genotyping additional tag SNPs for tolerating missing data is still cost-effective.Conclusion: Genotyping robust tag SNPs is more practical than just genotyping the minimum tag SNPs if we can not avoid the occurrence of missing data. Our theoretical analysis and experimental results show that the performance of our algorithms is not only efficient but the solution found is also close to the optimal solution.