Batch COVID-19 testing with divide-and-conquer

I put together a numerical simulation of how batch testing with divide-and-conquer could hypothetically improve the efficiency of our use of back-end testing resources (like PCR). The idea is that specimens from multiple individuals can be combined (after subdividing) for testing and that one of several positive individuals would be enough to trigger a positive test result. If a group tests positive, then that group would be subdivided for further testing (with existing subdivided specimens).

My finding is that this may provide efficiency gains if the population being tested has a disease saturation below around 10%, and an order-of-magnitude gain in efficiency may be available where the saturation is below 1%.

For example:

Simulations per trial: 1000
saturation: 0 %, batch: 4 , levels: 2 , positiveavg: 0.0 , size: 16 , testavg: 1.0 , efficiency= 16.0 !
saturation: 2 %, batch: 4 , levels: 2 , positiveavg: 0.334 , size: 16 , testavg: 3.428 , efficiency= 4.66 !
saturation: 4 %, batch: 4 , levels: 2 , positiveavg: 0.666 , size: 16 , testavg: 5.444 , efficiency= 2.93 !
saturation: 6 %, batch: 4 , levels: 2 , positiveavg: 0.988 , size: 16 , testavg: 7.224 , efficiency= 2.21 !
saturation: 8 %, batch: 4 , levels: 2 , positiveavg: 1.295 , size: 16 , testavg: 8.604 , efficiency= 1.85 !
saturation: 10 %, batch: 4 , levels: 2 , positiveavg: 1.624 , size: 16 , testavg: 9.776 , efficiency= 1.63 !
saturation: 12 %, batch: 4 , levels: 2 , positiveavg: 1.863 , size: 16 , testavg: 10.604 , efficiency= 1.5 !
saturation: 14 %, batch: 4 , levels: 2 , positiveavg: 2.278 , size: 16 , testavg: 11.968 , efficiency= 1.33 !
saturation: 16 %, batch: 4 , levels: 2 , positiveavg: 2.59 , size: 16 , testavg: 12.904 , efficiency= 1.23 !
saturation: 18 %, batch: 4 , levels: 2 , positiveavg: 2.897 , size: 16 , testavg: 13.612 , efficiency= 1.17 !
saturation: 20 %, batch: 4 , levels: 2 , positiveavg: 3.23 , size: 16 , testavg: 14.312 , efficiency= 1.11 !
saturation: 22 %, batch: 4 , levels: 2 , positiveavg: 3.538 , size: 16 , testavg: 15.172 , efficiency= 1.05 !
saturation: 24 %, batch: 4 , levels: 2 , positiveavg: 3.879 , size: 16 , testavg: 15.692 , efficiency= 1.01 !
saturation: 26 %, batch: 4 , levels: 2 , positiveavg: 4.097 , size: 16 , testavg: 16.196 , efficiency= 0.98
saturation: 28 %, batch: 4 , levels: 2 , positiveavg: 4.406 , size: 16 , testavg: 16.524 , efficiency= 0.96

Python source code: https://gist.github.com/BrentBradburn/1d5ba5b44a8e8bce19a9ba2d7ec8106d

P.S. It seems like this would be most apropos to light-touch specimen gathering (maybe saliva) more so than deep nasal swabbing.

P.P.S. This batching approach can be yet more efficient if the testing is skipped at the bottommost (individual) level. For example, the lowest batch might be a household – which would be a useful granularity for receiving test results. Doing this would produce efficiency gains even in communities with higher saturation of the disease.

3 Likes

Thanks for sharing @BrentBradburn!

P.S. I moved this to #i-am-working-on.

1 Like

I am working on similar idea using excel. Maybe we can collaborate and make it better.

Wayne

2 Likes

The idea of grouping tests has been studied extensively both mathematically and algorithmically. See https://en.wikipedia.org/wiki/Group_testing for more in this topic.
The optimal algorithm does not do divide and conquer: you should first divide the whole pool into small groups of equal same size and then test each of them using a variation of divide and conquer. The optimal size would be -1/log(1-p), where p is the infection rate.

2 Likes

I like this idea, but is anyone doing it? I’ve talked to a lot of people here in Sweden working with both testing for virus presence and antibodies development but of all the people I’ve talked to, nobody has heard of anyone pooling patient samples (although this is a common approach when working with samples from animals). Is anyone doing patient pooling today? Especially for PCR-based testing?

1 Like