Error-tolerant pooling designs with inhibitors

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.

Group Testing with Multiple Inhibitor Sets and Error-Tolerant and Its Decoding Algorithms

In this article, we advance a new group testing model [Formula: see text] with multiple inhibitor sets and error-tolerant and propose decoding algorithms for it to identify all its positives by using [Formula: see text]-disjunct matrix. The decoding complexity for it is [Formula: see text], where [Formula: see text]. Moreover, we extend this new group testing to threshold group testing and give the threshold group testing model [Formula: see text] with multiple inhibitor sets and error-tolerant. By using [Formula: see text]-disjunct matrix, we propose its decoding algorithms for gap g = 0 and g > 0, respectively. Finally, we point out that the new group testing is the natural generalization for the clone model.

Nonadaptive algorithms for threshold group testing with inhibitors and error-tolerance

A group test gives a positive (negative) outcome if it contains at least u (at most l) positive items, and an arbitrary outcome if the number of positive items is between thresholds l and u. This problem introduced by Damaschke is called threshold group testing. It is a generalization of classical group testing. Chen and Fu extended this problem to the error-tolerant version and first proposed efficient nonadaptive algorithms. In this article, we extend threshold group testing to the k-inhibitors model in which a test has a positive outcome if it contains at least u positives and at most k-1 inhibitors. By using (d + k - l, u; 2e + 1]-disjunct matrix we provide nonadaptive algorithms for the threshold group testing model with k-inhibitors and at most e-erroneous outcomes. The decoding complexity is O(n(u+k) log n) for fixed parameters (d, u, l, k, e).

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.

Identification and classification problems on pooling designs for inhibitor models

Pooling designs are common tools to efficiently distinguish positive clones from negative clones in clone library screening. In some applications, there is a third type of clones called "inhibitors" whose effect is in a sense to obscure the positive clones in pools. Various inhibitor models have been proposed in the literature. We address the inhibitor problems of designing efficient nonadaptive procedures for both identification and classification problems, and improve previous results in three aspects: (1) The algorithm that is used to identify the positive clones works on a more general inhibitor model and has a polynomial-time decoding procedure that recovers the set of positives from the knowledge of the outcomes. (2) The algorithm that is used to classify all clones works in one-stage, i.e., all tests are arranged in advance without knowing the outcomes of other tests, along with a polynomial-time decoding procedure. (3) We extend our results to pooling designs on complexes where the property to be screened is defined on subsets of biological objects, instead of on individual ones.

Simulation Modeling of Pooling for Combinatorial Protein Engineering

Pooling in directed-evolution experiments will greatly increase the throughput of screening systems, but important parameters such as the number of good mutants created and the activity level increase of the good mutants will depend highly on the protein being engineered. The authors developed and validated a Monte Carlo simulation model of pooling that allows the testing of various scenarios in silico before starting experimentation. Using a simplified test system of 2 enzymes, ßgalactosidase (supermutant, or greatly improved enzyme) and •-glucuronidase (dud, or enzyme with ancestral level of activity), themodel accurately predicted the number of supermutants detected in experimentswithin a factor of 2. Additional simulations usingmore complex activity distributions showthe versatility of themodel. Pooling ismost suited to cases such as the directed evolution of newfunction in a protein, where the background level of activity is minimized, making it easier to detect small increases in activity level. Pooling ismost successful when a sensitive assay is employed. Using the modelwill increase the throughput of screening procedures for directed-evolution experiments and thus lead to speedier engineering of proteins.