An official website of the United States government
In this paper, we propose algorithms that leverage a known community structure to make group testing more efficient. We consider a population organized in connected communities: each individual participates in one or more communities, and the infection probability of each individual depends on the communities (s)he participates in. Use cases include students who participate in several classes, and workers who share common spaces. Group testing reduces the number of tests needed to identify the infected individuals by pooling diagnostic samples and testing them together. We show that making testing algorithms aware of the community structure, can significantly reduce the number of tests needed both for adaptive and non-adaptive group testing.
more »
« less
Community-Aware Group Testing
Group testing is a technique that can reduce the number of tests needed to identify infected members in a population, by pooling together multiple diagnostic samples. Despite the variety and importance of prior results, traditional work on group testing has typically assumed independent infections. However, contagious diseases among humans, like SARS-CoV-2, have an important characteristic: infections are governed by community spread, and are therefore correlated. In this paper, we explore this observation and we argue that taking into account the community structure when testing can lead to significant savings in terms of the number of tests required to guarantee a given identification accuracy. To show that, we start with a simplistic (yet practical) infection model, where the entire population is organized in (possibly overlapping) communities and the infection probability of an individual depends on the communities (s)he participates in. Given this model, we compute new lower bounds on the number of tests for zero-error identification and design community-aware group testing algorithms that can be optimal under assumptions. Finally, we demonstrate significant benefits over traditional, community-agnostic group testing via simulations using both noiseless and noisy tests
more »
« less
- PAR ID:
- 10474608
- Publisher / Repository:
- IEEE
- Date Published:
- Journal Name:
- IEEE Transactions on Information Theory
- Volume:
- 69
- Issue:
- 7
- ISSN:
- 0018-9448
- Page Range / eLocation ID:
- 4361 to 4383
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
In this paper, we propose algorithms that leverage a known community structure to make group testing more efficient. We consider a population organized in disjoint communities: each individual participates in a community, and its infection probability depends on the community (s)he participates in. Use cases include families, students who participate in several classes, and workers who share common spaces. Group testing reduces the number of tests needed to identify the infected individuals by pooling diagnostic samples and testing them together. We show that if we design the testing strategy taking into account the community structure, we can significantly reduce the number of tests needed for adaptive and non-adaptive group testing, and can improve the reliability in cases where tests are noisy.more » « less
-
null (Ed.)Summary Group testing involves pooling individual specimens (e.g., blood, urine, swabs, etc.) and testing the pools for the presence of disease. When the proportion of diseased individuals is small, group testing can greatly reduce the number of tests needed to screen a population. Statistical research in group testing has traditionally focused on applications for a single disease. However, blood service organizations and large-scale disease surveillance programs are increasingly moving towards the use of multiplex assays, which measure multiple disease biomarkers at once. Tebbs and others (2013, Two-stage hierarchical group testing for multiple infections with application to the Infertility Prevention Project. Biometrics69, 1064–1073) and Hou and others (2017, Hierarchical group testing for multiple infections. Biometrics73, 656–665) were the first to examine hierarchical group testing case identification procedures for multiple diseases. In this article, we propose new non-hierarchical procedures which utilize two-dimensional arrays. We derive closed-form expressions for the expected number of tests per individual and classification accuracy probabilities and show that array testing can be more efficient than hierarchical procedures when screening individuals for multiple diseases at once. We illustrate the potential of using array testing in the detection of chlamydia and gonorrhea for a statewide screening program in Iowa. Finally, we describe an R/Shiny application that will help practitioners identify the best multiple-disease case identification algorithm.more » « less
-
Accurate detection of infected individuals is one of the critical steps in stopping any pandemic. When the underlying infection rate of the disease is low, testing people in groups, instead of testing each individual in the population, can be more efficient. In this work, we consider noisy adaptive group testing design with specific test sensitivity and specificity that select the optimal group given previous test results based on pre-selected utility function. As in prior studies on group testing, we model this problem as a sequential Bayesian Optimal Experimental Design (BOED) to adaptively design the groups for each test. We analyze the required number of group tests when using the updated posterior on the infection status and the corresponding Mutual Information (MI) as our utility function for selecting new groups. More importantly, we study how the potential bias on the ground-truth noise of group tests may affect the group testing sample complexity.more » « less
-
Abstract BackgroundPrompt identification of infections is critical for slowing the spread of infectious diseases. However, diagnostic testing shortages are common in emerging diseases, low resource settings, and during outbreaks. This forces difficult decisions regarding who receives a test, often without knowing the implications of those decisions on population-level transmission dynamics. Clinical prediction rules (CPRs) are commonly used tools to guide clinical decisions. MethodsUsing early severe acute respiratory syndrome coronavirus disease 2 (SARS-CoV-2) as an example, we used data from electronic health records to develop a parsimonious 5-variable CPR to identify those who are most likely to test positive. To consider the implications of gains in daily case detection at the population level, we incorporated testing using the CPR into a compartmentalized model of SARS-CoV-2. ResultsWe found that applying this CPR (area under the curve, 0.69; 95% confidence interval, .68–.70) to prioritize testing increased the proportion of those testing positive in settings of limited testing capacity. We found that prioritized testing led to a delayed and lowered infection peak (ie, “flattens the curve”), with the greatest impact at lower values of the effective reproductive number (such as with concurrent community mitigation efforts), and when higher proportions of infectious persons seek testing. In addition, prioritized testing resulted in reductions in overall infections as well as hospital and intensive care unit burden. ConclusionWe highlight the population-level benefits of evidence-based allocation of limited diagnostic capacity.SummaryWhen the demand for diagnostic tests exceeds capacity, the use of a clinical prediction rule to prioritize diagnostic testing can have meaningful impact on population-level outcomes, including delaying and lowering the infection peak, and reducing healthcare burden.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript
- Journal Article:
- https://doi.org/10.1109/TIT.2023.3250119
