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

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

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.