Interval group testing for consecutive positives

To identify splice sites in a genome, Cicalese et al. (2005) studied interval group testing where all items in the search space are linearly ordered and each of them is either positive or negative. The goal is to identify all positive ones by interval group tests, each asking a query of the type “does a set of consecutive items contain any positive one?” We complete the study of error-tolerant one- and two-stage approaches by dealing with some cases which have not been well studied. Motivated by applications to DNA sequencing, group testing for consecutive positives has been proposed by Balding and Torney (1997) and Colbourn (1999) where n items are linearly ordered and up to p positive items are consecutive in the order. Juan and Chang (2008) provided an optimal sequential algorithm that consists of interval group tests. In this paper, we study error-tolerant one- and two-stage interval group testing for consecutive positives. Based on some results in the literature, we derive optimal nonadaptive algorithms. For two-stage approach, the number of interval group tests used is asymptotically upper bounded by en which differs by a factor of e from the lower bound, where e is the number of errors allowed.