Abstract FR:

Cette these est consacree a l'etude des plus longues sous-sequences communes (lcs) a un ensemble de chaines de caracteres et a leur usage dans l'analyse des sequences biologiques. En deux mots, une sous-sequence commune a plusieurs chaines est une suite de caracteres, pas necessairement consecutifs, que l'on trouve dans le meme ordre dans chaque chaine. Les lcs nous interesse selon deux points de vue: algorithmique: peut-on determiner, approximer et encadrer leur longueur ? comment construire une lcs ? peut-on les enumerer ? ces questions sont classiques en optimisation combinatoire et nous avons developpe une methode de construction d'une lcs. Le probleme etant np-difficile, nous avons defini une methode approchee, de complexite polynomiale, dont nous avons etudie les performances. Biologique: nous montrons certaines applications des lcs dans l'analyse des sequences biologiques. D'abord en definissant une distance qui permet de retrouver des sequences voisines et de classer un nouvel element dans un arbre de sequences. Puis en proposant une methode d'alignement multiple d'une famille de sequences proteiques