Identification and classification problems on pooling designs for inhibitor models

Group Testing with Blocks of Positives and Inhibitors

The main goal of group testing is to identify a small number of specific items among a large population of items. In this paper, we consider specific items as positives and inhibitors and non-specific items as negatives. In particular, we consider a novel model called group testing with blocks of positives and inhibitors. A test on a subset of items is positive if the subset contains at least one positive and does not contain any inhibitors, and it is negative otherwise. In this model, the input items are linearly ordered, and the positives and inhibitors are subsets of small blocks (at unknown locations) of consecutive items over that order. We also consider two specific instantiations of this model. The first instantiation is that model that contains a single block of consecutive items consisting of exactly known numbers of positives and inhibitors. The second instantiation is the model that contains a single block of consecutive items containing known numbers of positives and inhibitors. Our contribution is to propose efficient encoding and decoding schemes such that the numbers of tests used to identify only positives or both positives and inhibitors are less than the ones in the state-of-the-art schemes. Moreover, the decoding times mostly scale to the numbers of tests that are significantly smaller than the state-of-the-art ones, which scale to both the number of tests and the number of items.

Pooled screening for synergistic interactions subject to blocking and noise

The complex molecular networks in the cell can give rise to surprising interactions: gene deletions that are synthetically lethal, gene overexpressions that promote stemness or differentiation, synergistic drug interactions that heighten potency. Yet, the number of actual interactions is dwarfed by the number of potential interactions, and discovering them remains a major problem. Pooled screening, in which multiple factors are simultaneously tested for possible interactions, has the potential to increase the efficiency of searching for interactions among a large set of factors. However, pooling also carries with it the risk of masking genuine interactions due to antagonistic influence from other factors in the pool. Here, we explore several theoretical models of pooled screening, allowing for synergy and antagonism between factors, noisy measurements, and other forms of uncertainty. We investigate randomized sequential designs, deriving formulae for the expected number of tests that need to be performed to discover a synergistic interaction, and the optimal size of pools to test. We find that even in the presence of significant antagonistic interactions and testing noise, randomized pooled designs can significantly outperform exhaustive testing of all possible combinations. We also find that testing noise does not affect optimal pool size, and that mitigating noise by a selective approach to retesting outperforms naive replication of all tests. Finally, we show that a Bayesian approach can be used to handle uncertainty in problem parameters, such as the extent of synergistic and antagonistic interactions, resulting in schedules for adapting pool size during the course of testing.

Threshold group testing on inhibitor model

In classical group testing, one is given a population [Formula: see text] and an unknown subset [Formula: see text] of positive items, and the goal is to determine D by testing subsets of [Formula: see text]. Threshold group testing is a generalization of classical group testing, where the outcome of a group test is determined by the number of positive items in the test. In group testing on inhibitor model, inhibitors are the third type of item that dictate the test outcome to be negative regardless of how many positives are in the test. The threshold group testing on k-inhibitor model is a natural combination of threshold group testing and inhibitor model. In this article, we provide nonadaptive algorithms to conquer the threshold group testing on k-inhibitor model where error-tolerance is considered. Furthermore, we provide a two-stage algorithm to identify all inhibitors and find a g-approximate set.

An almost optimal algorithm for generalized threshold group testing with inhibitors

Group testing is a search paradigm where one is given a population S of n elements and an P is a subset of S defective elements and the goal is to determine P by performing tests on subsets of S. In classical group testing a test on a subset Q is a subset of S receives a YES response if [formula: see text] ≥ 1, and a NO response otherwise. In group testing with inhibitors (GTI), identifying the defective items is more difficult due to the presence of elements called inhibitors that interfere with the queries so that the answer to a query is YES if and only if the queried group contains at least one defective item and no inhibitor. In the present article, we consider a new generalization of the GTI model in which there are two unknown thresholds h and g and the response to a test is YES both in the case when the queried subset contains at least one defective item and less than h inhibitors, and in the case when the queried subset contains at least g defective items. Moreover, our search model assumes that no knowledge on the number |P| of defective items is given. We derive lower bounds on the minimum number of tests required to determine the defective items under this model and present an algorithm that uses an almost optimal number of tests.