Grid-Block Designs With Applications To DNA Library Screening

Combinatorial group testing is a basic tool in conducting experiments of testswhich can be applied to molecular biology. For example, in DNA library screening,group testing is used to select positive clones efficiently. A clone is called positiveif it contains some given probes. Grid-block design is derived from it and becomesan important tool in DNA library screening. The notion of grid-block design wasfirst introduced by Fu, Hwang, Jimbo, Mutoh and Shiue. Each r×c grid-block is anr×c grid. We view each row and each column in each grid as a test respectively,and we put each clone on each grid point. So the grid-block design decreases highlythe number of the tests and also saves much necessary time. It is so efficient andconvenient in DNA library screening that more and more researchers are interestedin it and extensive researches have been done on it.In this thesis, we mainly use methods in combinatorial design theory to studyr×c gird-block designs when (r,c)∈{(2, 5), (3, 4), (4, 4)}. The main results aresummarized as follows:1. For the case of r=2 and c=5, according to the necessary conditions for the ex-istence of r×c grid-block design, we get the necessary condition of D_2×5(K_v)(v denotes the number of clones which are to be tested) is v≡1 (mod 25).In order to prove the necessary condition is also sufficient. We first find somecrucial small grid-block designs, which are used in proof, by mainly using dif-ference method in design theory. Then, by virtue of these small designs andthe methods in the recursive construction (mainly using Wilson's fundamen-tal construction), we prove that a D_2×5(K_v) exists whenever v≡1 (mod 25). Thus, we can get a conclusion: a D_2×5(K_v) exists if and only if v≡1 (mod 25).2. For the case of r=4 and c=4, the necessary condition for the existence ofD_4×4(K_v) is v≡1 (mod 96). To prove the existence of D_4×4(K_v), similarto (1), we first find some crucial small grid-block designs using backtrackingalgorithms. Then, we use these small designs together with recursive construc-tions in design theory to finish the proof. So we get the result that a D_4×4(K_v)exists if and only if v≡1 (mod 96).3. For the case of r=3 and c=4, we also first obtain the necessary conditions forthe existence of D_3×4(K_v). They are v≡1, 16, 21, 36 (mod 60). Because theconditions have four cases, we discuss in steps. Similar to (1) and (2), weprove the necessary conditions v≡1, 21 (mod 60) are sufficient. For the othercases of D_3×4(K_v), that is, for v≡16, 36 (mod 60), we give the constructionmethod about how to prove the existence of D_3×4(K_v). In this method, weneed some crucial small ingredient designs. They are D_3×4(K_v), where v∈{36, 76, 30⁵, 30⁶, 30⁵15¹, 30⁶15¹}. For these values of v, we prove the existenceof D_3×4(K_v) except v=30⁵15¹, which is still under investigation. Especial, forv=36 and 76, the methods to construct D_3×4(K₃₆) and D_3×4(K₇₆) are differentfrom the methods used above. The above small designs are constructed byusing complete orbit and abelian group while the D_3×4(K₃₆) is constructed byusing short orbit and the D_3×4(K₇₆) is constructed by using short orbit andnonabelian group. This is an innovated point in this thesis.The above three points are the main results in this thesis. I think some resultsmay be improved. For example, according to the algorithm and structure we selected,the existence of D_3×4(K_v) when v=30⁵15¹ is still under search. Maybe, we canimprove our algorithm and make it much more efficient or we can take other delicatestructures to prove the existence. Of course, we can also use other methods to provethe necessary conditions v≡16, 36 (mod 60) are sufficient. Finally, in order to make grid-block much more efficient and convenient in DNA library screening, we couldconstruct grid-block of large scale. That means we construct grid-block with large rand c. Of course, with the large scale, the proof of existence will also become muchmore difficult. That needs further study and exploration.