  This paper deals with an abstraction of a unified problem of drug discovery
and pathogen identification. Pathogen identification involves identification of
disease-causing biomolecules. Drug discovery involves finding chemical
compounds, called lead compounds, that bind to pathogenic proteins and
eventually inhibit the function of the protein. In this paper, the lead
compounds are abstracted as inhibitors, pathogenic proteins as defectives, and
the mixture of "ineffective" chemical compounds and non-pathogenic proteins as
normal items. A defective could be immune to the presence of an inhibitor in a
test. So, a test containing a defective is positive iff it does not contain its
"associated" inhibitor. The goal of this paper is to identify the defectives,
inhibitors, and their "associations" with high probability, or in other words,
learn the Immune Defectives Graph (IDG) efficiently through group tests. We
propose a probabilistic non-adaptive pooling design, a probabilistic two-stage
adaptive pooling design and decoding algorithms for learning the IDG. For the
two-stage adaptive-pooling design, we show that the sample complexity of the
number of tests required to guarantee recovery of the inhibitors, defectives,
and their associations with high probability, i.e., the upper bound, exceeds
the proposed lower bound by a logarithmic multiplicative factor in the number
of items. For the non-adaptive pooling design too, we show that the upper bound
exceeds the proposed lower bound by at most a logarithmic multiplicative factor
in the number of items.
