Combinatorial problems arising from pooling designs for dna library screening

Abstract

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 concept 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 possible 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 having the maximal possible number of columns.
Thirdly, error correction capability of group testing procedures is essential in view of applications such as DNA library screening. We consider a error correcting 2CPD-matrices.