Abstract

DNA contains major information to control the development of any organism. This had been a distant dream until two restriction enzymes and DNA ligases were discovered in 1970s. This made it possible to manipulate DNA, create DNA Library and decode DNA. DNA Library Screening is very expensive since the number of defectives (probes) is very small when compared to the huge number of candidates (clones). It is a typical instance of group testing. Using d-disjunct matrices to construct non-adaptive pooling designs has been proved to be an efficient algorithm. Researchers have been trying different constructions by using different methods over the last two decades. There are two major problems in the previous works. The first is there is no general setting in pooling designs. The second one is there is no general procedure or tool to construct pooling designs. I propose a general setting in pooling design and a general procedure for constructing d-disjunct matrices by using the simplicial complex and graph property.

The interactions between proteins are important in many biological functions. I use a complete graph to describe the protein-protein interaction problem, however the algorithm is not that efficient. I then use a d-disjunct matrix to solve the protein-protein interaction problem, and proposed four constructions for d-disjunct matrix, two non-adaptive algorithms and a generalization.

Using non-unique probe brought a new challenge to the traditional pooling design. One positive outcome is a set of candidates rather than just one. The fundamental problem, that whether all viruses can be identified by using only non-unique probes, is solved in this dissertation. We found that all n viruses cannot be identified without using unique probes. Furthermore, for the considered n viruses, only n-2 viruses can be identified by using only non-unique probes. I conclude this dissertation with some useful conclusions on the computational complexity of pooling designs by reducing from the known NP problems.