Algorithmes de prédiction et de recherche de multi-structures d'ARN

RNA (ribonucleic acid) molecules have various functions in cells. Just as they can store and deliver the DNA message for the protein synthesis (messenger RNAs), they can also directly catalyze chemical reactions or act as a regulator (functional RNAs, also called non-coding RNAs). Nowadays, recent sequencing technologies yield billions of genomic sequences - DNA, RNA - at a very small cost. However, sequencing is only the first step: The function of the sequence remains open for investigation. The objective of the thesis is to define new computational methods to help sequence and structure analysis of non-coding RNAs. In this perspective, the "secondary structure" of an RNA,made with base pairs, provides useful hints to further study its function. Our work is focused on sets of all possible RNA structures for a given sequence, introducing the concept of "RNA multi-structures". The thesis details how such sets can be constructed systematically to generate all locally optimal secondary structures, and how they can be used as a pattern to identify non-coding RNAs in genomic sequences. We provide efficient algorithms for these two problems. These algorithms have been implementated in the software tools Alterna and Regliss and tested on real data, providing new insight into RNA structuresL'ARN (acide ribonucléique) est une molécule ubiquitaire qui joue plusieurs rôles fondamentaux au sein de la cellule: synthèse des protéines avec les ARN messagers, activité catalytique ou implicationdans la régulation, les ARN non-codants. Les nouvelles technologies de séquençage à haut-débit permettent de produire des milliards de séquences à moindre coût, posant de manière cruciale la question de l'analyse de ces données. L'objectif de cette thèse est de définir de nouvelles méthodes computationnelles pour aider à l'analyse de ces séquences dans le cas des ARN non-codants. Dans cette perspective, la "structure secondaire" d'un ARN, formée par l'ensemble des appariements entrebases, délivre des informations utiles pour étudier la fonction de l'ARN. Notre travail se concentre plus particulièrement sur l'ensemble des structures potentielles que peut adopter une séquence d'ARN donnée, ensemble que nous appelons "multi-structure". Nous apportons deux contributions: un algorithme pour générer systématiquement toutes les structures localement optimales composantune multi-structure, et un algorithme basé sur la recherche d'unemulti-structure pour identifier un ARN non-codant dans une séquence génomique. Ces résultats ont été mis en oeuvre dans deux logiciels, Alterna et Regliss, appliqués avec succès à des ensembles de test