Yann Ponty, Ecole Polytechnique
Jérôme Waldispühl, McGill University
Abstract
Le problème du design (ou repliement inverse) de structures secondaires d’ARN est le suivant : la donnée est une structure secondaire d’ARN dont on ne connaît pas la séquence. L’objectif est de générer une ou plusieurs séquences qui se replient selon cette structure. Dans la plupart des applications pratiques de ce problème en biologie, des contraintes de séquence doivent être ajoutées : présence de motifs particuliers à des positions données, interdiction absolue d’autres motifs quelle que soit leur localisation dans la séquence. Le but de la thèse est de développer une méthode à base de modélisation par des langages formels, suivie de génération aléatoire de séquences, afin de résoudre efficacement le problème du design avec contraintes de séquences.
Context
La question de savoir si le problème de design de structures secondaires d’ARN est NP-difficile ou non est ouverte. Un certain nombre d’approches heuristiques (recherche locale ou algorithmes génétiques) et exactes (branch and bound, programmation linéaire) ont été développées pour tenter de le résoudre. Parmi ces approches, une seule, à base de recherche locale, peut gérer les motifs interdits. Cette approche, qui est parmi les meilleures pour résoudre le problème sans contraintes de séquences, trouve en revanche très vite ses limites lorsque des motifs sont interdits. Nous avons commencé à développer une approche originale à base de grammaires formelles pour résoudre ce problème, que ce soit avec ou sans contraintes de motifs.
Objectives
Le but principal de la thèse est de développer une chaîne algorithmique efficace pour résoudre le problème. Pour cela, il faudra en particulier (mais pas seulement) s’attaquer aux problèmes suivants : (a) optimiser la construction des grammaires formelles qui modélisent les contraintes de structures et de séquence, afin de minimiser autant que possible leur taille ; (b) développer et étudier une nouvelle variante du problème de la génération aléatoire de mots de langages formels, consistant à générer des mots du langage dans un périmètre donné à partir d’un mot donné. Au final, cette chaîne algorithmique donnera lieu à un logiciel prototype qui, une fois validé sur des données biologiques, aura vocation à être mis à disposition de la communauté bioinformatique.
Work program
Extra information
Référence principale : Yu Zhou, Yann Ponty, Stéphane Vialette, Jérôme Waldispühl, Yi Zhang, and Alain Denise. Flexible RNA design under structure and sequence constraints using formal languages. Proceedings of ACM-BCB - ACM Conference on Bioinformatics, Computational Biology and Biomedical Informatics - Washington, 2013.