Deux méthodes pour la détection de répétitions en tandem avec évolution

Nous présentons deux algorithmes pour la détection d’un nouveau type de répétitions approximatives dans les textes, appelées répétitions avec évolution. Une répétition avec évolution est une série de copies presque contiguës, chaque copie étant similaire (au sens de la distance de Hamming dans cette présentation) à la copie précédente et à la copie suivante. D’un point de vue global, les répétitions avec évolution étendent les traditionnelles répétitions approximatives en tandem où chaque copie doit être dans le voisinage d’un modèle donné. Par manque d’algorithmes adaptés, ces répétitions n’ont été découvertes dans les séquences génomiques que très récemment et sont peu documentées dans la littérature.

Nous présentons un algorithme en O(l.|w|^2) pour le calcul de toutes les répétitions avec évolution dans un mot w, l étant la longueur d’une copie. Cet algorithme repose sur l’utilisation de classes d’équivalences et de graphes. Nous présentons ensuite un algorithme en O(|w|), ainsi que sa version parallèle, pour lesquels nous commençons par calculer un tableau contenant toutes les distances de Hamming entre les copies potentielles, puis nous parcourons ce tableau pour construire une répétition avec évolution complète à partir des copies valides.

Note : Cette présentation sera précédé d’une introduction à la bioinformatique , aucune connaissance biologique particulière n’est nécessaire à la bonne compréhension du sujet.