Low-Cost and High-Throughput Testing of COVID-19 Viruses and Antibodies via Compressed Sensing: System Concepts and Computational Experiments

The ongoing Covid-19 pandemic has already claimed thousands of human lives. In addition, it has also forced a worldwide shutdown of social life and commerce, and the resulting economic depression has caused tremendous suffering for millions of people.

In the absence of a vaccine, the experience of public health authorities in several countries has shown that large-scale shutdowns can only be safely ended if a systematic “test and trace” program singapore_covid19 ; salathe2020covid is put in place to control the spread of the virus. This, in turn, is predicated on the widespread availability of mass diagnostic testing. However, most countries including the US are currently experiencing a scarcity ranney2020critical of various medical resources including tests fair_allocation .

One simple method to increase the effective testing capacity by testing pooled samples of a number of test subjects collectively instead of testing samples from each person individually. This idea of “group testing” goes back many decades dorfman1943 and is based on the following intuition. If the rate of infection in the population is relatively low, statistically, most individual will test negative. With group testing, a single negative test result on a pooled sample immediately shows that all individuals in that pool are infection-free.

This potentially allows us to reduce the total number of tests per subject so the throughput of the existing testing infrastructure is increased hanel2020boosting i.e. a much larger number of people can be tested compared to individual testing while keeping the number of tests the same.

Pooling does have its risks. The additional pre-processing required for preparing the pooled samples could affect the accuracy of the test because of possible degradation or contamination of the RNA. Pooling also requires dilution of the individual samples, and this in turn may increase the chances of a false negative result. However, pooling tests have been successfully used for diagnostic testing for infectious diseases in the past Taylor512 ; arnold_2013 . Preliminary studies on the Covid-19 virus also show that pooling samples Yelin2020 can be effective with existing tests.

The current testing bottlenecks in the Covid-19 crisis has led to a resurgence of interest in using group testing methods for Covid-19 diagnosis. Specifically, there have been recent studies Sinnott-Armstrong2020 ; Shani-Narkiss2020.04.06.20052159 ; poolingStanfordcommunity into adapting pooling methods similar to dorfman1943 for Covid-19 testing. In zhu2020noisy , the authors studied noisy group testing for virus detection.

In this paper, we propose a different approach based on the compressed sensing theory OptimalRecovery Candes05 donoho_compressed_2006 for detection of viruses and antibodies using pooled sample testing. In compressed sensing, the measurement reading is not just a binary reading (‘positive’ or ‘negative’) as in group testing, but instead the measurement reading of compressed sensing can be real-numbered quantification of the quantity of target DNA in the pooled sample. The traditional group testing methods such as dorfman1943 can be thought of as special cases of the more powerful compressed sensing framework proposed in this paper. This is because the measurement reading of group testing is a binary reduction of the real-numbered quantification of compressed sensing. Through compressed sensing, it is possible to test $n$ persons for viruses by only using $O(k\log(n))$ samples, where $k$ is the number of virus-infected persons. This is a significant reduction compared with testing each individual person, which would require $n$ testing. This can translate into an increase of test throughput in the order of $n/(k\log(n))$, which can be quite significant if the number of infected people is much smaller than the total population.

Indeed, the real-numbered quantification from compressed sensing can greatly help speed up the testing of viruses and reduce the cost of testing, by taking advantage of the sparsity of virus infections in the population. Compared with conventional group testing (including non-adaptive and adaptive group testing), compressed sensing has the following advantages:
(1) Compressed sensing uses real-numbered quantitative measurement results (quantification of target DNA etc. ) to infer virus infections or antibodies. These measurement readings contain more information about the collected samples than the binary readings of group testing. This will make inference from compressed sensing measurements more robust against noises an outliers in the measurements, and require fewer tests.

(2) Compressed sensing is known to require fewer measurements (or lower sample complexity) to infer virus infections than group testing. The sparsity $k$ that compressed sensing can handle for successful detection is allowed to grow linearly (proportionally) with $n$, while the recoverable sparsity $k$ is of the order $O(\sqrt{n})$ for non-adaptive group testing du1993combinatorial . This will potentially translate higher testing throughput for compressed sensing than group testing.

