Sujets

View

View Item

Domain Bioinformatics
Domain - extra Algorithmics
Year 2014
Starting Septembre 2014
Status Open
Subject Design de structures secondaires avec contraintes de séquences : une approche globale fondée sur les langages formels
Thesis advisor DENISE Alain
Co-advisors
Laboratory LRI Bioinfo
Collaborations 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.

Preprint accessible à : https://www.lri.fr/~denise/publications/ZhPoViWaZhDe2013.pdf

Prerequisite
Details
Expected funding Institutional funding
Status of funding Expected
Candidates Vincent Le Gallic
user alain.denise
Created Wednesday 11 of June, 2014 20:59:39 CEST
LastModif Sunday 15 of June, 2014 20:12:22 CEST
Comments
Attachments (0)

Attachments

 filenamecreatedhitsfilesize 
No attachments for this item


The original document is available at https://edips.lri.fr/tiki-view_tracker_item.php?itemId=3993