Chargement...
 

Bioinformatics

Domaine
Bioinformatics
Domain - extra
Algorithmics
Année
2014
Starting
Septembre 2014
État
Open
Sujet
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
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
Détails
Expected funding
Institutional funding
Status of funding
Expected
Candidates
Vincent Le Gallic
Utilisateur
alain.denise
Créé
Mercredi 11 juin 2014 20:59:39 CEST
dernière modif.
Dimanche 15 juin 2014 20:12:22 CEST

Fichiers joints

 filenamecrééhitsfilesize 
Aucun fichier joint à cette fiche


Ecole Doctorale Informatique Paris-Sud


Directrice
Nicole Bidoit
Assistante
Stéphanie Druetta
Conseiller aux thèses
Dominique Gouyou-Beauchamps

ED 427 - Université Paris-Sud
UFR Sciences Orsay
Bat 650 - aile nord - 417
Tel : 01 69 15 63 19
Fax : 01 69 15 63 87
courriel: ed-info à lri.fr