Collaborative Research: Optimized Testing Strategies for Fighting Pandemics: Fundamental Limits and Efficient Algorithms

About This Grant

Large-scale high-throughput prevalence and diagnostic testing is essential for the containment and mitigation of pandemics. The testing bottleneck in the COVID-19 pandemic has led to a resurgence of interest in group testing, where several people's biological samples are mixed together and examined in a single test. When the rate of infection in the population is low, this method can significantly reduce the total number of tests per subject and increase the throughput of the existing testing infrastructure. However, traditional group testing has the following limitations: First, efficient group testing based methods for the estimation of prevalence have been largely overlooked in the literature. Second, traditional group testing usually assumes that the testing results are qualitative (positive versus negative), not quantitative (providing viral load information). Third, the theoretical study of group testing rarely takes practical constraints, such as the sensitivity of the pooled tests and the dilution effect, into consideration, which hinders the applicability of the testing schemes in practice. The goal of this project is to overcome these limitations of traditional group testing and design advanced pooled testing strategies for efficient prevalence tracking and accurate infection diagnosis. It will develop optimized pooled testing strategies with strong theoretical performance guarantees yet feasible and cost-effective in practice. The proposed research is organized in three research thrusts as follows. Thrust 1 aims to design effective sampling and testing algorithms to estimate the prevalence in communities and track its evolution, under scarce testing resource constraints. Thrust 2 focuses on the design of optimized pooling and decoding algorithms for compressed sensing based (COVID-19) virus diagnostic testing. Thrust 3 validates the accuracy and efficiency of the proposed pooled testing through experiments on anonymized COVID-19 samples. This project bridges group testing and online learning, the two largely disconnected areas, with the objective to effectively allocate limited testing resources for efficient prevalence tracking. Such integration leads to novel sampling strategies, broadens the paradigm of group testing, and advances the state of the art of online learning. Moreover, the proposed compressed sensing based diagnostic testing leverages quantitative measurements provided by advanced testing technologies, which can significantly increase test throughput, reduce the number of needed tests, decrease the consumption of scarce reagents, and provide results robust against observation noises and outliers. The rich compressed sensing theory provides possible approaches to the rigorous mathematical certification of the correctness of the decoded results. Besides, the clinical constraints on pooled testing also lead to novel problem formulation and theoretical characterization, enriching the study of compressed sensing. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.