Maude Pupin (LIFL)

La comparaison de séquences nucléiques est délicate du fait de la petite taille de leur alphabet (4 lettres). Par ailleurs, la comparaison de séquences a pour but de mettre en évidence des régions conservées. Une idée est de ne pas traiter les positions dans les séquences de façon indépendante, mais de travailler sur les mots. Le problème est de gérer les mutations nombreuses qui surviennent au cours du temps. Le décodage local propose une méthode originale pour gérer ces mutations : il extrait l’information intrinsèque aux séquences. La taille de l'alphabet initial est augmentée en prenant en compte le voisinage des positions.
Chaque position de la séquence est renommée avec un indice. Deux positions ayant des contextes équivalents portent le même indice. Ainsi, la détection des régions conservées au sein d'une séquence ou entre plusieurs séquences est facilitée.
Dans un premier temps, l'algorithme de décodage local sera décrit. Puis, une application à l'alignement multiple de séquences sous la forme de graphes sera présentée.

Maude Pupin, Laurent Debomy, Claudine Devauchelle, Alexander Grossmann, Alain Hénaut, Ivan Laprevotte, Ming Zhang, Gilles Didier