In this thesis, we address the problem of identifying and quantifying variants (alternative splicing and genomic polymorphism) in RNA-seq data when no reference genome is available, without assembling the full transcripts. Based on the idea that each variant corresponds to a recognizable pattern, a bubble, in a de Bruijn graph constructed from the RNA-seq reads, we propose a general model for all variants in such graphs. We then introduce an exact method, called KisSplice, to extract alternative splicing events and show that it outperforms general purpose transcriptome assemblers. We put an extra effort to make KisSplice as scalable as possible. In order to improve the running time, we propose a new polynomial delay algorithm to enumerate bubbles. We show that it is several orders of magnitude faster than previous approaches. In order to reduce its memory consumption, we propose a new compact way to build and represent a de Bruijn graph. We show that our approach uses 30% to 40% less memory than the state of the art, with an insignificant impact on the construction time. Additionally, we apply the techniques developed to list bubbles in two classical problems: cycle enumeration and the K-shortest paths problem. We give the first optimal algorithm to list cycles in undirected graphs, improving over Johnson's algorithm. This is the first improvement to this problem in almost 40 years. We then consider a different parameterization of the K-shortest (simple) paths problem: instead of bounding the number of st-paths, we bound the weight of the st-paths. We present new algorithms using exponentially less memory than previous approaches

Nous développons une approche générique pour comprendre comment différents régimes alimentaires peuvent influencer la qualité et la composition du lait. Cette question s'intègre dans le cadre du Flux Balance Analysis (FBA), qui consiste à analyser un réseau métabolique en optimisant un système de contraintes linéaires. Nous avons proposé une extension du FBA pour analyser la transformation des nutriments en intégrant des hypothèses biologiques utilisées par différents modèles numériques dans un modèle générique de la glande mammaire. Notre méthode permet de quantifier les précurseurs qui interviennent dans la composition des sorties du système, en calculant des contributions des entrées dans les sorties [AIO]. A l'aide de cette approche, nous avons montré que la transformation des nutriments du lait ne peut pas être modélisée par l'optimisation d'une combinaison linéaire des flux des réactions sur un modèle du métabolisme mammaire. Pour étudier plus précisément la flexibilité d'un réseau métabolique, nous avons proposé un algorithme e

La croissance exponentielle de la génération de données pour la bioinformatique couplée à une stagnation des fréquences d'horloge des processeurs modernes accentuent la nécessité de fournir des implémentation tirant bénéfice des capacités parallèles des ordinateurs modernes. Cette thèse se concentre sur des algorithmes et implementations pour des problèmes de bioinformatique. Plusieurs types de parallélisme sont décrits et exploités. Cette thèse présente des applications en génétique, avec un outil de détection de QTL paralllisé sur GPU, en comparaison de structures de protéines, avec un outil permettant de trouver des régions similaires entre protéines parallélisé sur CPU, ainsi qu'à l'analyse de larges graphes avec une implémentation multi-GPUs d'un nouvel algorithme pour le problème du "All-Pairs Shortest Path".

