Recherche de similarités dans les séquences d'ADN : modèles et algorithmes pour la conception de graines efficaces

Most commonly used similarity search methods in genomic sequences are heuristic ones. These are based upon text filtering that allows one to infer potential regions of similarity. This thesis proposes new filter definitions to search for similarities in genomic sequences, and fast algorithms to measure the efficiency of these filters. More precisely, we study the spaced seed model and propose an algorithm to measure the seed efficiency on similarities of a certain kind, called homogeneous similarities. A generic algorithm has also been developed to measure the seed efficiency, together with an extension of the spaced seed model called subset seed. Finally, we propose and analyze a multi-seed approach in the framework of lossless filtration, and apply it to the problem of oligonucleotide design. Several software tools have been developed to search for similarities as well as to design seed-based filters.Les méthodes de recherche de similarités les plus fréquemment utilisées dans le cadre de la génomique sont heuristiques.Elles se basent sur un principe de filtrage du texte qui permet de localiser les régions potentiellement similaires.Dans cette thèse, nous proposons de nouvelles définitions de filtres pour la recherche de similarités sur les séquences génomiques et des algorithmes associés pour mesurer leurs caractéristiques. Plus précisément, nous avons étudié le modèle des graines espacées, et proposé un algorithme d'évaluation de l'efficacité des graines sur des similarités d'une classe particulière (similarités dites homogènes). Nous avons également développé un algorithme général pour la mesure de l'efficacité des graines, ainsi qu'un nouveau modèle de graine appelé graine sous-ensemble, extension du modèle des graines espacées. Enfin nous donnons, dans le cadre du filtrage sans perte, une extension à l'aide de graines multiples, que nous analysons et appliquons au problème de la conception d'oligonucléotides. Nous avons réalisé et donnons accès à des outils pour la conception des filtres, ainsi que pour la recherche de similarités