Bui Thach V, Echizen Isao, Kuribayashi Minoru, Kojima Tetsuya, Nguyen Thuc D
Department of Computer Science, National University of Singapore, Singapore 117417, Singapore.
National Institute of Informatics, Tokyo 101-8430, Japan.
Entropy (Basel). 2022 Oct 30;24(11):1562. doi: 10.3390/e24111562.
The main goal of group testing is to identify a small number of specific items among a large population of items. In this paper, we consider specific items as positives and inhibitors and non-specific items as negatives. In particular, we consider a novel model called . A test on a subset of items is positive if the subset contains at least one positive and does not contain any inhibitors, and it is negative otherwise. In this model, the input items are linearly ordered, and the positives and inhibitors are subsets of small blocks (at unknown locations) of consecutive items over that order. We also consider two specific instantiations of this model. The first instantiation is that model that contains a single block of consecutive items consisting of exactly known numbers of positives and inhibitors. The second instantiation is the model that contains a single block of consecutive items containing known numbers of positives and inhibitors. Our contribution is to propose efficient encoding and decoding schemes such that the numbers of tests used to identify only positives or both positives and inhibitors are less than the ones in the state-of-the-art schemes. Moreover, the decoding times mostly scale to the numbers of tests that are significantly smaller than the state-of-the-art ones, which scale to both the number of tests and the number of items.
分组测试的主要目标是在大量物品中识别出少量特定物品。在本文中，我们将特定物品视为阳性和抑制剂，非特定物品视为阴性。特别地，我们考虑一种名为 的新型模型。如果一个物品子集包含至少一个阳性且不包含任何抑制剂，则对该子集的测试为阳性，否则为阴性。在这个模型中，输入物品是线性排序的，阳性和抑制剂是该顺序上连续物品的小片段（位置未知）的子集。我们还考虑了该模型的两种具体实例。第一种实例是包含一个连续物品块的模型，该块由确切已知数量的阳性和抑制剂组成。第二种实例是包含一个连续物品块的模型，该块包含已知数量的阳性和抑制剂。我们的贡献是提出高效的编码和解码方案，使得用于仅识别阳性或同时识别阳性和抑制剂的测试数量少于现有技术方案中的数量。此外，解码时间大多与测试数量成比例，而测试数量明显小于现有技术方案中的数量，现有技术方案的测试数量与测试数量和物品数量都成比例。
