COMBINATORIAL PROBLEMS ARISING FROMPOOLING DESIGNS FOR DNA LIBRARY SCREENING

Colbourn (1999) developed some strategy for nonadaptive group testing when the items are linearly ordered and the positive items form a consecutive subset of all items. Müller and Jimbo (2004) improved his strategy by introducing the con-cept of 2-consecutive positive detectable matrices (2CPD-matrix) requiring that all columns and bitwise OR-sum of each two consecutive columns are pairwise distinct. Such a matrix is called maximal if it has a maximal pos-sible number of columns with respect to some obvious constraints. Using a recursive construction they proved the existence of maximal 2CPD-matrices for any column size m ∈ N except for the case m = 3. Moreover, maximal 2CPD-matrices such that each column is of some fixed constant weight are constructed. This leads to pooling designs, where each item appears in the same number of pools and all pools are of the same size. Secondly, we investigate 2CPD-matrices of some constant column weight τ ∈ N. We give some recursive construction of such matrices hav