Doctorat
Equipe : Bioinformatique
Passage à l'échelle, propriétés et qualité des algorithmes de classements consensuels pour les données biologiques massives
Début le 01/10/2017
Direction : COHEN-BOULAKIA, Sarah
Ecole doctorale : ED STIC 580
Etablissement d'inscription : Université Paris-Saclay
Lieu de déroulement : LRI - BioInfo
Soutenue le 14/06/2021 devant le jury composé de :
Directrice de thèse :
- Sarah Cohen-Boulakia Professeure, LISN, Université Paris-Saclay
Rapporteurs et examinateurs :
- Guillaume Fertin, Professeur, LS2N (Laboratoire des Sciences du Numérique de Nantes), Université de Nantes
- Sylvie Hamel, Professeure, Département d’informatique et de recherche opérationnelle, Université de Montréal, Canada
Examinateurs :
- Mokrane Bouzeghoub, Professeur, DAVID, UVSQ, Université Paris-Saclay
- Miguel Couceiro, Professeur, LORIA (Laboratoire lorrain de Recherche en Informatique et ses Applications), Université de Lorraine
- Gaëlle Lelandais, Professeure, I2BC (Institut de biologie intégrative de la cellule), Université Paris-Saclay
- Stéphane Vialette, Directeur de Recherche CNRS, LIGM (Laboratoire d’Informatique Gaspard-Monge), Université Gustave Eiffel
Co-encadrant, jury invité :
- Alain Denise, Professeur, LISN, Université Paris-Saclay
Jury invité :
- Adeline Pierrot, Maître de Conférences, LISN, Université Paris-Saclay
Activités de recherche :
Résumé :
Les médecins et biologistes sont régulièrement amenés à interroger des bases de données biologiques publiques, par exemple lorsqu’ils se renseignent sur les gènes les plus associés à une maladie donnée. Le mot-clé choisi au moment d’interroger la base de données est particulièrement important : plusieurs reformulations synonymes d’une même maladie (par exemple « breast cancer » et « breast carcinoma ») aboutissent à des classements parfois très différents pouvant aller jusqu’à plusieurs milliers de gènes. Certains gènes, triés par pertinence, peuvent se retrouver à égalité (importance égale vis-à-vis de la maladie). De plus, certains gènes retournés en utilisant certaines reformulations peuvent être absents lorsque d’autres reformulations sont choisies. On dit alors que les classements sont incomplets et avec égalités. L’enjeu est alors de combiner l’information apportée par ces différents classements de gènes. La problématique consistant à partir d’une liste de classements et de calculer un classement dit consensuel aussi représentatif que possible des classements d’entrée est appelée « agrégation de classements ». Ce problème est connu pour être NP-difficile. Alors que la majorité des travaux considèrent les classements complets et sans égalités, nous nous sommes placés dans le contexte des classements incomplets avec égalités. Nos contributions peuvent se décomposer en trois parties. Premièrement, nous avons conçu une heuristique basée sur des graphes qui consiste à partitionner le problème de départ en sous-problèmes indépendants pour le cas où les classements sont incomplets et avec égalités. Deuxièmement, nous avons conçu un algorithme capable de déterminer des points communs entre tous les classements consensuels optimaux, permettant ainsi de fournir à l’utilisateur une indication quant à la robustesse du classement consensuel renvoyé. Une étude expérimentale sur un grand nombre de jeux de données biologiques massifs a mis en évidence la pertinence biologique des résultats fournis par nos méthodes. La dernière contribution est la suivante : les données manquantes pouvant s’interpréter de différentes façons selon le contexte, nous avons proposé un modèle paramétré permettant de prendre en compte ces différences. Nous avons conçu des algorithmes pour ce modèle et fait une étude axiomatique de ce dernier en nous basant sur la théorie du choix social.
