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

Les molecules d'ARN jouent un role fondamentale dans les processus chimiques mis en jeu au coeur de la cellule. Les travaux presentes dans cette these concernent la comparaison des structures secondaires d'ARN. Celles-ci ont ete formalisees par M. S. Waterman a la fin des annees 70 et capturent une grande partie des informations relative a la structure des molecules d'ARN. En se basant sur une approche similaire a celle de Shapiro et Viennot, nous les representons par des arborescenes ordonnees etiquetes. L'un des objectifs de cette these est d'explorer les algorithmes de comparaison d'arborescences existants et d'envisager differentes extensions. La famille d'algorithme etudiee s'appuie sur la generalisation des methodes de comparaison entre les mots appliquees au genome. Nous choisissons de nous focaliser sur l'un des meilleurs (en complexite) algorithmes de calcul de la distance d'edition connus a ce jour, celui de Zhang-Shasha, et effectuons une analyse exacte de sa complexite en moyenne. Ensuite, nous transposons aux arborescences quelques avancees en matiere de comparaison de sequences. Nous proposons deux algorithmes originaux d'edition locale d'arborescences non-ordonnees et ordonnees, puis une extension a l'algorithme de Zhang-Shasha afin d'effectuer une edition densifiee d'arborescences. Puis, nous presentons les resultats d'un point de vue biologique et appliquons cet ensemble d'ameliorations aux structures secondaires d'ARN. Ces ameliorations concernent la compression structurelle, l'edition locale et l'edition densifiee de structures secondaires. Pour conclure, nous presentons un protoype d'outil logiciel permettant la comparaison de structures secondaires d'ARN et implementant les diffferents concepts ayant vu le jour au cours de cette these.