Séminaire joint avec ROOT(LIFAT)

par Kilian Raschel (CNRS & Institut Denis Poisson, Université de Tours), Ronan Bocquillon (LIFAT, université de Tours)

vendredi 11 sept. 2026, 10:30 → 11:50 Europe/Paris

E1 2090 (Tours)

Titre (Kilian Raschel) : Compter les excursions sur un échiquier : histoire de la conjecture de Gessel et développements modernes

Résumé : Compter les chemins sur un réseau est une question facile à énoncer, mais qui peut conduire à des problèmes étonnamment profonds. Nous retracerons l'histoire de la conjecture de Gessel, depuis la découverte expérimentale d'une formule remarquable jusqu'à sa démonstration assistée par ordinateur, puis à une preuve faisant intervenir fonctions génératrices et fonctions elliptiques. Cet exemple permettra d'illustrer les liens entre combinatoire, probabilités, calcul formel et géométrie complexe, ainsi que quelques développements et questions ouvertes.

 

titre (Ronan Bocquillon) : Recherche et comparaison de motifs métaboliques et génomiques pour la construction de phylogénies bactériennes.

Nous nous intéressons à l'étude conjointe de réseaux métabolique et génomique. Plus particulièrement, nous cherchons à identifier des chaînes de réactions (métabolisme) catalysées par des enzymes codés par des gènes voisins (génome). Ces chaînes constituent des marqueurs d'espèce utiles à leur comparaison (phylogénie).

Plus formellement, nous définissons un graphe orienté D, associé au métabolisme. Ses sommets représentent des enzymes et sont étiquetés avec la nomenclature EC (une classification numérique des enzymes basée sur les réactions chimiques qu'elles catalysent). Nous plaçons un arc entre deux enzymes si un produit d'une réaction catalysée par la première enzyme est un substrat d'une réaction catalysée par la seconde. Nous définissons également un graphe non-orienté G, associé au génome. Nous reprenons les sommets de D et nous plaçons une arête entre deux enzymes si les gènes qui les encodent sont séparés de moins de delta (un paramètre choisi entre 1 et 3 en pratique) gènes dans le génome. Nous devons allons trouver un chemin simple P de couverture maximale dans D, de telle sorte que le sous-graphe de G induit par P forme une unique composante connexe. Ce problème est NP-difficile au sens fort dans le cas général. Nous résolvons ce problème à l'aide de méthodes basées sur la programmation mathématique et la programmation par contraintes.

Nous essayons aujourd'hui de mieux modéliser le problème des biologistes en introduisant de nouveaux critères basés sur une distance d'édition de graphe.