key: cord-0525616-o1ijoomx
authors: Yi, Jirong; Cho, Myung; Wu, Xiaodong; Xu, Weiyu; Mudumbai, Raghu
title: Error Correction Codes for COVID-19 Virus and Antibody Testing: Using Pooled Testing to Increase Test Reliability
date: 2020-07-29
journal: nan
DOI: nan
sha: 15f45618b6c81c970ef8eba3428657efdc8abcaa
doc_id: 525616
cord_uid: o1ijoomx

We consider a novel method to increase the reliability of COVID-19 virus or antibody tests by using specially designed pooled testings. Instead of testing nasal swab or blood samples from individual persons, we propose to test mixtures of samples from many individuals. The pooled sample testing method proposed in this paper also serves a different purpose: for increasing test reliability and providing accurate diagnoses even if the tests themselves are not very accurate. Our method uses ideas from compressed sensing and error-correction coding to correct for a certain number of errors in the test results. The intuition is that when each individual's sample is part of many pooled sample mixtures, the test results from all of the sample mixtures contain redundant information about each individual's diagnosis, which can be exploited to automatically correct for wrong test results in exactly the same way that error correction codes correct errors introduced in noisy communication channels. While such redundancy can also be achieved by simply testing each individual's sample multiple times, we present simulations and theoretical arguments that show that our method is significantly more efficient in increasing diagnostic accuracy. In contrast to group testing and compressed sensing which aim to reduce the number of required tests, this proposed error correction code idea purposefully uses pooled testing to increase test accuracy, and works not only in the"undersampling"regime, but also in the"oversampling"regime, where the number of tests is bigger than the number of subjects. The results in this paper run against traditional beliefs that,"even though pooled testing increased test capacity, pooled testings were less reliable than testing individuals separately."

In the absence of a vaccine to the SARS-CoV-2 coronavirus, 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 [1, 2] 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 [3] of various medical resources including tests [4] . Pooled sample testing has been proposed as a method for increasing the effective capacity of existing testing infrastructure using the classical method of group testing. However, group testing requires highly accurate test results to be effective; a single false negative test result can potentially cause many infected individuals to be incorrectly diagnosed which could lead to further propogation of the virus. Of couirse, test accuracy can be increased by testing each sample multiple times, but this defeats the main purpose of group testing which is to reduce the number of tests.

In this paper, we propose a more sophisticated version of pooled sample testing that also has the ability to increase the diagnostic accuracy of existing tests even if the individual tests are not highly accurate without requiring an increase in the number of tests. In other words, our proposed method of pooled sample testing can deliver highly accurate diagnostic results for individuals with very low rates of false positives and false negatives, even if the tests themselves are highly errorprone. Our method achieves this using mathematical ideas from the theories of compressed sensing and error-correction coding.

The most common tests for the COVID-19 virus 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-PCR 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) [5] or recent innovation digital PCR (dPCR) also allows the quantification of the RNA i.e. it produces an estimate of the quantity of the RNA material present in the sample [6] .

Some researchers [7] 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 [8] and other DNA amplification methods.

The PCR-based virus tests are highly sensitive (i.e. have low rates of false negatives) as well as specific (i.e. successfully differentiates between the Covid-19 virus and other pathogens and therefore shows low false positive rates). However, pooled sampling methods require sample dilution and additional preparation that may potentially result in degraded sensitivity as well as specificity.

In addition to tests for an active COVID-19 viral infection, there has also been interest in testing for the presence of antibodies to the COVID-19 virus. The antibody tests might show whether a person in the past was infected with the COVID-19 virus. Virus and antibody tests complement each other.

Antibody tests typically use blood samples (unlike virus tests that use nasal swabs), and can use an enzyme immunoassay process such as ELISA (enzyme-linked immunosorbent assay) [9] . ELISA's tests typically show high sensitivity; however, some of the early antibody tests that were commercially introduced for COVID-19 may have issues with selectivity [9] .

