Nonadaptive algorithms for threshold group testing

Abstract

Threshold group testing first proposed by Damaschke is a generalization of classic group testing. Specifically, a group test is positive (negative) if it contains at least u (at most 1) positives, and if the number of positives is between I and u, the test outcome is arbitrary. Although sequential group testing algorithms have been proposed, it is unknown whether an efficient nonadaptive algorithm exists. In this paper, we give an affirmative answer to this problem by providing efficient nonadaptive algorithms for the threshold model. The key observation is that disjunct matrices, a standard tool for group testing designs, also work in this threshold model. This paper improves and extends previous results in three ways: 1. The algorithms we propose work in one stage, which saves time for testing. 2. The test complexity is lower than previous results, at least for the number of elements which need to be tested is sufficiently large. 3. A limited number of erroneous test outcomes are allowed. (C) 2008 Elsevier B.V. All rights reserved.