Abstract
Large scale screening is a critical tool in the life sciences, but is often limited by reagents, samples, or cost. An important challenge in screening has recently manifested in the ongoing effort to achieve widespread testing for individuals with SARS-CoV-2 infection in the face of substantial resource constraints. Group testing methods utilize constrained testing resources more efficiently by pooling specimens together, potentially allowing larger populations to be screened with fewer tests. A key challenge in group testing is to design an effective pooling strategy. The global nature of the ongoing pandemic calls for something simple (to aid implementation) and flexible (to tailor for settings with differing needs) that remains efficient. Here we propose HYPER, a new group testing method based on hypergraph factorizations. We provide theoretical characterizations under a general statistical model, and exhaustively evaluate HYPER and proposed alternatives for SARS-CoV-2 screening under realistic simulations of epidemic spread and within-host viral kinetics. We demonstrate that HYPER performs at least as well as other methods in scenarios that are well-suited to each method, while outperforming those methods across a broad range of resource-constrained environments, being more flexible and simple in design, and taking no expertise to implement.
Introduction
Widespread testing is essential for controlling pandemics, but resources—reagents, lab time, and costs—are often limited. Group testing (pooling multiple samples into one test) can save resources, but designing these pools effectively is a major challenge. Existing methods often suffer from rigidity, being tied to specific hardware like 96-well plates, or complexity, requiring specialized robotics and complex decoding algorithms.
HYPER seeks a "Goldilocks" solution: a method that is mathematically optimal, flexible enough for any sample volume, and simple enough for manual lab implementation. It allows labs to screen up to 18 times more individuals with the same number of tests without requiring specialized equipment.
Methods: Hypergraph Factorization
The core of HYPER is Hypergraph Factorization. In this framework, pools are represented as vertices and the assignment of an individual to multiple pools is represented as a hyperedge. HYPER utilizes combinatorial results, such as Baranyai’s Theorem, to create "maximally balanced" designs.
This balance ensures that every individual is in the same number of pools ($q$), every pool is the same size, and every combination of pools is used as evenly as possible. This uniformity is critical for predictable workloads and consistent sample dilution. The protocol follows a two-stage approach:
- Stage 1 (Pooled Testing): Samples are pooled according to the hypergraph design and tested. A "conservative decoder" identifies "putative positives"—individuals whose samples were exclusively in pools that tested positive.
- Stage 2 (Individual Testing): These putative positives are re-tested individually to confirm the final results.
Evaluation and Results
The authors evaluated HYPER using both standard statistical models and a realistic COVID-19 simulation of 12.5 million individuals. The simulation accounted for within-host viral kinetics and epidemic spread, providing a rigorous test of how pooling dilution affects the Limit of Detection (LOD).
Key Findings
- Efficiency: HYPER is approximately 25% more efficient than comparable plate-based array designs while maintaining sensitivity.
- Scalability: In resource-scarce scenarios, HYPER achieved a screening capacity 12 to 18 times higher than individual testing.
- Robustness: Unlike one-stage methods that lose sensitivity as prevalence rises, HYPER’s two-stage approach remains robust due to individual confirmation in the second stage.
- Practicality: The method is designed for manual feasibility; a technician can pool 192 samples in under 90 minutes using a HYPER design where individuals are split into at most 3 pools ($q \le 3$).
Discussion and Limitations
While HYPER offers significant gains, it is still limited by the physical sensitivity of PCR tests; extreme dilution in very large pools carries a risk of false negatives for samples with low viral loads. Additionally, while $q \le 3$ is manageable for manual pipetting, it remains more labor-intensive than simpler 1-pool methods. Future work may explore higher $q$ values for labs equipped with robotics to achieve even greater efficiency.
To facilitate immediate adoption, the authors provide an online tool at hyper.covid19-analysis.org for generating custom lab designs.
Summary updated