One simple method to increase the effective testing capacity is by testing pooled samples of a number of test subjects collectively instead of testing samples from each person individually. In a simple version of this "group testing" [10] idea, a single negative test result on a pooled sample immediately shows that all individuals in that pool are infection-free. Thus, individual tests only need to be performed when a specific pooled test sample yields a positive test result. When the rate of infection in the population is low, this method allows us to reduce the total number of tests per subject so the throughput of the existing testing infrastructure is increased [11] . Pooling tests have been successfully used for diagnostic testing for infectious diseases in the past [12, 13] .

The current testing bottleneck 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 [14] [15] [16] into adapting pooling methods similar to [10] for Covid-19 testing. Preliminary studies on the COVID-19 virus also show that pooling samples [17] can be effective with existing RT-PCR tests.

In a recent work [18] , we proposed a different approach based on the compressed sensing theory [19] [20] [21] for detection of viruses and antibodies using quantitative PCR test results (for example, from qPCR) for pooled sample testing. A compressed sensing approach for virus detection was also reported in [22] . The compressed sensing method can potentially achieve higher efficiencies and better performance than group testing. In fact, group testing can be seen as a special case of the more general compressed sensing method, where the test result is more than just binary.

The basic idea behind the compressed sensing pooled sampling method is to prepare a set of mixtures of several individuals' swab specimens, where the mixtures are carefully chosen to be different from each other in such a way that, under the assumption that only a small fraction of the individual samples have non-zero viral RNA, each individual's diagnostic status can be determined by testing a number of mixtures much smaller than the number of individuals.

Our simulations in [18] show that the compressed sensing method is effective in achieving a significant increase in testing capacity. In this paper, we take this idea further and show that the compressed sensing method can also increase the accuracy of diagnostic tests by taking advantage of redundancy in the pooled sample test results to correct for some number of incorrect test results.

To Let p denote the infection rate in the population:

While the information vector b can be represented by the N information bits b i , i = 1 . . . N , an elementary result from information theory shows that the entropy of the information vector is much smaller than N bits, when the infection rate is low:

where we assumed that each individual in the population independently has a probability p of being infected. The entropy h(b) represents the number of bits required to losslessly represent the information in b. Thus, (1) can be interpreted as a theoretical justification for pooled sample testing: in theory, we only need tests that deliver a total of N t = h(b) bits of information in order to fully recover the infection status b i of every individual in the pool. If the tests are binary i.e. only indicate positive/negative infection status and are completely error-free, then in theory we can fully diagnose all N individuals with as few as h(b) such tests. If the test provide richer non-binary results (e.g. quantification of viral RNA concentration from RT-qPCR tests), in theory the number of tests needed may be much smaller than h(b).

In this sense, pooled sample testing methods such as the compressed sensing method, can be thought of as data compression codes. However, the tools of information theory allow us to design codes that have much more powerful capabilities than just lossless data compression. In particular, we can generalize from lossless data compression to codes that can perform error corrections. In the context of virus testing, this means a class of pooled sample testing techniques that can achieve accurate diagnostic results even with tests that are individually highly error-prone.

We show in this paper a class of pooled sample testing methods that do exactly this: increased diagnostic accuracy (error correction) without requiring an increased number of tests. In other words, we demonstrate a method of pooled sample testing that requires no larger number of tests in aggregate, yet delivers more accurate diagnostic results than separately testing each individual. In this paper, our focus is not on increasing test capacity by reducing the number of required tests, but is instead on purposefully creating pooled samples to increase test reliability or to increase tests' robustness against test errors. There are several recognizable distinctions between this work on error correction and recent group testing/compressed sensing works for virus/antibody detection: 1) The main purpose of error correcting pooled testing is to increase test reliability, not to reduce required test numbers as in group testing/compressed sensing, even though this paper's proposed approach provides error correction capability also in the case of using a reduced number of tests; 2) In our proposed error correction codes using pooled testing, the testings can operate in an "oversampling" regime where the number of performed tests is larger than the number of subjects; 3) In addition, in error correction codes using pooled testing, we do not necessarily require the prevalence to be low or require the involved signal to be sparse: the signal considered can be a fully dense signal.

We remark that the results in this paper run against traditional wisdoms that grouping samples together for testing would lower test accuracy or reliability compared with individual separate testings, due to factors such as sample dilutions and pipetting errors, even though pooled testings could increase test capacity. Our results show this conventional wisdom can be wrong, and, in some cases, we can purposefully perform pooled testing to significantly increase, rather than decrease, test accuracy or reliability.

Our work is most related to [20] , one of the seminal papers in compressed sensing, which uses linear programming to perform decoding under channel errors. Compared with [20] , in this paper, we purposefully design pooled testing matrices with '0' or '1' elements to increase test reliability, instead of being given a particular channel (linear transformation) as in [20] . In addition, we are working with non-negative signals, which bring additional structures for sensing and inference [23, 24] . Compared with recent works which aim to boost test robustness against noisy measurements in group testing and compressed sensing [25, 26] , our work considers not only "undersampling" regime, but also "oversampling" regime; not only sparse signals, but also dense signals. We purposefully design/use pooled testing to increase test reliability, instead of trying to increase the reliability of group testing/compressed sensing used in the "undersampling" regime mainly for increasing test capacity.

In this section, we will give a mathematical formulation of performing robust virus testing through error correction code. We will focus on describing the idea of error correction code for virus testing through quantitative pooled testing, even though the idea of error correction code can be extended to traditional qualitative pooled testing. We also focus our description on virus testing, and the mathematical principles extend to antibody testing.

The quantitative modeling of the pooled testing problem requires the application of real-time quantitative polymerase chain reaction (real-time qPCR) which is built on top of the PCR and conducted in a thermal cycler. The real-time qPCR can give quantitative measurements of the amplified DNA copies by using fluorescent reporters in multiple PCR cycles. In each PCR cycle, the DNA template can be doubled, and the strength of the signal from fluorescent reporter is proportional to the number of amplified DNA molecules. One can use the threshold cycle C t , which is defined as the number of cycles required for the fluorescent signal to cross a threshold, to determine the quantity of DNAs in the qPCR.

Assume that we get n samples for n subjects with one sample for each, and we will perform m tests to determine the quantities of COVID-19 viruses in these samples. We denote by x ∈ [0, ∞) n the quantity of the DNA that can be generated from the subjects' viral RNAs. In each of the m tests, we will create a pooled sample by mixing the samples from multiple subjects. We use a matrix P ∈ {0, 1} m×n to denote the participation of n samples in m tests, i.e. the sample of the

, and it will not be used in the j-th test if P ij = 0. This means that the number of 1's in the i-th column of P is the number of tests that the sample of i-th subject will participate in. We will model the allocation of the subjects' samples by a matrix W ∈ [0, 1] m×n , and each W ij is the fraction of the j-th sample used in the i-th test, meaning the sum of each column in W is no bigger than 1. With those setup above, we get a measurement matrix as

where represents the Hadamard multiplication. The corresponding m mixed samples will go through m quantitative PCR to quantify the amount of DNAs. Due to potential background noises and gross errors caused by factors such as dilutions, sample and reagent contamination, and operational mistakes, the final quantitative measurements y ∈ R m from the real-time PCR can be modeled as

where f (·) : R n → R m , v ∈ R m , and e ∈ R m represent the true signal, the observation noise, and the possible gross error. For example, in the ideal case f (Ax) = Ax, we have

Our goal is to recover the sample measurements x ∈ [0, ∞) n for n subjects from m tests measurements y ∈ R m under possible outliers.

In practice, according to [18, 28] , a measurement matrix from the expander bipartite graph can achieve good practical performance with theoretical justifications, and we can specify the matrix P as such matrices, i.e., a sparse binary matrix. The sparsity of matrix P is determined by taking practical considerations such as reducing the operational complexity of pooling, and reducing the risk of dilution resulting from pooling. Due to the above constraints, one can design the matrix P based on bipartite expander graphs [29, 30] . Though one has the freedom to design the allocation matrix W , one can use an even-allocation scheme. Thus, if the j-th subject is involved in c tests, then the j-th column of P has only c 1's, and the j-th column of A will have nonzero values at the corresponding locations being 1 c . The low prevalence among population in practice allows us to assume that the signal x ∈ [0, ∞) n is sparse or approximately sparse, i.e., most of its entries are zero (or extremely close to zero). We also assume that that the gross error v ∈ R m is sparse, due to relative rareness of operational mistakes, chemical reaction failure, and sample dilution.

