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

大规模高通量流行率和诊断检测对于遏制和缓解流行病至关重要。COVID-19大流行的检测瓶颈导致对群体检测的兴趣重新抬头，即将几个人的生物样本混合在一起并在一次检测中进行检查。当人群中的感染率较低时，这种方法可以显著减少每个受试者的测试总数，并增加现有测试基础设施的吞吐量。然而，传统的团体测试有以下局限性：第一，有效的团体测试为基础的方法估计患病率在很大程度上被忽视的文献。其次，传统的团体测试通常假设测试结果是定性的（阳性与阴性），而不是定量的（提供病毒载量信息）。第三，对群体测试的理论研究很少考虑实际的约束条件，如混合测试的敏感性和稀释效应，这阻碍了测试方案在实践中的适用性。该项目的目标是克服传统群体检测的这些局限性，设计先进的合并检测策略，以实现有效的流行率跟踪和准确的感染诊断。它将开发优化的汇集测试策略，具有强有力的理论性能保证，但在实践中是可行的和具有成本效益的。推力1旨在设计有效的抽样和测试算法，以估计社区的流行程度，并跟踪其演变，在稀缺的测试资源的限制。第二个重点是为基于压缩感知（COVID-19）的病毒诊断测试设计优化的池化和解码算法。Thrust 3通过对匿名COVID-19样本的实验验证了拟议的合并测试的准确性和效率。该项目将团体测试和在线学习这两个基本上互不相关的领域连接起来，目的是有效分配有限的测试资源，以有效跟踪流行情况。这种整合导致了新的抽样策略，扩大了小组测试的范式，并推进了在线学习的艺术状态。此外，所提出的基于压缩感测的诊断测试利用由先进测试技术提供的定量测量，这可以显著增加测试吞吐量，减少所需测试的数量，减少稀缺试剂的消耗，并提供对观察噪声和离群值鲁棒的结果。丰富的压缩感知理论为解码结果的正确性提供了严格的数学证明。此外，临床上对合并测试的限制也导致了新的问题表述和理论表征，丰富了压缩感知的研究。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.