IMPROVED ALGORITHMS FOR GROUP-TESTING WITH INHIBITORS

Recent biological applications motivate a new group testing model wher e in addition to the category of the positive samples and the one of t he negative samples, there is a third class of samples called inhibito rs. The presence of positives in a test set cannot be detected if the test set contains one or more inhibitors. Let n be the total number of samples and p and r denote the number of positive and inhibitor sampl es, respectively. Farach et al. (1997), who introduced this model, hav e given a lower bound of Omega (log(((n)(p))((n-p)(r)))) on the number of tests required to find the p positives. They have also described a randomized algorithm to find the p positives which achieve this bound when p + r << n. In this paper, we give a better lower bound on the n umber of tests required to find the p positives by uncovering a relati on between this group testing problem and cover-free families. We also provide efficient deterministic algorithms to find the positive sampl es. (C) 1998 Elsevier Science B.V. All rights reserved.