Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 3 Juin 2003

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

par Richard Groult (LIFAR-ABISS Université de Rouen)

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.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr