Inférence de motifs structurés : algorithmes et outils appliqués à la détection de sites de fixation dans le séquences génomiques
Institution:
Université de Marne-la-ValléeDisciplines:
Directors:
Abstract EN:
In this work, we concentrated our interest on a problem in molecular biology: the detection of binding sites in DNA sequences. This problem, from a certain point of view, finds diverse solutions in text algorithmics. We first present the specificity of such sites, and look at the existing representations used to modelize them. We then review the existing algorithms aimed at detecting these sites, and try to evaluate the pertinence of the main approaches employed. In particular, we try to discuss the trade off that exists between sensibility and complexity when dealing with such a problem. Our work consists in developing a new representation for binding sites, which incorporates one of the main characteristics of some of them: their ability to appear associated in a more or less constrained manner. We introduce the notion of a structured model, develop several exact combinatorial algorithms to infer such models, and present the software, called SMILE, we made using these algorithms. Going back to the biological problem which motivated this work, we apply our tool to infer known and unknown binding sites in a few sets of DNA sequences. The results of these experiments are compared to those obtained by some of the most used software on the same sets of sequences. We then discuss of the biological pertinence of all these results. Finally, we try to place our work in the current context, and define several directions to explore to improve the inference of binding sites. The algorithms and tools we made are all generic, they can be applied to extract any kind of structured signals that are common to a set of sequences. In particular, they can already treat protein sequences
Abstract FR:
Au cours de ce travail, nous nous sommes particulièrement intéressés à un problème de biologie moléculaire: la détection de sites de fixation dans des séquences d'ADN. Ce problème, perçu sous un certain angle, trouve des solutions variées grâce aux travaux réalisés en algorithmique du texte. Après une présentation des spécificités de ces sites, nous passons en revue les représentations informatiques existantes utilisées pour les modéliser. Puis, nous faisons état des différents travaux algorithmiques effectués dans le domaine de leur détection. La pertinence des principales approches est discutée. Nous essayons en particulier de présenter les différents aspects du compromis qui paraît inévitable entre sensibilité et complexité quand on traite un tel problème. Notre apport consiste ensuite à développer une nouvelle représentation pour les sites de fixation. Celle-ci prend en compte une caractéristique de certains d'entre eux: leur capacité à s'associer sous certaines contraintes. Nous introduisons la notion de modèle structuré, et développons plusieurs algorithmes combinatoires exacts de détection de tels modèles. Nous présentons ensuite l'outil que nous avons conçu à partir de ces algorithmes, dénommé SMILE. Nous ramenant au problème biologique qui a motivé ces travaux algorithmiques, nous appliquons cet outil à l'inférence de sites de fixation connus et inconnus dans des jeux de séquences nucléiques expérimentaux ou directement issus de génomes complets. Les résultats de ces expériences sont comparés avec ceux qu'obtiennent certains outils couramment utilisés sur les mêmes jeux de données, et leur pertinence biologique est discutée. Pour finir, nous jugeons l'apport des modèles structurés et esquissons plusieurs directions à explorer pour améliorer la détection de sites de fixation. Les représentations, algorithmes et outils développés dans cette thèse sont généraux, et peuvent donc être appliqués à l'extraction de tous types de signaux structurés et approchés, communs à plusieurs séquences. En particulier, ils peuvent d'ores et déjà être utilisés pour inférer des motifs dans des séquences protéiques