Covid-19 : Des algorithmes contre la pandémie

Des compétences en mathématiques et en informatique mises d’une gestion optimisée des stocks de tests de dépistage

Professeur, spécialiste de la sécurité informatique à l’ENS-PSL, David Naccache s’est engagé dans la lutte contre le Covid-19 en mobilisant au pied levé une équipe de chercheurs et de normaliens en informatique et mathématiques. En combinant algorithmes et techniques de group testing développées par Robert Dorfman dans les années 40, ces informaticiens et mathématiciens sont parvenus à proposer une méthode de contrôle de la pandémie moins gourmande en tests.
Déjà déployée dans plusieurs pays, elle a permis de réduire par 3 à 4 le nombre de tests nécessaires pour une population. Elle est particulièrement précieuse à l’heure où la pandémie touche indifféremment pays développés et pays pauvres.

David Naccache
David Naccache

« Nous avons maintenant plein d'informaticiens, des mathématiciens et des normaliens assis à la maison, donc potentiellement une large base scientifique disponible pour simuler modéliser etc. Notamment on aura des algorithmiciens, des spécialistes de l'apprentissage, des cryptologues… ».

C’est par ces mots adressés à l'Institut Pasteur que David Naccache, professeur et spécialiste de la sécurité informatique à l’ENS-PSL, a offert de mobiliser pendant le confinement toute une équipe d’experts pour travailler à l’élaboration d’une méthode inédite de dépistage groupé à l’aide d’algorithmes. Appelée pool testing, celle-ci consiste à diviser le nombre de tests nécessaires sur une population donnée, en mutualisant des tests en fonction d'une probabilité d'infection a priori (1).

Initialement inventée en 1943 par Robert Dorfman, professeur d’économie à Harvard, et utilisée pendant la guerre pour détecter chez les soldats les cas de syphilis, la logique dite du pool testing a été appliquée avec succès dans ses différentes variantes à l’épidémie de VIH. Aujourd’hui, c’est le dépistage du Covid-19 qui la replace dans l’actualité.

La méthode proposée par l’équipe de David Naccache a été adoptée en Espagne et est en cours d'évaluation au Maroc et au Portugal. Les premières estimations indiquent qu'avec les taux de contamination actuels de la population dans les zones géographiques concernées, les algorithmes optimisés par les chercheurs permettent de réduire le nombre de tests par un facteur de 3 à 4 par rapport au test groupé « aveugle » classique.

 

De la sécurité informatique aux tests de dépistage du Covid-19 : réinventer ses compétences

« Dès que le début de l'épidémie j'ai été pris d'un fort sentiment d'impuissance face au désarroi de la population et à l’angoisse du corps médical. Je voulais, comme beaucoup de nos concitoyens, "faire quelque chose de concret" » explique David Naccache. Réserviste, il informe dès le début de la pandémie le Général Olivier Kim de sa disponibilité tout en s’inscrivant à la réserve sanitaire, qui comporte des bénévoles appartenant principalement au corps médical, mais aussi des informaticiens et des logisticiens.

Par ses contacts, David Naccache a réussi à commander des masques et du gel qu’il distribue à des collègues mais aussi aux chauffeurs de taxis et aux VTC. « Ces initiatives, m’ont permis de forger une certaine image de la situation. J’ai alors entamé une réflexion de fond sur la manière dont mes connaissances spécifiques en informatique et mathématiques pourraient servir à combattre le virus. »

La majorité des chercheurs en sécurité informatique s’intéressant à l'examen de l'application Stop Covid, David Naccache souhaite appliquer les talents de son équipe à l'amélioration des méthodes de test pour pallier à la pénurie de kits de dépistage au début de la pandémie en Europe.

Il réalise alors rapidement qu’il y a une importante marge de gain dans la mise en œuvre de tests groupés : ceux déjà existants ne prenaient pas en compte des paramètres importants comme la probabilité individuelle de contamination a priori, qui peut facilement s’obtenir à l’aide de questionnaires, de simples examens cliniques ou encore d’algorithmes d’intelligence artificielle. « À partir de là, il n’y avait plus qu’à ».

Il propose à Christophe d’Enfert, directeur scientifique de l’Institut Pasteur, Olivier Gascuel, directeur du département de biologie computationnelle, Robert Weil et Simon Cauchemez, directeurs de l’unité de modélisation des maladies infectieuses de mobiliser des doctorants et alumni de l’École contre le Covid-19.

 

