Drapeau Anglais

Algorithmique des structures biologiques :
l'édition d'arborescences pour la comparaison de structures secondaires d'ARN

Laurent Tichit

Responsable: Serge Dulucq

Résumé :

Les molécules d'ARN jouent un rôle fondamental 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 relatives à 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 arborescences ordonnées étiquetées.
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'algorithmes é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 extensions à 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 prototype d'outil logiciel permettant la comparaison de structures secondaires d'ARN et implémentant les différents concepts ayant vu le jour au cours de cette thèse.

Mots clés :

Algorithmique, Arborescence, ARN, Comparaison, Complexité, Distance, Programmation Dynamique, Série génératrice, Structure secondaire.

Rapport de Thèse :

Au format Postscript

Valid HTML 4.01!