Hyqualibio homepage

Projet défi Mastodons HyQualiBio

Le projet HyQualiBio est un projet du défi Mastdons (Mission Interdisciplinarité du CNRS) issu de la fusion des projets Mastodons QualiBioConsensus et HyQual en 2017.

Il propose de s’attaquer aux défis posés par la très grande variété des données biologiques et des méthodes d’analyse et de fouille de données biologiques.

L’originalité des approches développées dans HyQualiBio repose sur la prise en compte et l’explicitation systématique de critères de qualité, au niveau des données, des méthodes d’analyse et de fouille, et jusqu’aux connaissances produites.

Le projet comporte deux axes hautement complémentaires.

Axe Classements de données consensuels
Il s'intéresse au développement et à la compréhension fine des algorithmes de classement de données consensuels, particulièrement utiles pour le classement de données scientifiques (en particulier biologiques) qui peuvent être ordonnées selon de nombreux critères de qualité (fiabilité, réputation de la source de données fournissant les données, complétude...). Ces algorithmes produisent un classement consensus, reflétant les points communs d’un ensemble de classements pris en entrée.

Formellement, le problème s’exprime en termes de calcul d’un classement qui est une médiane des classements donnés en entrée, selon une fonction de distance fixée. Le problème ainsi posé est connu pour être NP-difficile et bien des points théoriques sont largement ouverts.

En outre, dans les applications réelles, en particulier en bioinformatique, les classements peuvent ne pas être des permutations où les éléments sont strictement ordonnés, mais ils peuvent n'être que partiellement ordonnés : certains éléments occupent la même position car ils ont la même importance d'après le critère choisi. Dans ce cas, on parle de classements avec égalités. Aussi, les classements peuvent ne pas comporter les mêmes éléments, on parle alors de classements incomplets.

La plupart des approches actuelles se concentrent sur les permutations, laissant plusieurs questions ouvertes à la fois pratiques et théoriques dans le cadre du classement avec égalités et/ou de classements incomplets.

Sur cet axe, nos résultats principaux obtenus sont les suivants.
- Nous avons conçu et implémenté la première version d'une nouvelle heuristique pour le classement consensuel [JOBIM2017], fondée sur une approche à base de graphes et capable de considérer des classements incomplets et avec égalités. Ces travaux sont ont obtenus le prix du meilleur poster à la conférence JOBIM 2017 !
- Nous avons proposé un cadre uniforme pour représenter les classements (complets ou non, avec ou sans égalités) et avons proposé de définir des distances génériques dites Kemeny-compatibles [MasterPierre2017]. Nous étudions actuellement les propriétés des distances ainsi (re)définies .
- Nous avons affiné des résultats d’énumération de certaines classes de permutations [Pie17], ouvrant la voie à une meilleure connaissance de l’espace des solutions du problème d’agrégation de classements.
- Nous avons obtenu de nouveaux résultats algorithmiques de complexité paramétrée pour les données biologiques fondées sur des structures de données pouvant être exploitées dans les classements de données biologiques [CPM2017].
Axe Approches hybrides pour les données du Web
Il a pour cadre la fouille de données, la représentation et la découverte de connaissances en Biologie. Il s'attache à étudier et comprendre les problèmes de qualité qui se posent à la fois sur les données et les motifs extraits. Les données biologiques du Web étant représentées de façon quasi systématique en RDF, ce type de données est au coeur de plusieurs des contributions de notre projet.

Sur cet axe, les résultats principaux obtenus sont les suivants :
- Nous avons exploité notre expertise sur l’analyse formelle de concepts pour proposer une nouvelle représentation particulièrement concise des forêts dans les méthodes de forêts aléatoires ainsi qu’une méthode pour rendre plus efficace l’élimination des arbres dans les forêts aléatoires. [ICFCA2017]
- Nous avons effectué une étude comparative de trois approches d’extraction des connaissances pour évaluer leur capacité à expliquer pourquoi une ressource est définie comme associée à une catégorie.
- Nous avons proposé un nouveau type de lien d’identité entre des données RDF, capable de prendre en compte l’identité de deux instances dans un contexte particulier. Nous avons conçu, développé et évalué un algorithme de détection de ces liens d’identité [KCAP2017-a].
- Nous avons proposé une nouvelle approche de fouille dans les bases de connaissances capable de détecter les contraintes de clés conditionnelles valides pour une sous partie d’un ensemble de données. Nous avons montré que cette technique augmente fortement la qualité des résultats des approches de détection de liens d’entité utilisant les clés [ISWC2017].
- Nous avons proposé une nouvelle approche permettant d’inférer l’évolution des axiomes d’une ontologie (e.g., disjonction de classes, fonctionnalité des propriétés) en exploitant la différence symétrique entre deux versions d’une source de données RDF évolutives [KCAP2017-b].
- Nous avons exposé un tutoriel à BDA 2017 sur le thème de “Knowledge Graph Completion” et un tutoriel sur ce même thème a été accepté à la conférence WWW 2018.