INTRODUCTION : Les syndromes polymalformatifs constituent un large groupe de maladies génétiques dont l'hétérogénéité limite notre capacité à identifier le gène causal à l’aide des investigations conventionnelles. Le séquençage de l'exome en clinique offre une solution à cette limitation et est maintenant disponible en recherche ou dans quelques laboratoires cliniques aux États-Unis. L'utilisation systématique du séquençage de l'exome reste encore entravée par notre capacité à gérer les trouvailles accidentelles et à prédire efficacement le ou les changements causals à partir de plusieurs milliers de variants. Ainsi, pour faciliter l'analyse de l'exome et accélérer l'implémentation du séquençage de l'exome en clinique, nous avons développé, et récemment publié à ce sujet, un logiciel nommé PhenoVar. Celui-ci intègre les données génotypiques et phénotypiques, puis suggère à l’utilisateur une courte liste priorisée de diagnostics potentiels pour révision. Nous présentons ici les données préliminaires de la validation de PhenoVar chez des patients atteints de syndromes polymalformatifs indéterminés, en comparaison à l'analyse bio-informatique standard. MÉTHODE : Un total de 27 patients atteints de syndromes polymalformatifs d'étiologie génétique probable a été accepté pour le séquençage de l'exome. Un résultat normal a été obtenu pour chaque patient lors d’une analyse d'hybridation génomique comparative sur micropuce et reste sans diagnostic clair après le test de quelques gènes susceptibles par séquençage Sanger. À ce jour, nous avons réalisé le séquençage de 22 patients. Un médecin généticien a effectué l'analyse de ces patients utilisant PhenoVar, en parallèle à l'analyse standard réalisée par l'équipe de bio-informatique. RÉSULTATS : En moyenne, PhenoVar a réduit le nombre de diagnostics potentiels à réviser de façon manuelle à 20 par patient, en comparaison à 64 pour l'analyse bio- informatique conventionnelle. Nous avons obtenu un rendement diagnostique global de 50% (11/22) et de 45% avec PhenoVar. Neuf fois sur onze, le bon diagnostic s’est retrouvé dans les dix premiers diagnostics de la liste de PhenoVar. Nous avons aussi identifié une variation pathologique dans BRCA2, trouvaille accidentelle réalisée durant l’analyse conventionnelle et remise au patient avec son consentement. L’outil PhenoVar permet de masquer ce type de diagnostics sans lien avec la présentation clinique. La dépendance à l’égard des bases de données s’est avérée être une limite de notre approche. CONCLUSION : Nos résultats préliminaires suggèrent que le séquençage de l'exome combiné avec PhenoVar, en utilisant une approche axée sur le phénotype, conduit à un rendement diagnostique similaire à l'analyse bio-informatique standard et réduit le nombre de diagnostics à réviser. Comme il peut être utilisé directement par les médecins généticiens, ce logiciel pourrait faciliter l'utilisation de routine du séquençage de l'exome dans un cadre clinique. / BACKGROUND : Polymalformation syndromes consist in a large group of heterogeneous genetic disorders, for which our ability to identify the causative gene using conventional investigations remains limited. Exome sequencing offers a solution and is now available either on a research basis or in few USA clinical laboratories. Routine utilization of exome sequencing is still hindered by our capacity to manage accidental findings and to predict effectively the causative change(s) out of several thousands of variants. To facilitate exome analysis and accelerate implementation of exome sequencing in clinical practice, we have developed and recently published a software named PhenoVar. This software integrates the patient’s phenotype to the genotype data and suggests to the physician-user a short list of prioritized potential diagnoses for review. Here, we present the preliminary results of PhenoVar validation in patients affected with an undetermined polymalformation syndrome, in comparison to standard bioinformatics analysis. METHODS : A total of 27 patients with polymalformative syndromes of likely genetic etiology were accepted for exome sequencing. Each patient has a normal CGH array and remains without a clear diagnosis after Sanger sequencing-based gene tests. To date, we completed the sequencing of 22 patients. A medical geneticist performed the analysis on these patients using PhenoVar, in parallel of the standard analysis done by the bioinformatics team. RESULTS : On average, PhenoVar reduced the number of potential diagnoses for manual review to 20 per patient in comparison to 64, for standard bioinformatics analysis. We obtained a global diagnostic yield of 50% (11/22) and a yield of 45% with PhenoVar. Nine times out of eleven, the correct diagnosis was found in the top ten diagnoses of the PhenoVar’s list. We also identified a pathological variant in BRCA2, accidental finding made during the conventional analysis and given to the patient who provided consent. PhenoVar allows hiding such diagnoses unrelated to the clinical presentation. Dependency on central databases has proven to be a limitation of our approach. CONCLUSION : Our preliminary results suggests that exome sequencing combined with PhenoVar, using a phenotype-driven approach, led to a similar diagnostic yield than standard bioinformatics analysis and reduced the number of diagnoses to review. Since it can be used directly by medical geneticists, this software could facilitate routine utilization of exome sequencing in clinical practice.

