Pooling design algorithms based on group testing theory

There is a fundamental information processing problem for molecular biology: how to efficiently determine highly complex key structural properties of the systems. These key structural properties, for example DNA sequencing, are determined via testing, known as pooling design, and concern with efficiency highlights three aspects of these tests. All things being equal we would like to (1) use the fewest number of tests, (2) keep each test as short in duration as possible and (3) insure that experimental error is minimized. Not surprisingly, it is usually impossible to satisfy all three of these requirements at once.; However, there is a well-established set of techniques used in various non-biological settings that can help us find highly efficient ways of performing these tests. It is called combinatorial group testing. Various techniques from group testing have already proven effective when applied to molecular biology. This thesis further develops the application of group testing methods to some important open problems in pooling designs in molecular biology. The first application is a novel decoding algorithm identifying all positive clones in the presence of both inhibitors and experimental errors. The second uses group testing to find a polynomial-time approximation for a minimization problem for non-unique probe selection. Lastly, we present an improved construction for a pooling design that reduces the number of tests for DNA library screening.