Publications

[JOBIM17] P. Andrieu, L. Bulteau, S. Cohen-Boulakia, A. Denise, A. Labarre, A. Pierrot and S.Vialette: Towards a new heuristics to compute Consensus Ranking of Big Biological datasets [Best Poster Awards JOBIM 2017]

[Pie17] Adeline Pierrot: UNIVERSALITY IN SUBSTITUTION-CLOSED PERMUTATION CLASSES. Permutation Pattern 2017.

[MasterPierre2017] P. Andrieu: Trier efficacement les jeux de données biologiques et biomédicaux par les techniques d'agrégation, Mémoire de Master 2, Mention Bioinformatique de l’Université Paris-Saclay.

[consrank18] Nous travaillons sur la rédaction d’un article commun (LRI, LIGM, IFB) autour de la conception et du développement de la plateforme consensus-ranking à soumettre au track démonstration de la conférence VLDB 2018 (deadline 1er mars 2018)

[CPM2017] L. Bulteau, G. Fertin, C. Komusiewicz: Beyond Adjacency Maximization: Scaffold Filling for New String Distances. CPM 2017: 27:1-27:17

[ISWC2017] D. Symeonidou, L. Galarraga, N. Pernelle, F. Saïs and F. Suchanek. VICKEY: Mining Conditional Keys on RDF datasets, ISWC 2017.

[KCAP2017-a] J. Raad, N. Pernelle and F. Saïs: Detection of Contextual Identity Links in a Knowledge Base, K-CAP 2017

[KCAP2017-b] F. Saïs, C. Pruski and M. Da Silveira: Inferring the evolution of ontology axioms from RDF data dynamics. K-CAP 2017

[ICFCA2017] T. P. Makhalova, S. O. Kuznetsov: On Overfitting of Classifiers Making a Lattice. ICFCA 2017: 184-197

Co-encadrements doctoraux

Pierre Andrieu (thèse débutée au 1er Octobre 2017) “Passage à l'échelle, propriétés et qualité des algorithmes classements consensuels pour les données biologiques massives”. Encadrement par le LRI avec travaux en cours commun avec le LIGM d’une part (algorithmes de graphes et algorithmique combinatoire) et le LORIA (propriété mathématiques des algorithmes de consensus) d’autre part.

Robin Milosz, étudiant en thèse à l’Université de Montréal sous la direction de Sylvie Hamel, visite le LRI pour 6 mois d’Octobre 2017 à Mars 2018. Encadrement par le LRI avec travaux en cours commun avec le LIGM et le LORIA. Titre de la thèse : “Étude combinatoire et algorithmique de médianes de permutations sous la distance de Kendall-Tau”

Prototypes et plateformes

Une nouvelle version de l’outil ConQuR-Bio est en ligne : http://conqur-bio.lri.fr/ ConquR-Bio interroge automatiquement la base de données Gene du NCBI à partir d’un mot clé fourni par l’utilisateur, effectue des reformulations de requêtes (recherche de synonymes du mot clé) et classe les résultats avec une série d’algorithmes de classements consensuels. ConQur-Bio est utilisé régulièrement (au moins trois fois par semaine) par des utilisateurs extérieurs (en France issus de l’APHP, Institut Curie et Institut Pasteur et plusieurs plateformes de l’IFB).

La plateforme consensus-ranking sera mise en ligne au 1er mars 2018. Cette plateforme (version béta sur rank-and-ties.lri.fr) donne accès à un ensemble de 12 algorithmes ré-implémentés, à 7 jeux de données réels ainsi que de très nombreux jeux de données générés.