A Compressed Sensing Approach to Group-testing for COVID-19 Detection

Ghosh, Sabyasachi; Agarwal, Rishi; Rehan, Mohammad Ali; Pathak, Shreya; Agrawal, Pratyush; Gupta, Yash; Consul, Sarthak; Gupta, Nimay; Goyal, Ritika; Rajwade, Ajit; Gopalkrishnan, Manoj

We propose Tapestry, a novel approach to pooled testing with application to COVID-19 testing with quantitative Polymerase Chain Reaction (PCR) that can result in shorter testing time and conservation of reagents and testing kits. Tapestry combines ideas from compressed sensing and combinatorial group testing with a novel noise model for PCR. 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. While other pooling techniques require a second confirmatory assay, Tapestry obtains individual sample-level results in a single round of testing. When testing $n$ samples with $t$ tests, as many as $k= O(t / \log n)$ infected samples can be identified at clinically-acceptable false positive and false negative rates. This makes Tapestry viable even at prevalence rates as high as 10\%. Tapestry has been validated in simulations as well as in wet lab experiments with oligomers. Clinical trials with Covid-19 samples are underway. An accompanying Android application Byom Smart Testing which makes the Tapestry protocol straightforward to implement in testing centres is available for free download.