FU Berlin, Fachbereich Mathematik und Informatik, Institut für Informatik
Weakly Adaptive Group Testing
Leszek Gasieniec, University of Liverpool (joint work with A. De Bonis, U. Vaccaro & Qin Xin)
Group Testing refers to the situation in which one is given a set of objects
O an unknown subset P of O. The task is to determine the content of P by asking
queries of the type "does P intersect with Q?", where Q is also a subset of O.
Group testing is a basic search paradigm that occurs in a variety of situations
such as quality control in product testing, searching in storage systems,
multiple access communications, and software testing, among the others. Group
testing procedures have been recently applied in Computational Molecular Biology,
where it is used for screening library of clones with hybridisation probes and
sequencing by hybridisation.
Motivated by particular features of group testing algorithms used in biological
screening, we study the efficiency of group testing algorithms running in a
constant number of stages. Our results include:
* an optimal two-stage algorithm that uses a number of tests of the same order
as the information theoretic lower bound on the problem,
* efficient algorithms for the case in which there is a Bernoulli probability
distribution on the possible sets P,
* an optimal algorithm for the case in which the outcome of tests may be
unreliable because of the presence of "inhibitory" items in O.
Finally we present recent advances in a "group testing with gaps" which forms a
trade-off between the two extreme scenarios, i.e., a "group testing with
consecutive positives" and the general group testing problem.
We conclude with an investigation of some future work directions which
include large scale tests on a cluster of computers
where we can take advantage of the parallelism inherent in the data
structure we are using.
| [ home ] [ up ] | webmaster@inf.fu-berlin.de |