COVID testing, hypercubed

Neil Turok is a cosmologist noted for innovating approaches to understanding the Big Bang. He was hard at work on bouncing universes when the novel coronavirus pandemic struck and changed both the world and his research.

Turok, who holds the Mike and Ophelia Lazaridis Niels Bohr Chair in Theoretical Physics at Perimeter Institute, is also the founder of one of Perimeter’s sister institutes, the African Institute for Mathematical Sciences (AIMS). Keenly aware that regularly testing everyone for COVID is expensive, and that this poses a particular challenge in the developing world, Turok joined an AIMS-centered team looking at group testing to reduce costs. A paper outlining their new scheme has just been published in the prestigious international journal Nature.

Sometimes known as “batch testing” or “pool testing,” group testing works by combining samples taken from many people. This is an old idea – first proposed in the 1940s when the US Army wanted to test all returning troops for syphilis – but it’s never been widely deployed. Now, with “test, test, test” being crucial to beat COVID, group testing is an idea whose time has come.

The 1940s group testing scheme is straightforward: you divide people into groups, test each group, and then test each individual in any group that tests positive. That’s only two sequential rounds of testing, so it’s fast, but depending on the prevalence of infection, it still requires a lot of tests.

The idea can be pushed further. In principle, the best scheme for minimizing the number of tests is a binary search: you divide a positive group in half, and test one half. If it’s negative, the other half must be positive. If it’s positive, you must test the other half.

This approach lets you test the greatest number of people with the fewest tests, but can involve multiple sequential rounds testing. Since each test can take several hours, the binomial search is often too slow to be useful against COVID.

There’s a clear need for a better group-testing scheme that balances cost and speed. To develop one, Wilfred Ndifon – a mathematical biologist who is the Chief Scientific Officer at AIMS – and Leon Mutesa – a geneticist at the University of Rwanda, and coordinator of that nation’s COVID response task force – assembled a multidisciplinary team. Ndifon invited Turok to join them to develop an algorithm which could find infected individuals quickly, and in the smallest number of tests.

The team has what they believe is a brand-new idea for group testing. It’s based on geometry.

Imagine testing a group of nine people, arranged in a three-by-three grid. Test groups of people by row, and then by column. Imagine you get positive test results from row one and for column three only. This means that the individual at row one, column three is the infected person. Testing this way gives you “coordinates” for any positive person in a group of nine with just six tests in total.

Similarly, arrange 27 people in a cube that’s three-by-three-by-three like a Rubik’s cube, and you can get the coordinates for any positive person in nine tests. And though other arrangements are harder to picture, there’s no particular reason to stop with three dimensions.

“For physicists, it’s very natural to reach for higher dimensions,” says Turok. “In fact, I think we overdo it. But in this case, it gives us an exponential advantage.”

While the mechanics of combining and barcoding these samples become complex, the mathematical advantages of this testing scheme just keep cubing along. Group testing with a four-dimensional hypercube allows for testing 81 people with just 12 tests, while a five-dimensional hypercube tests 243 people with 15 tests.

“That’s a nice number because it’s about the size of a passenger plane,” says Turok. “Imagine clearing every arriving plane in a small number of tests. It’s a tremendous public health advantage.”

Indeed, this testing scheme is now being used for population screening of air passengers at Rwanda’s international airport, using a lab at University of Rwanda’s state-of-the-art Center for Human Genetics, where Mutesa is the director.

It’s also being used to regularly test one of the top rugby teams in South Africa and is, Turok thinks, likely to catch on with others.

“We have already demonstrated cost savings by a factor of 15, relative to individual tests,” says Turok. “With further refinements, cost reductions of a factor of over 100 are achievable.” The University of Edinburgh, where Turok is on leave for the 2020/21 academic year, is planning a major trial of the method with that goal in mind.

Getting the medical community – not to mention the public – to put their faith in a coronavirus testing scheme that involves the word “hypercube” is a hurdle of its own. Nevertheless, the promising early results and clear mathematical advantages have public health scientists around the world beginning to come calling.

“It’s early days, but this could be a game changer,” says Turok. “In which case: how wonderful it would be, to see the solution to COVID come out of Africa.”