Group testing via hypergraph factorization applied to COVID-19

David Hong, Rounak Dey, Xihong Lin, Brian Cleary, Edgar DobribanNature Communications 2022 · DOI

TL;DR

HYPER is a new two-stage group testing framework that uses hypergraph factorization to create "maximally balanced" sample pools. It matches or outperforms existing COVID-19 testing methods like P-BEST and plate-based arrays in resource-limited settings while remaining flexible enough for any batch size and simple enough to implement without complex specialized software.

What Problem Does This Paper Address?

During the COVID-19 pandemic, the demand for testing often far outstripped the supply of reagents, lab capacity, and time. Group testing (pooling multiple samples into one test) is a classic solution to increase throughput, but existing methods faced a "trilemma" of trade-offs:

  1. Efficiency: How many people can you screen per test?
  2. Flexibility: Can the method adapt to different batch sizes ($n$) or varying disease prevalence?
  3. Simplicity: Is it easy for a lab technician to perform manually, or does it require robotic pipetting and complex "black box" decoding algorithms?

Standard methods like Dorfman testing are simple but inefficient. Advanced "one-stage" methods like P-BEST are efficient but rigid (often requiring exactly 384 samples) and rely on complex sparse regression for decoding, making them difficult to deploy in resource-constrained or low-tech environments.

Methods

The authors introduce HYPER (Hypergraph-based Pooling for Efficient Resources), a two-stage pooling strategy.

  • Stage 1 (Pooled Testing): Samples are assigned to multiple pools. If a pool tests negative, everyone in it is cleared. If a pool is positive, its members are "putative positives."
  • Stage 2 (Individual Testing): Only the putative positives are tested individually to confirm the result.

The core innovation is the use of hypergraph factorization to design the pools. In this mathematical framework, pools are "vertices" and sample assignments are "hyperedges." By "factorizing" this graph, the authors ensure the design is maximally balanced in three ways:

  1. Every individual is assigned to the same number of pools ($q$, typically 2 or 3).
  2. All pools are as close to the same size as possible.
  3. Pool combinations are used as evenly as possible.

This balance ensures that every sample receives the same level of sensitivity and that the lab workload is predictable. Unlike P-BEST, HYPER uses "conservative decoding"—if you are in a negative pool, you are out. This can be done with a pencil and paper.

Datasets

The paper evaluates HYPER using two distinct approaches:

  1. General Statistical Model: A standard mathematical model using fixed parameters for prevalence, sensitivity, and specificity to derive theoretical bounds on performance.
  2. COVID-19 Simulation: A realistic simulation based on the model by Cleary and Hay et al. (2021). This model is sophisticated: it simulates 12.5 million individuals and accounts for viral kinetics (how viral load rises and falls over time) and dilution effects (how pooling multiple samples reduces the concentration of the virus, potentially leading to false negatives).

Key Insights and Ideas

  • Balance Equals Robustness: By ensuring pools are equal sizes, the authors minimize the risk that some samples are diluted more than others, making the test sensitivity uniform across the entire batch.
  • The Power of $q=2$ or $3$: While Dorfman testing ($q=1$) is the simplest, splitting a sample into just 2 or 3 pools significantly increases the ability to "rule out" negatives, drastically boosting efficiency without the logistical nightmare of splitting a sample 6+ times (as seen in some code-based designs).
  • Flexibility is a Feature: Most advanced pooling designs are "hard-coded" for specific numbers (like 96-well plates). HYPER’s mathematical construction allows it to generate a valid, balanced design for any number of samples and pools.
  • Decoupling Math from Execution: The underlying combinatorics are sophisticated, but the end result is a simple look-up table for lab techs. The authors even provided an online tool to generate these assignments automatically.

Key Results

  • Efficiency Gains: In "testing-scarce" scenarios (high sample volume, low test budget), HYPER achieved an effective screening capacity ~12x higher than individual testing.
  • Outperforming Alternatives: In head-to-head simulations, HYPER was roughly 25% more efficient than plate-based arrays and P-BEST across a wide range of scenarios, while maintaining comparable sensitivity.
  • Prevalence Adaptation: HYPER proved robust as the simulated epidemic grew. While Dorfman testing's efficiency collapses as prevalence rises, HYPER (especially with $q=2$ or $3$) maintained a significant advantage.
  • Sensitivity: Like all pooling methods, there is a slight drop in sensitivity (roughly 10% lower than individual testing) due to dilution, but the authors argue the massive increase in capacity (finding more cases overall) far outweighs the loss of sensitivity on a population level.

Limitations and Future Work

  • Manual Labor: While simpler than P-BEST, HYPER still requires splitting samples into 2 or 3 pools, which is more labor-intensive than standard one-to-one testing or simple Dorfman pooling.
  • Dilution Limits: The study confirms that as pool sizes grow very large, the "limit of detection" becomes a factor. HYPER cannot bypass the laws of physics regarding sample dilution.
  • Advanced Decoders: The authors used a "conservative" decoder for simplicity. They note that more complex algorithms (like "Definite Defective" decoding) could potentially squeeze out even more efficiency, though at the cost of the "pencil and paper" simplicity they aimed for.

Summary updated

Abstract

Large scale screening is a critical tool in the life sciences, but is often limited by reagents, samples, or cost. An important recent example is the challenge of achieving widespread COVID-19 testing in the face of substantial resource constraints. To tackle this challenge, screening methods must efficiently use testing resources. However, given the global nature of the pandemic, they must also be simple (to aid implementation) and flexible (to be tailored for each setting). Here we propose HYPER, a group testing method based on hypergraph factorization. We provide theoretical characterizations under a general statistical model, and carefully evaluate HYPER with alternatives proposed for COVID-19 under realistic simulations of epidemic spread and viral kinetics. We find that HYPER matches or outperforms the alternatives across a broad range of testing-constrained environments, while also being simpler and more flexible. We provide an online tool to aid lab implementation: http://hyper.covid19-analysis.org .
BibTeX
@inproceedings{hong2022group,
  author = {David Hong and Rounak Dey and Xihong Lin and Brian Cleary and Edgar Dobriban},
  title = {{Group testing via hypergraph factorization applied to COVID-19}},
  booktitle = {Nature Communications},
  year = {2022},
  doi = {10.1038/s41467-022-29389-z},
}
Figure