New combinatorial structures with applications to efficient group testing with inhibitors |
| |
Authors: | Annalisa De Bonis |
| |
Institution: | (1) Dipartimento di Informatica ed Applicazioni, Università di Salerno, 84084 Fisciano, (SA), Italy |
| |
Abstract: | Group testing with inhibitors (GTI) is a variant of classical group testing where in addition to positive items and negative items, there is a third class
of items called inhibitors. In this model the response to a test is YES if and only if the tested group of items contains at least one positive item
and no inhibitor. This model of group testing has been introduced by Farach et al. (Proceedings of compression and complexity
of sequences, pp 357–367, 1997) for applications in the field of molecular biology. In this paper we investigate the GTI problem both in the case when the
exact number of positive items is given, and in the case when the number of positives is not given but we are provided with
an upper bound on it. For the latter case, we present a lower bound on the number of tests required to determine the positive
items in a completely nonadaptive fashion. Also under the same hypothesis, we derive an improved lower bound on the number
of tests required by any algorithm (using any number of stages) for the GTI problem.
As far as it concerns the case when the exact number of positives is known, we give an efficient trivial two-stage algorithm.
Instrumental to our results are new combinatorial structures introduced in this paper. In particular we introduce generalized
versions of the well known superimposed codes (Du, D.Z., Hwang, F.K. in Pooling designs and nonadaptive group testing, 2006; Dyachkov, A.G., Rykov, V.V. in Probl. Control Inf. Theory 12:7–13, 1983; Dyachkov, A.G., et al. in J. Comb. Theory Ser. A 99:195–218, 2002; Kautz, W.H., Singleton, R.R. in IEEE Trans. Inf. Theory 10:363–377, 1964) and selectors (Clementi, A.E.F, et al. in Proceedings of symposium on discrete algorithms, pp. 709–718, 2001; De Bonis, A., et al. in SIAM J Comput. 34(5):1253–1270, 2005; Indyk, P. in Proceedings of symposium on discrete algorithms, pp. 697–704, 2002) that we believe to be of independent interest. |
| |
Keywords: | Group testing algorithms Superimposed codes Selectors Pooling designs Computational molecular biology |
本文献已被 SpringerLink 等数据库收录! |
|