Non-adaptive group testing in the presence of errors (Q1281776)

In the general group testing problem, the task is to determine the set of distinguished objects in a collection of objects by performing tests on subsets subsets (pools) of the collection. The objective of the group testing problem is to minimize the total worst-case (combinatorial group testing) or average case (probabilistic group testing) cost of the tests. The aim of the present paper is to show how the methods for constructing pooling designs can be used for constructing error tolerant designs. The main contributions include a discussion of useful error models, a unified treatment of known pooling design construction methods, and a new and more general design evaluation methodology. Computable formulas for predicting the average performance are proposed in the presence of errors for pooling designs constructed by several methods, including deterministic and randomized constructions. The use of these formulas is illustrated by an example. The asymptotic behaviour of random \(k\)-sets designs is also discussed. It is shown that the parameters can be chosen to achieve optimal asymptotic behaviour to within a constant factor for reasonable error probabilites. The proposed approach is proved to be useful for evaluating the known options for the design of trivial two-stage pooling designs relevant to real screening problems.