Presentation of the strategy
The strategy9,10 that we consider in the present paper is illustrated in Fig. 1. For its definition and optimization we assume that the test detects the presence of a single infected sample in a pool. We analyze later how to assess the occurrence of false negatives when testing pools. The strategy is characterized by the number of stages, ((k+1)), and the sequence of pool sizes, (m=(m_1,ldots ,m_k)), where (m_1>dots>m_k>1) and (m_j ) is a multiple of (m_{j+1}) for all j. At the first stage, pools with (m_1) samples are tested. The samples in each of those that test positive are combined in pools of size (m_2) following a nested scheme (see Fig. 1) and are tested at a second stage. The procedure is repeated until the (k+1)-th stage at which all the samples contained in pools that tested positive at the k-th stage are tested individually, i.e., (m_{k+1}=1).
Schematic depiction of the nested pool testing strategy with (k=2) and (m=(9,3)) when applied to one pool labeled, (W_0). The circles represent individual samples and the rectangles represent pools. The red circles correspond to infected samples. The non-infected circles are either green (when they belong to a pool that is being tested at the corresponding stage) or grey (when they have been identified as non-infected at a previous stage). At the first stage all 9 samples of the pool, (W_0), are tested together. The result is positive due to the presence of one infected sample. (W_0) is then divided into 3 sub-pools, (W_{00}), (W_{01}), (W_{02}), of 3 samples each that are tested at the second stage. After these tests, (W_{00}) and (W_{01}), are identified as not infected so that the samples in them are not further tested. (W_{02}) is identified as infected and all its samples are tested individually at the last stage. In the illustration the volume occupied by each pool seems to decrease from stage to stage: the pool volume is actually the same at all stages. The figure illustrates the labels, (W_{i_1…i_j}), that can be assigned a priori to individual samples and pools of all stages, regardless of whether they are going to be tested as such or not. The labeling is characterized by a sequence of as many subscripts, ({i_1,ldots ,i_j}), as stage number with, (i_1), the subscript that identifies the initial pool (in the figure, (i_1=0)).
The cost of the strategy, (D_k(m,p)), is defined as the expected number of tests per individual, (ET_k/m_1), for which there is an analytic expression9,10,12,14 as a function of the infection probability, p (see Methods). For each p, (D_k(m,p)) is minimized by the optimal strategy15. For all but a tiny set of values of p, the optimal has (m=(3^k,ldots ,3)) with (k=k_3(p)) given by Eq. (13) (with (mu =3))15. For the values of p for which it is not the optimum, its cost differs by a negligible amount with respect to the optimum (see Supplementary Note). We show in Fig. 2 the number of stages, (k_3(p)), in (a) and the expected number of tests per individual, (D_k) (black, Eq. 12), and standard deviation of this number (sigma (m,p)) (red, Eq. (14)), in (b), for the (m=(3^{k_3(p)},ldots ,3)) strategy. (k_3(p)) increases with decreasing p. Thus, it only makes sense to use it if15:
$$begin{aligned} p<1-1/3^{1/3} approx 0.3066387dots , end{aligned}$$
(1)
which is the equivalent of the upper bound of Dorfman’s for integer-sized pools.
Properties of the optimal nested strategy, (m=(3^k,ldots ,3)), as functions of p. (a) The number of stages, (k=k_3), with (k_3) given by Eq. (13) and (mu = 3), is a piece-wise constant decreasing function of p with discontinuities at the probabilities indicated with stars on the horizontal axis. (b) The expected value, (D_{k_3}(m, p)) (black curve), and standard deviation, (sigma (m,p)) (red curve), of the number of tests per individual stay close to one another and increase monotonically with p.
Expected cost and variability
The optimization problem worked out in15 looked at the minimization of the expected value of the number of tests per individual. Any realization of the strategy, however, will result in a number of tests that will differ from the expected value. Although the repeated application of the strategy will approach, on average, the expected cost, it is important to assess the variability around the mean. As shown in Fig. 2b the standard deviation of the number of tests per individual of the optimal strategy is of the same order of magnitude as the expected value. In this Section we present the results of stochastic numerical simulations, performed as explained in Methods, to understand the nature of this variability showing that it does not yield increasing costs.
We show in Fig. 3 histograms of the number of tests performed per pool obtained from simulations of the strategy with (k=3) and (m=(3^3,3^2, 3)) for values, p, for which it is optimal. 1000 realizations (initial pools) were done for each p. In Fig. 3a approximately 58% of the 27-sample pools required only one test, i.e., under ideal conditions, 15,660 individuals could be reported as negative using only 580 tests. This is key for the large reduction in the average number of tests per individual ((sim 0.2), instead of 1) and per pool ((sim 5.4) instead of 27) of the example. The second most frequent situation in Fig. 3a, with (sim 34%) of the instances, is the one with 10 tests/pool. This corresponds to initial pools with only one infected sample or with more that remain in the same pool until the k-th stage, for which the total number of tests and the number of tests per individual are, respectively (see Supplementary Note):
$$begin{aligned} {hat{T}}_k&=1+m_k +sum _{j=2}^k frac{m_{j-1}}{m_j}=1+kmu , end{aligned}$$
(2)
$$begin{aligned} {overline{D}}_k(m_1,ldots , m_k,tilde{p})&=frac{1}{m_1}+m_k tilde{p}+tilde{p}sum _{j=2}^k frac{m_{j-1}}{m_j}, end{aligned}$$
(3)
with (tilde{p}=1/m_1). The comparison of the three examples of Fig. 3 provides an explanation for the relationship between the cost and standard deviation displayed in Fig. 2b. We observe in Fig. 3 that, as p decreases within the range of optimality of the strategy with (k=3) and (m=(3^3,ldots ,3)) the fraction of initial pools that require the largest number of tests decreases while the fraction of those that require only one test (i.e., no infected samples), grows. The increasing ratio, (sigma /D_3), with decreasing p that is apparent in Fig. 2b can then be related to an increasing fraction of instances with no infected samples that are resolved with only one test. This is easy to explain if we assume that the pools can have at most one infected sample. In such a case, those with no infected samples are solved with a single test while the others require a total number of tests, ({hat{T}}_k), given by Eq. (2). Defining the stochastic variable, X, so that (X=0) if the pool contains no infected samples and (X=1) otherwise and calling, ({hat{p}}), the probability that (X=1), the mean and standard deviation of X are (langle Xrangle = {hat{p}}) and ({hat{sigma }}= sqrt{{hat{p}}(1-{hat{p}})}) and satisfy ({hat{sigma }}/langle Xrangle >1) for ({hat{p}}<1/2) with ({hat{sigma }}/langle Xrangle ) increasing for decreasing ({hat{p}}<1/2). Thus, the ratio increases because the deviation approaches zero more slowly than the mean. The “worst” pools (those with exactly one infected sample) are solved with a number of tests given by Eq. (2), which is smaller than the number of samples in the initial pool, (mu ^k), for (mu =3) and (kge 2). Thus, having a standard deviation of the same order of magnitude as the cost is reflecting the relatively high chance that the number of tests to perform will be smaller than the expected value.
Stochastic simulations of the nested strategy with (k=3) and (m=(3^3,3^2,3)) applied to 1000 first-stage pools with infection probabilities, p, for which the strategy is optimal (the one in (b), slightly smaller than the value at which the optimum switches from having (k=2) to having (k=3) and the one in (c), slightly larger than the value at which the optimum switches from having (k=3) to having (k=4)). The figures show histograms (as fraction of occurrences and in log scale) of the number of tests performed per pool. (a) (p=0.02) (544 infected samples, prevalence (overline{p}=0.0201)) (b) (p=0.0398) (1073 infected samples, prevalence (overline{p}=0.0201)) (c) (p=0.0135) (369 infected samples, prevalence (overline{p}=0.0201)). Green bars correspond to the theoretical values that we computed (see Supplementary Note). The apparent mismatch between theory and simulations is solely due to fluctuations and disappears as the number of initial pools is increased.
Practical implementation of the nested strategy: constraints and runs in parallel
In this Section we present a series of analyses to determine the best way to proceed when there are constraints that prevent the use of the theoretically optimal nested strategy or when the strategy is applied in parallel on various pools simultaneously.
Pool testing under unknown prevalence
The infection prevalence of the analyzed population can be estimated as explained in the Supplementary Note to determine the optimal strategy.
We analyze in this subsection the cost of applying the strategy, ((3^k,ldots ,3)) with (k=k_3(p)) to cases with infection probability different from p. We compare in Fig. 4 the cost, (D_k(m,p)), of the strategies with (m=(3^k,ldots ,3)) and different values of k for all values of p. Let us call ((p_{3,k+1},p_{3,k})) the interval of optimality of the strategy with (k+1) stages (the interval where (k_3(p)=k)). At (p=p_{3,k+1}), it is (D_k=D_{k+1}), with (D_k<D_{k+1}) for (p>p_{3,k+1}) and (D_kge D_{k+1}), otherwise. We observe that, even if not optimal, the ((k+1)-)th stage strategy produces a noticeable reduction in the cost for (p<p_{3,k+1}). This is related to the results of Fig. 3: when a strategy with (m=(3^k,ldots ,3)) is applied to situations with (p<p_{3,k+1}), initial pools with more than one infected sample become increasingly rare and the cost is correctly approximated by Eq. (3), which is smaller than 1. The procedure to estimate p as the strategy is applied that is described in the Supplementary Note is based on this analysis.
Cost of different nested strategies. (a) (D_k(m,p)) vs p for strategies with (m=(3^k,ldots ,3)) and (k=1) (black), (k=2) (red), (k=3) (green), (k=4) (blue). (b) (D_k(m,p)) vs p for the strategies with (m=(120,20,4)), (m=(120,15,3)), (m=(120,12,3)), (m=(120,10,2)), (m=(120,8,2)), (m=(120,6,2)), (m=(120,6)), (m=(120,5)), (m=(120,4)), (m=(120,3)) and (120, 2) (blue), (m=(120,24,6,2)) (red) and (m=(81, 27 , 9,3)) (black).
Based on this discussion we conclude that, if the value of p is poorly known a priori, it is advisable to use a strategy with (m=(3^k,ldots ,3)) and a relatively small number of stages, ((k+1)). As discussed in the Supplementary Note, after the strategy is applied to several pools, the estimate of p can be improved and the value of k be retuned.
Maximum number of samples allowed in a pool
We now analyze how to proceed if the optimal strategy requires a value, (m_1), that is larger than the maximum allowed for the test to be reliable. We arbitrarily set the bound (m_1le 120) and assume that p is such that the optimal (m=(3^k,ldots ,3)) strategy has (k+1=6) and (m_1=3^5=243>120) (( p_{3,6}approx 0.0015059<p <0.0045108approx p_{3,5})). As explained in the Supplementary Note, the constrained optimization problem can be solved algorithmically more efficiently using some analytic results of15. In particular, if (m_1=120) the strategies whose costs should be compared to decide the optimal are: (m=(120,24,6,2)), (m=(120,20,4)), (m=(120,15,3)), (m=(120,12,3)), (m=(120,10,2)), (m=(120,8,2)), (m=(120,6,2)), (m=(120,6)), (m=(120,5)), (m=(120,4)), (m=(120,3)) and (120, 2). We show in Fig. 4b these strategies and the strategy of the form (m=(3^k,ldots ,3)) with the largest k such that (m_1=3^k<120). We observe that the (m=(3^4,3^3,3^2,3)) scheme has the smallest cost even for values, (p< p_{3,5}approx 0.0045), outside its region of optimality and that its cost keeps on reducing as p is decreased. For the smallest values of p, the strategy with (m=(120,24,6,2)) is best. As p is reduced beyond the values displayed in Fig. 4b, the costs of all the strategies with (m_1=120) approach the same value, which is smaller than the cost approached by the (m=(3^4,3^3,3^2,3)) strategy. For small enough p, there is at most one infected sample per pool, the expected number of tests per individual is given by Eq. (3) with (tilde{p}=p) and is dominated by the term, (1/m_1). Thus, the larger (m_1), the larger the reduction.
We then conclude that, given an upper bound, (m_{1, max}), on the number of samples that can be combined in a pool, and an infection probability, p, such that (3^{k_3(p)}>m_{1, max}) it is advisable to use the strategy, (m=(3^k,ldots , 3)), with (k = lfloor {log _3(m_{1,max})}rfloor ), if p is not much smaller than the probability for which the strategy is optimal. For very small p, larger reductions are achieved as (m_1) grows, regardless of whether (m_1= 3^k) or not. The search for the optimal strategy can be done algorithmically as described in the Supplementary Note. Starting with (m_1= 3^k), however, has other advantages as discussed in the following.
Running the nested strategy in parallel
For testing facilities, cost reduction is not only achieved through savings in reagents but also by reducing the throughput time. For the latter, PCR tests are usually run on various sets simultaneously using multi-well plates. If our strategy were applied in such a way that all the tests were performed sequentially, the expected throughput time would be proportional to the expected number of tests. If the strategy is run in parallel on a fixed number of simultaneous pools, this relationship between throughput time and number of tests no longer holds. Facilities face the pressure to deliver their results on a reliable time frame. For this, it is important that they have an estimate of the expected throughput time or, equivalently, the number of samples processable per unit time. In the case of a pandemic like the SARS-CoV-2 one, it is also important for governments and other institutions to decide the most efficient scheme to test their populations of concern. Coming back to our strategy, suppose that, at the first stage, the test is run on as many pools as the number of wells in the plates available in the facility, i.e., all the wells are used. The question then arises of what happens at subsequent stages. If more wells are needed than those available, then the application of the strategy will require additional rounds of tests. In this section we analyze this aspect. To this end, let us assume that we use a (k+1) nested strategy with pool sizes (m=(m_1,ldots ,m_k)) in a set-up that allows (N_w) tests to be performed in parallel. Let us assume that, at the first stage, we use all the available wells, i.e., we run the test on (N_w) pools. We want to compare the number of pools to be tested at subsequent stages with (N_w). This is equivalent to comparing the number of tests, (ET^{(j)}_k) (Eq. (11)), that are expected to be performed at each stage, j, of the strategy, (m=(m_1,ldots ,m_k)), starting from one initial pool, with the number one. We show in Fig. 5a a plot of (E{T}^{(j)}_{k}(m,p)), (2le jle k), as a function of p for strategies with (m=(3^k,ldots ,3)) and various, k. The curves are drawn with thicker lines over the range of optimality of each scheme. The horizontal line (magenta) corresponds to the first stage (always equal to 1). We observe that (E{T}^{(j)}_{k}(m,p)) increases with p for every j and k. Thus, within its range of optimality, ((p_{3,k_3+1},p_{3,k_3})), the (m=(3^{k_3}, ldots , 3)) scheme requires the largest number of tests (on average) for (p=p_{3,k_3}). The number of tests expected at the second stage ((j=2)) is about twice the number at (j=1) for (p=p_{3,k_3}) while both numbers are approximately equal for (p_{3,k_3+1}). For fixed k and p, (E{T}^{(j)}_{k}) increases with j. Thus, we can expect the largest number of tests at the last stage, (k+1). The ratio of the number expected for two subsequent stages, however, never exceeds (sim 2.1) for any, p, smaller than the maximum value for which the strategy is optimal. This is reflected in Fig. 5b where we have plotted the ratio (E{T}^{(j+1)}_{k}(m,p)/E{T}^{(j)}_{k}(m,p)) with (m=(3^k,ldots ,3)) and (1le jle k) for various k. All the ratios decrease with decreasing p, those with (jge 2) approach 1 as (prightarrow 0) with an unnoticeable k dependence and the ratio, (E{T}^{(2)}_{k}/E{T}^{(1)}_{k}), goes to zero (as (m_1^2p/m_2)). Computing (E{T}^{(j)}_{k}(m,p)) for (m=(mu ^{k},ldots ,mu )) at the highest end of its region of optimality, (p=p_{mu ,k_mu }), we obtain:
$$begin{aligned} E{T}(j,mu )equiv E{T}^{(j)}_{k}(mu ^{k_mu },ldots ,mu ,p_k)&=mu ^{j-1} left( 1-mu ^{-mu ^{2-j}}right) qquad 2le j le k+1, end{aligned}$$
(4)
which is independent of k. We show in Fig. 5c plots of (E{T}(j,mu )) as functions of j for various values of (mu ). We observe that (E{T}(j,mu )) increases with j approaching the limiting value, ({mathbf{ET_mu }}= mu log (mu )). This implies that, if we use a (m=(3^{k_3},ldots ,3)) scheme for situations with (ple p_{3,k_3}), we can expect that the number of tests at each stage will never exceed ({mathbf{ET_3}}sim 3.296) times the number of tests of the first stage. The upper bound, ({mathbf{ET_mu }}), increases with (mu ). Thus, the largest (mu ), the largest will be the expected number of tests at any given stage compared with the first one (given that (ple p_{mu ,k})). This is important when running the strategy in parallel on (N_w) pools: having to test more pools than (N_w) (what we call overflow) at stages (jge 2) complicates the book-keeping and increases the throughput time.
Table 1 illustrates how the strategy (m=(27,9,3)) performs for (p=0.02) when run on 96 pools simultaneously. In this table, the time unit identifes the number of the run. Given that up to 96 wells can be tested simultaneously in this example, in principle, new pools of samples could be accommodated in the empty wells of runs 5–7. The optimization in the use of these wells will be the matter of future studies. This and other examples are compared in greater detail in the Supplementary Note. The interface available at31 not only gives information on the expected cost but also on the throughput time for users to choose, among the various strategies they probed, which one best meets their needs.
Expected number of tests per stage. (a) Expected number of tests, (E{T}^{(j)}_{k}(m,p)), at each stage, j, with (2le jle k), as a function of p for strategies of the form (m=(3^k,ldots ,3)) with (k=1) (black), (k=2) (red), (k=3) (green) and (k=4) (blue). The thicker portion of the curves correspond to the values of p for which each of the schemes is optimal. The horizontal line in magenta corresponds to the number of tests at the first stage ((j=1)) for all k. (b) Ratio of the number of tests expected for two subsequent stages, (E{T}^{(j+1)}_{k}(m,p)/E{T}^{(j)}_{k}(m,p)), of the strategies with (m=(3^k,ldots ,3)) and (k=1) (black), (k=2) (red), (k=3) (green), (k=4) (blue) and (k=5) (magenta). (c) (ET(j,mu )=E{T}^{(j)}_{k}(mu ^{k_mu },ldots ,mu ,p_k)), as a function of j for (mu =2) (black), (mu =3) (red), (mu =4) (blue) and (mu =5) (magenta). We plotted the curves for any value of j, but only integer ones are meaningful.
Based on this discussion and on the results of the tables in the Supplementary Note, we conclude that the schemes with
(m=(3^k,ldots ,3))
are also good because they produce some of the smallest overflows when running the strategy in parallel. Even when subdividing the pools in two would produce less overflow, these strategies require more stages and, consequently, more time to identify the infected samples than those in which the pools are subdivided in three. In clinical laboratories the turnaround time directly impacts on the productivity. Thus, the schemes with
(m=(3^k,ldots ,3))
would be preferable.
