Largeurs de graphes pour de l'algorithmie exacte en bio-informatique structurale des ARNs
Par
Bertrand Marchand
LIX, École Polytechnique, Palaiseau, France et LIGM, Marne-la-Vallée, France
mardi 13 juin 2023, 10:30-12:00 EST, Salle 3195
Pavillon André-Aisenstadt, Université de Montréal, 2920 Chemin de la Tour
Abstract: Les molécules d'ARN consistent en des chaînes de blocs appelés nucléotides (A, U, G, C), et sont surtout connues comme étant de simples intermédiaires dans la synthèse des protéines (ARN messager). Pourtant, elles assurent aussi une grande variété d'autres fonctions au sein des systèmes biologiques, allant de la régulation de l'expression de gènes jusqu'à la catalyse de réactions chimiques. Pour ces ARNs dits "fonctionnels" ou "non-codants", la structure de repliement 3D adoptée est cruciale, et constitue en général la caractéristique conservée par l'évolution, plutôt que simplement la séquence.
De manière peu surprenante, plusieurs problèmes computationnels impliquant cette structure doivent être résolus quotidiennement par les bioinformaticiens lors de l'étude de ces ARNs. On peut citer par exemple le problème du repliement (quelle est la structure préférentielle d'une séquence donnée ?), de la transition entre différents repliements (calcul de barrières d'énergie) ou de l'alignement entre ARNs repliés. Ces problèmes sont typiquement NP-difficiles, surtout lorsque l'on va vers des modèles d'énergie réalistes d'un point de vue biologique.
Cette présentation se focalisera sur des résultats récents d'application de l'algorithmie paramétrée exacte à ces problèmes. Les structures d'ARNs y sont typiquement modélisées en tant que graphes, et un accent particulier est mis sur les approches à base de largeurs de graphes. Le problème de la suppression minimale d'arêtes pour atteindre une valeur de largeur arborescente (treewidth) cible [1], ou celui du calcul de version dirigée de largeurs de graphes [2], seront par exemple mentionnés.
Bio: Doctorant en France à l'École Polytechnique, les recherches de Bertrand Marchand portent sur l'algorithmie pour la bioinformatique des ARNs. Il s'intéresse notamment aux applications possible de l'algorithmie dite paramétrée, un domaine relativement récent et très dynamique de la recherche algorithmique.
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.