(3) The inference results from compressed sensing not only reveal which persons test positive or negative, but also reveal a quantitative evaluation of infections for the persons who test positive. For example, it can reveal the viral loads (copies/ml) of persons who test positive. These quantitative results can help achieve better diagnosis and treatment of infected persons, and can also help study infectious power of viruses in different phases of infections.

There are broadly two types of tests for Covid-19: (a) serological tests that look for the presence of antibodies to the virus, or (b) swab tests that look for RNA from the live virus. While antibody tests have certain advantages e.g. can detect infections even after the subject has recovered, the most common tests currently used in the US and recommended by the CDC are swab tests. These tests use the Reverse Transcription Polymerase Chain Reaction (RT-PCR) process to selectively amplify DNA strands produced by viral RNA specific to the Covid-19 virus.

The RT-qPCR process which is considered the gold standard for the detection of mRNA consists of three distinct steps: (1) reverse transcription of RNA into cDNA, (2) selective amplification of a target DNA fragment using the Polymerase Chain Reaction (PCR), and (3) detection of the amplification product. While the simple “end-point” version of PCR only allows binary detection (presence or absence) of a target RNA sequence, the real-time or quantitative version of the PCR process (qPCR) Gibson01101996 also allows the quantification of the RNA i.e. it produces an estimate of the quantity of the RNA material present in the sample nolan2006quantification .

Some researchers Lamb2020 have proposed the Reverse Transcription Loop-Mediated Isothermal Amplification (RT-LAMP) as a potentially cheaper and faster alternative to RT-PCR for swab tests. While we focus on tests based on the RT-qPCR process, the methods proposed in this paper are also compatible with RT-LAMP Schmid-Burgk2020 and other DNA amplification methods.

In this paper, we propose to use compressed sensing to detect viruses and antibodies of COVID-19. Considering the physical and complexity constraints of pooling for compressed sensing, we identify sparse bipartite graph based measurement matrices for compressed sensing applied to this purpose. In particular, we propose to use expander graph based measurement matrices Weiyuexpander2007 for pooling or measurement designs.

As mentioned above, group testing has a long history of being used to detect pathogens, tracing back to World War II, and it has also recently been applied to testing COVID-19 viruses Sinnott-Armstrong2020 ; Shani-Narkiss2020.04.06.20052159 . To the best of our knowledge, this work might be the first to develop compressed sensing techniques for detecting viruses using qPCR and other tools, especially when applied to COVID-19 viruses ¹¹1The authors of this paper conceived the idea of performing group testing and compressed sensing for COVID-19 virus detection during the early outbreak in China, and the pandemic status of COVID-19 has motivated us to carry out this research. . On a related but different subject, we note that compressed sensing was proposed in ShentalGenetic2010 to study human genetics, and used to identity people with rare alleles (“allele is one of two or more alternative forms of a gene that arise by mutation and are found at the same place on a chromosome.”).

In this section, we describe the system architecture of using compressed sensing to speed up the testing of COVID-19 viruses or antibodies, including sensing matrix design and decoding algorithm design. We will focus on developing such systems using Polymerase Chain Reaction (PCR) machines, especially real-time PCR (quantitative PCR, qPCR or RT-PCR) machines, to test the viruses, though the concepts and ideas introduced in this paper extend to testing viruses using other technologies or platforms and also to testing antibodies. (We note that in the literature, there are inconsistencies about the meanings of “RT-PCR”, which are used as abbreviations for both reverse transcription PCR and real-time PCR.) We start by introducing some background knowledge on the real-time quantitative PCR PCRHandbook .

The polymerase chain reaction (PCR) is one of the most powerful and widely used technologies in molecular biology to detect and quantify specific sequences within a DNA or cDNA template. Using PCR, specific sequences within a DNA or cDNA template can be copied, or “amplified”, to thousands or to a million times using sequence-specific oligonucleotides, heat-stable DNA polymerase, and thermal cycling kralik_basic_2017 . PCR theoretically amplifies DNA exponentially, doubling the number of target molecules with each amplification cycle.

