Les séquences répétées en tandem sont constituées de motifs adjacents. Elles constituent une classe de séquences génétiques dont font partie microsatellites et minisatellites. Dans cette thèse, nous traitons le problème de la comparaison de séquences répétées en tandem sous un modèle évolutif particulier. Plus précisément, nous nous intéressons au problème de leur alignement dans lequel, en plus des trois opérations classiques, mutation, insertion et délétion, nous considérons l'amplification en tandem et la contraction en tandem. L'amplification copie un facteur de la séquence, c'est-à-dire un ou plusieurs caractère(s), et met le ou les exemplaire(s) du facteur copié à côté du facteur original, la contraction est l'événement inverse. L'amplification (resp. la contraction) est dite « n-aire d'ordre m », si elle copie (resp. retire) m motif(s) n fois. Nous proposons une méthode donnant un score d'alignement, qui est une métrique, entre deux séquences répétées en tandem, sous un modèle comprenant les cinq opérations précédemment citées où l'amplification et la contraction sont unaires d'ordre 1. Le problème est difficile car les opérations ne sont pas commutatives. Notre solution fait appel à de l'algorithmique de graphe. Nous avons réalisé un programme nommé MS_Align qui implémente cette méthode. Il s'agit du premier programme capable d'aligner des cartes de minisatellites. À l'aide de ce programme, nous avons étudié des données biologiques provenant du minisatellite humain MSY1. Comme nous le montrons, notre modèle évolutif s'applique bien à ce type de séquences d'ADN. Nous avons construit à partir de nos résultats des arbres phylogénétiques semblables à ceux obtenus grâce à d'autres marqueurs du chromosome Y indépendants de MSY1, nos arbres offrent une meilleure résolution. Une partie de cette thèse est consacrée au problème général où nous relaxons les contraintes sur les amplifications et contractions.

Les microsatellites, séquences répétées en tandem de période une à six paires de bases, sont des entités génomiques présentes dans tous les organismes qu'ils soient animaux, végétaux ou microbiens. Ils présentent un cycle de vie caractérisé par trois phases principales : une apparition et une maturation, une dynamique à l'état mature, puis une dégénérescence. Nous nous intéressons dans cette thèse à la première phase, l'apparition des microsatellites. <br />Pour traiter ces questions, nous nous sommes basés sur l'analyse de la séquence du génome humain. L'une des lacunes de ce type d'analyse est qu'il faut d'abord extraire les microsatellites du génome, et qu'il existe plusieurs algorithmes de nature et fonctionnement différents. La première partie de cette thèse se concentre donc sur la comparaison de quelques-uns des principaux algorithmes de recherche de répétitions en tandem, et dresse un portait des différentes qualités et limitations de chacun des algorithmes.<br />Deux possibilités majeures sont détaillées, l'apparition par l'intermédiaire d'éléments transposables (ETs), et l'apparition spontanée à partir d'une séquence quelconque. Dans le premier cas, l'étude est focalisée sur le rôle des queues polyA des séquences Alu chez les primates. La question de l'apparition à partir d'une séquence quelconque cherche à établir l'impact de trois mécanismes mutationnels différents sur la création et le développement primordial des microsatellites : la mutation ponctuelle, le glissement de polymérase et la micro-duplication adjacente de quelques nucléotides. Un modèle général d'apparition des microsatellites est aussi proposé, suggérant une dynamique d'apparition plus complexe que ce qui était précédemment supposé.