An almost optimal algorithm for generalized threshold group testing with inhibitors

Theoretical Bounds on the Number of Tests in Noisy Threshold Group Testing Frameworks

We consider a variant of group testing (GT) models called noisy threshold group testing (NTGT), in which when there is more than one defective sample in a pool, its test result is positive. We deal with a variant model of GT where, as in the diagnosis of COVID-19 infection, if the virus concentration does not reach a threshold, not only do false positives and false negatives occur, but also unexpected measurement noise can reverse a correct result over the threshold to become incorrect. We aim to determine how many tests are needed to reconstruct a small set of defective samples in this kind of NTGT problem. To this end, we find the necessary and sufficient conditions for the number of tests required in order to reconstruct all defective samples. First, Fano’s inequality was used to derive a lower bound on the number of tests needed to meet the necessary condition. Second, an upper bound was found using a MAP decoding method that leads to giving the sufficient condition for reconstructing defective samples in the NTGT problem. As a result, we show that the necessary and sufficient conditions for the successful reconstruction of defective samples in NTGT coincide with each other. In addition, we show a trade-off between the defective rate of the samples and the density of the group matrix which is then used to construct an optimal NTGT framework.

Theoretical Bounds on Performance in Threshold Group Testing Schemes

A threshold group testing (TGT) scheme with lower and upper thresholds is a general model of group testing (GT) which identifies a small set of defective samples. In this paper, we consider the TGT scheme that require the minimum number of tests. We aim to find lower and upper bounds for finding a set of defective samples in a large population. The decoding for the TGT scheme is exploited by minimization of the Hamming weight in channel coding theory and the probability of error is also defined. Then, we derive a new upper bound on the probability of error and extend a lower bound from conventional one to the TGT scheme. We show that the upper and lower bounds well match with each other at the optimal density ratio of the group matrix. In addition, we conclude that when the gaps between the two thresholds in the TGT framework increase, the group matrix with a high density should be used to achieve optimal performance.

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.