Matrices score-position, algorithmes et propriétés

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.The work presented in this thesis is a part of the algorithmic and the combination of text and is apply to bio-informatic. More precisely, they relate to the location of grounds weighted modeled by position weIght matrices scoring in an unweighted text. This work is applied to the problem of biological research binding sites of transcription factors in a genome. This applrcation contributes to understanding the regulation of genes. We tackled two problems, find a single. matnx in a text and then the simultaneous search of a whole matrices. To accelerate existing algonthms, we have been inspired by exact research algorithms known for their effectiveness. The difference is that the dice are scoring position probabilistic grounds usmg. functions score. We must integrate the distribution of these functions in the search algonthms. Regardmg the first problem we proposed an extension of the Knuth. Morris and Pratt algorithm witch is based on a pre-treatment ta optimize route of ground along the text .Regarding the second problem we used an indexing structure in order to factor all matnces. ThIs structure uses distributions of scores associated to each matrix. ln both cases we are dea!mg with upstream part of baselines. We chose to pre-treat matrices in relation to the bio-mformatic application because the binding sites of transcription factors data are relatively stable over time. These algorithms have been implemented in a software available online called TFMscan. They have been validated on a large-scale bases data transcription factors Jaspar and Transfac .LILLE1-Bib. Electronique (590099901) / SudocSudocFranceF