key: cord-0615797-mt6gr5zh
authors: Joly, Emilien; Mallein, Bastien
title: A tractable non-adaptative group testing method for non-binary measurements
date: 2020-12-16
journal: nan
DOI: nan
sha: 97b0bf313d4ddca83031c51029dcbf1b48b112e4
doc_id: 615797
cord_uid: mt6gr5zh

The original problem of group testing consists in the identification of defective items in a collection, by applying tests on groups of items that detect the presence of at least one defective item in the group. The aim is then to identify all defective items of the collection with as few tests as possible. This problem is relevant in several fields, among which biology and computer sciences. In the present article we consider that the tests applied to groups of items returns a emph{load}, measuring how defective the most defective item of the group is. In this setting, we propose a simple non-adaptative algorithm allowing the detection of all defective items of the collection. This method improves on classical group testing algorithms using only the binary response of the test. Group testing recently gained attraction as a potential tool to solve a shortage of COVID-19 test kits, in particular for RT-qPCR. These tests return the viral load of the sample and the viral load varies greatly among individuals. Therefore our model presents some of the key features of this problem. We aim at using the extra piece of information that represents the viral load to construct a one-stage pool testing algorithm on this idealized version. We show that under the right conditions, the total number of tests needed to detect contaminated samples can be drastically diminished.

The group testing problem consists in identifying a subset of defective items among a larger set by using tests on pools of items answering the question "Does this pool contains at least one defective item?". This problem has a long history, and appeared several times in different fields of medical biology [Dor43, Tho62, TM06, FHG + 12] and computer sciences [MTT08, IKWO18, AJS19] . It has also been the subject of an important mathematical literature, which studied optimal algorithms for the detection of defective items with minimal use of tests, which are considered a limiting resource. Those algorithms can be divided into two main categories: adaptive testing: in which the choice of a pool is influenced by the previous results of tests applied to the group;

non-adaptive testing: in which the choice of a pool does not depend on the results of previous tests.

The aim of a pool testing algorithm is to assess, as precisely as possible, the status (defective or not) of each item, through the tests made on pools of items, while using as few tests as possible.

It should be clear that the more permissive adaptive testing option allows for more flexibility, a more parsimonious use of tests can thus be archived in this setting. At one extreme, a search tree can be used to detect defective items with a maximal economy of tests [CJBJ17] . In contrast, non-adaptive testing allows the possibility to massively parallelize the procedure. As all pools can be constructed before any result is known, all tests can be performed simultaneously, which can decrease the time needed to obtain the result. Moreover, in the context of biological testing, non-adaptive schemes decrease the risk of contamination or of decay of samples during their treatment.

It might be noted that several types of adaptive testing allow some level of parallelizing. For example, two-or three-stages algorithms can be considered. In this situation, a first set of pools is constructed without prior information. Using the result of testing on these pools, a second set of pools is constructed. With the tests made on this second set of pools, the status of each item is assessed in a two-stage algorithm, or a third set of pools is constructed and tested in a third stage algorithm, before assessing the status of the items.

One of the first pool testing algorithms to be describe was introduced by Dorfman [Dor43] , as a method to detect syphilis in recruited US soldiers. This algorithm is the following: samples taken from individuals are pooled together in a group, which is then tested for syphilis. If the pool turns negative, all individuals are declared non-contaminated, while if the pool turns positive, then each individual of the pool is tested. Note that this is a two-stage algorithm, which we refer to as Dorfman's algorithm.

Several adaptive and non-adaptive pool testing algorithms have been described over the years, such as matrix testing [CCK + 99], smart testing [TM06] , and testing based on risk estimation for items [ABB19, BBC + 20] . We refer to [AJS19] for a recent survey on this topic. To compare these algorithms, it is necessary to specify more precisely the context in which they are used, such as the relative number of defective and non-defective items, the authorized false positive and false negative rates, etc.

Prevalence and efficiency of pooling procedures. As stated above, the objective of pool testing is the reduction of the number of tests used on a population of N items in order to identify the defective ones. If an algorithm uses a total of T tests, we measure its resource-based efficiency by the quantity

This ratio measures the average number of tests used per item in this pool testing algorithm to detect the defective ones. Therefore, the lower this ratio is, the more parsimonious the algorithm.

Observe that any reasonable algorithm of pool testing should verify E < 1, as otherwise the testing of any item separately represents a more efficient use of resources. In the present article, we assume that a known proportion p of items is defective. It is worth noting that in that situation, a lower bound on the efficiency of a reasonable non-adaptive pool testing algorithm is E(p) ≥ p. Indeed, there are approximately pN defective items among N , so if one makes less than pN tests, there is no possibility to detect the defective items if all pools contains at least one defective. One is interested in the optimal dependency of E in the parameter p.

The optimal efficiency of the Dorfman algorithm previously described is obtained by choosing the size of the pool depending on the value of p in such a way that it is minimal. It can be computed as follows

