Adaptive Graph-Constrained Group Testing
Adaptive Graph-Constrained Group Testing
复制标题
DOI：
10.1109/tsp.2021.3137026
复制
发表时间：
2022-01-01
影响因子：
5.4
通讯作者：
Mitra，Urbashi
中科院分区：
文献类型：
--
作者：
Sihag，Saurabh;Tajer，Ali;Mitra，Urbashi
本文研究了自适应分组测试的问题，该测试从一个具有一定规模的总体中分离出个缺陷项。存在限制或偏好，这些限制或偏好决定了如何将项目合并用于测试。一个图形化的模型形式化的池的限制和偏好。这样的图约束组测试研究在三个设置：人口与缺陷，人口面临的潜在存在的抑制剂，和人口与社区结构。为每种设置提供了自适应组测试框架。在没有抑制因子的种群中，现有的非自适应框架可以通过测试次数完美地隔离缺陷项，其中测试次数是在底层图上随机游走的混合时间。本文提供了一个两阶段的框架，可以完美地隔离到缺陷项目的正则图使用测试的数量，从而实现了一个因子的近似增益的非自适应框架。这两个阶段的框架的原则扩展到社区结构的图和图的抑制剂项目。特别是，当图中存在抑制剂时，提出了一个四阶段的组测试框架。结果表明，在全连通图的情况下，测试足以隔离缺陷项。这符合相应的必要条件的测试规模。自适应graphconstrained组测试框架也进行了实证评估。
This paper considers the problem of adaptive group testing for isolating up todefective items from a population of size. There exist restrictions or preferences which determine how the items can be pooled for testing. A graphical model formalizes the pooling restrictions and preferences. Such graph-constrained group testing is investigated in three settings: populations with defectives, populations facing the potential presence of inhibitors, and populations with community structures. Adaptive group testing frameworks are provided for each setting. In populations without inhibitors, existing non adaptive frameworks can isolate the defective items perfectly withnumber of tests, where is the-mixing time of a random walk over the underlying graph. This paper provides a two-stage framework that can perfectly isolate up todefective items for a regular graph usingnumber of tests, thus achieving an approximate gain of a factor ofover the non-adaptive frameworks. This twostage framework's principles are extended to community-structured graphs and graphs with up toinhibitor items. In particular, when inhibitors are present in the graph, a four-stage group testing framework is proposed. The results show that in the regimefor a fully connected graph,tests are sufficient for isolating the defective items. This matches the corresponding necessary condition on tests which scales. The adaptive graphconstrained group testing framework is also empirically evaluated.