Dans un premier temps, nous avons modélisé la structure d’une famille d’ARN avec une grammaire de graphes afin d’identifier les séquences qui en font partie. Plusieurs autres méthodes de modélisation ont été développées, telles que des grammaires stochastiques hors-contexte, des modèles de covariance, des profils de structures secondaires et des réseaux de contraintes. Ces méthodes de modélisation se basent sur la structure secondaire classique comparativement à nos grammaires de graphes qui se basent sur les motifs cycliques de nucléotides. Pour exemplifier notre modèle, nous avons utilisé la boucle E du ribosome qui contient le motif Sarcin-Ricin qui a été largement étudié depuis sa découverte par cristallographie aux rayons X au début des années 90. Nous avons construit une grammaire de graphes pour la structure du motif Sarcin-Ricin et avons dérivé toutes les séquences qui peuvent s’y replier. La pertinence biologique de ces séquences a été confirmée par une comparaison des séquences d’un alignement de plus de 800 séquences ribosomiques bactériennes. Cette comparaison a soulevée des alignements alternatifs pour quelques unes des séquences que nous avons supportés par des prédictions de structures secondaires et tertiaires. Les motifs cycliques de nucléotides ont été observés par les membres de notre laboratoire dans l'ARN dont la structure tertiaire a été résolue expérimentalement. Une étude des séquences et des structures tertiaires de chaque cycle composant la structure du Sarcin-Ricin a révélé que l'espace des séquences dépend grandement des interactions entre tous les nucléotides à proximité dans l’espace tridimensionnel, c’est-à-dire pas uniquement entre deux paires de bases adjacentes. Le nombre de séquences générées par la grammaire de graphes est plus petit que ceux des méthodes basées sur la structure secondaire classique. Cela suggère l’importance du contexte pour la relation entre la séquence et la structure, d’où l’utilisation d’une grammaire de graphes contextuelle plus expressive que les grammaires hors-contexte. Les grammaires de graphes que nous avons développées ne tiennent compte que de la structure tertiaire et négligent les interactions de groupes chimiques spécifiques avec des éléments extra-moléculaires, comme d’autres macromolécules ou ligands. Dans un deuxième temps et pour tenir compte de ces interactions, nous avons développé un modèle qui tient compte de la position des groupes chimiques à la surface des structures tertiaires. L’hypothèse étant que les groupes chimiques à des positions conservées dans des séquences prédéterminées actives, qui sont déplacés dans des séquences inactives pour une fonction précise, ont de plus grandes chances d’être impliqués dans des interactions avec des facteurs. En poursuivant avec l’exemple de la boucle E, nous avons cherché les groupes de cette boucle qui pourraient être impliqués dans des interactions avec des facteurs d'élongation. Une fois les groupes identifiés, on peut prédire par modélisation tridimensionnelle les séquences qui positionnent correctement ces groupes dans leurs structures tertiaires. Il existe quelques modèles pour adresser ce problème, telles que des descripteurs de molécules, des matrices d’adjacences de nucléotides et ceux basé sur la thermodynamique. Cependant, tous ces modèles utilisent une représentation trop simplifiée de la structure d’ARN, ce qui limite leur applicabilité. Nous avons appliqué notre modèle sur les structures tertiaires d’un ensemble de variants d’une séquence d’une instance du Sarcin-Ricin d’un ribosome bactérien. L’équipe de Wool à l’université de Chicago a déjà étudié cette instance expérimentalement en testant la viabilité de 12 variants. Ils ont déterminé 4 variants viables et 8 létaux. Nous avons utilisé cet ensemble de 12 séquences pour l’entraînement de notre modèle et nous avons déterminé un ensemble de propriétés essentielles à leur fonction biologique. Pour chaque variant de l’ensemble d’entraînement nous avons construit des modèles de structures tertiaires. Nous avons ensuite mesuré les charges partielles des atomes exposés sur la surface et encodé cette information dans des vecteurs. Nous avons utilisé l’analyse des composantes principales pour transformer les vecteurs en un ensemble de variables non corrélées, qu’on appelle les composantes principales. En utilisant la distance Euclidienne pondérée et l’algorithme du plus proche voisin, nous avons appliqué la technique du « Leave-One-Out Cross-Validation » pour choisir les meilleurs paramètres pour prédire l’activité d’une nouvelle séquence en la faisant correspondre à ces composantes principales. Finalement, nous avons confirmé le pouvoir prédictif du modèle à l’aide d’un nouvel ensemble de 8 variants dont la viabilité à été vérifiée expérimentalement dans notre laboratoire. En conclusion, les grammaires de graphes permettent de modéliser la relation entre la séquence et la structure d’un élément structural d’ARN, comme la boucle E contenant le motif Sarcin-Ricin du ribosome. Les applications vont de la correction à l’aide à l'alignement de séquences jusqu’au design de séquences ayant une structure prédéterminée. Nous avons également développé un modèle pour tenir compte des interactions spécifiques liées à une fonction biologique donnée, soit avec des facteurs environnants. Notre modèle est basé sur la conservation de l'exposition des groupes chimiques qui sont impliqués dans ces interactions. Ce modèle nous a permis de prédire l’activité biologique d’un ensemble de variants de la boucle E du ribosome qui se lie à des facteurs d'élongation. / Initially, we modeled the structure of an RNA family with a graph grammar to identify sequences that correspond to it. Several other modeling approaches have been developed to derive sequences, such as stochastic context-free grammars, covariance models, secondary structures profiles and constraint networks. These modeling methods are based on secondary structure compared to our graph grammars which are based on the nucleotide cyclic motifs. To exemplify our graph grammar model, we used the loop E of the ribosome that contains the Sarcin-Ricin motif that has been widely studied since its discovery by X-ray crystallography in the early 90s. We built a graph grammar for the structure of the Sarcin-Ricin motif and derived the sequences that correspond to it. The biological relevance of these sequences is supported by an alignment of 800 bacterial ribosomal sequences. This comparison raised alternative alignments for some of the sequences that we supported by predictions of secondary and tertiary structures. According to a new tertiary structure, those alternative alignments accommodate the new derived sequences. The nucleotide cyclic motifs used in the grammar were observed by members of our laboratory in RNA tertiary structures that were solved experimentally. We study the sequences and tertiary structures of the nucleotide cyclic motifs of the Sarcin-Ricin motif. This study suggests that the space of sequences depends heavily on interactions between all nucleotides in the nearby three-dimensional space and not only between two adjacent base pairs. We compare the number of sequences generated by the graph grammar with non contextual methods and our graph grammar generates less sequences. This suggests the importance of context for the relationship between sequence and structure, hence the use of a contextual graph grammar is more expressive than context-free grammars. The graph grammars we used include the tertiary structure but neglect the interactions with extra-molecular factors, such as other macromolecules or ligands. In a second stage and to take into account these interactions, we developed a model incorporating the positioning of chemical groups on the surface of the tertiary structures. The assumption being that the chemical groups that are conserved on the surface of the RNA in active sequences are more likely to be involved in interactions with extra-molecular factors. Continuing with the example of the loop E, we searched the groups that could be involved its interactions with elongation factors. Knowledge of the groups involved in the important interactions serves to predict by three-dimensional modeling new sequences that have potentials to realize these interactions and thus the same function. There are few models that have been developed to address this problem: molecular descriptors, nucleotide adjacency matrices and others based on thermodynamics. These models use an oversimplified representation of the RNA structure, which limits their applicability. We applied our model to the tertiary structures of a set of variants of a sequence of one instance of the Sarcin-Ricin motif from a bacterial ribosome. Wool and coworkers at the University of Chicago studied this proceeding experimentally by testing the viability of twelve variants. They identified four viable variants and eight lethal. We used this set of twelve sequences for training our model and we identified a set of essential properties to their biological function. For each variant of the training set we built models of tertiary structures. We then measured the partial charges of exposed atoms on the surface and we encoded this information into vectors. We used principal component analysis to transform the vectors into a set of uncorrelated variables, called principal components. Using the weighted Euclidean distance and a nearest neighbor algorithm, we applied the technique of "Leave-One-Out Cross-Validation" to choose the best parameters to predict the activity of a new sequence to match these principal components. Finally, we validated the predictive model using a new set of eight variants whose viability has been verified experimentally in our laboratory. In conclusion, graph grammars are used to model the relationship between sequence and structure of an RNA structural element, such as the ribosomal loop E containing the Sarcin-Ricin motif. Applications range from the correction of sequence alignment to sequence design with a predetermined structure. We also developed a model to take into account the specific interactions related to a specific biological function. Our model is based on the retention of the exposure of chemical groups that are involved in these interactions. This model has allowed us to predict the biological activity of a set of variants of the loop E that binds to elongation factors.