Indeed, if one creates pools of n items, one test is required for the pool to detect if defective items are present or not, and if the pool is positive (which happens with probability 1 − (1 − p) n ), an additional one is needed per item. The equivalent is obtained by choosing n ≈ p −1/2 as p → 0. Mézard et al. [MTT08] constructed asymptotically optimal non-adaptive and two-steps pool testing algorithms, which detects asymptotically all defective items, while keeping an efficiency of

for some C * > 0. This algorithm is based on the construction of random pools of size n ≈ cp −1 of items, such that each item belongs to L ≈ C| log p| pools. An item is declared non-defective if it belongs to at least one pool tested negative, is declared defective if it belongs to at least one positive pool with all the other items being declared non-defective, and is declared ambiguous otherwise. In that situation, depending of the value of c, C, either with high probability each defective item will belong to at least one pool of non-defective items, and thus be identified as non-defective, or with high probability, the number of ambiguous items after the first stage is small enough that they can be tested individually.

Pooling in the context of the COVID-19 epidemics. In the context of COVID-19, pool testing has been massively proposed and implemented as a method to diminish the marginal cost of a test as well as to answer local shortages of test kits, see for example [BBC + 20, GRK + 20, SNGYL20, BAKS + 20, HSP20, SAKH20, LSF20, GG20, MNB + 20, TAN20, LPBG + 20] among many others. The necessity of early detection of contaminated individuals has been underlined many times, in particular due to the large number of presymptomatic, asymptomatic and mildly symptomatic individuals that remain contagious and can carry the diseases to vulnerable people. As a result, the demand for effective and quick testing has skyrocketed, with the offer being limited by the number of test kits and trained medical professionals for the sampling.

The question of optimization of pool testing thus has practical consequences, as improving on the efficiency of a testing algorithm can increase the number of individuals that can be tested with the same number of kits.

A typical test used for the detection of contamination to SARS-COV-2 is the RT-qPCR test (or PCR test for short), the reverse-transcriptase quantitative polymerase chain reaction. This test allows the measurement of the number of RNA segments typical of the virus that are present in a given sample (usually, three different RNA segments are tested simultaneously to improve on the measure), which is related to the viral load of the sample. As the name suggest, the measure is quantitative, thus returns more than binary response (which would be akin to a defective/not defective result in the classical pooling literature). As such, it seems that this additional piece of information could be used to improve on the existing group testing strategies to reduce the the number of tests needed for detection.

