Retour en image : séminaire NUMEV MIPS de Yann Ponty

Vendredi 3 mai avait lieu le 5ème Séminaire de l’année 2024, présenté par Yann Ponty.

Les Séminaires NUMEV-MIPS sont ouverts à un large public d’étudiants, étudiantes, chercheurs et chercheuses de toutes disciplines, qui souhaitent en savoir plus sur les domaines de recherche actuels de la communauté NUMEV-MIPS (Mathématiques, Informatique, Physique et Systèmes) ou sur les possibilités de développer ses compétences et savoir-faire.

Yann Ponty – Directeur de Recherche CNRS – LIX, Ecole Polytechnique, Institut Polytechnique de Paris

« RNA design: Hard but exemplarily combinatorial »

Abstract: RNA design is a discipline in Computational Biology aiming at the production of RNAs sequences targeting a predefined function. Design targets a wide diversity of objectives, for instance: encoding a given amino-acids sequence; optimizing levels of translation; evading degradation by nucleases; expose specific recognition sites towards interaction with partners; adopt alternative conformations depending of presence/absence of metabolites. On a computational level, RNA design can usually be tackled as a search/random generation of sequences featuring/avoiding motifs, compatible with one or several structures, or adopting a predefined structure as its unique energy-minimizing conformation (aka inverse folding). Most associated problems are difficult in the sense of complexity theory ((NP/#P)-hard), but are highly relevant in practice, and arguably deserving of a CS perspective.

In this talk, I will present an overview of the field, and the relevance of key computational problems in the context of health and synthetic biology.
I will describe recent contributions towards practically solving several RNA design problems, using concepts from graph theory and parameterized complexity. In particular, I will show that the generation of sequences simultaneously compatible with several RNA structures has strong connection with the enumeration of stable sets in Bipartite graphs. One can then use graph decompositions to obtain a parameterized complexity solution for the uniform/Boltzmann weighted generation of designs. We further generalized this approach to general set of constraints, and implemented it within a generic solver/sampler, named infrared and applicable to a variety of applications in Bioinformatics and beyond. If time allows, I will highlight the inverse folding problem, and show that the structure of its objective function implies the existence of undesignable local motifs, the absence of which ends up massively depleting the set of designable structures. I will finally mention recent results for generating, in linear-time, solutions to the (NP-hard) inverse folding for reasonable subsets of targeted structures.

Overall, RNA design is a subfield of Bioinformatics that is both mature and gaining in momentum. It features problems that both showcase the relevance of modern algorithmic techniques, and are certainly worthy of further attention from the graph/algorithms community.

This work is based on multiple collaboration including (but not limited to) Danny Barash, Théo Boury, Laurent Bulteau,  Cédric Chauve, Alain Denise, Stefan Hammer, Alice Héliou, Jan Manuch, Bertrand Marchand, Ladislav Stacho, Wei Wang, Sebastian Will,  Hua-Ting Yao …

Plus d’infos sur Yann Ponty : https://www.lix.polytechnique.fr/~ponty/