Dans un premier temps, nous avons modélisé la structure d’une famille d’ARN avec une grammaire de graphes afin d’identifier les séquences qui en font partie. Plusieurs autres méthodes de modélisation ont été développées, telles que des grammaires stochastiques hors-contexte, des modèles de covariance, des profils de structures secondaires et des réseaux de contraintes. Ces méthodes de modélisation se basent sur la structure secondaire classique comparativement à nos grammaires de graphes qui se basent sur les motifs cycliques de nucléotides. Pour exemplifier notre modèle, nous avons utilisé la boucle E du ribosome qui contient le motif Sarcin-Ricin qui a été largement étudié depuis sa découverte par cristallographie aux rayons X au début des années 90. Nous avons construit une grammaire de graphes pour la structure du motif Sarcin-Ricin et avons dérivé toutes les séquences qui peuvent s’y replier. La pertinence biologique de ces séquences a été confirmée par une comparaison des séquences d’un alignement de plus de 800 séquences ribosomiques bactériennes. Cette comparaison a soulevée des alignements alternatifs pour quelques unes des séquences que nous avons supportés par des prédictions de structures secondaires et tertiaires. Les motifs cycliques de nucléotides ont été observés par les membres de notre laboratoire dans l'ARN dont la structure tertiaire a été résolue expérimentalement. Une étude des séquences et des structures tertiaires de chaque cycle composant la structure du Sarcin-Ricin a révélé que l'espace des séquences dépend grandement des interactions entre tous les nucléotides à proximité dans l’espace tridimensionnel, c’est-à-dire pas uniquement entre deux paires de bases adjacentes. Le nombre de séquences générées par la grammaire de graphes est plus petit que ceux des méthodes basées sur la structure secondaire classique. Cela suggère l’importance du contexte pour la relation entre la séquence et la structure, d’où l’utilisation d’une grammaire de graphes contextuelle plus expressive que les grammaires hors-contexte. Les grammaires de graphes que nous avons développées ne tiennent compte que de la structure tertiaire et négligent les interactions de groupes chimiques spécifiques avec des éléments extra-moléculaires, comme d’autres macromolécules ou ligands. Dans un deuxième temps et pour tenir compte de ces interactions, nous avons développé un modèle qui tient compte de la position des groupes chimiques à la surface des structures tertiaires. L’hypothèse étant que les groupes chimiques à des positions conservées dans des séquences prédéterminées actives, qui sont déplacés dans des séquences inactives pour une fonction précise, ont de plus grandes chances d’être impliqués dans des interactions avec des facteurs. En poursuivant avec l’exemple de la boucle E, nous avons cherché les groupes de cette boucle qui pourraient être impliqués dans des interactions avec des facteurs d'élongation. Une fois les groupes identifiés, on peut prédire par modélisation tridimensionnelle les séquences qui positionnent correctement ces groupes dans leurs structures tertiaires. Il existe quelques modèles pour adresser ce problème, telles que des descripteurs de molécules, des matrices d’adjacences de nucléotides et ceux basé sur la thermodynamique. Cependant, tous ces modèles utilisent une représentation trop simplifiée de la structure d’ARN, ce qui limite leur applicabilité. Nous avons appliqué notre modèle sur les structures tertiaires d’un ensemble de variants d’une séquence d’une instance du Sarcin-Ricin d’un ribosome bactérien. L’équipe de Wool à l’université de Chicago a déjà étudié cette instance expérimentalement en testant la viabilité de 12 variants. Ils ont déterminé 4 variants viables et 8 létaux. Nous avons utilisé cet ensemble de 12 séquences pour l’entraînement de notre modèle et nous avons déterminé un ensemble de propriétés essentielles à leur fonction biologique. Pour chaque variant de l’ensemble d’entraînement nous avons construit des modèles de structures tertiaires. Nous avons ensuite mesuré les charges partielles des atomes exposés sur la surface et encodé cette information dans des vecteurs. Nous avons utilisé l’analyse des composantes principales pour transformer les vecteurs en un ensemble de variables non corrélées, qu’on appelle les composantes principales. En utilisant la distance Euclidienne pondérée et l’algorithme du plus proche voisin, nous avons appliqué la technique du « Leave-One-Out Cross-Validation » pour choisir les meilleurs paramètres pour prédire l’activité d’une nouvelle séquence en la faisant correspondre à ces composantes principales. Finalement, nous avons confirmé le pouvoir prédictif du modèle à l’aide d’un nouvel ensemble de 8 variants dont la viabilité à été vérifiée expérimentalement dans notre laboratoire. En conclusion, les grammaires de graphes permettent de modéliser la relation entre la séquence et la structure d’un élément structural d’ARN, comme la boucle E contenant le motif Sarcin-Ricin du ribosome. Les applications vont de la correction à l’aide à l'alignement de séquences jusqu’au design de séquences ayant une structure prédéterminée. Nous avons également développé un modèle pour tenir compte des interactions spécifiques liées à une fonction biologique donnée, soit avec des facteurs environnants. Notre modèle est basé sur la conservation de l'exposition des groupes chimiques qui sont impliqués dans ces interactions. Ce modèle nous a permis de prédire l’activité biologique d’un ensemble de variants de la boucle E du ribosome qui se lie à des facteurs d'élongation. / Initially, we modeled the structure of an RNA family with a graph grammar to identify sequences that correspond to it. Several other modeling approaches have been developed to derive sequences, such as stochastic context-free grammars, covariance models, secondary structures profiles and constraint networks. These modeling methods are based on secondary structure compared to our graph grammars which are based on the nucleotide cyclic motifs. To exemplify our graph grammar model, we used the loop E of the ribosome that contains the Sarcin-Ricin motif that has been widely studied since its discovery by X-ray crystallography in the early 90s. We built a graph grammar for the structure of the Sarcin-Ricin motif and derived the sequences that correspond to it. The biological relevance of these sequences is supported by an alignment of 800 bacterial ribosomal sequences. This comparison raised alternative alignments for some of the sequences that we supported by predictions of secondary and tertiary structures. According to a new tertiary structure, those alternative alignments accommodate the new derived sequences. The nucleotide cyclic motifs used in the grammar were observed by members of our laboratory in RNA tertiary structures that were solved experimentally. We study the sequences and tertiary structures of the nucleotide cyclic motifs of the Sarcin-Ricin motif. This study suggests that the space of sequences depends heavily on interactions between all nucleotides in the nearby three-dimensional space and not only between two adjacent base pairs. We compare the number of sequences generated by the graph grammar with non contextual methods and our graph grammar generates less sequences. This suggests the importance of context for the relationship between sequence and structure, hence the use of a contextual graph grammar is more expressive than context-free grammars. The graph grammars we used include the tertiary structure but neglect the interactions with extra-molecular factors, such as other macromolecules or ligands. In a second stage and to take into account these interactions, we developed a model incorporating the positioning of chemical groups on the surface of the tertiary structures. The assumption being that the chemical groups that are conserved on the surface of the RNA in active sequences are more likely to be involved in interactions with extra-molecular factors. Continuing with the example of the loop E, we searched the groups that could be involved its interactions with elongation factors. Knowledge of the groups involved in the important interactions serves to predict by three-dimensional modeling new sequences that have potentials to realize these interactions and thus the same function. There are few models that have been developed to address this problem: molecular descriptors, nucleotide adjacency matrices and others based on thermodynamics. These models use an oversimplified representation of the RNA structure, which limits their applicability. We applied our model to the tertiary structures of a set of variants of a sequence of one instance of the Sarcin-Ricin motif from a bacterial ribosome. Wool and coworkers at the University of Chicago studied this proceeding experimentally by testing the viability of twelve variants. They identified four viable variants and eight lethal. We used this set of twelve sequences for training our model and we identified a set of essential properties to their biological function. For each variant of the training set we built models of tertiary structures. We then measured the partial charges of exposed atoms on the surface and we encoded this information into vectors. We used principal component analysis to transform the vectors into a set of uncorrelated variables, called principal components. Using the weighted Euclidean distance and a nearest neighbor algorithm, we applied the technique of "Leave-One-Out Cross-Validation" to choose the best parameters to predict the activity of a new sequence to match these principal components. Finally, we validated the predictive model using a new set of eight variants whose viability has been verified experimentally in our laboratory. In conclusion, graph grammars are used to model the relationship between sequence and structure of an RNA structural element, such as the ribosomal loop E containing the Sarcin-Ricin motif. Applications range from the correction of sequence alignment to sequence design with a predetermined structure. We also developed a model to take into account the specific interactions related to a specific biological function. Our model is based on the retention of the exposure of chemical groups that are involved in these interactions. This model has allowed us to predict the biological activity of a set of variants of the loop E that binds to elongation factors.