Les travaux présentés dans cette thèse s'inscrivent dans le cadre de l'algorithmique et de la combinatoire du texte et s'appliquent à la bio-informatique. Plus particulièrement, ils concernent la localisation de motifs pondérés modélisés par des matrices score-position dans un texte non pondéré. Ces travaux sont appliqués au problème biologique de la recherche de sites de fixation de facteurs de transcription dans un génome. Cette application contribue à la compréhension de la régulation des gènes. Nous nous sommes attaqués à deux problèmes complémentaires, la recherche d'une seule matrice dans un texte puis la recherche simultanée d'un ensemble de matrices. Pour accélérer les algorithmes existant, nous nous sommes inspiré des algorithmes de recherche de motifs exacts connus pour leur efficacité. La différence est que les matrices score-position sont des motifs probabilistes, utilisant des fonctions de score. Nous devons donc intégrer la distribution de ces fonctions dans les algorithmes de recherche. Concernant le premier problème nous proposons une extension de l'algorithme de Knuth, Morris et Pratt qui repose sur un pré-traitement du motif pour optimiser le parcours le long du texte. Concernant le second problème nous avons utilisé une structure d'indexation afin de factoriser l'ensemble des matrices. Cette structure tire partie des distributions de scores associées à chaque matrice. Dans les deux cas, nous traitons en amont une partie des données de départ. Nous avons choisi de pré-traiter les matrices par rapport à l'application bio-informatique car les sites de fixation de facteurs de transcription sont des données relativement stables dans le temps. Ces algorithmes ont été mis en oeuvre dans un logiciel disponible en ligne appelé TFMscan. Ils ont fait l'objet d'une validation à grande échelle sur les bases de données de facteurs de transcription Jaspar et Transfac. Mots clés : informatique, algorithmique de texte, algorithmique discrète, combinatoire, probabilité, matrices score-position, matrices position-poids, ADN, sites de fixation de facteurs de transcription, régulation des gènes.
Président : Directeur de Thèse : Hélène Touzet, CR CNRS HDR, Université de Lille I Co-encadrant : Jean-Stéphane Varré, Maître de Conférences, Université de Lille I Rapporteurs : Mireille Régnier, DR INRIA, INRIA Rocquencourt Mathieu Raffinot, CR CNRS HDR, Université de Paris VII Membres : Mireille Clerbout, Professeur, Université de Lille I Sophie Schbath, DR INRA, INRA de Jouy-en-Josas
Thesis of the team Bonsai defended on 04/07/2008
français
English