To address the need of robust quantification of DNA, real-time polymerase chain reaction (real-time PCR) was developed based on the polymerase chain reaction (PCR). Real-time PCR is carried out in a thermal cycler (providing temperature conditions for each cycle of reactions), but with the capacity to illuminate each sample with a beam of light and detect the fluorescence emitted by the excited fluorophore PCRHandbook .

In traditional (endpoint) PCR, detection and quantification of the amplified sequence are performed at the end of the reaction after the last PCR cycle. In real-time quantitative PCR, PCR product (the amplified sequences) is measured at each PCR cycle. Namely, Real-time PCR can monitor the amplification of a targeted DNA module in the PCR in real time. By monitoring reactions during the exponential amplification phase of the reaction, users can determine the initial quantity of the target with great precision. The working physical principle of the RT-PCR is that it detects amplification of DNA in real time by the use of fluorescent reporter. The fluorescent reporter signal strength is directly proportional to the number of amplified DNA molecules.

Real-time PCR commonly relies on plotting fluorescence against the number of cycles on a logarithmic scale to perform DNA quantification. During the exponential amplification phase, the quantity of the target DNA template (amplicon) doubles every cycle. A threshold for detection of DNA-based fluorescence is set 3–5 times of the standard deviation of the signal noise above background. The number of cycles at which the fluorescence exceeds the threshold is called the threshold cycle ($C_{t}$) or, quantification cycle ($C_{q}$). One can then use this threshold cycle $C_{t}$ to determine the quantity of target DNA in the sample. In ideal cases, if the threshold cycle of a DNA sample $A$ precedes that of another sample $B$ by $N$ cycles, then this DNA sample $A$ contains $2^{N}$ times more target DNAs than DNA sample $B$ at the beginning of the reaction. In practice, people often use the standard curve method for real-time PCR to determine the relation between threshold cycle $C_{t}$ and target quantity.

In the experiments, we consider two types of binary pooling matrix: Bernoulli random matrix where each entry of the matrix is ‘0’ with probability 0.5, and is ‘1’ with probability 0.5, and measurement matrix obtained from an expander graph Weiyuexpander2007 where each column has a fixed number of ones. Experimenting with random Bernoulli pooling matrices can show the typical performance of such pooling matrices. In practice, one needs to work with deterministic pooling matrices. To design a deterministic matrices, one can use algorithms in ChoTesting to precisely verify the performance guarantee of a randomly generated matrix for virus testing. After the verification, we can then use it as a deterministic pooling matrix in practice.

For these two types of binary pooling matrix, we consider two different values for the number of people tested, i.e., $n=120$ and $n=60$. For each of the two values of length $n$, we recover the value of $x$ with different sparsity (sparsity is the number of people infected in this group of people), i.e., $k=3$ and $k=5$. In the experiments, we set random $k$ entries of the signal of length $n$ to be random numbers within $[5,10]$, while the other entries are set to be positive numbers close to 0.

When $n=60$, for each $k$ and measurement matrix type, we take different measurements $m$=$10$,$15$,$20$,…, and $60$. For each possible $m$, we run 100 trials to evaluate the successful recovery rate via solving

where $A\in\mathbb{R}^{m\times n}$ is the measurement matrix, $x$ is the signal to be recovered, and $y\in\mathbb{R}^{m}$ is the measurement vector. After a signal is decoded, we use a thresholding technique to identify the persons with viruses. For each trial, we set a threshold $\tau=0.5$. The signal entry will determined to be ‘positive’ with viruses, if the recovered value is at least $\tau$, and ‘negative’ if it is less than $\tau$. We then calculate the true positive rate (TPR),true negative rate (TNR), false positive rate (FPR), and false negative rate (DNR). We also consider the recovery success rate: if the reconstruction error (the Euclidean distance between the true signal $x$ and the recovered signal $\hat{x}$) is smaller than $10^{-3}$, we count the recovery as a success. The numerical results are shown in Figure 2 to Figure 5 for Bernoulli measurement matrices. Numerical results are shown in Figures 6 to 9 for expander graph based measurement matrices. As we can see from these figures, $n=60$, we only need around $m=20$ tests to achieve very low false negative rates and false positive rates, which means that we can increase the throughput of virus testing by $\frac{n}{m}\approx 3$ times. For $n=120$, we also need around $m=20$ tests to achieve low false negative and false positive rates, which translates to around $\frac{n}{m}\approx 6$ times increase in test throughput. For $k=2$ and $n=200$, when we use expander graph based pooling matrix with 5 ‘1’s in each column, we can already achieve a near zero false positive and false negative rates when $m=20$. This translates to a $\frac{200}{20}$ folds of speedup in test throughput.