La technologie des microarrays demeure à ce jour un outil important pour la mesure de l'expression génique. Au-delà de la technologie elle-même, l'analyse des données provenant des microarrays constitue un problème statistique complexe, ce qui explique la myriade de méthodes proposées pour le pré-traitement et en particulier, l'analyse de l'expression différentielle. Toutefois, l'absence de données de calibration ou de méthodologie de comparaison appropriée a empêché l'émergence d'un consensus quant aux méthodes d'analyse optimales. En conséquence, la décision de l'analyste de choisir telle méthode plutôt qu'une autre se fera la plupart du temps de façon subjective, en se basant par exemple sur la facilité d'utilisation, l'accès au logiciel ou la popularité. Ce mémoire présente une approche nouvelle au problème de la comparaison des méthodes d'analyse de l'expression différentielle. Plus de 800 pipelines d'analyse sont appliqués à plus d'une centaine d'expériences sur deux plateformes Affymetrix différentes. La performance de chacun des pipelines est évaluée en calculant le niveau moyen de co-régulation par l'entremise de scores d'enrichissements pour différentes collections de signatures moléculaires. L'approche comparative proposée repose donc sur un ensemble varié de données biologiques pertinentes, ne confond pas la reproductibilité avec l'exactitude et peut facilement être appliquée à de nouvelles méthodes. Parmi les méthodes testées, la supériorité de la sommarisation FARMS et de la statistique de l'expression différentielle TREAT est sans équivoque. De plus, les résultats obtenus quant à la statistique d'expression différentielle corroborent les conclusions d'autres études récentes à propos de l'importance de prendre en compte la grandeur du changement en plus de sa significativité statistique. / Microarrays remain an important tool for the measurement of gene expression, and a myriad of methods for their pre-processing or statistical testing of differential expression has been proposed in the past. However, insufficient and sometimes contradictory evidence has prevented the emergence of a strong consensus over a preferred methodology. This leaves microarray practitioners to somewhat arbitrarily decide which method should be used to analyze their data. Here we present a novel approach to the problem of comparing methods for the identification of differentially expressed genes. Over eight hundred analytic pipelines were applied to more than a hundred independent microarray experiments. The accuracy of each analytic pipeline was assessed by measuring the average level of co-regulation uncovered across all data sets. This analysis thus relies on a varied set of biologically relevant data, does not confound reproducibility for accuracy and can easily be extended to future analytic pipelines. This procedure identified FARMS summarization and the TREAT gene ordering statistic as algorithms significantly more accurate than other alternatives. Most interestingly, our results corroborate recent findings about the importance of taking the magnitude of change into account along with an assessment of statistical significance.

Le récepteur de l'acide rétinoïque RAR est une protéine de la superfamille des récepteurs nucléaires liant le ligand acide rétinoïque (AR). En présence de son ligand, RAR induit la transcription de ses gènes cibles alors qu'en son absence la transcription est inhibée. Le mécanisme de régulation de RAR est altéré dans les lignées cellulaires humaines de carcinome mammaire dû à une baisse de capacité de synthèse de l'AR. Aussi, l'expression des microARN (miR) est perturbée dans le cancer du sein et un grand nombre de gènes ont été identifiés, après une analyse in-silico, comme des cibles prédites des miRs. Ces derniers peuvent être régulés pas des facteurs de transcription et ils sont capables d'inhiber la prolifération cellulaire et d'induire l'apoptose via la régulation de leurs cibles. Ainsi, les miRs peuvent jouer un rôle dans le mécanisme de régulation de RAR et être impliqués dans des boucles de régulation avec ce récepteur. Dans le cadre de ce travail, nous décrivons une approche développée pour prédire et caractériser des circuits de régulation au niveau transcriptionnel et post-transcriptionnel dans le cancer du sein. Nous nous sommes intéressés aux boucles de régulation de type feed-forward où RAR régule un miR et en commun ils régulent un ensemble de gènes codants pour des protéines dans les cellules tumorales mammaires MCF7 et SKBR3. Ces circuits ont été construits en combinant des données de ChIP-chip de RAR et des données de micro-puces d'ADN tout en utilisant des outils in-silico de prédiction des gènes cibles de miRs. Afin de proposer le modèle approprié de régulation, une analyse in-silico des éléments de réponse de l'AR (RARE) dans les promoteurs des miRs est réalisée. Cette étape permet de prédire si la régulation par RAR est directe ou indirecte. Les boucles ainsi prédites sont filtrées en se basant sur des données d'expression de miR existantes dans des bases de données et dans différentes lignées cellulaires, en vue d'éliminer les faux positifs. De plus, seuls les circuits pertinents sur le plan biologique et trouvés enrichis dans Gene Ontology sont retenus. Nous proposons également d'inférer l'activité des miRs afin d'orienter leur régulation par RAR. L'approche a réussi à identifier des boucles validées expérimentalement. Plusieurs circuits de régulation prédits semblent être impliqués dans divers aspects du développement de l'organisme, de la prolifération et de la différenciation cellulaire. De plus, nous avons pu valider que let-7a peut être induit par l'AR dans les MCF7. / The retinoic acid receptor (RAR) is a type of nuclear receptor that is activated by the ligand retinoic acid (RA). In the presence of ligand, RAR induces the transcription of its targets whereas in the absence of ligand the transcription is blocked. The mechanism of regulation of RAR is altered in breast cancer cell lines due to a reduced capacity to synthesize RA. Also aberrant patterns of microRNA (miR) expression have been reported in human breast cancer and a number of genes involved in breast cancer progression have been identified by in-silico analysis to be targets of miRs. The miRs could be controlled by transcription factors and via the regulation of their mRNA targets, the miRs could promote apoptosis and even inhibit cell proliferation. Hence, the miRs may play a role in the mechanism of regulation of RAR and could be involved in regulatory loops with this receptor. In this work, we describe an approach developed for the prediction and characterization of mixed transcriptional and post-transcriptional regulatory circuits in breast cancer. We concentrated in particular on feed-forward loops, in which RAR regulates a miR, and together with it, a set of joint target protein coding genes in human breast cancer cell lines MCF7 and SKBR3. These loops are constructed by combining ChIP-chip datasets of RAR with datasets of DNA microarrays and by using miR target prediction tools. In order to predict the appropriate model of regulation, in-silico analysis was performed to look for retinoic acid response element (RARE) in miR promoter. This step could identify if the regulation by RAR is direct or indirect. The regulatory loops will be then filtered, in order to reduce the number of false positive, based on databases designed to represent human miR expression profiles in different tissues or cell types. Moreover, only biologically relevant circuits enriched in Gene Ontology were retained. Also, we propose to infer miR activity in order to detect their regulation by RAR. This approach was able to find some existing experimental data. Several regulatory circuits seem to be involved in various aspects of organism development, proliferation and cell differentiation. Furthermore, we were able to validate the induction of let-7a by RA in MCF7 cells.

