A Compressed Sensing Approach to Pooled RT-PCR Testing for COVID-19 Detection

Sabyasachi Ghosh, Rishi Agarwal, Mohammad Ali Rehan, Shreya Pathak, Pratyush Agarwal, Yash Gupta, Sarthak Consul, Nimay Gupta, Ritika, Ritesh Goenka, Ajit Rajwade, Manoj GopalkrishnanIEEE Open Journal of Signal Processing 2021 · DOI

TL;DR

This paper introduces "Tapestry," a novel single-round pooled RT-PCR testing method for COVID-19 that combines compressed sensing and combinatorial group testing. Tapestry significantly reduces testing time and reagent costs by intelligently pooling samples and using quantitative PCR readouts, achieving high accuracy even at prevalence rates up to 9.5%.

What Problem Does This Paper Address?

The COVID-19 pandemic highlighted the critical need for widespread and rapid testing. Traditional RT-PCR testing, while accurate, is resource-intensive, requiring significant time, reagents, and skilled personnel. This bottleneck becomes particularly acute in scenarios with low infection prevalence, where most tests are performed on uninfected individuals, leading to wasted resources. Existing pooled testing methods, while more efficient, often require a second round of testing for positive pools, increasing time and labor. The authors aim to develop a single-round pooled testing strategy that is both resource-efficient and highly accurate, even with quantitative PCR data and realistic noise conditions.

Methods

The core of the "Tapestry" method lies in its innovative decoding algorithm, which combines two key approaches:

  • Combinatorial Group Testing (CGT): Initially, the algorithm employs a "Combinatorial Orthogonal Matching Pursuit" (COMP) algorithm. COMP is adept at identifying "sure negatives" (samples definitively not infected) and can also flag "high-confidence positives." This initial filtering step significantly reduces the number of samples that need further analysis.
  • Compressed Sensing (CS): Following the COMP stage, the remaining samples are analyzed using compressed sensing techniques. Unlike traditional CGT, Tapestry leverages the quantitative output of RT-PCR (viral load, not just positive/negative) to reconstruct the viral load of each individual sample. This quantitative information allows for more precise identification of infected individuals and reduces false positives compared to purely Boolean group testing.

The paper also introduces novel sensing matrix designs, particularly those based on Kirkman Triple Systems. These deterministic matrices offer a balance between good reconstruction properties for CS and sparsity for efficient pooling, leading to fewer tests in practice compared to randomly generated matrices. A novel noise model for RT-PCR experiments is also developed and used for simulations.

Datasets

The paper uses two types of data for evaluation:

  • Synthetic Data: Generated using a novel noise model for RT-PCR, simulating various infection prevalence rates (k, the number of infected samples, ranging from 5 to 20 out of n=961 samples).
  • Real Lab Data: Obtained from two sources:
  • National Center of Biological Sciences (NCBS) in India (datasets with n=40, k={1,2,3,4} and n=16, k={0,1,2,3,4}).
  • Wyss Institute at Harvard Medical School, USA (datasets with n=60, k=2 and n=120, k=2).

The paper does not introduce new benchmark datasets but rather uses existing experimental setups and data from these labs.

Key Insights and Ideas

  • Quantitative Readout is Key: Leveraging the quantitative viral load information from RT-PCR, rather than just a binary positive/negative result, significantly improves the accuracy and reduces false positives in pooled testing.
  • Two-Stage Decoding for Efficiency: Combining COMP for initial filtering with CS for precise reconstruction offers a powerful and efficient decoding strategy. COMP handles the bulk of negative samples, simplifying the problem for the more computationally intensive CS stage.
  • Deterministic Matrices for Practicality: While random matrices offer theoretical guarantees, deterministic matrices derived from combinatorial designs like Kirkman Triple Systems provide practical advantages in terms of ease of implementation and potentially fewer tests required in real-world scenarios.
  • Noise Modeling Matters: Developing a realistic noise model for RT-PCR experiments is crucial for accurately evaluating the performance of pooled testing algorithms.
  • Single-Round Advantage: Eliminating the need for a second round of testing significantly reduces overall testing time and labor, a critical factor during a pandemic.

