key: cord-168557-xt4bf31r authors: Yi, Jirong; Cho, Myung; Wu, Xiaodong; Mudumbai, Raghu; Xu, Weiyu title: Optimal Pooling Matrix Design for Group Testing with Dilution (Row Degree) Constraints date: 2020-08-05 journal: nan DOI: nan sha: doc_id: 168557 cord_uid: xt4bf31r In this paper, we consider the problem of designing optimal pooling matrix for group testing (for example, for COVID-19 virus testing) with the constraint that no more than $r>0$ samples can be pooled together, which we call"dilution constraint". This problem translates to designing a matrix with elements being either 0 or 1 that has no more than $r$ '1's in each row and has a certain performance guarantee of identifying anomalous elements. We explicitly give pooling matrix designs that satisfy the dilution constraint and have performance guarantees of identifying anomalous elements, and prove their optimality in saving the largest number of tests, namely showing that the designed matrices have the largest width-to-height ratio among all constraint-satisfying 0-1 matrices. In the current COVID-19 pandemic, before effective vaccines are introduced, large-scale shutdowns can be safely ended if a systematic "test and trace" program [1, 2] is adopted to contain the spread of the virus. Widespread availability of mass diagnostic testing is needed for re-opening economy, school and social activities. However, most countries including the US are currently experiencing a scarcity [3] of various medical resources including tests [4] , and the test throughput or capacity can be limited. 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 or newly introduced compressed sensing techniques for virus testing [5] [6] [7] [8] [9] [10] [11] using the RT-qPCR (real-time Quantitative Polymerase Chain Reaction) tests. However, there is potentially a dilution problem associated with group testing when samples are pooled together. When a positive sample is mixed with multiple negative samples, the concentration of the substances to be tested will be reduced, sometimes below the detection threshold of adopted testing technologies. This limits the number of samples that can be pooled together. Recently the FDA of the US has authorized pooled testings for COVID-19 infection by Quest Diagnostics, and another pooled testing from the LabCorp. Possibly partially due to dilution concerns, the FDA's emergency use authorizations (EUA) for pooled testing allows pooling to no more than 4 specimens for the test developed by Quest Diagnostics, and allows pooling to no more than 5 specimens for the test from the LabCorp [12] [13] [14] [15] [16] [17] [18] [19] . Considering the dilution constraint, we ask the following question, "What is the best pooling design which maximizes test throughput while having a required capability of identifying infected samples, and satisfying the dilution constraint of pooling no more than r > 0 specimens in each pool?" In this paper, we give explicit designs for such matrices, and prove their optimality in maximizing test throughput under dilution constraint. We remark that, when there is no dilution constraint, maximizing test throughput under a given infection-identifying capability reduces to a traditional group testing problem. In this paper, we focus on non-adaptive group testings which deal with n test subjects, and perform m nonadaptive (pooled) tests. Non-adaptive testing has the advantage of reducing the latency of an individual's test because one can infer infection statuses of a group of subjects in a single RT-qPCR run. We require a pooling matrix design using which we are able to infer the correct infection status for each of these n people, whenever there are no more than k people infected among them. It is well-known that the pooling strategy can be represented by an m × n matrix A which elements being '0' or '1'. The j-th (1 ≤ j ≤ n) person's sample is part of the i-th pool (test, 1 ≤ i ≤ n) if and only if the element of A in its i-th row and j-th column is '1', namely A i,j = 1. Moreover, as mentioned above, we require that each row of the pooling matrix have at most r 1's. Given an identification capability parameter k, we would like to design a group testing matrix of dimension m × n such that n m is maximized. In this short paper, we focus on k = 1, but the results in this paper can be extended to larger k using similar techniques. Proof. We first prove that there are no 'good' group testing matrices for which n m > r+1 2 . To make sure that we can correctly infer the correct status of each of the n elements whenever there is no more than k = 1 positive element, the columns of this matrix must be non-zero columns and must be distinct from each other. Suppose that we have a 'good' group matrices, which has n 1 columns with a single '1', n 2 columns with two '1's, n 3 columns with three '1's, ...., and n m columns with m '1's. Then we have m i=1 n i = n. Moreover, for every 1 ≤ i ≤ m, we have In addition, the total number of '1's in the matrix is given by T = m i=1 i × n i . Since the number of '1's in each row is no more than r, we have We now argue that n cannot be bigger than m × r+1 2 . Suppose instead that n > m × r+1 2 . Since there are at most m columns with a single '1', then there must be at least columns which have at least two '1's. We let l be the largest integer such that l i=1 m l ≤ n. Then we have However, this contradicts with T ≤ rm. So we must have n m ≤ r+1 2 . Now we show an explicit construction of a m × n 'good' group testing matrix with m = r and n = r(r+1) . This matrix has m = r distinct columns with a single '1' (part of this matrix making an r × r identity matrix), and m 2 = r 2 = r(r−1) 2 distinct columns with two '1's in each column. So in total there are r + 2 × r(r−1) 2 = r + r(r − 1) = r 2 '1's in this matrix. By the symmetry of this matrix's construction, each row of this matrix has exactly r 2 × 1 r = r '1's in each of its rows. 3 Examples for FDA approved Pooling Size r = 4 or r = 5 From the result in the last section, we have the following optimal design for r = 4: It would be interesting to extend this work to adaptive testing, and compressed sensing with dilution constraints [20] . 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 The detection of defective members of large populations Evaluation of group testing for SARS-CoV-2 RNA. medRxiv Efficient and practical sample pooling for highthroughput PCR diagnosis of COVID-19. medRxiv 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 A compressed sensing approach to group-testing for COVID-19 detection Office of The Commissioner. Coronavirus (COVID-19) update: facilitating diagnostic test availability for asymptomatic testing and sample pooling Office of The Commissioner. Coronavirus (COVID-19) update: FDA authorizes first diagnostic Test for screening of people without known or suspected COVID-19 infection Office of The Commissioner. Coronavirus (COVID-19) update: FDA issues first emergency authorization for sample pooling in diagnostic testing FDA authorizes Quest Diagnostics COVID-19 diagnostic testing for specimen pooling for emergency use FDA opens door to 'batch testing' for COVID-19 with new green lights for Quest Diagnostics High-throughput pooling and real-time PCR-based strategy for malaria detection LabCorp COVID-19 test gets 1st FDA OK for asymptomatic screening SARS-CoV-2 RNA, qualitative Real-Time RT-PCR Compressive sensing over graphs