Under all these assumptions, we can formulate the problem of recovering x ∈ R n from y ∈ R m (we remark here that m can be bigger than n) as

where z 0 is the number of nonzero elements in z, λ ∈ R is a tuning parameter for controlling the tradeoff between z 0 and Az − y − u 0 , the u 2 is the 2 norm of u, ≥ 0 is a parameter controlling the tolerance for noise, and the x ≥ 0 means that every element of x is nonnegative. In (5), we used z as an estimate for x and u as an estimate for v, and y − Az − u is an estimate for e. Due to combinatorial nature of · 0 , solving (5) is sometimes computationally challenging, and the norm · 1 can be used as a relaxation technique instead in practice to achieve good performance without much computational complexity [18, 28] . Thus, we can reformulate (5) as

where z 1 is the sum of the absolute value of all the elements in z, and we will refer (6) as 1 − 1 minimization. Once the estimate for x is obtained, If z j ≥ τ where τ is the threshold value, then we claim the j-th subject is infected and tests "positive"; otherwise, we declare "negative" test result for the subject.

There is a large volume of literature which proposed algorithms for solving (6) under certain conditions such as the restricted isometry property and the null space condition. These ideas range from using off-the-shelf softwares such as CVX [31] , to algorithms specifically designed for 1 − 1 minimization such as the homotopy method and iteratively reweighted least square algorithm [28] . In this paper, we will use the CVX [31] .

In this section, we conduct numerical experiments in order to evaluate the performance of our proposed method, which is the error correcting pooled testing introduced in (6). We focus on models for COVID-19 virus testing. In pooled testing, we use Bernoulli matrices each element of which is either 1 or 0. The numbers of people tested are set to 25 and 40, i.e., n = 25 and 40. We consider a scenario where k out of n people have COVID-19 virus by setting randomly chosen k elements in x ∈ R n to be positive and other n − k elements to zero. The value of each of the non-zero elements in x is chosen uniformly at random from [5, 10] . We consider the sparsity level k from 1 to 6 in the simulations.

In pooled testing, the Gaussian noise vector v in (4) is generated i.i.d. according to the Gaussian distribution N (0, σ 2 ), where the noise level σ 2 is varied from 5e-1 to 2e0. For the outliers, we generate the sparse outlier vector e as in (4) by having each element of e be a non-trivial (non-zero) outlier with probability P out . If an outlier indeed happens at the i-th measurement, we generate the outliers for the i-the measurement in the following way: 1) If the corresponding (Ax) i is positive, with 95% probability, we set the outlier e i as −(Ax) i and reset v i = 0 such that y i = 0 (this is to simulate a "false negative" measurement); with the other 5% probability, we set the outlier e i as 5 × q + 2, where q follows the standard Gaussian distribution N (0, 1), and keep the originally generated v i ; 2) if the corresponding (Ax) i is equal to 0, we will set e i as 5 × |q| + 2, where q follows distribution N (0, 1), and keep the originally generated v i . If there is no non-trivial outlier for the i-the measurement, and (Ax) i = 0, we set v i = 0 and e i = 0, to simulate this test as a "negative" test revealing 0 virus. Since the measurement results y must be a non-negative vector, for the i-th test, we let y i = max{(Ax) i + e i + v i , 0} to make sure the generated measurement y be a non-negative vector (to avoid randomly generated e and v being too small dragging (Ax) i +e i +v i to negative region). In the numerical evaluations, we respectively consider three probabilities of the outlier error, denoted by P out , to be 1%, 5%, and 15%. For pooled testing, we use (6) to recover x, and use threshold τ = 1 to decide whether a subject tests positive or negative. We introduce this threshold to suppress the noise in x may caused by outlier error and Gaussian noise.

