1. IEEE Signal Processing Magazine
2. Signal Processing Digital Library*
3. Inside Signal Processing Newsletter
4. SPS Resource Center
5. Career advancement & recognition
6. Discounts on conferences and publications
7. Professional networking
8. Communities for students, young professionals, and women
9. Volunteer opportunities
10. Coming soon! PDH/CEU credits
Click here to learn more.
10 years of news and resources for members of the IEEE Signal Processing Society
The coronavirus (COVID-19) pandemic has led to widespread morbidity and mortality. Several countries have been forced into prolonged lockdowns in a desperate attempt to control the pandemic by physical distancing. Such lockdowns have devastated livelihoods and put large numbers of people at grave risk of prolonged unemployment, poverty, and even starvation.
Is there an alternative to lockdown? Early identification of infected individuals can enable quarantining of the individuals and thus control the spread of the disease. It is not enough to quarantine symptomatic individuals because infected individuals are often asymptomatic for many days. Widespread testing of asymptomatic individuals with the RT-PCR (Reverse Transcription Polymerase Chain Reaction) method can help identify the infected individuals early. However, widespread testing of asymptomatic individuals is not an available option in many countries due to constraints on resources such as time, basic equipment, cost, skilled manpower, and reagents.
The use of group testing can make widespread testing of asymptomatic individuals an available option. The current low rate of COVID-19 infection in the world population means that most samples tested are not infected, so that most tests are wasted on uninfected samples. Group testing is a process of pooling together samples of 'n' different people into multiple pools, and testing the pools instead of each individual sample. A negative result on the pool implies that all 'n' samples were negative. This saves a huge amount of testing resources, especially with low infection rates.
Group testing for medical applications has a long history dating back to the Dorfman pooling method from 1940s which was proposed for testing of blood samples for syphilis. Simple group testing schemes have already been applied in the field by several research labs in Germany, Nebraska and Israel for COVID-19 testing. Recently, Wuhan health authorities carried out a very large scale group testing for COVID-19, employing groups of size 10 and 5.
The problem with testing asymptomatic individuals is that they can get infected after they get tested. Ideally we should be testing these individuals frequently, perhaps a few times a month, or even a few times a week. Simple group testing schemes are not suited for this because their savings comes at the cost of a longer time to result. Simple group testing schemes require pooling of samples and a second round of RNA extraction and testing for all samples in positive pools. This second round can increase the time to result and be laborious to perform in laboratories where the RNA extraction process is done manually. In situations like daily testing where the result needs to be delivered fast or the additional labour required for a second round of RNA extraction is not an option, these schemes are less attractive.
Can the savings of simple pooling be retained while simultaneously returning individual-level quantitative results in a single round of testing? Yes, by use of techniques from compressed sensing. Compressed sensing is a well-known paradigm for acquisition of information (typically images) directly in compressed format, as opposed to complete acquisition followed by compression later. In the context of its application for pooled testing, this gives rise to a model equation of the following form: 'y = Ax + g'. Here 'g' is the measurement noise. 'A' is a carefully designed binary 'mixing' matrix of size 'm' by 'n', with 'm' much smaller than 'n'. The aim is to estimate the ground truth 'x' from observations 'y' and the matrix 'A'. This is a system of linear equations where the number 'm' of equations is far fewer than the number 'n' of unknowns. Typically one will not have a unique solution. However it is possible to design 'A' to ensure a unique sparse solution 'x'. Moreover, the algorithms for recovery of 'x' are computationally efficient and robust against noise [CandesWakin2008,Berinde2008].
We present Tapestry Pooling which is inspired from the theory of compressed sensing [CandesWakin2008]. Here 'x' is a vector of 'n' elements, where the i-th element 'x(i)' represents the viral concentration in the sample of the i-th person. If x(i) > 0, it means that the i-th person is infected. If x(i) = 0, it means the person is non-infected. Since prevalence rates of infection are low, we can regard 'x' to be a sparse vector, i.e. with mostly zeros. The Tapestry method creates a small number 'm' of pools, where 'm' is much less than 'n'. Each pool is constituted of equal volume aliquots from 3n/m samples. The element A(i,j) = 1$ i and only if the j-th sample has been included in the i-th pool, and 0 otherwise. Instead of testing each of the 'n' people individually, we test only the 'm' pools in the RT-PCR machine. The vector 'y' is a vector of 'm' elements representing the total viral concentration in each of the 'm' pools as measured by the RT-PCR machine.
In designing Tapestry, we had to confront three challenges. First, how do we design the mixing matrix 'A'? Second, what is an appropriate noise model that captures the underlying physical reality of the PCR test? Third, given the particular properties of our 'A' matrix and the noise model, what is a good recovery algorithm that estimates virus numbers, recovers support of 'x' accurately, and exploits the non-negativity of 'x' and 'y'?
The design of the pooling matrix 'A' requires imposing constraints that 'A' be binary, sparse and that no sparse vector (apart from the 0 vector) lies in its nullspace. The matrix 'A' should be sparse so that not too many samples contribute to any pool. This is to simplify the implementation of the pooling procedure from a technician's point of view. In Tapestry, the 'A' matrices we employ are Kirkman triples and Social Golfer triples from the Combinatorial Theory of Designs.
We introduced a new noise model. When a test is negative, PCR returns negative unless there is cross-contamination with another sample. Hence there is no noise when a test is negative. When a test is positive, qPCR estimates an affine transform of the log of the viral concentrations, leading to a multiplicative noise model.
Our recovery algorithm combines combinatorial ideas from classical group testing literature with compressed sensing ideas. We apply the classical group testing algorithm called COMP (Combinatorial Orthogonal Matching Pursuit) to eliminate samples that are clearly negative. We then apply compressed sensing techniques adapted to our noise model to the residual equations.
All these innovations allow Tapestry to deliver as many as 1000 individual results with as few as 90 tests in a single round of PCR at a prevalence rate of one percent. The quantitative results show remarkable concordance with results that would be obtained by separate individual testing of each sample.
Tapestry has a number of salient features, compared to other available group testing methods:
Our single-round testing technique can be deployed in many different scenarios such as the following:
A number of people are involved with and contributing fruitfully to Tapestry. These include Profs. Manoj Gopalkrishnan and Ajit Rajwade from IIT Bombay, Prof. Dror Baron from NCSU, and Prof. Chandra Murthy from IISc Bangalore.
A detailed description of our algorithms, theory and experimental results can be found in our medrxiv and arxiv pre-prints. We have designed an Android app named Byom Smart Testing to make our Tapestry protocol easy to deploy in the future. The app can be accessed here. We are also sharing our code and some amount of data here. Tapestry has a website with all the latest updates.
There have been other groups working on different aspects of the problem of pooled testing, prominent examples being the binary PCR work of Dror Baron (see also this link), the work on Origami Assays for mixing matrix design by Peter Woolf and the work by the group of Noam Shental.
[CandesWakin2008]: E. Candes and M. Wakin, An introduction to compressive sampling, IEEE Signal Processing Magazine = 2008]
[Berinde2008]: R. Berinde, A. C. Gilbert, P. Indyk, H. Karloff and M. J. Strauss, Combining geometry and combinatorics: A unified approach to sparse signal recovery,46th Annual Allerton Conference on Communication, Control, and Computing, 2008.]
© Copyright 2020 IEEE – All rights reserved. Use of this website signifies your agreement to the IEEE Terms and Conditions.
A not-for-profit organization, IEEE is the world's largest technical professional organization dedicated to advancing technology for the benefit of humanity.