Intérêts de recherche

Durant ma thèse, j'ai participé aux projets de recherche ANR GRAAL (Décompositions de Graphes et Algorithmes) et PHYLARIANE (Phylogénomique : Algorithmes et représentation intégrés pour l'analyse de l'’évolution du vivant), qui concernent mes deux domaines de recherche principaux : l'algorithmique des graphes et son utilisation en bioinformatique. Je fais également partie du groupe de travail Graphes du GDR IM.

Heuristique d'optimisation de la représentation de réseaux
phylogénétiques implémentée dans SplitsTree.

Bioinformatique

La conception d'algorithmes pour résoudre des problèmes posés par des biologistes, en particulier dans le domaine de la phylogénie, est au coeur de mes préoccupations. En particulier, j'ai déjà travaillé sur les arbres de duplication (et leur résistance face à certains réarrangements topologiques) avec Denis Bertrand et Olivier Gascuel, et sur la représentation de réseaux phylogénétiques (un certain type de graphes planaires à dessiner automatiquement avec des longueurs d'arêtes imposées) avec Daniel Huson.

Mon projet de thèse porte d'ailleurs sur les réseaux phylogénétiques, et l'utilisation de méthodes combinatoires. Ces réseaux phylogénétiques correspondent aux arbres d'évolution des espèces, dont certaines branches se rejoignent (créant ainsi un réseau plutôt qu'un arbre) à cause d'échanges de matériel génétique entre deux espèces coexistantes (par transfert horizontal de gène, hybridation, etc.).

Le principe des méthodes combinatoires est de ne pas manipuler directement les séquences d'ADN, mais des ensembles finis de petits éléments (triplets, quadruplets, etc.), ce qui permet d'aborder la reconstruction de réseaux phylogénétiques un peu comme un puzzle. Une bonne approche pour aider à reconstruire ces puzzles est l'utilisation de graphes (ensembles de points ou sommets reliés ou non par des arêtes), que l'on cherche notamment à décomposer, pour résoudre le problème en "divisant pour régner". Ce qui donne une excellente transition pour aborder mon autre domaine de recherche principal.

Théorie et algorithmique des graphes

Je m'intéresse également aux aspects théoriques et algorithmiques de certaines décompositions de graphes (décomposition modulaire, décomposition arborescente). J'ai aussi travaillé sur diverses classes de graphes d'intersection, dont celle des graphes de 2-intervalles et diverses restrictions ou variations. Je m'interroge sur la complexité (polynomial ou NP-complétude ?) de divers problèmes de reconnaissance de ces classes de graphes. Cette recherche a commencé en stage de master, encadré par Michel Habib et en collaboration avec Stéphane Vialette. Le nuage des mots les plus fréquents dans mon mémoire donne une bonne idée des thèmes qui m'ont occupé l'esprit :

absurde adn algorithme annexe annotées arc arêtes arn astéroïde biparti cas chapitre chemin chromatique circulaires classe clique comparabilité complémentaire complet complexité construire contrexemple cordes coupe couplage couples couverture couvrant cycle degré dénombrement disjoints doit droit droite dynamique éclatement effet ensembles entiers entrelacement équilibrés étiquetés eulérien exemple existe extrémité génération grand graphe inclusion indépendant intersectant intersecter intersection intervallaire intervalle linéaire log max maximale maximum noeuds nombre noté notes np obtenir ordonnancement ordre parcours permet permutation polynomial possibles précédence problème programmation propriété réalisation recherche relation résoudre second section séquences seulement sommets stable structure support taille théorie trapézoïdal trapézoïdes triplet trouver unions unitaire

Avec Christophe Crespelle, nous étudions de nouveaux paramètres pour évaluer la complexité des graphes du point de vue de l'encodage des voisinages de leurs sommets : la linéarité et la contiguïté. De bonnes représentations des voisinages nous a déjà conduit à des algorithmes efficaces sur des classes de graphes d'intersection, notamment un algorithme de parcours en largeur des graphes trapézoïdaux selon n'importe quel ordre de priorité fourni en entrée, de complexité linéaire par rapport au nombre de sommets.

Traitement automatique des langues naturelles

Parmi les questions combinatoires très théoriques sur les graphes et les arbres, certaines trouvent également des applications sur le langage, en plus de la bioinformatique.

Ainsi, je travaille sur l'utilisation des représentations arborées (inspirées de la phylogénie) pour représenter les mots d'un texte afin d'obtenir des nuages arborés, qui ont de multiples utilisations en sciences humaines, dont nous avons exploré certaines avec Delphine Amstutz.

Quant aux règles de réécriture, elles sont à la base du logiciel Densidées, développé avec Hyeran Lee, qui permet une évaluation automatique de la densité des idées, indicateur linguistique dont la dégradation a été liée avec l'apparition de la maladie d'Alzheimer.

Ces deux projets de recherche m'ont permis d'aborder des outils permettant de traiter de relations sémantiques pour le premier (calculées à partir des cooccurrences entre mots), et de syntaxe pour le second (ce sont les catégories grammaticales des mots du texte qui servent de base au calcul de la densité des idées).