{"id":356,"date":"2020-04-09T10:47:16","date_gmt":"2020-04-09T08:47:16","guid":{"rendered":"http:\/\/members.loria.fr\/ADeleforge\/?p=356"},"modified":"2020-12-17T18:26:59","modified_gmt":"2020-12-17T16:26:59","slug":"the-maths-of-pool-testing-mixing-samples-to-speed-up-covid-19-detection","status":"publish","type":"post","link":"https:\/\/members.loria.fr\/ADeleforge\/the-maths-of-pool-testing-mixing-samples-to-speed-up-covid-19-detection\/","title":{"rendered":"The Maths of Group Testing: Mixing Samples to Speed Up COVID-19 Detection"},"content":{"rendered":"

\"\"<\/a> Version Fran\u00e7aise Ici <\/a>\"\"<\/a>\u00a0<\/em><\/p>\n

 <\/p>\n

\"\"<\/a><\/p>\n

Update 17\/12\/2020 :<\/span><\/strong> Since the publication of this post, a group of French researchers has created a website gathering recent publications and news articles on the use of group testing for COVID-19 detection around the world. Check it out!<\/span> https:\/\/www.groupool-covid19.org\/<\/a><\/p>\n

Now that a large part of the world’ population<\/a> is in lockdown to fight against the global spread of the new coronavirus, the crucial question is: What’s next? As lock-down measures will progressively be lifted, the key to avoid second and third waves of the pandemics will be massive and rapid testing<\/strong>, combined with case tracking and targeted quarantining. Unfortunately, the testing capacity of most countries is currently not nearly enough<\/a>.<\/p>\n

<\/p>\n

Last week, researchers at the Frankfurt Red Cross Blood Donor Service and the Institute for Medical Virology at the University Hospital Frankfurt of Goethe University succeeded in developing a procedure<\/a> that makes it possible to immediately and dramatically increase worldwide testing capacities<\/strong> for detecting SARS-CoV-2, the virus behind COVID-19. The procedure is based on pool testing<\/strong><\/em> (also called group testing<\/a><\/strong>), a principle as genius as simple, that was already used to detect syphilis during WWII. Rather than analysing individual patients’ samples (usually swabs from the throat or nose), one mixes a bunch of samples together, say 8, and runs the test on this cocktail, called a mini-pool<\/em><\/strong>. If the result is negative, you can reliably conclude that none of the 8 patients were infected, from one single test<\/strong>! If the test is positive, just divide your samples into two groups of 4 and repeat, until either a negative result is reached or a single sample is left.<\/p>\n

\"\"<\/a>
Figure 1<\/strong>. In this example, 8<\/strong> samples (including 1 positive) are fully analysed by running only 6<\/strong> tests, thanks to group testing. Note that mini-pool #5 did not have to be tested since #4 was tested negative: we deduce its positivity without a test. Depending on the (unknown) position of the positive sample, between 4 and 7 tests will be needed in that example.<\/figcaption><\/figure>\n

This procedure could readily be implemented by any laboratory in the world without the need for extra equipment. Given that running a single PCR test<\/a> for COVID-19 takes several hours on dedicated machines<\/a>, cutting down their number could save precious time <\/strong>in the ongoing fight against SARS-CoV-2.<\/p>\n

But how much<\/em><\/strong> time exactly? The figure below shows the theoretical average number of test per sample needed using group testing as a function of the population’s infection rate for different mini-pool sizes:<\/p>\n

\"\"<\/a><\/p>\n

Note that using mini-pools of size 1 corresponds to classical testing: one test per sample. The graph shows that if the proportion of infected people is larger than about 25% in the tested population, group testing is not advantageous compared to conventional testing. However, in a scenario where large campaigns of tests are conducted on random people in cities in order to track and isolate positive cases, it is reasonable to assume that no more than 10% of the population will be infected by COVID-19 at any given time. Here is a zoomed version of the above graph for infection rates below 10%. We also show on the right the inverse <\/em>of the graph,\u00a0which represents the average speed-up<\/em><\/strong> brought by group testing:<\/p>\n

\"\"<\/a><\/p>\n

We see that for infection rates around 5%, using mini-pools of 4 already boosts testing capacities by a factor of 2.5<\/strong>, while for infection rates around 1% mini-pools of 16 may speed up tests by a factor of 10 or more<\/strong> ! It is also interesting to note that for infections rates above 6%, using pools of more than 4 samples does not significantly improve results.<\/p>\n

Deriving the formulas for those graphs is actually a quite fun maths\u00a0 problem! In the rest of this blog post, I will try to explain how to do it in an accessible way. My goal is to provide an example of interesting and useful maths exercise to enjoy during lockdown. I also secretly hope that it can help raising awareness in group testing<\/strong>, which does not seem to have received a lot of attention<\/a> as of yet by politicians or media. Let’s spread the word together!<\/em><\/p>\n

1. Hypotheses<\/h2>\n

First, we will assume that each test can detect a positive sample inside a mini-pool with 100% accuracy<\/strong> (no false positives<\/a> or false negatives). The German study on SARS-CoV-2<\/a> mentioned earlier showed that mini-pools of 5 samples<\/strong> can be used without degrading accuracy. This recent paper<\/a> from the Israel Institute of Technology and the Rambam Health Care Campus (Haifa, Israel) suggests that pools of up to 32<\/strong> or even 64<\/strong> samples could be used while keeping the false-negative rate relatively low. Amplification cycles (running multiple tests) can also be used to improve reliability, but this will not be investigated here.<\/p>\n

Second, we will suppose that all samples have the same independent probability<\/strong> P+<\/sub><\/em> (between 0 and 1) of being positive, representing the population’s infection rate<\/strong>. Note that this independence assumption does not hold if we test, e.g.<\/em>, a group of people leaving in the same house. Here, we assume that samples are taken uniformly at random<\/em> in an infected population.<\/p>\n

Finally, for the sake of exposure, we will only consider mini-pools of size N<\/em> where N<\/em> is a power of 2<\/strong>, e.g.<\/em>, 23 <\/sup>= 2 x 2 x 2 = 8. This will make computations easier and cleaner.<\/p>\n

2. Worst-case number of tests<\/h2>\n

As a warm up exercise, let us find what is the maximal number of tests <\/strong>T<\/em>max <\/sub>needed<\/strong> to analyse an initial mini-pool of N=<\/em>2K<\/sup><\/em> samples. This corresponds to the \u00ab\u00a0worst case\u00a0\u00bb where every mini-pool<\/strong> along the procedure is tested positive<\/strong> and hence has to be split into two and further analysed. An example of this situation is illustrated below:<\/p>\n

\"\"<\/a>
Figure 2.<\/strong> A \u00ab\u00a0bad\u00a0\u00bb example where pool-testing 8 samples requires 15 tests.<\/figcaption><\/figure>\n

By counting the number of positive mini-pools of size >1, we see that:<\/p>\n

\"\"<\/a><\/p>\n

Using the formula for sums of geometrical series<\/a>, we obtain:<\/p>\n

\"\"<\/a><\/p>\n

Shoot, <\/em>in the worst case, we have to run more tests<\/strong> than when simply testing the N<\/em> samples individually! Is pool-testing really that good after all?<\/p>\n

Well, it all depends on how often<\/strong><\/em> this worst situation happens. To get an idea of this, let us stick to the example of Figure 2<\/strong> where exactly half<\/strong> of the samples to be tested are positive. Then, the worst case only happens when the samples are precisely in the alternated order +<\/strong><\/span>,–<\/strong>,+<\/strong><\/span>,–<\/strong>,… The probability of this to happen is the number of alternated orderings divided by the total number of orderings:<\/p>\n

\"\"<\/a><\/p>\n

To order N<\/em> samples, there are N<\/em> ways of choosing the first one, then (N<\/em>-1) ways of choosing the second one, (N<\/em>-2) ways of choosing the third one, etc. The total number of orderings is hence N<\/em> x (N<\/em>-1) x (N<\/em>-2) x … x 1 = N<\/em>! (\u00ab\u00a0N factorial\u00a0\u00bb<\/em>). To order them alternately, there are (N<\/em>\/2)! ways to order positive samples and (N<\/em>\/2)! ways to order negative samples, hence (N\/2)! x (N\/2)! = ((N\/2)!)\u00b2 ways in total. We obtain:<\/p>\n

\"\"<\/a><\/p>\n

where we used the following combinatorics notation:<\/p>\n

\"\"<\/a><\/p>\n

pronounced \u00ab\u00a0n choose k\u00a0\u00bb<\/em>. This counts the number of ways of placing k<\/em> identical elements into n<\/em> available positions. Here is a summary of our results for different values of N<\/em>:<\/p>\n\n\n\n\n\n\n\n\n
Initial mini-pool size<\/strong> N<\/em><\/td>\nMaximum number of tests<\/strong> T<\/em>max<\/sub><\/td>\nProbability<\/strong> P<\/em>worst<\/sub> (for 50% infection)<\/td>\n<\/tr>\n
2<\/td>\n3<\/td>\n1\/2<\/td>\n<\/tr>\n
4<\/td>\n7<\/td>\n1\/6<\/td>\n<\/tr>\n
8<\/td>\n15<\/td>\n1\/70<\/td>\n<\/tr>\n
16<\/td>\n31<\/td>\n1\/12,870<\/td>\n<\/tr>\n
32<\/td>\n63<\/td>\n1\/601,080,390<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

As can be seen, the worst case happens very rarely when using sufficiently large mini-pools. That’s reassuring!<\/p>\n

3. Average number of tests<\/h2>\n

Let us now look at the more general problem of the average number of tests<\/strong> needed when using mini-pools of size N<\/em>, for a given infection rate P+<\/sub><\/em>. To tackle this we will need to introduce appropriate notations (which is often the most difficult part of real-world maths problems). We will denote by m(i)<\/sup><\/em> a mini-pool of i<\/em> samples, i.e., a pool of i<\/em>. The mini-pools of a given size will be numbered \u00ab\u00a0from left to right\u00a0\u00bb, as shown in the example below:<\/p>\n

\"\"<\/a>
Figure 3.<\/strong> Numbering of mini-pools for an initial mini-pool of 8 samples.<\/figcaption><\/figure>\n

With this notation, the individual samples are hence written as pools of 1<\/em>, that is, m1<\/sub>(1)<\/sup><\/em>, m2<\/sub>(1)<\/sup><\/em>, … , mN<\/sub>(1)<\/sup><\/em>. We will use R+<\/sub>[m(i)<\/sup><\/em>] to denote the positivity<\/em> of a pool, where\u00a0R<\/em>+<\/sub>[m(i)<\/sup><\/em>]=1 if m(i)<\/sup><\/em> contains a positive sample and R<\/em>+<\/sub>[m(i)<\/sup><\/em>]=0 otherwise. Similarly we will denote by R<\/em>–<\/sub>[m(i)<\/sup><\/em>] = ( 1 – R<\/em>+<\/sub>[m(i)<\/sup><\/em>] ) the negativity<\/em> of a pool.<\/p>\n

When doing a group test, we first need to test the initial mini-pool containing all samples. Then, whenever a mini-pool is tested positive, we split it into 2 pools of equal size and run further tests on them. A first approach to estimate the number of test needed is hence to count twice the number of positive mini-pools<\/strong> of size 2 or more. Following our notations, this gives:<\/p>\n

\"\"<\/a><\/p>\n

This can be written in a more compact way using the mathematical symbol for sums:<\/p>\n

\"\"<\/a><\/p>\n

However this formula is missing \u00ab\u00a0shortcuts\u00a0\u00bb, such as the one showed in Figure 1<\/strong>. When a mini-pool is tested positive, if the first half of it is tested negative, then there is no need to test the second half: we know it must be positive. To remove these shortcuts in our count, we need to correct the above formula as follows:<\/p>\n

\"\"<\/a><\/p>\n

The new term removes one test whenever the first half of a pool is negative while the second half is positive. For what follows, it will be convenient to rewrite this formula only in terms of the negativity<\/em> of mini-pools:<\/p>\n

\"\"<\/a><\/p>\n

We now want to know how much T<\/em> will be in average<\/strong>, given that each individual sample has a probability P<\/em>+<\/sub> of being positive. This quantity is called the \u00ab\u00a0expectation of T\u00a0\u00bb<\/em> and we note it E{T<\/em>}. Using the fact that the expectation is linear<\/em> and that the expectation of the product of two independent variables is the product of their expectations, we have from\u00a0 the previous formula:<\/p>\n

\"\"<\/a><\/p>\n

We are left with the problem of computing the expectations of the mini-pools’ negativities. By our hypothesis, a single sample is negative with probability P–<\/sub><\/em>=(1-P<\/em>+<\/sub>). Hence, we have:<\/p>\n

\"\"<\/a><\/p>\n

for any n<\/em> between 1 and N<\/em>. In addition, a mixture of i<\/em> samples will be tested negative if and only if every sample in it is negative<\/strong>. Its expected negativity is hence the product<\/strong> of the expected negativity of each sample, i.e.<\/em>,\u00a0(P– <\/sub><\/em>) x (P– <\/sub><\/em>) x (P– <\/sub><\/em>) x … This gives:<\/p>\n

\"\"<\/a><\/p>\n

Inserting these in the previous expression of E{T<\/em>} we obtain:<\/p>\n

\"\"<\/a><\/p>\n

After simplification, we finally obtain the following general formula for the average number of tests:<\/p>\n

\"\"<\/a><\/p>\n

It is also convenient to express the average number of test per sample<\/strong>. To do this, we divide the above expression by the initial size of the mini-pool, N<\/em>=2K<\/em><\/sup>:<\/p>\n

\"\"<\/a><\/p>\n

This expression is a polynomial<\/a> in P<\/em>–<\/sub>. As expected, we see that if the population is 100% infected (P<\/em>– <\/sub>= 0), pool-testing requires about twice as many tests as the regular procedure (the \u00ab\u00a0worst-case\u00a0\u00bb situation studied in the last section). We also see that the number of needed tests decreases with the infection rate, as showed in the graphs at the beginning of this post.<\/p>\n

Here is a table detailing mean numbers of tests per samples<\/strong> as a function of infection rate and initial mini-pool size:<\/p>\n\n\n\n\n\n\n\n\n
Infection rate \u25ba
\n<\/strong>\u25bc Initial mini-pool size<\/strong><\/td>\n		0.5%<\/b><\/td>\n1%<\/b><\/td>\n2%<\/b><\/td>\n3%<\/b><\/td>\n5%<\/b><\/td>\n8%<\/b><\/td>\n10%<\/b><\/td>\n20%<\/b><\/td>\n50%<\/b><\/td>\n<\/tr>\n
2<\/strong><\/td>\n0.51<\/td>\n0.51<\/td>\n0.53<\/td>\n0.54<\/td>\n0.57<\/td>\n0.62<\/td>\n0.64<\/td>\n0.78<\/td>\n1.12<\/td>\n<\/tr>\n
4<\/strong><\/td>\n0.26<\/td>\n0.28<\/td>\n0.31<\/td>\n0.34<\/td>\n0.39<\/td>\n0.48<\/td>\n0.53<\/td>\n0.77<\/em><\/td>\n1.30<\/td>\n<\/tr>\n
8<\/strong><\/td>\n0.15<\/td>\n0.17<\/td>\n0.21<\/td>\n0.25<\/td>\n0.33<\/em><\/td>\n0.45<\/em><\/td>\n0.52<\/em><\/td>\n0.82<\/td>\n1.41<\/td>\n<\/tr>\n
16<\/strong><\/td>\n0.09<\/td>\n0.12<\/td>\n0.18<\/td>\n0.23<\/em><\/td>\n0.33<\/em><\/td>\n0.46<\/td>\n0.54<\/td>\n0.87<\/td>\n1.47<\/td>\n<\/tr>\n
32<\/strong><\/td>\n0.07<\/em><\/td>\n0.10<\/em><\/td>\n0.17<\/em><\/td>\n0.23<\/em><\/td>\n0.34<\/td>\n0.48<\/td>\n0.57<\/td>\n0.90<\/td>\n1.51<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

4. Open questions<\/h2>\n

There are still interesting open questions left to explore. In particular, if the tests are not 100% accurate, what is the best way to reduce errors using multiple cross tests? How to generalise these formulas to initial pools which are not powers of two? I leave these questions to the interested readers, and maybe I’ll come back to it in a future blog post!<\/p>\n

Stay safe everyone!<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"

Version Fran\u00e7aise Ici \u00a0   Update 17\/12\/2020 : Since the publication of this post, a group of French researchers has created a website gathering recent publications and news articles on the use of group testing for COVID-19 detection around the world. Check it out! https:\/\/www.groupool-covid19.org\/ Now that a large part of the world’ population is […]<\/p>\n","protected":false},"author":176,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-356","post","type-post","status-publish","format-standard","hentry","category-non-classe"],"_links":{"self":[{"href":"https:\/\/members.loria.fr\/ADeleforge\/wp-json\/wp\/v2\/posts\/356","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/members.loria.fr\/ADeleforge\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/members.loria.fr\/ADeleforge\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/members.loria.fr\/ADeleforge\/wp-json\/wp\/v2\/users\/176"}],"replies":[{"embeddable":true,"href":"https:\/\/members.loria.fr\/ADeleforge\/wp-json\/wp\/v2\/comments?post=356"}],"version-history":[{"count":116,"href":"https:\/\/members.loria.fr\/ADeleforge\/wp-json\/wp\/v2\/posts\/356\/revisions"}],"predecessor-version":[{"id":589,"href":"https:\/\/members.loria.fr\/ADeleforge\/wp-json\/wp\/v2\/posts\/356\/revisions\/589"}],"wp:attachment":[{"href":"https:\/\/members.loria.fr\/ADeleforge\/wp-json\/wp\/v2\/media?parent=356"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/members.loria.fr\/ADeleforge\/wp-json\/wp\/v2\/categories?post=356"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/members.loria.fr\/ADeleforge\/wp-json\/wp\/v2\/tags?post=356"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}