Group Testing With Probabilistic Tests: Theory, Design and Application

DOI10.1109/TIT.2011.2148691MaRDI QIDQ5272323zbMATH OpenWikidataFDO

Authors Mahdi Cheraghchi, Ali Hormati, Amin Karbasi, Martin Vetterli

Publication date 12 July 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1009.3186

Mathematics Subject Classification ID

Optimal statistical designs (62K05) Applications of statistics to biology and medical sciences; meta analysis (62P10) Epidemiology (92D30)

Abstract: Identification of defective members of large populations has been widely studied in the statistics community under the name of group testing. It involves grouping subsets of items into different pools and detecting defective members based on the set of test results obtained for each pool. In a classical noiseless group testing setup, it is assumed that the sampling procedure is fully known to the reconstruction algorithm, in the sense that the existence of a defective member in a pool results in the test outcome of that pool to be positive. However, this may not be always a valid assumption in some cases of interest. In particular, we consider the case where the defective items in a pool can become independently inactive with a certain probability. Hence, one may obtain a negative test result in a pool despite containing some defective items. As a result, any sampling and reconstruction method should be able to cope with two different types of uncertainty, i.e., the unknown set of defective items and the partially unknown, probabilistic testing procedure. In this work, motivated by the application of detecting infected people in viral epidemics, we design non-adaptive sampling procedures that allow successful identification of the defective items through a set of probabilistic tests. Our design requires only a small number of tests to single out the defective items. In particular, for a population of size $N$ and at most $K$ defective items with activation probability $p$, our results show that $M=O(K^{2}log(N/K)/p^3)$ tests is sufficient if the sampling procedure should work for all possible sets of defective items, while $M=O(Klog(N)/p^3)$ tests is enough to be successful for any single set of defective items. Moreover, we show that the defective members can be recovered using a simple reconstruction algorithm with complexity of $O(MN)$.

Cited in

(16)

• Smart elements in combinatorial group testing problems
• The optimal procedures for quantitative group testing
• On the construction of unbiased estimators for the group testing problem
• A recovery algorithm and pooling designs for one-stage noisy group testing under the probabilistic framework
• Applications of bulk queues to group testing models with incomplete identification
• Multinomial group testing models with incomplete identification
• D-optimality of Group Testing for Estimation of Correlated Rare Diseases with Misclassification
• Deterministic versus randomized adaptive test cover
• Generalized Binary Binomial Group Testing
• Cutoff Point and Monotonicity Properties for Multinomial Group Testing
• Optimizing Nonadaptive Group Tests for Objects with Heterogeneous Priors
• Optimal Group Testing Designs for Estimating Prevalence with Uncertain Testing Errors
• Performance of Group Testing Algorithms With Near-Constant Tests Per Item
• Threshold and Majority Group Testing
• Static Risk-Based Group Testing Schemes Under Imperfectly Observable Risk
• Optimal Dorfman group testing for symmetric distributions

This page was built for publication: Group Testing With Probabilistic Tests: Theory, Design and Application

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5272323)