Etude algorithmique et statistique de la comparaison des structures secondaires d’ARN

Notre travail s’inscrit dans la problématique de la comparaison des structures d’ARN. De récentes avancées ont montré que bon nombre d’ARN, dits ARN non-codants, ne sont pas traduits en protéines mais ont un rôle fonctionnel dans les processus cellulaires. Il existe un lien fort entre la structure et la fonction d’un ARN non-codant. Les structures secondaires d’ARN sont souvent modélisées par des arbres ou par des séquences arc-annotées. Il existe des algorithmes polynomiaux d’édition et d’alignement d’arbres (Zhang, Shasha 1989 ; Jiang, et al. 1995 ; Klein 1998). Cependant, ces approches sont basées sur un système d’opérations d’édition peu adapté au cas des structures d’ARN.

En se basant sur un jeu d’opérations d’édition biologiquement réalistes et une modélisation par des séquences arc-annotées, il a été démontré que le problème de l’édition de deux structures secondaire d’ARN est NP-complet (Jiang, et al. 2002 ; Blin, et al. 2003). Nous avons étudié le problème d’alignement de structures secondaires d’ARN prenant en compte le jeu d’opérations d’édition réalistes, pour lequel nous proposons un algorithme de complexité polynomiale, ainsi que des variantes pour l’alignement local et la recherche d’un motif de structure secondaire dans une structure secondaire complète. La complexité de cet algorithme est analysée dans le pire cas et en moyenne. Nous avons également travaillé sur la construction de matrices de scores pour les opérations d’édition biologiquement réalistes. Enfin, nous avons étudié le problème de motif de structure secondaire commun à un ensemble de structures d’ARN, basé sur un modèle d’évaluation biologiquement pertinent.