Modèles combinatoires des structures d'ARN avec ou sans pseudonoeuds, application à la comparaison de structures.

This thesis proposes a model of RNA secondary structures with or without pseudoknots. According to a combinatorial approach, we design different models of these structures which we study according to two aspects. In one hand, we define random generation models which allow us to define a measure allowing a better recognition of biological structures. On the other hand, greatings to appropriated encodings and bijections to languages represented by non-contextual grammars, we count the structures composing the space of exact secondary structure prediction algorithms with pseudoknots. The first part deals with random models of RNA structures without pseudoknots. We show that these structures are a relevant source of random noise when determining whether the structures comparison softwares attribute a better comparison score between structures from the same family than alignments between real and random structures. We then compare the sensitivity and spcificity of RNAdistance, a structures comparison software, depending on the use of the "raw" score or on the Z-value. We compute several Z-values according to different models of random structures. We show that the Z-value computed from a Markov model improves the detection of large RNA while the Z-value computed from a model based on weighted grammars improves the detection of small RNA. We then consider, in the other hand, pseudoknotted secondary structure prediction algorithms. First we complete the Condon it et al. classification by describing the structures by their consistancy graph and we also characterize the planar restriction of the class of Rivas and Eddy. Then, we investigate the tradeoff between the complexity of existing algorithms and the size of their prediction space. We count the structures by coding them with words of algebraic languages. Then, we deduce asymptotic formulas count. We also show a bijection between the class of Lyngso and Pedersen and planar maps and a bijection between the class of undifferentiated pseudoknots we introduced and ternary trees.We show that the observed differences in complexity prediction algorithms are not always justified by the size of the space prediction. From these grammars, we design efficient algorithms for generating random RNA structure, uniform or controlled non-uniform, with pseudoknots.Ces travaux de thèse proposent une modélisation des structures secondaires d'ARN avec ou sans pseudonoeuds. Selon une approche combinatoire, nous concevons différents modèles de ces structures que nous étudions sous deux aspects. D'une part, nous définissons des modèles de génération aléatoire qui nous permettent de définir une mesure permettant une meilleure reconnaissance des structures biologiques. D'autre part, grâce à des codages appropriés et des bijections vers des langages représentés par des grammaires non-contextuelles, nous dénombrons les structures composant l'espace de prédiction des algorithmes exacts de prédiction de structures secondaires avec pseudonoeuds. La première partie concerne des modèles aléatoires de structures d'ARN sans pseudonoeuds. Nous montrons que ces structures aléatoires constituent une source de bruit pertinente lorsqu'il s'agit de déterminer si les logiciels de comparaison de structures attribuent un meilleur score à des comparaisons entre structures issues de la même famille d'ARN qu'à des alignements entre structures réelles et aléatoires. Nous comparons ensuite la sensibilité et la spécificité de RNAdistance, un programme de comparaison de structures, selon l'usage du score "brut" ou bien de la Z-valeur de ce score. Nous calculons plusieurs Z-valeurs selon différents modèles de structures aléatoires. Nous montrons que la Z-valeur calculée à partir d'un modèle de Markov améliore la détection des ARN de grande taille tandis que la Z-valeur calculée à partir d'un modèle basé sur des grammaires pondérées améliore la détection des ARN de petite taille. Nous nous intéressons ensuite, dans une deuxième partie, aux algorithmes de prédiction de structure secondaire avec pseudonoeuds. Nous complètons tout d'abord la classification de Condon et al. en décrivant les structures par leur graphe de cohérence et nous caractérisons également la restriction planaire de la classe de Rivas et Eddy. Nous étudions ensuite le compromis entre complexité des algorithmes existant et la taille de leur espace de prédiction. Nous dénombrons les structures en les codant par des mots de langages algébriques. Nous en déduisons alors des formules asymptotiques de dénombrement. Nous mettons aussi en évidence une bijection entre la classe de Lyngsø et Pedersen et des cartes planaires ainsi qu'une bijection entre la classe des pseudonoeuds indifférenciés, que nous avons introduite, et les arbres ternaires. Nous montrons alors que les différences de compléxité observées des algorithmes de prédiction ne sont pas toujours justifiées par la taille de l'espace de prédiction. A partir de ces grammaires, nous concevons des algorithmes efficaces de génération aléatoire, uniforme ou non uniforme contrôlée, de structures d'ARN avec pseudonoeuds