La méthode ChIP-seq est une technologie combinant la technique de chromatine immunoprecipitation avec le séquençage haut-débit et permettant l’analyse in vivo des facteurs de transcription à grande échelle. Le traitement des grandes quantités de données ainsi générées nécessite des moyens informatiques performants et de nombreux outils ont vu le jour récemment. Reste cependant que cette multiplication des logiciels réalisant chacun une étape de l’analyse engendre des problèmes de compatibilité et complique les analyses. Il existe ainsi un besoin important pour une suite de logiciels performante et flexible permettant l’identification des motifs. Nous proposons ici un ensemble complet d’analyse de données ChIP-seq disponible librement dans R et composé de trois modules PICS, rGADEM et MotIV. A travers l’analyse de quatre jeux de données des facteurs de transcription CTCF, STAT1, FOXA1 et ER nous avons démontré l’efficacité de notre ensemble d’analyse et mis en avant les fonctionnalités novatrices de celui-ci, notamment concernant le traitement des résultats par MotIV conduisant à la découverte de motifs non détectés par les autres algorithmes. / ChIP-seq is a technology combining the chromatin immunoprecipitation method with high-throughput sequencing and allowing the analysis of transcription factors in vivo on a genome wide scale. The treatment of such amount of data generated by this method requires strong computer resources and new tools have been recently developed. Though this proliferation of software performing only one step of the analyze leads to compatibility problems and complicates the analysis. Thus, there is a real need for an integrated, powerful and flexible pipeline for motifs identification. Here we proposed a complete pipeline for the analysis of ChIP-seq data freely available in R and composed of three R packages PICS, rGADEM and MotIV. Analyzing four data sets for the human transcription factors CTCF, STAT1, FOXA1 and ER we demonstrated the efficiency of or pipeline and highlighted its new features, especially concerning the processing of the results by MotIV that led to the identification of motif not detected by other methods.

