Time table of all LIRMM seminars

What is recursive structure? And how can we exploit it algorithmically? In this talk I will give as general an answer to these questions as I can by calling upon the new notion of structured decompositions. This is a category-theoretic formalism that Jade Master, Zoltan Kocsis and I recently introduced which yields a vast generalisation of tree-width to arbitrary categories. I will explain — assuming no prior knowledge at all of category theory — how to make use of structured decompositions for three purposes: (1) defining new tree-width-like invariants, (2) relating these decompositions to each-other via functors and (3) how one might go about proving algorithmic meta-theorems using the language of category theory. This is ongoing, multidisciplinary work. As such it requires lots people with different types of expertise, so you should consider this talk is an invitation to get involved!

L’incertitude est inhérente au problème de décision. Dans de nombreux contextes de conception de système de production : conception d’ateliers de fabrication additive, de chaînes logistiques inverses et de planification minière, de chaines d’assemblages aéronautiques, les décisions ne sont pas toutes prisent simultanément mais de façon séquentielle dépendant de la situation dans laquelle on se trouve. Au niveau de décision stratégique (conception) comme tactique (planification), la connaissance sur les mondes possibles peut être plus ou moins précise. En fonction de ce degré de connaissance, différentes théories comme celles des probabilités, des fonctions de croyance, des possibilités peuvent être utilisées. Dans ce contexte le comportement d’un décideur qui, face à l’incertitude, peut être plutôt pessimiste ou plutôt optimiste influence fortement les décisions et les performances. Dans cette exposé, je présenterai mes travaux de recherche sur les critères de décision sous incertitude prenant en compte l’optimisme du décideur dans les problèmes de décision séquentielle. Une analyse théorique ainsi qu’une application au problème de conception de chaîne logistique inverse seront développées.

An RNA consists of a chain of molecular blocks called nucleotides (A, U, G, C), resulting
from a transcription of a portion of a DNA strand. Although they are traditionally
thought of as mere intermediates in the synthesis of proteins, a subset of them,
dubbed functional RNAs, perform as such a wide variety of biological functions.

Their functions are largely determined by their 3D structures, i.e. the way nucleotides
are paired up in complex folding conformations. Understanding the connection between
the composition of a given sequence and its preferred folding conformations is therefore
key to understanding, or acting upon, many biological mechanisms.

RNA bioinformatics is then tasked with tackling several computational problems that naturally
arise from trying to understand this connection. The most natural one is folding: given
an RNA sequence, try to predict the structure(s) it will preferably adopt.
But one could also wonder about structure reconfiguration (how easy it is for
an RNA molecule to go from a folded structure to another ?) or structure-sequence
alignment (how compatible are a given fold and a given sequence ?).
All these problems are computationally hard,
especially when going towards realistic biological models.

This talk will focus on selected instances of such landmark problems, and on
current attempts to tackle them with exact parameterized algorithmics. A particular
focus will be given to graph algorithms, and graph width parameters. Examples
of graph problems emerging from this angle include minimum edge deletion towards
a target treewidth value [1], or the computation of directed pathwidth for a particular
geometric subset of directed graphs [2].

References:
[1] B. Marchand, Y. Ponty, L. Bulteau. Tree Diet: Reducing the Treewidth to Unlock
FPT Algorithms in RNA Bioinformatics. Algorithms for Molecular Biology 2022.

[2] L. Bulteau, B. Marchand, Y. Ponty. A new parameterization for independent set
reconfiguration and applications to RNA kinetics. IPEC 2021.