We also conduct experiments with noisy measurements, and the signal is recovered from noisy measurements by solving

where $\epsilon>0$ is a parameter tuned to noise magnitude, and $y\in\mathbb{R}^{m}$ is the noisy measurement vector. We follow the same setup as in previous section expect that for each trial of each set of parameter $(m,n)$, we add randomly generated noise vector $v$ with normalized magnitude $10^{-3}$ to the measurements, namely $y=Ax+v$. For each trial of each set of parameter, we treat the recovery as successful if it achieves a reconstruction error less than $10^{-2}$. The results of the recovery probabilities, false positive rates, and false negative rates are shown in the following figures from Figure 13 to Figure 20. Figure 10 shows the results for $k=2$ and $n=200$, demonstrating a possible increase of throughput by 10 times.

We can see that similar increases in testing throughput are also observed as in the noiseless cases. In fact, for a large range of reasonable noise levels, we can observe similar increases in testing throughput with low false positive rates and false negative rates.

In another experiment, we numerically evaluate the performance of exhaustive search in detecting viruses. We take $n=40$ and $k=2$, and the number of measurements is taken as $m=5$,$6$,$7$,$8$, $9$, and $10$. For each set of $(m,n,k)$, we run 10 trials. In each trial, the pooling matrix is a Bernoulli random matrix. The measurement result is contaminated with random noise normalized to have a magnitude of $10^{-3}$. A trial is considered to have successful recovery if the recovery error is less than $10^{-2}$ in the noisy case. In exhaustive search, since the true signal has sparsity of $k$, we will simply perform brute force calculations over all the possible sets of $k$ infected persons. For each possible such set of cardinality $k$, we extract the corresponding columns from the measurement matrix. By doing this, we get an overdetermined system, and solve it via the least squares method. There are totally ${n\choose k}$ possible such sets, which means we need to solve the least square ${n\choose k}$ times for each trial. The results are shown in Figure 11. As we can see, using only $10$ measurements, the false positive rate and false negative rates are very low (in fact 0 in this experiment). That amounts to a factor of $\frac{40}{10}=4$ speedup in throughput of the test.

We now look at the testing data of COVID-19 viruses from the state of Iowa. The rate of testing positive is around 8.7 percent by early April, meaning among all the tests carried out, 8.7 percent of them came back with a ‘positive’ result. We consider a microplate of 96 wells, and assume that the PCR machine can analyze 96 samples in one operational period. Then we do a computational experiment to answer, “using compressed sensing, for how many people these 96 compressed sensing (pooling) samples can correctly identify all the carriers of viruses present in that group of people?” In this experiment, we fix the number of measurements, namely $m$, as 96. Then we vary the number of people $n$, and randomly pick 8.7 percent of them (namely $k=ceil(0.087n)$, where $ceil(\cdot)$ is the ceiling function) as virus carriers. We accordingly generate the virus quantity vector $x$. We plot the successful recovery rate of $x$, the false positive rate and false negative rate as functions of $n$ in Figure 12. As $n$ increases, there are more virus carriers, and false positive rates and false negative rates are expected to increase when $m=96$ is fixed. We observe that for $n\leq 300$, these false positive rates and false negative rates stay very low. This means that, when 8.7 percent of people have viruses, using compressed sensing, the throughput of testing can grow to as much as $\frac{300}{96}\approx 3$ times. For both Bernoulli random matrices and expander graph based matrices with 7 ‘1’s in one column, we observe similar behaviors. When the percent of people carrying viruses decreases, say to $1$ percent, compressed sensing can even increase the throughput by more than 10 times.

This paper focuses on non-adaptive compressed sensing, which can have the advantange of minimizing the latency in obtaining the test results for tested persons. However, it is totally possible to increase the throughout of testing by using adpative measurements for compressed sensing, as adopted in poolingStanfordcommunity ; Shani-Narkiss2020 for group testing.