Loading...
 
[Show/Hide Left Column]

Tracker Item History Help

Close
warningNot logging
Tracker changes are not being logged: Go to Action log admin to enable

Version Date User Field ID Field Old New
8 12:35 225 Domain - extra Algorithmics
7 12:35 185 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

5 12:35 224 Candidates Vincent Le Gallic
4 12:35 180 Abstract The problem of RNA secondary structure design is the following: given a target secondary structure, one aims to create a sequence that folds into, or is compatible with, a given structure. In several practical applications in biology, additional constraints must be taken into account, such as the presence/absence of regulatory motifs, either at a specific location or anywhere in the sequence. The aim of the project is to develop new efficient algorithms for this problem.


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.


4 12:35 181 Context We recently investigated the design of RNA sequences from their targeted secondary structure, given these additional sequence constraints. To this purpose, we developed a general framework based on concepts of language theory, namely context-free grammars and finite state automata, and on random generation of sequences. Deep investigations needs to be done from this general framework, in order to develop efficient algorithms, and then to apply them on problems from molecular biology.
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.
4 12:35 183 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.
3 12:35 179 Subject RNA structure design under sequence constraints using formal languages
Design de structures secondaires avec contraintes de séquences : une approche globale fondée sur les langages formels
2 12:35 181 Context We recently investigated the design of RNA sequences from their targeted secondary structure, given these additional sequence constraints. To this purpose, we developed a general framework based on concepts of language theory, namely context-free grammars and finite state automata, and on random generation of sequences. This framework needs to be investigated further, in order to develop very efficient algorithms and software, and to apply them on problems from molecular biology.
We recently investigated the design of RNA sequences from their targeted secondary structure, given these additional sequence constraints. To this purpose, we developed a general framework based on concepts of language theory, namely context-free grammars and finite state automata, and on random generation of sequences. Deep investigations needs to be done from this general framework, in order to develop efficient algorithms, and then to apply them on problems from molecular biology.
2 12:35 183 Objectives

1 12:35 179 Subject Design de structures d'ARN avec contraintes de séquences
RNA structure design under sequence constraints using formal languages
1 12:35 181 Context We recently investigated the design of RNA sequences from their targeted secondary structure, given these additional sequence constraints. To this purpose, we developed a general framework based on concepts of language theory, namely context-free grammars and finite state automata. This lead to the first design algorithm that deals with mandatory and forbidden motifs. Our method was used by molecular biologists, in order to design and test in vivo genomic sequences with desired structural features.

We recently investigated the design of RNA sequences from their targeted secondary structure, given these additional sequence constraints. To this purpose, we developed a general framework based on concepts of language theory, namely context-free grammars and finite state automata, and on random generation of sequences. This framework needs to be investigated further, in order to develop very efficient algorithms and software, and to apply them on problems from molecular biology.
1 12:35 183 Objectives

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 at lri.fr