English version

Accueil

Recherche

Enseignement

Programmes

Informations personnelles
Contactez-moi !

Intérêts de recherche

Thèmes :
Combi Mathématiques discrètes et algorithmique
Bio Informatique pour la biologie
Tal Informatique pour le traitement
des langues et des textes
Visu Visualisation

Mes travaux de recherche portent sur l'algorithmique des graphes, avec des applications en bioinformatique et en analyse de corpus textuels.

Je coordonne actuellement les projets de recherche suivants :

Je participe également au projet de recherche suivant :

Par le passé, j'ai coordonné les projets de recherche suivants :

J'ai également participé aux projets de recherche suivants :

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
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 doctorat portait 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.


Traitement automatique des langues naturelles et humanités numériques

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 les représentations arborées (inspirées de la phylogénie) qui permettent de représenter les mots d'un texte afin d'obtenir des nuages arborés. L'outil TreeCloud conçu avec Jean Véronis a fait l'objet de multiples utilisations en sciences humaines : analyse de pièces de théâtre avec Delphine Amstutz, d'un corpus de presse sur l'affaire du Médiator avec William Martinez et d'un corpus d'articles du XIXe siècles de la Revue des Deux Mondes sur les savoirs biologiques avec Nadège Lechevrel. J'ai également utilisé cet outil dans des méthodologies d'analyses développées pour un corpus de pétitions en ligne, un corpus de résumés de projets de recherche sur la biodiversité ayant obtenu un financement en Europe ou encore un corpus d'articles scientifiques sur les réseaux phylogénétiques.

Pour l'analyse du langage de patients atteint de la maladie d'Alzheimer, j'ai développé avec avec Hyeran Lee deux logiciels : Densidées, 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, et iPhoComp, qui estime l'indice de complexité phonétique d'une liste de mots en français.

Suite à divers travaux sur des corpus textuels avec des collègues littéraires de l'UPEM, et à la participation au hackathon HackEgalitéFH en mars 2017, à l'issue duquel le projet George, le deuxième texte a été primé, je travaille également sur la constitution et l'analyse d'un corpus de textes littéraires écrits par des femmes et étudiés en collège, lycée et à l'université, dans le cadre du projet PEPS CNRS/RNMSH VisiAutrices que je coordonne (2017-2018).


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 avons étudié 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.



HTML4.01 valide CSS valide
Nuage de mots réalisé avec Freecorp TagBuilder.