Optimiser les tests groupés de dépistage à l’aide d’algorithmes

La réponse de l’Institut Pasteur, qui ne se fait pas attendre, est décisive pour initier concrètement les recherches. Il oriente le travail de David Naccache vers une méthode précise de test de dépistage appelée pool testing, qui consiste à mélanger des échantillons provenant de patients différents.

Cette méthode peut potentiellement permettre de s’assurer que plusieurs patients sont négatifs. En cas de résultat positif, une stratégie de « partager pour régner » permet de trouver les échantillons positifs. L’avantage de celle-ci ? « Clairement la réduction du nombre des tests nécessaires pour dépister une population donnée ».

Mais la taille optimale de ces tests groupés résulte d’essais pratiques et non d’un calcul mathématique. Cette question reste difficile du fait de la non-linéarité des taux d’erreur des tests et de la diversité des tests utilisés. L’équipe de David Naccache considère qu’un regroupement par 10 à 20 est probablement le meilleur choix pratique avec les techniques de test actuelles.

D'autres facteurs importants sont aussi à prendre en compte, comme la charge virale attendue chez une personne testée, qui a un impact sur la taille maximale qui peut être utilisée pour les groupes. L'étude de cet important facteur est proposée et modélisée par des chercheurs appartenant à GROUPOOL, une liste de diffusion constituée sur le pool testing du COVID-19, qui rassemble 10 scientifiques permanents universitaires, CNRS ou INRIA (2). Par exemple, si la charge virale est très faible, la probabilité qu'un malade soit détecté dans n grand groupe est faible. À l'inverse, si la charge virale est élevée, le test restera positif même mélangé à un grand nombre d'individus non-contaminés.

Il est alors nécessaire d'appliquer une pondération pour prendre en compte la charge virale du mélange testé.
C’est d’ailleurs le sujet de travaux algorithmiques récents, comme ceux de Dewei Wang pour son étude sur des tests VIH parus en 2018 (3). Lors de ses travaux, au lieu de traiter les réponses des tests comme des variables aléatoires binaires, c’est-à-dire « malades » versus « non-malades », Dewei Wang a effectué des évaluations en exploitant les distributions continues de biomarqueurs (4) sous-jacentes d'un test, pour les individus positifs et négatifs. Cette méthode permet d’éviter des hypothèses potentiellement restrictives de diagnostic.

Le physicien Jean-François Rupprecht, chercheur au CNRS à l’Université de Marseille a récemment attiré l’attention sur les recherches de Dewei Wang. Avec le mathématicien Bastien Mallein (Sorbonne Paris Nord SPN), et Vincent Brault (université Grenoble-Alpes) ils s’intéressent actuellement avec un groupe d’étude à une variante du problème appliquée au Covid-19, indique David Naccache (5).

 

Aider les équipes médicales à maîtriser ces outils

La mise en œuvre de ces tests, complexe et technique, requiert une formation spécifique des équipes médicales. Avec Eric Brier, Megi Dervishi, Rémi Géraud-Stewart et Ofer Ifrach-Stav, David Naccache prépare en ce moment un article qui « "distille" les meilleurs algorithmes sous la forme d’un "manuel" pratique et prêt à l’usage ».

L’adoption pratique de pool testing dépend ainsi de nombreux facteurs, dont notamment l’acuité du manque de kits de tests comme l’explique David Naccache : « faute d’alternative, on peut rogner sur la précision des tests pour dépister plus, mais lorsque la pénurie de kits se calme, mieux vaut investir davantage et tester plus précisément ! Mais les tests groupés restent à l’heure actuelle la solution de choix pour de nombreux pays en voie de développement et focalise beaucoup d’intérêt : même la Task Force de la Maison Blanche et le New York Times en parlent ! »

 

Lier cryptographie et algorithmes pour protéger les données médicales

David Naccache et son équipe se sont aussi interrogés sur la confidentialité de cette méthode, car le résultat positif ou négatif d’un test groupé révèle de l’information sur les autres membres du groupe. Par exemple, si le groupe d’un patient est testé positif alors que celui-ci sait être négatif, il peut en déduire qu’au moins un des membres de son groupe est positif.

Pour bien comprendre, il suffit de réduire l’échantillon à deux individus. Si le résultat positif d’un test groupé de A et B suivi d’un test positif de A ne révèle aucune information sur l’état de B. En revanche, le résultat négatif de A donne toute l’information sur B, qui sera par déduction considéré comme positif.

