key: cord-263831-7aj9ozpn
authors: Mutzel, P.; Bertram, A.; Jünger, P.; Krieger, H.; Schmitz, S.; Jünger, M.
title: Increasing Virus Test Capacity via Recursive Pool Testing with an Application to SARS-CoV-2 Testing
date: 2020-07-04
journal: nan
DOI: 10.1101/2020.07.02.20144956
sha: 
doc_id: 263831
cord_uid: 7aj9ozpn

In the context of adequate reactions to the current Covid-19 pandemic, Seifried, Ciesek et al. [6, 5] have proposed the application of SARS-CoV-2 pool testing in the pursuit of increasing testing capacity. We show how this method can be substantially improved in realistic scenarios, and we point out a possible impact on the ongoing discussion concerning the need of increased testing as a complementary measure to relaxed restrictions.

Seifried, Ciesek, et al. [6, 5] have proposed the application of SARS-CoV-2 pool testing in April 2020, see also [2, 1] . The described procedure uses two aliquots of each sample. The first set of aliquots is partitioned into pools of a given size and these pools are tested. A negative test result means that all corresponding samples in the pool are negative, a positive test result requires testing the corresponding samples in the pool individually using the corresponding second set of aliquots.

The authors state: "Dabei wird der Abstrichtupfer zunächst in ein Archivröhrchen gegeben und anschließend in ein Poolgefäß. Da sich bei dieser Poolmethode das Volumen im Poolgefäß nicht vermehrt, wird auch keine Verdünnung und damit keine Abnahme der Empfindlichkeit (Sensitivität) beobachtet." 1 According to the article, this pool test procedure was developed and patented by the Goethe University and the DRK blood donation service and leads to the fact that a constantly demanded extension of testing is made possible. The procedure was tested on 50 samples, of which 5 were SARS-CoV-2 positive. These 50 samples were divided into 10 pools of 5 samples each.

In a newer article, Lohse et al. [4] report on testing 1,191 samples, 23 of which are positive, they used pools of size 30 that were again subdivided into subpools of size 10, and they needed only 267 tests. This strategy requires 3 (rather than 2) aliquots of each sample. The authors state that borderline samples might escape detection in pools of size 30. However, they argue that those stem from almost recovered persons.

Both research groups emphasize a tremendously increased testing capacity when the infection rate is low and consequently, many pool tests will have a negative result.

We review the method in [6, 5] , henceforth called "the Frankfurt method", also in view of the variant in [4] , henceforth called "the Saarbrücken variant", propose a new variant based on recursive pool testing, demonstrate its potential in comparison to the Frankfurt method as well as the Saarbrücken variant, and discuss the possible impact on strategies that accompany the current relaxation of restrictions due to the Covid-19 pandemic.

The idea is to combine many samples into one combined sample ("pool") and apply the test to the combined sample. If the result is negative, all samples in the combined sample are negative. If the result is positive, further testing is necessary in order to determine negativity/positivity for all samples in the combined sample. This idea has already been applied for syphilis testing of soldiers in the 1940s, and is popular for HIV testing since 2009.

We are given n samples {s 1 , s 2 , . . . , s n } for testing. The Frankfurt pool testing method proceeds as follows:

1. Prepare to divide each sample s i into up to 2 aliquots s i,1 and s i,2 .

2. Partition the set of all n samples into subsets of a given size p < n. (In [6] we have n = 50 and p = 5, in [4] we have n = 1,191 and p = 30.)

3. Make a pool test for each subset using the aliquots s i,1 . (These tests can be performed  simultaneously.) 4. Declare all samples within each negatively tested subset negative.

5. Test all samples within each positively tested subset individually using the aliquots s i,2 .

Rather than testing all samples in a positive pool, the idea is to again split this pool subset into 2 (or more) smaller subsets for pool testing, and keep splitting as long as possible.

In detail, our enhancement concerns steps 1 and 5 of the Frankfurt pool testing method. For ease of exposition, we assume p to be a power of 2, i.e., p = 2 k for some k. (The method can be easily adapted to arbitrary values of p.) In step 1, we moderately increase the number of aliquots: 1'. Prepare to divide each sample s i into up to a = 1 + log 2 p aliquots {s i,1 , s i,2 , . . . , s i,a }.