We compare the pooled testing against the individual testing model, where the individual samples of subjects are tested separately (possible multiple times). In the individual testing, the i-th test is modeled as

where y i is i-th measurement result, mod (·, ·) means module operation, e i is the outlier, and v i is Gaussian noise following distribution N (0, σ 2 ) . We generate the noises and outliers in the same way as described for the pooled testing, except for in individual testing, we generate outliers and noises based on x mod (i−1,n)+1 instead of (Ax) i . For example, for n = 25 and i = 27, y i is the measurement result for the 2nd subject (this subject has been tested once already in the 2nd test), and the outlier and noise simulated for the 27-th test is randomly generated based on x 2 . In individual testing, if m < n, there must be some subjects who do not get qPCR tested at all; and in those cases, and for our simulations, we consider these subjects as COVID-19 negative. Additionally, in individual testing, if a subject is tested multiple times, and as long as one result is identified as being COVID-19 positive, we consider the subject as COVID-19 positive. This comes from the motivation of not missing COVID-19 positive cases. The number of measurements, denoted by m, is varied from 10 to 50 in n = 25 and from 10 to 80 in n = 40. Thus, in our individual testing scenario, the maximum number of tests for a subject is two.

For both the pooled testing and the individual testing, we run 100 random trials for each parameter setup, and record the False Negative Rate (FNR) and the False Positive Rate (FPR), which are computed on average out of 100 trials as follows: The FPR can be an important concern in COVID-19 antibody testing, while the FNR is an important concern in COVID-19 virus testing. Lower both FPR and FNR represent the better testing performance in detecting virus and checking antibody. Additionally, if one method (say, Method A) achieves the same FNR and FPR but with a smaller number of tests than another method (say, Method B), then we deem Method A better than Method B. This is because the number of tests is related to the throughput of testing, and a high-throughput testing allows us to increase the capacity of testing in a limited time. Therefore, we will compare the FNR and the FPR of the pooled testing against those of the individual testing under various setups of parameters including the number of tests, noise levels and probability of outlier occurrences.

In Figures from 2 to 5, (a), (b) , and (c) show the FNR of the pooled testing and the individual testing in log-scale with different probabilities of outlier error varied from from 1% to 15%, and (d), (e), and (f) describe the corresponding FPR. Here, the number of people tested is set to 25, i.e., n = 25, and the number of people having COVID-19 virus is varied from 1 to 6 out of 25, i.e., k = 1, ..., 6. The noise level is fixed to 1e0. From various simulations as shown in Figures from 2 and 5, the pooled testing lowers both the FNR and the FPR as the number of measurements increases. This is because as the number of measurements increases, we can recover more accurate results x and e via 1 − 1 minimization introduced in (6). Unlike the pooled testing, the individual testing can reduce the FNR as the number of measurements increases, while there is a slight increase in FPR at the same time. This is because the individual testing diagnoses the COVID-19 virus test "positive" once we have one positive test result among multiple tests.

From these various simulation results with different probabilities of outlier errors, in many cases, we demonstrate that the pooled testing can simultaneously have (significant) lower FNR and FPR than those of the individual testings. In a limited number of cases under m < n, the individual testing provides lower (although not significantly lower) FPR than that of the pooled testing, because only a few people are tested under individual testing, and fewer false positive mistakes are made (recall that the tested subjects are assumed to be diagnosed as "negative" ) Additionally, since, under m < n, there are simply untested subjects in individual testing, and, in general, a false negative outlier can have more impact on an individiual, the individual testing has relatively higher FNR across all the parameter setups of m and n.

Furthermore, we demonstrate the outperformance of the pooled testing in the COVID-19 testing against the individual testing with more test subjects. Figures from 6 to 9 show the comparison in both FNR and FPR as the number of measurements increases, between the pooling testing and the individual testing, for n = 40. In Figures from 6 to 9, (a), (b), and (c) show the FNR of the pooled testing and the individual testing with different probabilities of outlier error from 1% to 15% and different sparsity level from k = 1 to k = 6. Correspondingly, in Figures from 6 to 9, (d), (e), and (f) indicate the FPR of the both testing. Through the simulation results shown in Figures from 6 to 9, with even larger n, it is shown that the pooled testing can identify people having COVID-19 virus more accurately than the individual testing with small number of measurements. Therefore, the pooled testing can simultaneously have higher throughput and higher accuracy than the individual testing.

