Non-adaptive group testing in the presence of errors

AbstractIn group testing, the task is to determine the distinguished members of a set of objects O by asking subset queries of the form “does the set Q⊂-O contain a distinguished object?” In biological applications 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 screening a pooled subset of the objects with the probe. This procedure has become an important component of the experimental methods used for the compilation of physical maps of chromosomes and other genetic material.For many screening applications, it is most cost-effective to ask many subset queries in parallel. This leads to non-adaptive group testing problems. An important aspect of most screening environments is that the screening results are far from reliable. In this report we discuss some of the error models that can be used and show how they affect the design of non-adaptive screening experiments. We give a unified treatment of the known methods for constructing pooling designs, provide explicit formulas for their performance under different error assumptions and discuss the asymptotic performance of random designs