Step 5 is replaced by an application of the Divide&Conquer principle that is well-known in Computer Science: 5'. For each positively tested subset apply the divide&conquer method decribed next.

2 . CC-BY-NC-ND 4.0 International license It is made available under a is the author/funder, who has granted medRxiv a license to display the preprint in perpetuity. (which was not certified by peer review)

The copyright holder for this preprint this version posted July 4, 2020. . https://doi.org/10.1101/2020.07.02.20144956 doi: medRxiv preprint

For ease of exposition, we assume the pool subset to consist of the sample aliquots s b,1 , s b+1,1 , s b+2,1 , . . . , s b+p−1,1 .

These are the p consecutive aliquots starting at index b. E.g., for n = 16 and p = 4, the pool subsets are {s 1,1 , s 2,1 , s 3,1 , s 4,1 } {s 5,1 , s 6,1 , s 7,1 , s 8,1 } {s 9,1 , s 10,1 , s 11,1 , s 12,1 } {s 13,1 , s 14,1 , s 15,1 , s 16,1 }.

Then, with e = b + p − 1, dc test(b, e, d) stands for "Test the pool of the samples s b , s b+1 , s b+2 , . . . , s b+p−1 using aliquots d". So our task is dc test(b, e, 1). Here is dc test(b, e, d) in pseudocode: 

We have n = 16 samples s 1 , s 2 , . . . , s 16 all of which are negative but two, namely s 5 and s 15 , which are positive. The pool size is p = 4.

Both methods apply pool tests to the subsets The first and the third will have a negative result, the second and the fourth a positive result. Up to this point, both methods will have applied 4 tests. The Frankfurt pool testing method will now apply individual tests to the sample aliquots s 5,2 , s 6,2 , s 7,2 , s 8,2 , s 13,2 , s 14,2 , s 15,2 , and s 16,2 (8 individual tests) so that a total of 12 tests is performed.

The recursive pool testing method will replace {s 5,1 , s 6,1 , s 7,1 , s 8,1 } by {s 5,2 , s 6,2 } and {s 7,2 , s 8,2 } and make pool tests for both. It will get a positive result for the first and therefore test s 5,3 and s 6,3 individually. Then it will replace {s 13,1 , s 14,1 , s 15,1 , s 16,1 } by {s 13,2 , s 14,2 } and {s 15,2 , s 16,2 }, make pool tests for both and get a negative result for the first and a positive result for the second. Therefore it will test s 15,3 and s 16, 3 individually. This involves another 4 pool tests plus 4 individual tests, so, again, a total of 12 tests, no improvement in terms of the number of tests.

. CC-BY-NC-ND 4.0 International license It is made available under a is the author/funder, who has granted medRxiv a license to display the preprint in perpetuity.

The copyright holder for this preprint this version posted July 4, 2020. .

