Date : 2003
Type : Livre / Book
Type : Thèse / ThesisLangue / Language : français / French
Arbres (théorie des graphes) -- Informatique
Résumé / Abstract : Les molécules d'ARN jouent un rôle fondamentale dans les processus chimiques mis en jeu au coeur de la cellule. Les travaux présentés dans cette thèse concernent la comparaison des structures secondaires d'ARN. Celles-ci ont été formalisées par M.S. Waterman à la fin des années 70 et capturent une grande partie des informations relative à la structure des molécules d'ARN. En se basant sur une approche similaire à celle de Shapiro et Viennot, nous les représentons par des arborescenes ordonnées étiquetés. L'un des objectifs de cette thèse est d'explorer les algorithmes de comparaison d'arborescences existants et d'envisager différentes extensions. La famille d'algorithme étudiée s'appuie sur la généralisation des méthodes de comparaison entre les mots appliquées au génome. Nous choisissons de nous focaliser sur l'un des meilleurs (en complexité) algorithmes de calcul de la distance d'édition connus à ce jour, celui de Zhang-Shasha, et effectuons une analyse exacte de sa complexité en moyenne. Ensuite, nous transposons aux arborescences quelques avancées en matière de comparaison de séquences. Nous proposons deux algorithmes originaux d'édition locale d'arborescences non-ordonnées et ordonnées, puis une extension à l'algorithme de Zhang-Shasha afin d'effectuer une édition densifiée d'arborescences.Puis, nous présentons les résultats d'un point de vue biologique et appliquons cet ensemble d'améliorations aux structures secondaires d'ARN. Ces améliorations concernent la compression structurelle, l'édition locale et l'édition densifiée de structures secondaires. Pour conclure, nous présentons un protoype d'outil logiciel permettant la comparaison de structures secondaires d'ARN et implémentant les diffférents concepts ayant vu le jour au cours de cette thèse.