Le chercheur et son équipe s’inspirent de techniques cryptographiques afin de concevoir des tests résistant au fichage génétique, et qui feront prochainement l’objet d’une publication (6), « un champ de recherche passionnant et intriguant ! » indique-t-il.

« Nos tests étant conçus pour accumuler l’information aussi vite que possible, il est possible de les inverser pour concevoir des tests accumulant l’information très lentement, tout en s’assurant que l’information reste strictement croissante. Cela force le testeur à utiliser beaucoup de tests pour arriver à ses fins et ainsi mettre un « prix » (analogue au CAPTCHA) sur l’obtention du résultat du test. » étaye David Naccache.

Car pour le scientifique, il reste encore des mécanismes à expliquer : « il est facile de démontrer que lorsque le taux de contamination dans la population dépasse (3-√5)/2, il vaut mieux ne pas effectuer de test groupé et tester individuellement. Mais en même temps les chercheurs tombent sur des conjectures ardues comme par exemple celle énonçant qu’il n’existe pas de stratégie de test groupé capable d’effectuer moins de ½-log2 (32/27) de tests par patient positif ! »

Autre curiosité, observée par Eric Brier, co-auteur avec David Naccache de l’article (7) : « Dans une configuration où l’on sait que {A,B}, {B,C} et {A,C,D} sont positifs. Le patient A a la même probabilité d’être malade que s’il était dans une paire isolée. Et cela va plus loin encore ! Si on teste A et qu’il est négatif, B est positif et il nous reste la paire {C,D}. Si on teste A et qu’il est positif, il nous reste la paire {B,C}. Tout se passe donc comme si l’on avait… deux paires indépendantes. Même si nous pouvons le prouver nous n’avons pas d’explication élémentaire (« from THE BOOK ») de ce phénomène. »

 

Modélisation de la stratégie de "pool testing" du dépistage du Covid - 19 | Par Marc Beunardeau, Éric Brier, Noémie Cartier, Aisling Connolly, Nathanaël Courant, Rémi Géraud-Stewart, David Naccache et Ofer Yifrach-Stav.

 

Entretien réalisé en collaboration avec Mélissa Rossi, doctorante au département informatique de l'ENS-PSL.

_______

(1) Une probabilité a priori est probabilité d'affectation d'une observation à un groupe avant la collecte des données.

(2) Group testing as a strategy for the epidemiologic monitoring of COVID-19, Vincent Brault, Bastien Mallein, Jean-Francois Rupprecht, q-bio.QM/ 2005.06776 (2020).

(3) Group testing case identification with biomarker information, Dewei Wang, Christopher S. Mc Mahan, Joshua M.Tebbs, Christopher R.Bilder, Computational Statistics & Data Analysis, 1er février 2018.

(4) Un biomarqueur (ou marqueur biologique) est ”une caractéristique définie qui est mesurée comme un indicateur des processus biologiques normaux, des processus pathogènes ou des réactions à une exposition ou une intervention, y compris les interventions thérapeutiques “ (sources : FDA et NIH).Cela peut être n’importe quel indicateur biologique mesurable. Par exemple, les biomarqueurs peuvent être cellulaires ou moléculaires (ADN, ARN, protéines…).

(5) Vincent Brault, Bastien Mallein et Jean-Francois Rupprecht sont normaliens de la promotion 2008.

(6) Preservation of DNA Privacy During the Large Scale Detection of COVID, cosigné avec Marcel Hollenstein (Institut Pasteur), Peter B. Rønne (Université du Luxembourg), Peter Y A Ryan (Université du Luxembourg), Robert Weil (UPMC-Sorbonne Université et Institut Pasteur) et Ofer Yifrach-Stav (ENS-PSL).

(7) Optimal Covid-19 Pool Testing with a priori Information, Marc Beunardeau, Éric Brier, Noémie Cartier, Aisling Connolly, Nathanaël Courant, Rémi Géraud-Stewart, David Naccache, Ofer Yifrach-Stav, CoRR abs/2005.02940 (2020)

 

À propos de David Naccache

David Naccache est professeur et directeur du groupe de recherche en sécurité informatique à l'École normale supérieure-PSL.
Ses travaux portent majoritairement sur la cryptographie à clé publique, la sécurité informatique, et l'expertise judiciaire. À ce titre, il intervient pour la Cour de cassation, la Cour pénale internationale, et la Cour d'appel de Paris. Inventeur de plus de 180 familles de brevets, il est médaillé de l'Organisation mondiale de la propriété intellectuelle.