key: cord-0950218-5onwyh4b authors: Aldridge, Matthew title: Pooled testing to isolate infected individuals date: 2021-07-20 journal: 2021 55th Annual Conference on Information Sciences and Systems DOI: 10.1109/ciss50987.2021.9400313 sha: a9bf35640056cbf18f0f6cc0372a251824da8ffe doc_id: 950218 cord_uid: 5onwyh4b The usual problem for group testing is this: For a given number of individuals and a given prevalence, how many tests T* are required to find every infected individual? In real life, however, the problem is usually different: For a given number of individuals, a given prevalence, and a limited number of tests T much smaller than T*, how can these tests best be used? In this conference paper, we outline some recent results on this problem for two models. First, the"practical"model, which is relevant for screening for COVID-19 and has tests that are highly specific but imperfectly sensitive, shows that simple algorithms can be outperformed at low prevalence and high sensitivity. Second, the"theoretical"model of very low prevalence with perfect tests gives interesting new mathematical results. When testing individuals for a disease such as COVID-19, we can take a sample from each individual and test them separately; for individuals, this requires tests. Alternatively, we can pool samples together and test the pooled sample; in an ideal model, a test is positive if at least one individual in the pool is infected, and is negative otherwise. When the prevalence is low, the pooling method, known as 'group testing' or 'pooled testing', can identify all the infected individuals using fewer than tests, thereby making better use of scarce tests. (For background on group testing, see the recent survey paper [1] . ) Typically, the aim of group testing is to find every infected individual without erroneously declaring any uninfected individual to be infected. Thus the mathematical problem is typically this: Given the number of individuals and the prevalence , how many tests * are required to find the all the infected individuals, and what testing protocol achieves this. (There has also been some attention on the problem of finding a set that has a large overlap with the set of infected individuals [1] , [2] but that may not classify every single individual correctly.) However, considering applications in modern settings, especially in the current coronavirus pandemic, we propose a different goal. In a large workplace, healthcare facility, or university, for example, there may be a very limited number of tests available each day -certainly < * , so there are too few tests to accurately find every infected worker. Thus the aim should be to find as many infected individuals as possible with those limited tests, so that those individuals can be removed from the workforce to isolate at home (for example). Under this criterion, one could take samples from just a small proportion of the workforce but try to find all or almost all of the infected individuals in that subset; alternatively, one could take samples from a much larger proportion of the workforce, but be satisfied with finding a smaller fraction of the infected individuals within the subset. In order to compare different strategies, we propose using the expected number of tests per infected individual found (ETI) as the relevant figure of merit. That is, if a scheme uses an expected number E of tests and finds an expected number E of infected individuals, then the ETI is We would like this to be as large as possible. In this conference paper, we outline results for two different models, which we call the theoretical and practical models. Both models have the following features in common: • There are a large number of individuals. This number is sufficiently large that looking at mathematical results in the limit as → ∞ is useful. • The instantaneous prevalence rate ∈ (0, 1) is known. Throughout we write = 1 − . We use the i.i.d. prior where each individual is infected independently with probability . It will be useful to write = for the expected number of infected individuals. • Tests are very highly specific, in that a pool containing no infected samples is very highly likely to correctly give a negative result. We model this as the specificity being 1; thus under our model we can be certain that a positive test contains at least one infected sample. In our first model, the practical model, we attempt to give a realistic model for coronavirus testing. • The prevalence is a fixed constant as → ∞. This is because the prevalence of COVID-19 is unlikely to change depending on the size of organisation being tested. For screening of COVID-19 among asymptomatic people, values of the prevalence between 0.005 and 0.1 are likely to be of interest. • Tests are only moderately sensitive, in that pools containing one or more infected samples may give an erroneous negative result. Our model for this is to say that each test containing at least one infected sample correctly gives a positive result with probability ∈ (0, 1], independently between tests. Values of in the range = 0.6 to 0.9 are likely to be of interest for PCR tests. • As many stages of testing will be impractical and slow, we limit adaptive strategies to two stages of testing. • There are high costs for a false positive declaration (that is, wrongly declaring a noninfected individual to be infected) -for example, a healthcare worker may have to self-isolate for at least seven days for no reason. For this reason, false positive declarations will not be permitted, and we may only count individuals who we are certain are infected (under the above model assumptions). • So that individuals can be sure they have the virus before isolating, we require suspicion that an individual is infected to be definitively confirmed with an individual non-pooled test. Thus we have a first stage of pooled testing, then a second stage of limited individual testing. This is known as 'trivial two-stage testing'. (For more detailed information on the practicality of pooled testing for COVID-19, with detailed consideration of reallife issues and accurate modelling, see the forthcoming book chapter [3] . ) We give here some further justification for our consideration on trivial two-stage testing. When the sensitivity is less than 1, it is impossible to definitively rule out individuals as definitely noninfected, since any negative tests might have been false negatives. Thus the only way to definitively confirm an individual is infected is by them receiving an individual test and that test being positive. Thus the second stage in any of our algorithms must be individual tests, as pooled tests in the final stage will be worthless under the modelling assumptions and success criteria we have set out. In our second model, the theoretical model, we follow the most common set-up for theoretical results on group testingsee, for example [1] , [4] - [7] . • As → ∞, the prevalence scales like ∼ −(1− ) for ∈ [0, 1). Thus the true number of infected individuals is strongly concentrated around = ∼ . • Schemes must be fully nonadaptive, meaning all the tests are decided on in advance and are conducted in a single stage. • The criterion for success is that every individual declared to be infected is indeed infected. However, we do allow failure to meet this criterion, provided that the probability of such failure tends to 0 as → ∞. • The testing procedure is perfect. Any pool containing no infected individuals always gives a negative result, and any pool containing one or more infected individuals always gives a positive result. We consider trivial two-stage algorithms with two parameters, and , as studied in [8] , [9] for perfect noiseless tests. In the first stage, any individual that is sampled is sampled in pools, and each pool samples individuals. Typically is very small (1 and 2 are the most common values, but 3 and 4 are sometimes used). For individual non-pooled testing, we take = 1, = 1, and don't require a second stage. For all other sensible parameters we have > 1, and in the second stage we retest any individuals that were positive in all pooled tests. (Although we don't consider it here, it may be worthwhile to retest individuals whose pooled tests were mostly -but not entirely -positive. We intend to study this in future work.) Setting = 1, > 1, gives the simplest pooled algorithm, named Dorfman's algorithm, after Robert Dorfman's original group testing procedure [10] . Here, the sampled individuals are split into pools of size . If a pooled test is negative, it is assumed that all those individuals are noninfected. (This is not certain to be correct, but is strong evidence that retesting them is a poor use of resources compared with testing a new untested pool.) If the pooled test is positive, then those individuals are individually tested in the second stage. For general , , the most mathematically convenient method is to fix the number of individuals ≤ to be sampled, then to choose a testing strategy uniformly at random, subject to each test having weight and each individual having weight . This requires to be divisible by and , but since these are typically small, this is not much of a restriction. In practice, it can sometimes be more convenient to use a hypercube design. We explain this first by considering the case = 2, where we also use the term grid design. Here, we take individuals where is a multiple of 2 . We imagine the individuals placed on square grids of size × . Then each grid corresponds to 2 tests: tests each pooling the individuals in one row, and tests each pooling the individuals in one column. The grid design can be better than the random design for small (although the asymptotic performance is the same). However, 2 can be quite large, so the divisibility issue can be awkward. The grid design was studied recently by Broder and Kumar [9] . For > 2 the hypercube design requires = −1 for some integer > 1. We place each individuals in an × ×· · ·× -dimensional hypercube. Each test corresponds to one of the ( − 1)-dimensional 'slices' of the hypercube. The case = 3, = 9, with a 27 individuals in a 3 × 3 × 3 hypercube was prominently studied in [11] -this has nine 2-dimensional 3 × 3 slices: three front to back, three left to right, and three top to bottom. With a hypercube design, the divisibility restrictions are much stronger, but the extra structure can be more convenient for a laboratory to carry out. Theorem 1: In the practical regime, the above algorithm has ETI Proof: We give a brief justification of this result. The result for an individual test is clear: the test is positive if the individual is infected (with probability ) and the test correctly gives a positive result (with probability ) for an ETI of 1/( ). Now consider a trivial two-stage algorithm with parameters and .The number of first-stage tests-per-individual is / . An individual could potentially be retested in the second stage if it is either infected, with probability , or it is not infected but all of its tests has one of the other −1 individuals infected, with probability asymptotically (1 − −1 ) . (This would be exactly true if the test results were independent, but if an individual shares more than one pool with our given individual, that would not be the case. However, we prove in our full paper that the equation is asymptotically accurate in spite on the dependences.) If one of these criteria is fulfilled, the individual will be tested again if all tests correctly give a positive result, with probability . Hence the expected number of second-stage tests per individual is ( + (1 − −1 ) ). An infected individual is found if it is indeed infected, with probability , all pooled tests are correctly positive, with probability , and the individual test is correctly positive, with probability . All together, this is +1 . Finally, the ETI is the ratio of these two terms. Tables I and II shows the expected tests per infected individual found (ETI) for various plausible values of the sensitivity and the prevalence . The numbers in brackets are optimal values of ( , ), determined numerically. Note that (1, ) denotes Dorfman's simple pooling algorithm. Note that the pooled schemes are better than individual testing for all values of the parameters. The gain is biggest when the prevalence is low and the sensitivity is high. Dorfman's algorithm ( = 1) is best for moderately high prevalence or moderately low sensitivity. For a similar analysis of Dorfman's algorithm that also allows for imperfect specificity, see [3] . Recall that in the theoretical model all tests are perfectly accurate, and the number of infected individuals is very close to = , which scales like ∼ with ∈ [0, 1). Our result (stated slightly informally in this conference paper, with formalities to follow in a later paper full paper later) is the following. Proof: We give a brief justification for this result, again with a full formal proof to appear in a later paper. We use similar techniques to those used in [2] for the 'find one defective item' and 'approximate recovery' problems. First, ETI full is the ETI achieved when using * = max log 2 , 1 ln 2 ln tests to find all infected individuals [6] , [7] . Suppose we instead have = * tests, where < 1. We 'cut our losses' by immediately discarding all but individuals. This subset will have very close to infected individuals, and we can find all of them in max log 2 , tests, as required. Second, ETI saff is achieved by an idea inspired by the SAFFRON scheme of [12] (see also [1] ). Suppose for the moment that we have = 2 log 2 / tests. Take a subset of / = 1/ items, and note that it contains exactly one infected individual with probability Number the individuals from 1 to / , and let v ∈ {0, 1} be the number written in binary, where the length is = log 2 / = /2 (up to rounding). Further let v {0, 1} be v with the 0s and 1s flipped. Then individual is placed in the tests that correspond to the positions of the 1s in the vector (v v ) ∈ {0, 1} 2 = {0, 1}. Note that this means each item is in exactly = /2 of the 2 = tests. If the set contains zero infected individuals, then all tests will be negative, and we can rule all the individuals to be noninfected. If exactly one of the individuals is infected, then exactly = /2 of the tests will be positive, and the first /2 test outcomes will 'spell out' in binary the number of the infected individual. If there are two or more infected individuals, then strictly more than = /2 of the tests are positive, and we find none of the expected items. Thus with our tests we find one infected individual if and only if the set contains exactly one infected individual, with is an expected number of e −1 . Hence the ETI is Given the actual value of we have, we split it into segments of size 2 log 2 / , and run the SAFFRON-inspired algorithm separately on each, obtaining the same ETI. For a given parameter , we choose whichever out of the 'full' and 'SAFFRON' methods gives the best ETI. This proves the theorem. Note that the 'full' algorithm tests fewer individuals, but seeks to find every infected individual who was tested. In contract, the SAFFRON-inspired algorithm tests more individuals, but only expects to find e −1 /(1−e −1 ) = 58% of those infected. One convenient way of interpreting Theorem 2 is by considering the rate of group testing [1] , [4] . Here, we define the rate to be where ( ) is the binary entropy. Standard information theoretic conditions tell us that the rate is bounded above by 1; we want the rate to be as close as possible to 1, the higher the better. We can rewrite Theorem 2 as follows. . This is illustrated in Fig. 1 . Note that, for large , the SAFFRON method gives a higher rate than full , the usual rate for finding all defectives in the usual full group testing problem. Group testing: an information theory perspective On the all-or-nothing behavior of bernoulli group testing Group testing algorithms: bounds and simulations Performance of group testing algorithms with near-constant tests per item Information-theoretic and algorithmic thresholds for group testing Optimal group testing Conservative two-stage group testing A note on double pooling tests The detection of defective members of large populations A pooled testing strategy for identifying SARS-CoV-2 at low prevalence Saffron: A fast, efficient, and robust framework for group testing based on sparsegraph codes The author thanks David Ellis for helpful comments and useful advice.This work was supported by UK Research and Innovation under the project 'Analysing group-testing algorithms for Covid-19 surveillance and case-identification in UK schools, universities and health and social care settings.'