However, let us underline a couple of important caveats. First, the quantity measured by the PCR test is related to the logarithm of the viral load carried in the sample, rather than the viral load itself, with some noise on the measure [BMR20] . Therefore the exact viral load is not known, but rather its order of magnitude. Secondly, the viral load in defective items spans a large range, of several orders of magnitude [JMV + 20]. Therefore, if two defective items with viral loads c 1 and c 2 are tested in the same pool, the result of the measure will be log(

as c 1 and c 2 will typically be of different orders of magnitude. The aim of this article is to propose and study an algorithm that uses the viral load of an item to improve its efficiency. We construct this algorithm on an idealized version of the situation described above. We discuss in more details in Section 8 the adaptation of the algorithm to the COVID scenario, pointing some of its limitations.

Defective items with load. We consider in this article some theoretical aspects of pooling strategies that can be employed for the detection of defective items with load, in order to adapt to the PCR testing scenario previously described. We assume here that each defective item u has a positive value x u attached that we call its load. A non-defective item will have a load of 0. The test of a pool A of items has the effect of measuring the value max u∈A x u , i.e. the largest load among all items in the set A.

Observe that if the load of items belongs to {0, 1}, then we are in the settings of the classical pool testing, and a test only detects the presence of at least a contaminated item. However, if this load can takes more values, we show that the results of several tests can be crossed to extract additional information on the items. The load x u can be thought of as the logarithm of the viral load of an individual in PCR settings, and the choice of measuring the maximal load of a set comes from (1.3).

We denote by p the prevalence of defective items (i.e. the proportion of defective items in the set to be tested). We assume here that p is known (or at least adequately estimated), so it can be used to choose the size and number of pools to be made 1 . The load associated to each item can then be written as x u = ξ u Z u , where ξ u is a Bernoulli random variable with parameter p representing the fact that item u is defective or not, and Z u is an independent [0, 1]-valued random variable. In this article we will consider Z u uniformly distributed either on [0, 1] or on {1/K, 2/K, . . . , 1} for some K ∈ N. Note that we assume that all defective items have a positive load, but in real-world examples, there are limitations on the accuracy of the detection and some defective items would have a load of 0. We do not try to measure these false negative as they are present no matter the testing method used. 2

The quantity K described above can be interpreted as the level of precision of the measure. The larger K is, the easier it is to distinguish the level of two defective items with similar loads. As a result, the efficiency attained by our algorithm will decay as K increases, to attain optimal efficiency when K = ∞, which corresponds to Z u uniformly distributed on [0, 1].

The model of group testing with load allow us to explore the information carried by the maximal value of a set of items. It interpolates with the classical group testing model when K = 1, and its limit as K → ∞ is a universal problem, in the sense that all atomless distribution for x u would create the same combinatorial problem. The case K > 2 that generalizes the zero-one binary information corresponding to the healthydefective alternative is already present in [EM16] where the load of a pool is supposed to take the form of the sum of the load of each individual. The closest case to our study is the one of [DH00, Chap 11.3] and [HX87] for K = 2 with the limit that only one defective (of load 1) and one mediocre (of load 1/2) are allowed in the sample. In essence, the linear case considered in [EM16] and some generalizations described in [AJS19, p119] are simpler to study than the multilevel loads combined with the (non-linear) maximum load in the spirit of (1.3). Indeed, a lot of the information is lost in only considering the maximum so that the small loads are more likely to be hard to detect. See the results in Section 3 for precise explanations of this fact.

Organization of the paper. We propose here a very simple one-step (non-adaptive) algorithm for the detection of defectives, sometimes under the assumption that the same sample cannot be placed in more than L pools. This algorithm is asymptotically efficient as p → 0 while remaining simple to implement and to evaluate. We describe in the next section the general form of the algorithm we study. We then show how to optimize this algorithm assuming that each sample can only be part of a finite number of pools in Section 5, and optimal efficiency that can be obtained by this algorithm in Section 6. We then provide some numerical simulations to compare these asymptotic results to their finite value counterpart in Section 7.

In this work, we focus on a simple one-step non-adaptive algorithm. In this algorithm, items are organized on a grid, and the pools are made of the lines, columns and the diagonals of different slopes of this grid. The algorithm mainly focus on reconstructing the status of items from the measures made on these diagonals. The parameters of the algorithms to optimize are the size of the grid (representing the number of items in each pool) and the number of diagonals slopes to consider (representing the number of pools each item belongs to).

Defining the grid. Before describing the algorithm in more details, we introduce some notation. We assume the number of items to test to be sufficiently large that it is possible to divide them into batches of n 2 items. We describe the algorithm on a given batch.

The items are dispatched on a grid n×n, with each item being identified by its position (i, j) ∈ {1, . . . , n} 2 . We write ξ i,j = 1 if (i, j) is defective and ξ i,j = 0 otherwise. Moreover we denote by X i,j the load of the item (which is 0 if the item is non-defective, or a number in (0, 1] otherwise). With the modelling of the previous section, we note that (ξ

Defining the pools. The pools used can loosely be described as the diagonals of the grid. More precisely, we introduce the following sets of n items to construct the pools of the algorithm:

In an algorithm constructed such that each item is part of L pools, the pools will be taken as families of lines, columns and diagonals with slopes smaller than L − 2. In the rest of the article we will assume this family of pools will form a N (n 2 , n, L) multipool, in the terminology of [Tä20] . In other words, we need our pools to satisfy the following three properties:

1. each pool contains exactly n items; 2. each item belongs to exactly L pools; 3. two items (i, j) and (k, l) share at most one pool in common.

While the first two properties are straightforward from the definition, the third one is not, and only holds under some assumptions on n and L.

Proof. We first note that two line never cross, and that a line crosses with a column or a diagonal at exactly one point. Therefore, to verify that {L k , C k , D a k , 1 ≤ k ≤ n, a ≤ L − 2} is a multipool, it is enough to check that no too diagonal cross at more than one place (treating columns as diagonals of line 0).

Observe that for a = b, two diagonals D a k and D b cross at a point (i, j) such that k + ai ≡ + bi mod n, i.e. such that (b − a)i ≡ − k mod n. By the fundamental theorem of algebra, there exists a unique i ∈ [1, n] satisfying this property if and only if (b − a) is prime with n. As |b − a| ≤ L − 2 is smaller than the smallest prime factor of n, we deduce this is indeed the case, proving that any two pools cross at either 0 (if they have the same slope) or 1 point.

More generally we could prove that selecting families of lines, columns and diagonals in the n × n grid, it is possible to create a N (n 2 , n, L) multipool if and only if L − 2 is smaller than the smallest prime divisor of n.

In the rest of the article, we enumerate the pools as the family {P j , j ≤ nL}, with P 1 , . . . P n corresponding to the lines, P n+1 , . . . P 2n to the columns and the rest to the diagonals, in the increasing order of their slope. For each ≤ nL, the effect of probing the pool P corresponds to the action of discovering the value V := max (i,j)∈P X i,j , the largest load among all defective items belonging to the pool. Finally, for convenience, we denote P i,j the set of pools associated to the item (i, j),

Computation of the positives. The final step of the algorithm consists in a reconstruction of the load of each item via the information contained in the family {V , ≤ nL}. We observe immediately that if V = 0, then all items in the pool are non-defective, and if V = x = 0, then there exists at least one item in the pool with load equal to x.

To reconstruct the load of each item, we employ the following procedure.

3. Otherwise, we count the number of apparitions of the value V i,j inside of the pools containing (i, j) :

(a) If I i,j ≥ 2, meaning that at least two tests containing item (i, j) measured it with the same value, the item (i, j) is declared positive.

Here is the reason behind this definition. By the assumptions we made on the test, V i,j is an upper bound for the load X i,j of the item. In particular, if V i,j = 0, we label the item as non-defective. However, if V i,j > 0 it might be that the item has been, by chance, mixed with defective items in all the tests that were made on it. The fact that level V i,j is attained at least twice is a much stronger indication of the defectiveness of (i, j), as a false positive in that case would mean that it has been by chance mixed in two pools with different defective items sharing exactly the same load, and that in all other pools, there was at least one item with a larger load. In the asymptotic we will consider, this will not occur with large probability, and similarly if I i,j = 1, with high probability the item will be negative.

Observe the procedure we describe here to assess the load and status of each item is not the most accurate. With extra care, one could gain more precision of the reconstruction, for example by checking that each measured load in the pools has been associated to at least one item. However, the procedure described here has the advantage of simplicity and locality: to give the status of an item, one has only to consider the results of the tests related to this item. This makes the forthcoming computation of the probability that an item is wrongfully characterized significantly easier, and it remains efficient enough in the range of parameters we consider.

We sum up the complete procedure inside Algorithm 1 and a concrete toy example in Figure 1 .

It is worth noting that the algorithmic complexity of Algorithm 1 is O(n 2 L). In terms of test usage, it is easy to compute the efficiency of this algorithm as there are a total of nL pools of n items that are tested, in an effort to detect defective elements among n 2 items. The corresponding efficiency is then

To complete the study of this algorithm, one then need to compute its false positives (when R i,j = 1 implying detection as defective while X i,j = 0 so the item is non-defective) and false negatives (when R i,j = 0 whereas X i,j > 0) rates. We denote by F P R (respectively F N R) the expected number of false positives and false negatives returned by this algorithm, divided by the total number of contaminated items. These two quantities depend on the four parameters p, K, n and L in an intricate fashion. However, note that while n and L are integer parameter of the algorithms we can choose, p ∈ [0, 1] and K ∈ N are modelling parameters of the problem, representing respectively the proportion of defective items and the accuracy of the test. Therefore the main goal of this study is to optimize the efficiency E of this algorithm by choosing the optimal n(p, K) and L(p, K) in a way that insures that F P R and F N R both stay below fixed quantities ε and δ. Our main results are considered under the asymptotic p → 0 of a small proportion of defective items. But as most of the computations made are explicit before taking limits, computing the optimal value of n and L for given values p, K remains straightforward.

Parameters: n,L, Inputs: X = (X 1 , . . . , X n 2 ) Store X inside the grid (X i,j ) 1≤i,j≤n line by line; Define P 1 , . . . , P n as the lines, P n+1,...,P2n as the columns and P 2n+1 , . . . , P nL as the diagonals; Initialize a matrix S = (S i,j ) i,j of empty lists;

if V i,j = 0 and I i,j ≥ 2 then Set R i,j = 1; end end Store the matrix R line by line into a vector (R 1 , . . . , R n 2 ); Result: (R 1 , . . . , R n 2 ) Remark 2.4. Note that an item is falsely labelled as negative if it is part of at most one pool in which it is the item with the largest load. It corresponds to items at position (i, j) such that I i,j = 1 in the above algorithm. Therefore, items such that I i,j could be labelled as inconclusive and tested again in a separate batch in a two-steps algorithm with no false negative.

In this section, we give explicit upper bounds on the false negative and false positive rates of the algorithm. This does not take into account a possible defective measurement of the loads of the pools. The false negative rate of the algorithm is expressed as the probability that a contaminated item is not detected at the end of the algorithm whereas the false positive rate is the probability that a non-defective item is detected as defective. In Algorithm 1, it is straightforward to compute the false negative/positive rates, as the reconstructed status of an item only depend on the status of items sharing a pool with it. This algorithm being unchanged by changing the coordinates of the grid, as on a torus, these rates do not depend on the position (i, j) of the item in the grid. We thus only compute the false negative probability of item (1, 1), given its load. For all x ∈ (0, 1], we set and that

In particular, when K → ∞, the false positive rate F P R(n, L; p, K) tends to 0.

Proof. We observe that the probability to wrongfully declare an item as negative depends on K (in the discrete case) only through the fact that x takes its values in {1/K, 2/K . . . , 1}. This allows us to give a unified expression for the upper bound of F N . Given x the load of the item (1, 1), we note this item will be wrongfully declared negative in Algorithm 1 if and only if I 1,1 = 1 (as V 1,1 ≥ x > 0 a.s.). Decomposing according to the test in P 1,1 measuring the lowest viral load, we have

where ϕ(y) = P(min = V > y|X 1,1 = x) and 0 is a fixed element of P 1,1 . Using that the (V , ∈ P 1,1 ) remain i.i.d. conditionally on X 1,1 = x, thanks to Lemma 2.1, we have ϕ(y) = P(V 0 > y|X 1,1 = x) L−1 . Then, using that ϕ(y) ≤ ϕ(x) for all y ≥ x, we obtain

As in our setting there is a proportion x of positive items with load smaller than x, we obtain

which leads to the following upper bound for the false negative rate of an item with load x,

We can similarly compute the false positive rate of the algorithm by computing the probability that conditionally on (1, 1) being non-contaminated, this item is determined to be contaminated. This would happen if and only if (1, 1) is only part of contaminated pools, and that the two pools with the lowest measured load have the same value, that we write x. Noticing that false positive results never occur in the infinite precision setting K = ∞, we assume here that K < ∞. Using again that we have a multipool and that the measure of each test is independent conditionally on the value of X 1,1 we obtain F P (x) = P(I 1,1 ≥ 2, V 1,1 = x|X 1,1 = 0) = P(∃ 1 , 2 ∈ P 1,1 ,

with 0 a fixed element of P 1,1 . Let F (x) be the distribution function of V 0 conditionally on X 1,1 = 0. Then, we can use the upper bound

We finally get

In the rest of the article, we compute the optimal efficiency under different constraints, based on the above constructed pools, in different situations. We first consider non-adaptive strategies for detection of defective items based on the measure of lines and columns only, then adding eventually item tests for items whose status cannot be deduced by the first step algorithm. We then aim at optimal testing efficiency, assuming that samples can be infinitely divided, and recover results consistent with Mézard et al [MTT08] . In Section 7, we compare our asymptotic estimates with simulated experiments, and obtain the false positive/false negative rates and efficiency that can be archived in real testing conditions.

In this section, we derive equivalent expressions for the upper bound of the false discovery rates when the values of K and L remain fixed. We consider two asymptotic cases, when np → 0 and when np → λ > 0. It is implicitly assumed that n → ∞ and p → 0. In the second case, the calculations are based on the Poisson approximation of the number of defective items in a specific pool and are consequently more accurate than the rates in the first case.

Case np → 0. In this case, g n,p (x) can be lower bounded by g n,p (0) since it is a increasing function and g n,p (0) ∼ e −np . Then

The false discovery rate is then upper bounded by

In particular, we see that in this regime (as K and L remain fixed), the false negative rate is small with respect to the false positive rate.

Case np → λ > 0. In this situation, with L being fixed, we immediately obtain that the number of defective items in each pool converges to a Poisson(λ) random variable. We consider the asymptotic behaviour of the false positive and false negative rates obtained in this situation. We write Proof. We first compute the false negative rate. From the properties of Poisson processes, we note that the number of items in a pool with load between x and y is distributed as a Poisson random variable with parameter λ(y − x), independently of the number of items in this pool with load smaller than x or larger than y. In particular, for any given test , for any y ≥ x we have

Using this fact, with the same computations as in Proposition 3.1, we can compute the false negative rate of an item of load x as

In the case K = ∞ the computations can be made explicit as in that case

In particular, we also obtain F N (λ, L; ∞) ≤ L(1 − e −λ(1−x) ) L−1 .

Similarly, we can compute the false positive rate of a negative item in this regime. An item is falsely identified as a false positive if it does not belong to any pool with a negative item, and that if the smallest non-null value observed among the pools is attained at least twice. Using similar bounds as in the previous sections, we obtain

Bounding the above quantity by L(L−1) 2K (1 − e −λ ) L−2 , we obtain the result. From this formula, the false positive rate can be written explicitly as the probability that among L independent copies with the above distribution, the first and second running minimum are equal. We plot once again this function in L for different values of K.

In this section, we look to optimize Algorithm 1 while assuming that the number L of tests that can be made on each item is finite. This regime is relevant in particular if a test destroys or damages a sample of the item, so that limiting the number of tests made on each item becomes relevant. In the rest of the section L is a fixed constant, and n is a number with no prime factor smaller than L − 1. In that situation Lemma 2.1 holds and we are working with multipools, so that the formulas (3.1) and (3.2) both hold.

Recall that the efficiency of the algorithm is E = L n , therefore to improve the efficiency of the algorithm, one has to increase the size of the grid. However, augmenting the value of n has the effect of increasing the false positive and false negative rates. Therefore, to find the optimal efficiency of Algorithm 1, we fix ε > 0 and η > 0 as maximal values for the proportion of positive and negative items wrongfully labelled as negative and positive respectively, and we choose n as large as possible such that F N R(n, L; p, K) ≤ pε and F P R(n, L; p, K) ≤ (1 − p)η.

As the average number of false negatives found by the algorithm is of the order n 2 pε, we will also consider bounds in the regime when ε → 0 as n → ∞.

A choice of n for ε and η fixed. In this case, one has to choose n accordingly to have L(np) L−1 ≤ pε and L(L−1) 2K (np) L ≤ η. The largest n that satisfies the first condition is

and the largest n that satisfies the second condition is

We recommend to choose n as

This choice of n gives a efficiency of the algorithm given by

Note that these choices of values for n are driven by the results of Proposition 3.2 and hence are quite conservative, so the efficiency obtained here is an upper bound of the true optimal efficiency of Algorithm 1. Note that in a high precision setting (when K is large) the false positive are a minority inside the false discovery of the algorithm, and the efficiency will depend only on p, L and ε. We observe that the number of tests to use per item to detect defective ones with fixed false negative/positive rate becomes proportional to p the proportion of true negative. In other words, the total number of tests this algorithm need to detect defective items becomes ultimately proportional to the number of defective items when the number of non-defective items is large. This is a notable improvement on pool testing with {0, 1} response, in which the known optimal asymptotic efficiency is proportional to the product of the number of defective items and the log of the number of non-defective ones.

A choice of n for vanishing ε and η. Observe as well that in the settings we discuss, the expected number of false negatives in a given grid will grow as εpn 2 and the number of false positive as ηn 2 . It may be inconvenient to let the expected number of false discovery to grow as n becomes large. To avoid a positive proportion of items on the grid being false negatives, one could instead consider a maximal false positive rate of ε = α/(pn 2 ) as n → ∞ and η = β/n 2 .

In this situation, with similar computations as above, we obtain optimal choices of

and n 2 = 2Kβ L(L − 1)p L 1/(L+2) and the associated efficiency to L and n = min(n 1 , n 2 ) is

This efficiency is much larger than E ε,η (p), as expected from the lower tolerance to false negatives. It behaves as a power of p as p → 0. Remark that for L = 2, we have E α,η (p) ∼ C α p 2/3 as p → 0, so even with these settings, the algorithm becomes more efficient than Dorfman's method for p small enough, to the cost of a fixed proportion η of false positive. For L = 3, the algorithm becomes more efficient than Dorfman's algorithm even with a vanishingly small number of false positive.

In this section, we relax the assumption that L has to be kept fixed, and aim at choosing an optimal couple n, L so that the efficiency of the algorithm E = L/n is as small as possible, while controlling the false positive and false negative rates. While it is not mentioned explicitly, it is assumed everywhere in this section that L − 2 is smaller than the smallest prime factor of n, so that Lemma 2.1 can be applied. Using the growth rate of primordial numbers and the fact that an optimal choice of L will remain finite, there will always be a couple (n, L) satisfying the assumption of Lemma 2.1 close enough to the optimal theoretical choice, so this condition won't play a role in the asymptotic behaviour of the obtained efficiency.We first investigate the case when the precision of the loads K is infinite so that the choices of n and L are only driven by the reduction of the false negatives in the algorithm. We take interest in the quantity E * ε (p) := min L n , n, L ∈ N : F N R(n, L; p, ∞) ≤ εp . (6.1)

In this new context, L no longer fixed, and its choice might depend on p and ε. We recall that by Proposition 4.1 and the computations above, if np → λ ≥ 0, we have

As a result we are lead to choose n and L such that L(np) L−1 ≈ ε, while minimizing the efficiency of the algorithm E = L n ≈ p(ε/L) 1/(L−1) . We thus obtain that the efficiency of the algorithm is optimal when L is taken to minimize L → (ε/L) 1/(L−1) , and n as (ε/L) 1/(L−1) /p. Therefore, the optimum is attained by choosing np → λ > 0.

To precise the computations in that situation, we use the formula given in Proposition 4.1. We observe that as np → λ, we have

As ε → 0, the optimal is attained for λ, L such that L log(1 − e −λ ) = log(ε)(1 + o(1)), yielding

This quantity is minimal for λ = log 2. As a consequence, as p → 0, we recommand using n ≈ (log 2)/p, and as ε → 0 L ≈ − log ε log 2 , to obtain an optimal efficiency behaving as

Note in particular that n is chosen depending on the value of p, while L is chosen as a function of ε in this asymptotic regime.

Remark 6.1. As noted in Remark 2.4, Algorithm 1 could be adapted as a two-step algorithm in which every inconclusive item is tested again individually. Note that the upper bound we use for the false negative rate is exactly the rate of inconclusive elements (as we bound F N (x) by F N (0) ). In this two-step algorithm, the efficiency would therefore be E (2) (p) = E * ε (p)+ε −p log(ε)(log 2) −2 +ε, which is minimal for ε = (log 2) −2 p. This two-step algorithm would thus have an efficiency asymptotically bounded by (log 2) −2 p log(p) as p → 0.

Remark 6.2. We also observe that choosing ε = n −1−α for some α > 0, the efficiency becomes E * ε (p) ≈ 2.08(1 + α)p(− log p) as p → 0. With this choice of ε, the probability of observing one false negative in the grid decay to 0 as εn 2 p ≈ n −α . In that situation, we obtain an efficiency with a similar order of magnitude of the optimal results of [MTT08] , with a simpler (non-random) construction of the algorithm. Actually, the efficiency obtained here attains the lower bound of the optimal efficiency predicted in [MT11] for a two-steps binary pool testing algorithm. Therefore, the non-adaptive Algorithm 1, making use of the load value of items, archives the same efficiency as an optimal two-stage algorithm.

In this section, we illustrate the behavior of our proposed algorithm versus the two-steps Dorfman's algorithm and Mézard's optimal algorithm. We describe the choices of the parameters in the following.

• The simulations took the set {3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47} of the odd prime numbers under 50 as the possible values of n.

• The algorithm is allowed to perform tests in up to L max = 14 directions. In the case when n ≤ 14, we obviously restrict the number of directions to L max = n − 1.

• The prevalence parameter p varies between 0.05 and 0.2 with a constant increment of 0.05.

• We made vary K inside the set {2, 5, 10, 30, 200, 500} to illustrate its influence.

• For each choice of the parameters (n, L, p, K) above, we run 200 copies Algorithm 1.

Consequently, for each choice of the set of parameters, we observe 200 copies of the output of the algorithm. Afterwards, the matrix of results is compared to the matrix of the true matrix containing the information of the true positive and negative items. Thanks to that, we compute the mean number (over the 200 copies) of false positive and false negative discovered by the algorithm. Thus, we end with an estimation of the number of false negative F N (n, L, p, K) and the number of false positive F P (n, L, p, K). The next step is to compute the optimal value of the efficiency E as a function of p. Then, for any couple (p, K) fixed, we did the following concrete inclusions of the conditions of Section 5.

1. We fixed η = 0.01 and we discarded all the pairs n, L such that F P (n, L, p, K) ≥ η(1 − p)n 2 .

2. For each value of ε we considered, we discarded the pairs such that F N (n, L, p, K) ≥ εpn 2 .

3. Then, from all the remaining values of the pairs (n, L), we minimized the quotient E(p) = L/n.

This value E(p) as a function of p (for different values of K) is the one that we drew in the following illustrations. Figure 3 shows for the two different values K = 5 and K = 30, the behavior of our Efficiency curve versus Dorfman theoretical efficiency and a simulated Mézard, al. efficiency. We drew the resulting points of E(p) in three different colors (blue,purple,black) that correspond to the choices of ε given by (0.02, 0.08, 0.2). For each of these ensembles of points, we also drew a simple regression line. It has to be seen that the dependence of E on p is clearly linear and that the slope of the line is dependent on the choice of the parameter ε, as expected. It is also interesting to see that the effect of ε is less clear when K is small since the number of false positives is higher and then is more limitent than when K is large.

The next three plots (in Figure 4) show the choices of the parameter L during the optimization of E for fixed values of p and K. As before we let ε vary in between the different plots. Besides been a little unstable in the choice of L along p, we observe that the optimal L remains bounded (hence is fairly independent from the choice of p) and does change with a change of ε as suggested by the calculations in Section 6. The last three plots (in Figure 5 ) are the analogs of the previous plots with the slight difference that the displayed numbers correspond to the chosen values of n. In this case, we observe that, now, ε has no more effect on the chosen values of n. As expected, n depends on p in a decreasing manner and validate the calculation of Section 6. Indeed, we showed that the best choices of n allow to keep the product np more or less constant which is the case in the simulations. 

The application of the present algorithm to PCR testing in the context of the COVID-19 pandemic requires some adaptation and presents a couple of challenges. It should first be noted that the simplifications we made in our modeling were quite important. We thus begin by discussing in more details the discrepancies between the real-world problem and our idealized model.

Finite size of samples. In COVID-19 pool testing, the items that are tested are samples taken from subjects, via nasal swab, saliva sample or other method. If there seems to be usually enough matter to split the sample into several tests, it will not be possible to make an arbitrary large number of tests on each sample. Therefore, optimal computations made in Section 5 might be somewhat more relevant. Additionally, it is worth noting that combining several samples have the effect of creating a composition with the average viral load rather than the maximal, although the fact that this viral load is spread over several orders of magnitudes negates partially this problem as discussed in the introduction.

Noisiness in the measure. We chose to represent a lack of accuracy of the measure by replacing the continuously distributed viral load by a discrete distribution, as if contaminated tests could be arranged into "classes" of similarly measured viral load. In practice, the quantity returned is a real number, which is a measure on which a Gaussian noise is expected to be applied. More precisely, several steps of the process have the effect of creating uncertainty on the measure, and the variance that has to be expected from a pooled test might be rather large. There is first the collection of the portions of samples used to make the group testing, whose volume and associated viral load may vary with regards to the attended equal contributions. Next, the reverse transcriptase step that converts RNA samples of the virus into DNA might introduce additional noise depending on its rate of conversion. Finally, the PCR measurement itself products a noisy value, partially corrected by the fact that classically, two different DNA sequences for the virus are measured separately. It would then require some adaptation of our algorithm to adapt the "finite precision algorithm" to noisy Gaussian measure of the viral load in each pool, although classical likelihood ratio estimates might be successfully used here.

Distribution of the viral load among contaminated. Concerning the distribution of the viral load of the samples, we made here the choice of uniform distribution, which is the most favorable for this type of algorithm. Although this is quite far from what is effectively observed [JMV + 20, CRP + 20], the viral load observed among large groups of people is usually successfully approached by a mixture of two to three Gaussian variables with standard deviations between 3 and 6, spanning over the interval [20, 40] (c.f. [BMR20,

Appendix B]). The viral loads may be considered sufficiently spread over the interval so that the algorithm discussed above might still be relevant. The nice and explicit calculations on the choices of the parameters would need to be adapted. They might also need to be tuned from day to day, depending of the expected prevalence of samples on a given day, which might vary over time.

Precision limits of the PCR. As it was first noted in [Fur18] , theoretical aspects of pool testing usually assume that the quality of the test does not depend on the size of the pool. However, this is rarely the case in real-world applications, and it is indeed not the case for the present application. In particular, we show in [BMR20] that pooling has an impact on the measurement of samples with small viral loads, due to a dilution effect. In our toy model, this could be taken into account by specifying that in pools of size n, items with load smaller than c n are treated as non-defective items, for some increasing function c n . This has the effect of decreasing the value of the optimal choice for n, in order to detect enough contaminated individuals with small viral load. However, the computations in this case being very dependent on the function c n , we choose not to include it in the present work.

Random outcome of a pooled test. Finally, we assumed that each test of the pools is performed with no other error than the one inherent to the PCR itself. It is probably an oversimplification in this case, as pool testing implies important manipulations of the samples, with possible additional errors involved. For example, forgetting to collect one individual in a pool, contaminating a pool with a sample that should not belong to it, etc. Those human errors would create noise on the measures of the pools and so would deteriorate the information given to our algorithm. Therefore, it would need to be adapted to this situation, in order not to characterize as negative a sample measured at high values in all but one pool, for example. There is also the issue of systemic bias in PCR, as most machines only allow the measure of the relative viral load rather than an absolute value. As our algorithm only consider relative loads, this is not generally an issue for our method, when the algorithm is performed on a single machine.

Potential extensions. The algorithm presented here has the advantage of being simple to implement and easy to solve, even by hand. However, more precise algorithms might be employed with the help of automation for the creation of samples and measure of results. It would therefore be interesting to create more precise algorithms for PCR-type pool testing. A relevant generalization could be to collect and use additional information on the subjects. We can imagine that, throughout interviews, some individuals might be identified as being more likely to be contaminated, while others could be simply routinely tested. It is probably more efficient to tests the former in smaller pools and the latter in larger ones. An other project of interest might be the deconvolution of pools created by Dorfman's algorithm. More precisely, in the algorithm, instead of testing individually every member of a group detected as contaminated, it might be interesting to test several samples from different positive pools in a two-stage deconvolution that might represent a further economy of tests on Dorfman's algorithm. Choosing the right pools to pair together, as well as the number of positive pools to be de-convoluted at the same time might be an interesting expansion on the current work.

Optimal Risk-Based Group Testing

Group Testing: An Information Theory Perspective. Foundations and Trends in Communications and Information Theory

Maayan Salton, and Yotam Drier. Large-scale implementation of pooled RNA-extraction and RT-PCR for SARS-CoV-2 detection. medRxiv

Optimal Covid-19 Pool Testing with a priori Information

Group testing as a strategy for the epidemiologic monitoring of COVID-19

Pooling, lattice square, and union jack designs

Efficient algorithms for noisy group testing

Pooling For SARS-COV-2 Control In Care Institutions. medRxiv

Combinatorial group testing and its applications

The Detection of Defective Members of Large Populations

Code construction and decoding algorithms for semiquantitative group testing with nonuniform thresholds

Saving resources: Avian influenza surveillance using pooled swab samples and reduced reaction volumes in real-time RT-PCR

The illusion of group testing

Group Testing against Covid-19

Tapestry: A Single-Round Smart Pooling Technique for COVID-19 Testing. medRxiv

Sample Pooling as a Strategy to Detect Community Transmission of SARS-CoV-2

Group testing to identify one defective and one mediocre item

On the Optimality of the Kautz-Singleton Construction in Probabilistic Group Testing

An analysis of SARS-CoV-2 viral load by patient age

Pooling of samples for testing for SARS-CoV-2 in asymptomatic people

Sample Pooling as a Strategy to Detect Community Transmission of SARS-CoV-2

Neil Turok, and Wilfred Ndifon. A strategy for finding people infected with SARS-CoV

Group Testing With Random Pools: Optimal Two-Stage Algorithms

Group testing with random pools: Phase transitions and optimal strategy

Evaluation of Group Testing for SARS-CoV-2 RNA. medRxiv

Efficient and Practical Sample Pooling for High-Throughput PCR Diagnosis of COVID-19. medRxiv

Pooling of Nasopharyngeal Swab Specimens for SARS-CoV-2 detection by RT-PCR

Estimation of the Proportion of Vectors in a Natural Population of Insects

Pooling in systems biology becomes smart

Rapid, large-scale, and effective detection of COVID-19 via non-adaptive testing

We wish to thank members of MODCOV-19 platform of the CNRS for support, in particular Françoise Praz and Florence Débarre who gave us numerous helpful comments, in particular on the biological aspects of PCR. We also thank the members of the Groupool initiative for helpful discussions at the earlier stages of this project on group testing.