Adaptive group testing for consecutive positives Original Research Article

Motivated from an application to DNA library screening, Balding and Torney [The design of pooling experiments for screening a clone map, Fungal Genet. Biol. 21 (1997) 302–307] and Colbourn [Group testing for consecutive positives, Ann. Combin. 3 (1999) 37–41] studied the following group testing for consecutive positives. Suppose image is a linearly ordered set in which each item has a positive or negative state, and there are at most d positive items, forming a consecutive set under the order image. The object is to determine the set of positive items by means of group testing. To do this, we choose an arbitrary subset image called a pool, the outcome is positive when there is at least one positive item in this pool, and negative otherwise. Group testing is the processing of selecting pools and testing, to determine exactly which items are positive. This paper considers adaptive group testing by which each pool is examined before the next pool is selected. The minimum number of tests needed to determine the positives for at most d consecutive positive in a linearly ordered set of n items is denoted by image. Improving Colbournʹs bounds of image where c is a constant, we prove that image for image and image. Finally, we prove that image for image and image for image. We conjecture that the equality holds for a general image.