Abstract FR:

Cette these est consacree aux methodes de comparaison et d'alignement de sequences biologiques et plus particulierement aux algorithmes reposant sur la programmation dynamique. Les algorithmes de needleman & wunsch et de smith & waterman peuvent etre vus comme une suite d'operations elementaires dans l'algebre (max, +). L'utilisation de ce formalisme permet de concevoir un algorithme plus rapide strictement equivalent. Il s'agit en effet de construire un automate, puis de parcourir la banque de donnees grace a cet automate avec une complexite lineaire. Dans les cas degeneres de la programmation dynamique, l'automate est calculable en un temps acceptable, et l'algorithme devient performant. Les methodes d'alignement existantes sont basees sur des couts d'edition calculees additivement, position par position, en fonction d'une matrice de substitution fixe. Ceci implique qu'une substitution a toujours le meme poids, independamment de sa position. Or le biologiste privilegie certaines similitudes en fonction de ses connaissances sur les structures ou fonctions des sequences. La methode presentee ici, consiste a faire intervenir dans l'algorithme de programmation dynamique d'autres types d'informations pouvant influencer sur le resultat de l'algorithme. La premiere idee est la prise en compte de motifs. La methode consiste a realiser un alignement par programmation dynamique lettre a lettre au sens de smith & waterman, en attribuant un bonus supplementaire a tout chemin mettant en correspondance le meme motif sur les deux sequences. Le troisieme aspect de cette these porte sur l'aspect statistique des resultats de ces comparaisons. Il est precieux pour le biologiste d'avoir un guide, permettant de determiner les scores les plus significatifs. La methode la plus fiable semble etre celle du z-score qui consiste en une simulation de monte-carlo. Le z-score est independant des longueurs des sequences, contrairement au score. On presente ici des etudes sur plusieurs genomes complets, pour valider l'utilisation du z-score.