DIMACS Series in Discrete Mathematics and Theoretical Computer Science A Survey on Combinatorial Group Testing Algorithms with Applications to DNA Library Screening
---
paper_title: A common language for physical mapping of the human genome

paper_content:

In a report issued in January 1988, the National Research ::: Council (NRC) Committee on the Mapping and Sequencing ::: of the Human Genome, on which the present authors ::: served, recommended a staged mapping and sequencing project ::: with early emphases on physical mapping of human DNA, mapping and sequencing of the genomes of model organisms, and the development of sequencing technology (1). As the Committee's recommendations on physical mapping are beginning to be implemented on a substantial scale, it is timely to review these recommendations in the light of recent technical advances. In particular, the polymerase chain reaction (PCR) (2), a method that has only come ::: into widespread use during the past 2 years, seems to us to offer a path toward a physical map that largely circumvents two problems that were prominent in the NRC Committee's discussions. One of these was the difficulty of merging mapping data gathered by diverse methods in different laboratories into a consensus physical map. The second was the logistics and expense of managing the huge collections ::: of cloned segments on which the mapping data would depend ::: almost absolutely.
---
paper_title: Combinatorial Group Testing and Its Applications

paper_content:

Group testing was first proposed for blood tests, but soon found its way to many industrial applications. Combinatorial group testing studies the combinatorial aspect of the problem and is particularly related to many topics in combinatorics, computer science and operations research. Recently, the idea of combinatorial group testing has been applied to experimental designs, coding, multiaccess computer communication, done library screening and other fields. This book attempts to cover the theory and applications of combinatorial group testing in one place.
---
paper_title: Optimal Pooling Designs with Error Detection

paper_content:

Consider a collection of objects, some of which may be `bad', and a test which determines whether or not a given sub-collection contains no bad objects. The non-adaptive pooling (or group testing) problem involves identifying the bad objects using the least number of tests applied in parallel. The `hypergeometric' case occurs when an upper bound on the number of bad objects is known {\em a priori}. Here, practical considerations lead us to impose the additional requirement of {\em a posteriori} confirmation that the bound is satisfied. A generalization of the problem in which occasional errors in the test outcomes can occur is also considered. Optimal solutions to the general problem are shown to be equivalent to maximum-size collections of subsets of a finite set satisfying a union condition which generalizes that considered by Erd\"os \etal \cite{erd}. Lower bounds on the number of tests required are derived when the number of bad objects is believed to be either 1 or 2. Steiner systems are shown to be optimal solutions in some cases.
---
paper_title: Probabilistic nonadaptive group testing in the presence of errors and DNA library screening

paper_content:

We use the subset containment relation to construct a probabilistic nonadaptive group testing design and decoding algorithm that, in the presence of testing errors, identifies many positives in a population. We give a lower bound for the expected portion of positives identified as a function of an upper bound on the number of testing errors.
---

Title: DIMACS Series in Discrete Mathematics and Theoretical Computer Science A Survey on Combinatorial Group Testing Algorithms with Applications to DNA Library Screening

Section 1: Introduction
Description 1: Write about the basic problem of DNA library screening, its relation to group testing, different types of group testing algorithms, and previous surveys in the context.

Section 2: Preliminaries
Description 2: Define basic definitions and notations needed for the paper. Provide a taxonomy of non-adaptive group testing algorithms that guide the organization of later sections.

Section 3: Deterministic Algorithms
Description 3: Discuss the deterministic algorithms for group testing, including key constructions and important results.

Section 4: A General Perspective on Constructing Deterministic Pooling Designs
Description 4: Provide a new perspective on constructing a class of deterministic pooling designs, and introduce several open problems that arise from this perspective.

Section 5: Random Algorithms
Description 5: Present random algorithms used in group testing, discuss their key features and performance bounds.

Section 6: Error Tolerance Group Testing Algorithms
Description 6: Introduce and discuss group testing algorithms that incorporate error tolerance, including notable constructions and results.

Section 7: Conclusions
Description 7: Summarize the main contributions of the paper, discuss open questions, and suggest directions for future research.