The Parameterized Complexity of the Shared Center Problem
The Parameterized Complexity of the Shared Center Problem
复制标题
DOI：
10.1007/s00453-012-9730-7
复制
发表时间：
2012-07
期刊：
影响因子：
1.1
通讯作者：
Zhi-Zhong Chen;Wenji Ma;Lusheng Wang
中科院分区：
文献类型：
--
作者：
Zhi-Zhong Chen;Wenji Ma;Lusheng Wang
最近，共享中心（SC）问题被提出作为一种数学模型，用于使用已确认的单倍型数据库作为参考来推断给定个体组的等位基因共享状态。该问题被证明是NP完全问题，并为其最小化版本设计了比率2多项式时间逼近算法（称为最近共享中心（CSC）问题）。在本文中，我们考虑 SC 问题的参数化复杂性。首先，我们证明 SC 问题是 W[1]-hard，参数为 dandn，其中 dandna 分别是输入中的半径和（患病或正常）个体的数量。然后，我们提出了该问题的两种渐近最优参数化算法，并将其应用于连锁分析。
Recently, theshared center(SC) problem has been proposed as a mathematical model for inferring the allele-sharing status of a given set of individuals using a database of confirmed haplotypes as reference. The problem was proved to be NP-complete and a ratio-2 polynomial-time approximation algorithm was designed for its minimization version (called theclosest shared center(CSC) problem). In this paper, we consider the parameterized complexity of the SC problem. First, we show that the SC problem isW[1]-hard with parametersdandn, wheredandnare theradiusand the number of (diseased or normal) individuals in the input, respectively. Then, we present two asymptotically optimal parameterized algorithms for the problem and apply them to linkage analysis.