Efficient algorithms for genome-wide tagSNP selection across populations via the linkage disequilibrium criterion.
Efficient algorithms for genome-wide tagSNP selection across populations via the linkage disequilibrium criterion.
复制标题
DOI：
10.1142/9781860948732_0011
复制
发表时间：
2007-01-01
期刊：
影响因子：
--
通讯作者：
Jiang, Tao
中科院分区：
文献类型：
--
作者：
Liu, Lan;Wu, Yonghui;Jiang, Tao
本文利用成对r（2）连锁不平衡准则研究了多群体tagSNP的选择问题。我们提出了一种新的组合优化模型的tagSNP选择问题，称为最小共同tagSNP选择（MCTS）的问题，并提出有效的解决方案MCTS。我们的方法由三个主要步骤组成，包括（i）将SNP标记划分为小的不相交的组件，（ii）应用一些数据简化规则来简化问题，以及（iii）应用快速贪婪算法或拉格朗日松弛算法来解决剩余的（一般）MCTS。这些算法还提供了标记的下限（即所需tagSNP的最小数量）。下限允许我们评估我们的解决方案离最优值有多远。据我们所知，这是第一次在文献中讨论标记下界。我们评估我们的算法的性能真实的HapMap数据全基因组标记。实验表明，我们的算法比现有的单种群标记程序，如FESTA，LD-Select和多种群标记方法MultiPop-TagSelect快3到4个数量级。我们的方法还大大减少了所需的tagSNP相比，LD-Select对一个单一的人口和MultiPop-TagSelect对多个人口。此外，我们的算法所选择的tagSNPs的数量几乎是最优的，因为它们非常接近我们的方法所获得的相应的下限。
In this paper, we study the tagSNP selection problem on multiple populations using the pairwise r(2) linkage disequilibrium criterion. We propose a novel combinatorial optimization model for the tagSNP selection problem, called the minimum common tagSNP selection (MCTS) problem, and present efficient solutions for MCTS. Our approach consists of three main steps including (i) partitioning the SNP markers into small disjoint components, (ii) applying some data reduction rules to simplify the problem, and (iii) applying either a fast greedy algorithm or a Lagrangian relaxation algorithm to solve the remaining (general) MCTS. These algorithms also provide lower bounds on tagging (i.e. the minimum number of tagSNPs needed). The lower bounds allow us to evaluate how far our solution is from the optimum. To the best of our knowledge, it is the first time tagging lower bounds are discussed in the literature. We assess the performance of our algorithms on real HapMap data for genome-wide tagging. The experiments demonstrate that our algorithms run 3 to 4 orders of magnitude faster than the existing single-population tagging programs like FESTA, LD-Select and the multiple-population tagging method MultiPop-TagSelect. Our method also greatly reduces the required tagSNPs compared to LD-Select on a single population and MultiPop-TagSelect on multiple populations. Moreover, the numbers of tagSNPs selected by our algorithms are almost optimal since they are very close to the corresponding lower bounds obtained by our method.