RNA molecules consist of chains of individual blocks called nucleotides (A, U, G, C), and perform a wide variety of functions in biological systems. These functions critically depend on the 3D structures adopted by these molecules, i.e., the way nucleotides are paired up in complex folding conformations.
Several natural computational problems involving this structure then emerge, such as folding (what is the preferred structure of an RNA sequence?) or structure reconfiguration (is there a feasible reconfiguration path between these two structures?). These problems are typically 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.
Localisation
Salle de séminaire 4B125 (bâtiment Copernic)
5 Boulevard Descartes 77420 Champs-sur-Marne