標題: An Almost Optimal Algorithm for Generalized Threshold Group Testing with Inhibitors
作者: Chen, Hong-Bin
De Bonis, Annalisa
應用數學系
Department of Applied Mathematics
關鍵字: algorithms;group testing;inhibitors;superimposed codes
公開日期: 1-Jun-2011
摘要: Group testing is a search paradigm where one is given a population S of n elements and an unknown subset P subset of S of defective elements and the goal is to determine P by performing tests on subsets of S. In classical group testing a test on a subset Q subset of S receives a YES response if vertical bar Q boolean AND P vertical bar >= 1, and a NO response otherwise. In group testing with inhibitors (GTI), identifying the defective items is more difficult due to the presence of elements called inhibitors that interfere with the queries so that the answer to a query is YES if and only if the queried group contains at least one defective item and no inhibitor. In the present article, we consider a new generalization of the GTI model in which there are two unknown thresholds h and g and the response to a test is YES both in the case when the queried subset contains at least one defective item and less than h inhibitors, and in the case when the queried subset contains at least g defective items. Moreover, our search model assumes that no knowledge on the number vertical bar P vertical bar of defective items is given. We derive lower bounds on the minimum number of tests required to determine the defective items under this model and present an algorithm that uses an almost optimal number of tests.
URI: http://dx.doi.org/10.1089/cmb.2010.0030
http://hdl.handle.net/11536/23345
ISSN: 1066-5277
DOI: 10.1089/cmb.2010.0030
期刊: JOURNAL OF COMPUTATIONAL BIOLOGY
Volume: 18
Issue: 6
起始頁: 851
結束頁: 864
Appears in Collections:Articles


Files in This Item:

  1. 000291016200007.pdf