Time table of all LIRMM seminars

Le concept d’ordinateur quantique, basé sur des qubits et l’algorithmique quantique, existe depuis près de 30 ans (Feynman 1982, Shor 1995, Grover 1996). Ces dix dernières années, de véritables machines quantiques ont été construites (allant de 5 à 5000 qubits), permettant aujourd’hui d’exécuter des programmes (Farhi 2014, Google Quantum AI 2024).

La superposition quantique des variables de décision induit un nouveau paradigme de calcul, permettant d’envisager de casser la combinatoire et ouvrant ainsi la voie à un nouveau domaine : la Recherche Opérationnelle Quantique.

Après un bref rappel des outils manipulés et de l’intuition sous-jacente, je présenterai diverses approches pour modéliser (et éventuellement résoudre ?) le problème du voyageur de commerce (Traveling Salesman Problem, TSP).

We introduce ribbon graphs, also known as topological graphs or cellularly embedded graphs, and show how delta-matroids come from ribbon graphs in the same way that matroids come from graphs. The talk will be mainly introductory and include a discussion of minors, duality and twisted duality. We show how delta-matroids allows us to count spanning quasi-trees (the ribbon graph analogue of spanning trees) and prove a matrix-tree theorem.

Le diagnostic des maladies rares est un défi de taille. Chaque patient porte une histoire clinique unique, souvent parsemée d’errance et d’impasse diagnostique. C’est en affrontant ces complexités lors de mon internat de médecine en génétique médicale que j’ai pris conscience du potentiel du machine learning pour transformer cette quête diagnostique en un parcours plus rapide et plus précis.

Dès mes premiers travaux, j’ai développé des algorithmes capables d’explorer les données génomiques en profondeur, réinterprétant des résultats ambigus et détectant des anomalies subtiles, telles que les variations du nombre de copies ou les disomies uniparentales. Mais le véritable tournant est venu avec PhenoGenius, un modèle conçu pour dépasser les limites des descriptions cliniques traditionnelles. En exploitant la co-occurrence des symptômes, il priorise les gènes candidats avec une précision inédite, surmontant ainsi la variabilité inhérente aux symptômes saisis par des médecins.

Depuis mon arrivée dans l’équipe Computational Regulatory Genomics, je participe à construire des méthodologies pour résoudre de nouvelles impasses diagnostiques en utilisant des algorithmes de machine learning pour interpréter les variations non-codantes de notre génome, soit 98% de notre ADN actuellement inexpliqué en routine diagnostique.

Chaque avancée, chaque modèle développé, chaque algorithme affiné s’inscrit dans une ambition plus vaste : transformer la médecine personnalisée en une réalité concrète, où l’innovation algorithmique et l’intégration des données complexes permettent aux patients de trouver des réponses diagnostiques.

Large phylogenetic trees pose a significant challenge to evolutionary inference due to computational tractability issues. This challenge has become increasingly important with the growing availability of sequence data, driven by advancements in genomics and the rising popularity of phylodynamic analyses in epidemiological studies. Deep learning in birth-death modeling has grown in popularity in recent years, particularly for addressing scalability issues (e.g., data size) that affect standard likelihood-based methods such as Maximum Likelihood and Bayesian Inference. Previous studies using convolutional neural networks have shown that empirical birth-death trees are typically more unbalanced than their simulated counterparts. This is likely due to diversification rates varying over time and across clades. Differences in selective pressures, driven by temporally and spatially varying environmental conditions, have produced multiple diversification trajectories embedded within a single phylogeny. Current approaches to deep learning in birth-death modeling rely on compact vector encoding of phylogenetic trees and have proven efficient as an alternative to whole-tree likelihood-based methods. However, they may not provide accurate predictions using empirical trees when rate heterogeneity is presumed to be high. Here, we explore the application of a new encoding language that uses local information contained in individual vectors per node, combined with the splitting of the original tree into subtrees, to estimate changes in speciation and relative extinction rates across clades and over time. We demonstrate that this approach is efficient for large trees simulated with 10,000 tips, which are subsequently divided into 500 nodes subtrees. We examine the power and accuracy of our approach using two distinct node-sampling strategies: one designed to detect discrete rate shifts across the tree and the other to identify rate shifts among clades.

Coarse graph theory is an emerging research direction that aims to describe the global structure of graphs by ignoring their local structure. In this talk, I will present an overview of this area, highlighting both recent positive and negative developments. A key focus of this talk will be the notion of quasi-isometry and conditions under which graphs are quasi-isometric to graphs with bounded treewidth.

This talk is based on some recent joint works with Rutger Campbell, Maria Chudnowsky, James Davies, Marc Distel, Meike Hatzel, Freddie Illingworth, and Rose McCarty.

The vehicle routing problem with time windows (VRPTW) is a classical problem with many applications. To improve schedules accuracy, the models may consider time dependency in travel time. The real traffic data used as input to the optimizers are often obtained by location providers that predict the travel times for specified timeframes. The predictors estimate travel time based on historical data, where uncertainties from accidents, weather conditions, and working roads, may add unpredictable delays. These providers enhance their forecasts by monitoring the live traffic and updating the travel time throughout the day.

Since routes are typically designed iin advance, updates are hard to integrate once execution starts. In this context, this work introduces the robust time-dependent VRPTW (RTDVRPTW), which uses robust optimization to handle uncertainty in travel times.

In this talk, we discuss the computational properties of RTDVRPTW under various assumptions, present exact and heuristic solution methods, and share results from real-data experiments to offer practical insights.