Key Results

  • Significant Reduction in Tests: Tapestry, using a 93x961 Kirkman matrix, requires only 93 tests to detect 1% infected samples with high sensitivity and specificity, a substantial improvement over traditional methods. At a 9.5% prevalence rate, it still maintains viability and reduces testing costs by a factor of 2.3.
  • Improved Accuracy: The method achieves clinically acceptable false positive and false negative rates. For instance, with a 93x961 Kirkman matrix, COMP-SBL achieved a sensitivity above 0.99 and specificity above 0.95 for up to k=10 infected samples.
  • Comparison to Dorfman Pooling: Tapestry requires significantly fewer tests (e.g., 93 tests for 961 samples) compared to two-round Dorfman pooling (which might require hundreds of tests for the same number of samples, depending on prevalence).
  • Robustness to Noise: The algorithms were tested on a novel noise model for RT-PCR and showed good performance.
  • Wet Lab Validation: The approach was validated using wet lab experiments with oligomers.

Limitations and Future Work

  • Limitations:
    • The paper acknowledges that while the method can detect certain errors (pipetting, contamination), it may not catch all errors.
  • The "graceful failure mode" sacrifices some false negatives for fewer false positives when the estimated sparsity exceeds the algorithm's capacity.
  • While promising, the results on real data are limited in scope and scale compared to synthetic data.
  • Future Work:
    • Extensive testing on larger, real-world COVID-19 datasets.
  • Further development and implementation of various sensing matrix design algorithms.
  • Continued refinement of signal recovery algorithms.
  • Accounting for occasional pipetting errors more robustly.
  • Developing an Android app for easier deployment of the Tapestry protocol.

Summary updated

Abstract

We propose 'Tapestry', a single-round pooled testing method with application to COVID-19 testing using quantitative Reverse Transcription Polymerase Chain Reaction (RT-PCR) that can result in shorter testing time and conservation of reagents and testing kits, at clinically acceptable false positive or false negative rates. Tapestry combines ideas from compressed sensing and combinatorial group testing to create a new kind of algorithm that is very effective in deconvoluting pooled tests. Unlike Boolean group testing algorithms, the input is a quantitative readout from each test and the output is a list of viral loads for each sample relative to the pool with the highest viral load. For guaranteed recovery of [Formula: see text] infected samples out of [Formula: see text] being tested, Tapestry needs only [Formula: see text] tests with high probability, using random binary pooling matrices. However, we propose deterministic binary pooling matrices based on combinatorial design ideas of Kirkman Triple Systems, which balance between good reconstruction properties and matrix sparsity for ease of pooling while requiring fewer tests in practice. This enables large savings using Tapestry at low prevalence rates while maintaining viability at prevalence rates as high as 9.5%. Empirically we find that single-round Tapestry pooling improves over two-round Dorfman pooling by almost a factor of 2 in the number of tests required. We evaluate Tapestry in simulations with synthetic data obtained using a novel noise model for RT-PCR, and validate it in wet lab experiments with oligomers in quantitative RT-PCR assays. Lastly, we describe use-case scenarios for deployment.
BibTeX
@article{ghosh2021compressed,
  author = {Sabyasachi Ghosh and Rishi Agarwal and Mohammad Ali Rehan and Shreya Pathak and Pratyush Agarwal and Yash Gupta and Sarthak Consul and Nimay Gupta and Ritika and Ritesh Goenka and Ajit Rajwade and Manoj Gopalkrishnan},
  title = {{A Compressed Sensing Approach to Pooled RT-PCR Testing for COVID-19 Detection}},
  journal = {IEEE Open Journal of Signal Processing},
  year = {2021},
  doi = {10.1109/ojsp.2021.3075913},
}
Figure