Non-adaptive group testing in the presence of errors

In group testing, the task is to determine the distinguished members of a s et of objects O by asking subset queries of the form "does the set Q subset of or equal to O contain a distinguished object?" In biological applicatio ns of group testing, the task is to repeatedly screen a library of objects for those which are positive for a probe. The subset queries consist of scr eening a pooled subset of the objects with the probe. This procedure has be come an important component of the experimental methods used for the compil ation of physical maps of chromosomes and other genetic material. For many screening applications, it is most cost-effective to ask many subs et queries in parallel. This leads to non-adaptive group testing problems. An important aspect of most screening environments is that the screening re sults are far from reliable. In this report we discuss some of the error mo dels that can be used and show how they affect the design of non-adaptive s creening experiments. We give a unified treatment of the known methods for constructing pooling designs, provide explicit formulas for their performan ce under different error assumptions and discuss the asymptotic performance of random designs. 1998 Published by Elsevier Science B.V. All rights rese rved.