Here is an illustration of the actions of both methods (boxes correspond to tests, blue means "negative", red means "positive". Both methods initially divide the entire set of 16 samples 

So far we have split each pool into 2 subpools. Of course, we can just as well split into B > 2 subpools. Again, for ease of exposition, we assume that the pool size p is a power of B, i.e., p = B k for some k. In practice, we expect pools in which there is no or only one positive sample. In the former case, no further test is necessary. In the latter case, the positive sample is found after 1 + B log B p tests. E.g., let p = 4 and B = 2. Then the pool of size 4 is positive (first test). One of the two subpools of size 2 (second and third test) is positive and requires another two individual tests (fourth and fifth test), i.e., a total of 1 + 2 log 2 4 = 5 tests. The situation is illustrated in Figure 1 . The case p = 9 and B = 3 with a total of 1 + 3 log 3 9 = 7 tests is illustrated in Figure 2 . is the author/funder, who has granted medRxiv a license to display the preprint in perpetuity.

The copyright holder for this preprint this version posted July 4, 2020. . https://doi.org/10.1101/2020.07.02.20144956 doi: medRxiv preprint The analysis for two or more positive samples in a pool is more involved. If the pool contains two positive samples, then we can show that the function

gives the expected number of tests as a function of B and p. The picture on the right of Figure 3 shows a plot of the function f 2 (B, p). Again, it turns out that B = 3 is the best choice as long as p ≥ 13. Indeed, for pool sizes from 7 to 12, it would be optimal to split the pools into 4 pieces, for pool size 6, the value B = 5 would be ideal, and smaller pool sizes should be tested individually. Three or more positive samples in a pool of size up to 30 are quite unrealistic.

Our computational tests confirm that B = 3 is the best choice in realistic scenarios with pool size 30. So we restrict our attention in the following to the 3-split version of recursive pool testing. 

According to the Robert Koch Institute (RKI), the number of tests per week from calendar weeks 2 to 21 varied between 124,000 and 408,000 for about 170 laboratories, which is a total of about 2, 000 tests per laboratory week on average, i.e., 400 per day. The proportion of positive tests in Germany has been between 1.5 % and 9 %. In the 21st calendar week, 344,782 laboratory tests for the coronavirus (SARS-CoV-2) were carried out in Germany, 5,116 (1.5 %) have been positive.

. CC-BY-NC-ND 4.0 International license It is made available under a is the author/funder, who has granted medRxiv a license to display the preprint in perpetuity.

The copyright holder for this preprint this version posted July 4, 2020. .

Currently, a typical laboratory seems to test about 400 samples per day. Accordingly, we have simulated tests for n = 400 samples with pool size p = 27 for varying infection rates. The minima/maxima/averages/medians have been taken over 1,000,000 samples, in which the infected samples are uniformly randomly distributed. The results for the Frankfurt method in comparison to the 3-split version of the recursive method are presented in Table 1 and, for the medians only, as a bar chart in Figure 4 . The results show that, with small infection rates up to about 5 %, the new approach outperforms the Frankfurt approach by more than 50 %. For example, for an infection rate of 1.5 %, our method needs about 66 tests compared to the Frankfurt method with 150 tests (which is a reduction of 56 %). For larger rates, the advantage is less significant, and for rates from about 25 %, the Frankfurt approach is better.

Compared to current individual testing methods without pools, our experiments show that with a positive sample rate of 1.5 % the number of tests could be reduced by 83.5 %. CC-BY-NC-ND 4.0 International license It is made available under a is the author/funder, who has granted medRxiv a license to display the preprint in perpetuity.

The copyright holder for this preprint this version posted July 4, 2020. .

The Frankfurt pool testing method increases the test capacity significantly and our simulations indicate that recursive pool testing has the potential to increase the test capacity even further by a factor of about 2 in realistic scenarios. However, pool testing in general and the recursive method in particular have drawbacks that limit their applicability. We recall that we refer to the pool size as p and to the required number of aliquots as a.

As Lohse et al. [4] state, borderline samples might escape detection in pools of size 30. However, they expect those samples might stem from almost recovered persons.

With increased p, sensitivity, i.e., the chance to detect a positive sample in a pool of negative samples, diminishes. In PCR technology, ideal amplification follows a 2c pattern where c is the cycle number. Assuming a 40-cycle PCR, one can estimate the amount of amplified DNA by amplified DNA = initial DNA × 240. Typically, a realtime PCR reliably detects positive samples as long as the target reaches the threshold value by cycle 37 or 38. With each 1:2 dilution (50 % virus concentration) the ct-value is increased by 1. So, for a 1:p dilution, ct values increase by log 2 p. With a 128-size pool, one can assume an increase in the ct value from a single sample to a pool of log 2 128 = 7. This means that samples with single-sample ct values 31 or above might escape detection. With this in mind, the pool size can be determined by counterbalancing cost and sensitivity.

As a working hypothesis for the following, we assume that pools should not be larger than 30, on the other hand, it is desirable to stay close to 30.

Individual testing requires no sample splitting into aliquots, in our notation a = 1, the Frankfurt method requires up to a = 2, the Saarbrücken variant up to a = 3, and our recursive method with 3-splits up to a = 1 + log 3 p aliquots of each sample, at pool size p = 9 the latter amounts to a = 3 aliquots like the Saarbrücken variant, at pool size p = 27 the latter amounts to a = 4 aliquots. It is unclear, see also below, if a = 4 is tolerable in laboratory practice. We have pointed out the superiority of the 3-split recursive method, but we have not yet taken a limitation of the number of required aliquots into account. If a ≤ 3 is required, the 3-split method would have to set the pool size to only 9 which is undesirable. Likewise, the 4-split recursive method (B = 4) with "natural" pool size p = 4 2 = 16 is undesirable due to small pool size. On the other hand, 6-split with "natural" pool size p = 6 2 = 36 is undesirable, because the pools get too big. An interesting alternative is to consider 5-splits (i.e., take B = 5) and set the pool size to p = 5 2 = 25.

We have repeated the experiment reported in Table 1 and Figure 4 with this alternative in order to see if the number of tests deteriorates in comparison to the previous table for which up to 4 aliquots were needed. We also ran the Saarbrücken variant on the same instances in order to see how well it performs in comparison. The results are given in Table 2 and Figure 5 . We observe that recursive 5-split consistently outperforms the Saarbrücken variant and its performance only moderately deteriorates in comparison to the 3-split recursive method.

We also compared the same two methods as well as the 3-split recursive method on 1,000,000 random instances of the original Saarbrücken experiment, i.e., n = 1,191 samples, 23 of which positive, randomly distributed, 1,000,000 instances. The pool sizes are 30 for the Saarbrücken variant, 25 for the 5-split, and 27 for the 3-split recursive method, see Table 3 . The 5-split recursive method significantly outperforms the Saarbrücken method (both require up to 3 aliquots) even though it uses pools of size 25 rather than 30, and its performance is is pretty close to the one of the recursive 3-split method that requires up to 4 aliquots.

. CC-BY-NC-ND 4.0 International license It is made available under a is the author/funder, who has granted medRxiv a license to display the preprint in perpetuity.

The copyright holder for this preprint this version posted July 4, 2020. . However, with the 5/25 pooling, a lab can use the same pooling device with identical settings to produce 25-size pools by just using the previously generated size-5-pools as input and still keep the original (aliquot 1) as well as the size-5-pools (aliquot 2) and obtain the 3rd aliquot by making up the 25-size-pool. No re-programming is needed, and lab personnel does not need to keep in mind whether to pool 3, 9 or 27 samples as it would always boil down to 1 in 5.

. CC-BY-NC-ND 4.0 International license It is made available under a is the author/funder, who has granted medRxiv a license to display the preprint in perpetuity.

The copyright holder for this preprint this version posted July 4, 2020. . https://doi.org/10.1101/2020.07.02.20144956 doi: medRxiv preprint

With current technology, a batch with up to 94 samples takes a little over 3 hours to be analysed. Any time to pool samples would have to be performed beforehand and laboratory experience indicates that this takes about another roughly 2 hours for 380 samples (pooled into pools of size 5, thus 76 pools). Assuming no invalid results and only valid batches, as well as neglecting setup-times and time taken to produce the pools, individual results are available after 3a hours, i.e., 3 hours for individual testing (up to 94 samples), 6 hours with the Frankfurt method, 9 hours with the Saarbrücken variant as well as the 5-split recursive method at pool size 25, and 12 hours with the recursive 3-split method at pool size 27.

While it takes 8 hours to test 1,000 samples using a roche cobas 8800 analyzer, the authors have calculated that with pool size 5 it takes a little more than 14 hours for the same samples (1 % positives), and, with recursive pool testing at size 25 and 5, the turnaround-time would go up to 17 hours. While the extended waiting times are intolerable in many scenarios like testing due to individual doctoral prescription or testing in known hot spots, they might well be tolerable in mass testing without previous indications, e.g., when opening a school with 1,000 students and teachers and testing at fortnightly intervals for possible early detection of infections, mainly in settings with very few or no positive samples to be expected.

Of course, in order to convince laboratories to undertake changes in their workflow that are prone to prolonged turnaround times, the course of action must be provided in an easily digestible form. The question is: How could something like this be realized in practice?

First and foremost, the LIS (lab information system) needs to be able to distinguish between samples which can be pooled (let's call them "screening samples") and samples which must not be pooled ("diagnostic samples"). Those screening samples need to be entered into the system with a specific request, different from the diagnostic samples' entries. Also, the user (not necessarily the samples' originators) need to be able to see, at any time, at which point in the prospective pooling step a sample might be just now. Therefore, it might be prudent to allow for 3 different analyses if working with 2 different pools: "number analyses = number aliquots". We start with aliquots s i,1 of the n samples {s 1 , s 2 , . . . , s n } and add p samples into one pool which is then analysed using analysis corona pool 1. If corona pool 1 turns out negative, the lab order for those patients is fulfilled and the negative result is reported. All those with either a positive or invalid result appear with "not negative" (and hidden to the sender) on the lab report and make the next step (request) appear (open) on the lab report corona pool 2. Same here, any negative pools end up with the negative result behind this analysis while any positive or invalid results appear as "not negative" internally within the lab and make the third analysis appear, visibly, on the report corona screen. All 3 analyses might have the same friendly name appear on the lab report, visible to the samples' sender.

The strict consecutive pattern of dividing positive pools into subpools described in Section 2.2 has been useful for a concise description of the algorithm, but it is not necessary for the correctness of the recursive method. Rather, different aliquots of the samples in a positive pool can be arbitrarily assigned to the subpools.

Within the lab, samples will be archived and can be retrieved if any pool is positive. In order for the lab personnel to know whether to pool the samples with 26 or 8 or 2 or whatever number of other samples, samples should be stored in different archives and marked with different colours, depending on their status within the workflow chain.

An easier setup would be a pooling device that inherently can pool 5 samples and use this to undergo a 2-step pooling.

Step 1: Make pools of 5 of all screening samples.

Step 2: Make pools of 5 of all pools from step 1. This way, using the same pipetting robot and the same programming, the complete chain of barcode numbers can be passed on to the LIS after step 2 . CC-BY-NC-ND 4.0 International license It is made available under a is the author/funder, who has granted medRxiv a license to display the preprint in perpetuity.

The copyright holder for this preprint this version posted July 4, 2020. . https://doi.org/10.1101/2020.07.02.20144956 doi: medRxiv preprint is complete. This way, also, all containing pools of 5 which might be needed if the 25-size-pool comes back positive, are already available and ready for second stage testing. The downside is: With low prevalence, a significant number of size-5 pools are created unnecessarily, costing time.

However, already having the LIS know the next smaller pools barcode makes it easier to work with residual lists, i.e., which samples still have no result and where do I find them.

These days we face the situation that some restrictions imposed due to the Covid-19 pandemic are reduced stepwise and another shutdown would be disastrous for the economy. We regularly test the players in the German soccer leagues but have no plan how to detect new emerging hotspots in, say, re-opened kindergartens, schools, and retirement homes as early as possible. It seems that a substantially increased testing capability might help in developing an enhanced strategy in dealing with this situation. This view is shared, e.g., by the German Federal Minister of Health Jens Spahn [3] : "Es ist viel teurer, zu wenig zu testen, als zu viel zu testen." 2 Currently (end of June 2020), the German Federal State of Bavaria offers preventive SARS-CoV-2 mass testing to all (roughly 13,000,000) state inhabitants. We believe that pool testing in general and the recursive method in particular may be the method of choice.

However, one must not assume that sample pooling reduces the cost of testing by a factor of the pool size. It is clear that laboratories save on reagents with the reduced number of tests. With recursive pooling, we have shown that reagents use can be massively reduced. For positive sample rates of 1.5 %, the reduction is about 83 % with respect to current individual testing and 56 % with respect to the Frankfurt method, respectively. However, one must consider the downsides, namely the increased personnel and other consumable costs (like secondary tubes and pipette tips) due to longer hands-on times and more procedural steps. A major problem could also be the significantly prolonged turnaround times. However, this setup is certainly feasible for laboratories with limited PCR-capacity or countries with limited reagent supplies as well as those having to deal with sample numbers exceeding the laboratory capacities by a large factor over a prolonged period of time. We definitely think that recursive pool testing may be useful in mass testing when only few infections are to be expected.

We can suggest to labs involved in SARS-CoV-2 testing to consider evaluating this setup with their own equipment and calculate the "sweet spot" for their circumstances based on an arbitrary number of samples with varying positivity rates.

While it is also possible to transfer this idea to antibody-testing, one needs to keep in mind that antibody tests mostly follow a linear dilution formula while the exponential increase in DNA-fragments in PCR technology allows for greater dilution factors with relatively smaller impact on possible false-negatives.

Pooling samples could accelerate new coronavirus testing

Corona pool testing increases worldwide capacities many times over

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

FACT -Frankfurt adjusted COVID-19 testing-a novel method enables high-throughput SARS-CoV-2 screening without loss of sensitivity. medRxiv

Pool-Testen von SARS-CoV-2 Proben erhöht die Testkapazität weltweit um ein Vielfaches

We gratefully acknowledge the advice of Ulrich Jürgens, Andrea Krieger, Dirk Schmidt, and Norbert Schöngen.