Les gènes codant pour des protéines peuvent souvent être regroupés et intégrés en modules fonctionnels par rapport à un organelle. Ces modules peuvent avoir des composantes qui suivent une évolution corrélée pouvant être conditionnelle à un phénotype donné. Les gènes liés à la motilité possèdent cette caractéristique, car ils se suivent en cascade en réponse à des stimuli extérieurs. L’hyperthermophilie, d’autre part, est interreliée à la reverse gyrase, cependant aucun autre élément qui pourrait y être associé avec certitude n’est connu. Ceci peut être dû à un déplacement de gènes non orthologues encore non résolu. En utilisant une approche bio-informatique, une modélisation mathématique d’évolution conditionnelle corrélée pour trois gènes a été développée et appliquée sur des profils phylétiques d’archaea. Ceci a permis d’établir des théories quant à la fonction potentielle du gène du flagelle FlaD/E ainsi que l’histoire évolutive des gènes lui étant liés et ayant contribué à sa formation. De plus, une histoire évolutive théorique a été établie pour une ligase liée à l’hyperthermophilie. / Protein coding gene may often be grouped and integrated in functional modules with respect to an organelle. These modules may have constituents that follow a conditional correlated evolution to a given phenotype. Genes linked to motility posses this characteristic as they follow a cascade in response to external stimuli. Similarly, hyperthermophily is related to reverse gyrase, however no other element that could be associated with certainty is known. This may be caused by an unresolved case of non-orthologous gene displacement. Using a bioinformatic approach, a mathematical model for conditional correlated evolution for three genes has been developed and applied to the phyletic profiles of archaea. This has helped to develop theories about the potential functions of the flagellar gene FlaD/E and the evolutionary history of the genes that are linked to it and that may have contributed to its formation. In addition, a theoretical evolutionary history has been established for a ligase associated with hyperthermophily.

Les microARNs appartiennent à la famille des petits ARNs non-codants et agissent comme inhibiteurs des ARN messagers et/ou de leurs produits protéiques. Les mi- croARNs sont différents des petits ARNs interférants (siARN) car ils atténuent l’ex- pression au lieu de l’éliminer. Dans les dernières années, de nombreux microARNs et leurs cibles ont été découverts chez les mammifères et les plantes. La bioinforma- tique joue un rôle important dans ce domaine, et des programmes informatiques de découvertes de cibles ont été mis à la disposition de la communauté scientifique. Les microARNs peuvent réguler chacun des centaines de gènes, et les profils d’expression de ces derniers peuvent servir comme classificateurs de certains cancers. La modélisation des microARNs artificiels est donc justifiable, où l’un pourrait cibler des oncogènes surexprimés et promouvoir une prolifération de cellules en santé. Un outil pour créer des microARNs artificiels, nommé MultiTar V1.0, a été créé et est disponible comme application web. L’outil se base sur des propriétés structurelles et biochimiques des microARNs et utilise la recherche tabou, une métaheuristique. Il est démontré que des microARNs conçus in-silico peuvent avoir des effets lorsque testés in-vitro. Les sé- quences 3’UTR des gènes E2F1, E2F2 et E2F3 ont été soumises en entrée au programme MultiTar, et les microARNs prédits ont ensuite été testés avec des essais luciférases, des western blots et des courbes de croissance cellulaire. Au moins un microARN artificiel est capable de réguler les trois gènes par essais luciférases, et chacun des microARNs a pu réguler l’expression de E2F1 et E2F2 dans les western blots. Les courbes de crois- sance démontrent que chacun des microARNs interfère avec la croissance cellulaire. Ces résultats ouvrent de nouvelles portes vers des possibilités thérapeutiques. / MicroRNAs belong to the family of small non-coding RNAs and act as down regula- tors of messenger RNAs and/or their protein products. microRNAs differ from siRNAs by downregulating instead of shutting down. In recent years, numerous microRNAs and their targets have been found in mammals and plants. Bioinformatics plays a big role in this field, as software has emerged to find new microRNA targets. Each individual microRNA can regulate hundreds of genes, and it has been shown that microRNA expression profiles can classify human cancers. The need for artificially created mi- croRNAs is then justified, as one could target overexpressed oncogenes and promote healthy cell proliferation. MultiTar V1.0, a tool for creating artificial microRNAs, has been implemented and is available as a web application. The tool relies on structural and biological properties of microRNAs and uses a Tabusearch metaheuristic. A typical biological problem is presented and it is shown that an in-silico microRNA has in-vitro effects. The 3’UTR sequences of E2F1, E2F2 and E2F3 were given as input to the tool, and predicted microRNAs were then tested using luciferase essays, western blots and growth curves. At least one microRNA is able to regulate the three genes with luciferase essays and all of the created microRNAs were able to regulate the expres- sion of E2F1 and E2F2 with western blots. Growth curves were also studied in order to investigate overall biological effects, and reduction in growth was observed for all solutions. Results obtained with the predicted microRNAs and the target genes open a new door into therapeutic possibilities.

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.