a recovery algorithm and pooling designs for one stage noisy group testing under the CORD-Papers-2021-10-25 (Version 1)

Title: A Recovery Algorithm and Pooling Designs for One-Stage Noisy Group Testing under the Probabilistic Framework
Abstract: Group testing saves time and resources by testing each preassigned group instead of each individual, and one-stage group testing emerged as essential for cost-effectively controlling the current COVID-19 pandemic. Yet, the practical challenge of adjusting pooling designs based on infection rate has not been systematically addressed. In particular, there are both theoretical interests and practical motivation to analyze one-stage group testing at finite, practical problem sizes, rather than asymptotic ones, under noisy, rather than perfect tests, and when the number of positives is randomly distributed, rather than fixed. Here, we study noisy group testing under the probabilistic framework by modeling the infection vector as a random vector with Bernoulli entries. Our main contributions include a practical one-stage group testing protocol guided by maximizing pool entropy and a maximum-likelihood recovery algorithm under the probabilistic framework. Our findings highlight the implications of introducing randomness to the infection vectors -- we find that the combinatorial structure of the pooling designs plays a less important role than the parameters such as pool size and redundancy.
Published: 3/12/2021
DOI: 10.1101/2021.03.09.21253193
DOI_URL: http://doi.org/10.1101/2021.03.09.21253193
Author Name: Liu, Y
Author link: https://covid19-data.nist.gov/pid/rest/local/author/liu_y
Author Name: Kadyan, S
Author link: https://covid19-data.nist.gov/pid/rest/local/author/kadyan_s
Author Name: Pe aposer, I
Author link: https://covid19-data.nist.gov/pid/rest/local/author/pe_aposer_i
sha: 6247c9f87b286943df07716c6644bfe337e56252
license: medrxiv
source_x: MedRxiv; WHO
source_x_url: https://www.who.int/
url: http://medrxiv.org/cgi/content/short/2021.03.09.21253193v1?rss=1 https://doi.org/10.1101/2021.03.09.21253193
has_full_text: TRUE
Keywords Extracted from Text Content: COVID-19 −ê medRxiv preprint Let Y i ||x|| f 1 body medRxiv preprint doubly-regular samples doubly-regular M 80}. https://doi.org/10.1101/2021.03.09.21253193 doi [1] constant-pool matrix [22] [23] [24] t. [2] . constant-pool sign(Mx COVID-19 Reed-Solomon Y i [2, 3] individuals T = n/2 = 192 inner × ê (1) 1} 384 [8] M ij = 1 medRxiv matrix M ∈ { ∈ {0 medRxiv preprint ∈ {8 medRxiv preprint 2 384well E (1) ) Algorithm 1 randomly-drawn [5] matrix
Extracted Text Content in Record: First 5000 Characters:Group testing saves time and resources by testing each preassigned group instead of each individual, and one-stage group testing emerged as essential for cost-effectively controlling the current COVID-19 pandemic. Yet, the practical challenge of adjusting pooling designs based on infection rate has not been systematically addressed. In particular, there are both theoretical interests and practical motivation to analyze one-stage group testing at finite, practical problem sizes, rather than asymptotic ones, under noisy, rather than perfect tests, and when the number of positives is randomly distributed, rather than fixed. Here, we study noisy group testing under the probabilistic framework by modeling the infection vector as a random vector with Bernoulli entries. Our main contributions include a practical one-stage group testing protocol guided by maximizing pool entropy and a maximum-likelihood recovery algorithm under the probabilistic framework. Our findings highlight the implications of introducing randomness to the infection vectors -we find that the combinatorial structure of the pooling designs plays a less important role than the parameters such as pool size and redundancy. Group testing is a procedure to find positives in a cohort by applying tests for the presence of any positives to cohort subsets (groups), instead of testing each individual separately. When the fraction of positives among the samples is low, implementing group testing saves time and resources. Group testing has applications in genetics [21] , drug screening [13] communications [25] and epidemiology [23] . One-stage group testing [6] addresses the scenario of groups being set in advance, independently of test results -a common practical requirement, e.g. due to testing speed constraints. Existing algorithms on infection vector recovery for noisy group testing under the combinatorial prior (the number of positives among samples is fixed) include LP relaxation [16] , belief propagation [20] , Markov Chain Monte Carlo (MCMC) [9] , Noisy Combinatorial Orthogonal Matching Pursuit (NCOMP) [4] , separate decoding [18] and Definite positives (DD) [19] . However, group testing under a fully probabilistic framework has not been extensively studied. In particular, to the best of our knowledge, there has been a lack of work on non-asymptotic results on noisy group testing in the realistic scenario where number of positives in not known in advance, as in [2, 3] , but rather is a random variable. As part of the global efforts to control the COVID-19 pandemic, there has been an emerging body of work on implementing one-stage group testing for COVID-19 [10, 11, [22] [23] [24] . However, testing scenarios vary significantly due to fluctuating infection rates across time and geography often caused by emerging variants, as well as different testing objectives, such as screening of health care workers versus large scale monitoring of the community. Group testing protocols should thus be adjusted according to the infection rate among the tested samples, measurement error rates, and the recovery error tolerance level [5] . As a result, systematically studying one-stage noisy group testing with a random number of positives is of both theoretical interests and practical importance. In this paper, we study noisy group testing under the probabilistic framework in order to address the practical challenges posted by group testing implementation for COVID-19. The rest of the paper is organized as follows. We begin with an introduction of the noisy group testing under the probabilistic framework in Section 2, including a group testing protocol and a novel recovery algorithm under the probabilistic framework. The performance of the recovery algorithm and the pooling designs is in Section 3. Finally, we conclude with a discussion on future work in Section 4. We assume a tested cohort of n individuals, with some infection rate f among the population the cohort is sampled for. Note, that the actual number of true positives is not known in advance, as combinatorial priors unrealistically assume [2, 3] . Also, this is the ground truth rate of infected individuals, as opposed to the observed positivity rate. Specifically: We aim to design a protocol to test n samples with t < n tests. We arrange the pool assignments into a pooling matrix M ∈ {0, 1} t×n such that M ij = 1 if and only if individual j is included in pool i. Notice that each row i sum of M correspond to a pool size s i , and each column j sum corresponds to the number of pools that a sample participates, which we define as redundancy r j . Following [1] and [8] , we focus on the following four classes of pooling designs that are of practical interests (see Fig. 1 Under the noiseless setting, a test result is negative if and only if all samples in the pool are negative. In practice, test results might suffer from measurement errors. Suppose the test we use for each pool has a false negative rate of f 0 a
PDF JSON Files: document_parses/pdf_json/6247c9f87b286943df07716c6644bfe337e56252.json
G_ID: a_recovery_algorithm_and_pooling_designs_for_one_stage_noisy_group_testing_under_the
S2 ID: 232204212