Covid-19: the Inria researchers aiming to optimise group testing

As a second wave of Covid-19 spreads across France, group testing has emerged as the most promising strategy for carrying out quick and efficient testing on ever greater numbers of people. When it comes to screening, you can either test absolutely everyone, which requires a massive number of tests, or you can test groups of individuals. With the second option, samples are taken from everyone, but only one test is carried out within the group: if it comes back negative, this indicates that the whole group is negative; if it’s positive, then additional individual tests are carried out.  This approach significantly reduces the number of tests performed, without affecting reliability.

But what criteria should be used to form these groups so as to ensure the procedure is effective? The researchers from the Inocs project team at the Inria Lille - Nord-Europe research centre came up with a solution. “Our research concerns optimisation, with a particular focus on the use of mathematical programming to solve large-scale optimisation problems”, explains Luce Brotcorne, director of research and head of the team. These mathematical methods, which can be used to solve problems involving large quantities of variables and decision criteria (which are often unpredictable, such as consumer behaviour), have found a use in networks for the distribution of energy, goods and services.

“We regularly work with the industrial sector, which provides us with new problems. This is mutually beneficial, in that it forces us to come up with operational solutions, but it also enables us to expand upon our basic research”, adds Frédéric Semet, professor of mathematics at the École Centrale de Lille and researcher within the team. But the health sector is familiar territory for Inocs, the team having developed a methodology for optimising health protocols for patients hospitalised at home.

Back at the start of lockdown, one of the team’s researchers, Martine Labbé, came up with the idea of working on the optimisation of group testing for Covid-19.

“We are constantly on the lookout for new optimisation methods”, explains Luce Brotcorne. “And so we were familiar with recent work carried out in relation to group testing. This technique has been around since the 1940s, but working out the size and the make-up of groups is a problem. For a long time, it was felt that this issue could only be addressed approximately. But the publication Martine Labbé identified showed that it is possible to find an optimum solution, using mathematical techniques like the ones we develop within Inocs, even with a really high number of patients”.

The Inocs researchers worked to generalise the results of this publication, developing an algorithm that integrates additional constraints. One such constraint was the maximum size of groups to be tested, which is crucial when it comes to detecting Covid. A key part of their approach involves explicitly factoring in differences in the prevalence** of the disease among the population, meaning that, in order to optimise the forming of test groups, the researchers needed to analyse detailed, anonymised epidemiological data. “For this reason, we have been working in close collaboration with statisticians from the Inria Nancy - Grand-Est and Rennes - Bretagne-Atlantique research centres, as well as doctors and virologists from Lille University Hospital”, explains Luce Brotcorne.

What are the preliminary results from this research on aggregated public data? “Our algorithm reduces the number of daily tests by more than a quarter compared to a mass approach: with the same testing capacity, this means you can carry out a bigger number of tests each day”, explains Frédéric Lemet.

The project ran for a few months, partly during lockdown, with all of the team’s researchers focused on the same objective. “This is quite rare, and it’s a really rewarding experience. There are normally only two or three of us working on team projects”, adds the researcher.

The Inocs researchers are now waiting impatiently for feedback from staff at Lille University Hospital on how their algorithm has performed, but they also have their eye on other developments. Beyond Lille University Hospital, they are looking into the possibility of a bigger partnership with software publishers in the field of medical analysis. “Our approach isn’t limited to Covid-19 - we think it can be adapted to the detection of other diseases, taking their specific characteristics into account”, says Luce Brotcorne.

*Inocs – which stands for INtegrated Optimisation with Complex Structures – is a joint undertaking involving Inria, the École Centrale de Lille and the Université libre de Bruxelles. Comprising six permanent researchers, it hosts 12 PhD students and postdoctoral researchers, plus two research engineers.

** The prevalence of a disease is the number of recorded cases within a specific group (and can be refined using categories such as age, sex, etc.)

*** Tifaout Almeftah, Luce Brotcorne, Diego Cattaruzza, Bernard Fortz, Kaba Keita, Martine Labbé, Maxime Ogier, Frédéric Semet.