|
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.
|
|
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
|
![[Show/Hide Left Column]](styles/coelesce/img/icons/oleftcol.png "[Show/Hide Left Column]"){kind=icon}
