Improved algorithms for group testing with inhibitors

Recent biological applications motivate a new group testing model where in addition to the category of the positive samples and the one of the negative samples, there is a third class of samples called inhibitors. 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 samples, respectively. Farach et al. (1997), who introduced this model, have 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 number of tests required to find the p positives by uncovering a relation between this group testing problem and cover-free families. We also provide efficient deterministic algorithms to find the positive samples. (C) 1998 Elsevier Science B.V. All rights reserved.