Julien Fradin, doctorant au sein de l’équipe COMBI, soutiendra sa thèse intitulée « Graphes complexes en biologie : problèmes, algorithmes et évaluation »

mardi 4 décembre à 10h30 dans l’amphi du bâtiment 34, sur le site de la Faculté des Sciences.

Jury de thèse : Guillaume Fertin (Directeur de thèse), Géraldine Jean (co encadrante), Ioan Todinca (Rapporteur, LIFO), Annie Château (Rapporteur, U Montpellier 2 – MAB), Michel Habib (U Paris Diderot, IRIF), Florian Sikora (U Paris Dauphine, LAMSADE, Damien Eveillard (Invité)

Résumé :
Afin de mieux comprendre le fonctionnement d’un système biologique, il est nécessaire d’étudier les interactions entre les différentes entités qui le composent. Pour cela, on peut modéliser ces réseaux d’interactions biologiques sous la forme de graphes dont les sommets sont colorés. Une problématique commune consiste alors à rechercher un sous-graphe
d’intérêt dans ces graphes pouvant comporter des milliers de sommets et d’arêtes. Dans ce manuscrit, on s’intéresse à deux problèmes conçus pour répondre à cette problématique. On présente tout d’abord un état de l’art sur le problème GRAPH MOTIF, pour lequel il existe une large littérature algorithmique, puis on réalise une étude algorithmique approfondie du problème MAXIMUM COLORFUL ARBORESCENCE.
Le problème MAXIMUM COLORFUL ARBORESCENCE est une redéfinition plus précise d’un problème de la littérature qui avait été introduit dans le but de déterminer de novo la formule moléculaire de petites molécules inconnues. Alors que MAXIMUM COLORFUL ARBORESCENCE est, tout comme le problème original, algorithmiquement difficile à résoudre même dans des classes d’arbres très contraints, cette nouvelle définition nous permet ainsi d’obtenir de nouveaux algorithmes d’approximation dans ces mêmes arbres
contraints et même de trouver une nouvelle classe de graphes dans laquelle MAXIMUM COLORFUL ARBORESCENCE se résout en temps polynomial. On montre également des résultats de complexité paramétrée pour ce nouveau problème, qu’on compare ensuite à ceux de la littérature pour le problème original sur des instances issues de données biologiques.

Mots-clés : Bioinformatique, Graphes, Complexité paramétrée, Approximation

***********

Abstract:
In order to better understand how a biological system works, it is necessary to study the interactions between the different entities that compose it. To do this, we can model these biological interaction networks with graphs whose vertices are colored. A standard problem then consists in searching for a subgraph of interest in these graphs, which can include thousands of vertices and edges. In this manuscript, we are interested in two problems designed to address this issue. First of all, we present a state of the art on the GRAPH MOTIF problem, for which there exists a large algorithmic literature, then we carry out an in-depth algorithmic study of the MAXIMUM COLORFUL ARBORESCENCE problem.
The MAXIMUM COLORFUL ARBORESCENCE problem is a more precise redefinition of a problem in the literature that had been introduced to determine de novo the molecular formula of unknown small molecules. While MAXIMUM COLORFUL ARBORESCENCE is, like the original problem, algorithmically difficult to solve even in very constrained tree classes, this new definition allows us to obtain new approximation algorithms in these same constrained trees. It even allows us to find a new graph class in which MAXIMUM COLORFUL ARBORESCENCE is solved in polynomial time. We also show parameterized complexity results for this new problem, which we then compare to those in the
literature for the original problem on instances from biological data.

Keywords: Bioinformatics, Graphs, Parameterized complexity, Approximation