2-Stage Fault Tolerant Interval Group Testing
by
Ferdinando Cicalese
AG Genominformatik, Technical Faculty, Bielefeld University, Germany and Dipart. Informatica ed Applicazioni, University of Salerno, Italy
Coauthors: José Augusto Amgarten Quitzau

We study the following fault tolerant variant of the interval group testing model: Given four positive integers n, p, s, e, determine the minimum number of questions needed to identify a (possibly empty) subset P of {1, 2, ..., n} (with - P - not greater than p), under the following constraints. Questions have the form "Has P non-empty intersection with I?", where I can be any interval in the search space {1, 2, ..., n}. Questions are to be organized in s batches of non-adaptive questions (stages), i.e, questions in a given batch can be formulated relying only on the information gathered with the answers to the questions in the previous batches. Up to e of the answers can be erroneous or lies.

The study of interval group testing is motivated by several applications. remarkably, to the problem of identifying splice sites in a genome. In particular, such application motivates to focus algorithms that are fault tolerant to some degree and organize the questions in few stages, i.e., on the cases when s is small, typically not larger than 2. To the best of our knowledge, we are the first to consider fault tolerant strategies for interval group testing.

We completely characterize the fully non-adaptive situation and provide tight bounds for the case of two batch strategies. Our bounds only differ by a factor of √(11/10) for the case p=1 and at most 2 in the general case.

PDF

Date received: July 25, 2007