In order to check the impact of Gaussian noises on the detection performance, we further run simulations by varying noise levels. We vary the Gaussian noise level from 5e-1 to 2e0. We randomly choose 100 trials and record the FNR and the FPR of the pooled testing and the individual testing. Here in the simulations, we set the sparsity level to 3, i.e., k = 3, and consider the two probability of outlier error 5% and 15%. 

In this subsection, we further run simulations by varying the sparsity level, i.e., the number of people having COVID-19 viruses. For these simulations, we set the noise level to 5e − 1 and the probability of outlier error P out to 0.01. We vary the sparsity level k from 1 to 6. Figures 14 and 15 show the FNR and FPR of both the pooled testing and individual testing with different sparsity level when n = 25 and n = 40 respectively.

The overall takeaway from the Figures 6 to 9 is that the pooled sampling method achieves significantly higher accuracy compared to individual testing. Also in absolute terms, the pooled sampling method is able to provide accurate diagnostic results even when individual test results are highly noisy. Some specific observations from the simulations are as follows.

• In most of the simulations, the pooled sampling method simultaneously achieves lower FPR and FNR than individual sampling. We did not observe even a single instance when the opposite was true i.e. where individual testing outperformed the pooled sampling method in both FPR and FNR. • The FPR for the individual sampling method actually gets worse with increased number of measurements. This is simply an artifact of the individual testing method in conservative strategy in order to prevent miss in COVID-19 positive case. The overall accuracy of the individual testing method does always improve with increased number of measurements when FNR is taken into account along with FPR. • For the pooled sampling method, both FPR and FNR always monotonically decrease with increased number of measurements. (The apparent non-monotonicity in e.g. 

Interrupting transmission of COVID-19: lessons from containment efforts in Singapore

COVID-19 epidemic in Switzerland: on the importance of testing, contact tracing and isolation

Critical supply shortages the need for ventilators and personal protective equipment during the Covid-19 pandemic

Fair allocation of scarce medical resources in the time of Covid-19

A novel method for real time quantitative RT-PCR

Quantification of mRNA using realtime RT-PCR

Rapid detection of novel coronavirus (COVID-19) by reverse transcription-loop-mediated isothermal amplification

LAMP-Seq: population-scale COVID-19 diagnostics using a compressed barcode space

Enzyme immunoassay (EIA)/enzyme-linked immunosorbent assay (ELISA)

The detection of defective members of large populations

Boosting test-efficiency by pooled testing strategies for SARS-CoV-2

High-throughput pooling and real-time PCR-based strategy for malaria detection

Evaluation of the pooling of swabs for real-time PCR detection of low titre shedding of low pathogenicity avian influenza in turkeys

Evaluation of group testing for SARS-CoV-2 RNA

Efficient and practical sample pooling for high-throughput PCR diagnosis of COVID-19

Sample pooling as a strategy to detect community transmission of SARS-CoV-2

Evaluation of COVID-19 RT-qPCR test in multi-sample pools

Low-cost and high-throughput testing of COVID-19 viruses and antibodies via compressed sensing: system concepts and computational experiments

Near optimal signal recovery from random projections: universal encoding strategies

Decoding by linear programming

Compressed sensing

A compressed sensing approach to group-testing for COVID-19 detection

Sparse recovery of nonnegative signals with minimal expansion

A unique nonnegative solution to an underdetermined system: From vectors to matrices

Noisy pooled PCR for virus testing

Practical high-throughput, nonadaptive and noise-robust SARS-CoV-2 testing

Real-time PCR handbook

A mathematical introduction to compressive sensing

Efficient compressive sensing with deterministic guarantees using expander graphs

Efficient and robust compressed sensing using high-quality expander graphs

CVX: Matlab software for disciplined convex programming