Comparaison de Séquences Biologiques

Saïd ABDEDDAÏM

IBP-Litp 1996/Th/09: THÈSE de DOCTORAT de l'UNIVERSITÉ PARIS 6 Litp / Litp research reports
155 pages - Décembre/December 1996 - French document.

PostScript : Ko /Kb

Titre / Title: Comparaison de Séquences Biologiques

Résumé : Cette thèse porte sur l'alignement de séquences, et plus particulièrement sur l'alignement de plus de deux séquences biologiques. Les algorithmes que nous avons développés opèrent en deux étapes : dans une première étape des blocs (alignements d'occurrences de facteurs sans écartements) compatibles sont sélectionnés dans les séquences, la seconde étape consiste à aligner les séquences entre les blocs.

Notre stratégie de sélection des blocs, est une stratégie gloutonne tout en étant prudente. Nous nous intéressons particulièrement au calcul de blocs qui ne concernent pas nécessairement toutes les séquences à aligner. Pour calculer efficacement ces blocs, nous définissons la structure de graphe hybride, dans lequel un chemin reliant deux occurrences signifie que celles-ci ne peuvent faire partie d'un bloc compatible avec les blocs précédemment sélectionnés. La prise en compte d'un nouveau bloc se traduit par l'insertion d'arêtes dans le graphe hybride. Nous décrirons un nouvel algorithme incrémental permettant de maintenir la fermeture transive de la relation décrite par le graphe hybride après l'insertion d'un bloc.

Sous certaines hypothèses, induites par l'observation d'alignement fait à la main, nous montrons que l'on peut efficacement aligner les séquences entre les blocs à l'aide d'un algorithme de programmation dynamique que nous avons développé.

Nous illustrons sur des données réelles l'efficacité (en temps de calcul et qualité des alignements) de nos algorithmes comparés à deux programmes usités CLUSTAL W et TREEALIGN.

Abstract : We report in this thesis on our work on alignment of sequences, particularly on multiple alignment of biological sequences. Our algorithms work in two steps: first compatible blocks (alignments of occurrences of factors without gaps) are computed on the sequences, then the sequences are aligned between the blocks.

Our strategy for the selection of blocks is greedy but cautious. We are interested particularly in the computation of blocks which do not necessarily concern all the sequences to align. To compute efficiently these blocks, we have defined the structure of hybrid graph, in which when a path relie two occurrences, it means that these occurrences can be in a block compatible with the blocks already computed. Adding a new block means inserting edges in the hybrid graph. We describe a new incremental algorithm that allows to keep the transitive closure of the relation described by the hybrid graph after the insertion of a new block.

The observation of actual alignments has lead us to formulate assumptions wich allow us to align efficiently the sequences between the blocks, using a dynamic programming algorithm.

We show in real data the efficiency (in computation time and alignments quality) of our algorithms comparing to two programs CLUSTAL W and TREEALIGN.

Publications internes Litp 1996 / Litp research reports 1996