Une molécule d'ARN est une chaîne de nucléotides A, C, G et U : elle possède un seul brin au contraire de l'ADN qui en posséde deux et forme ainsi une structure hélicoïdale. Ces nucléotides créent des liaisons deux à deux (A et U, C et G) et forment ainsi une structure planaire : cette structure porte le nom de structure secondaire (la structure tertiaire étant la structure spatiale qui ne nous intéresse pas ici) . Le sujet de ce stage est l'étude d'algorithmes déterminant cette structure secondaire pour des molécules d'ARN quelconques. Deux algorithmes sont considérés : ils sont basés sur le même principe mais font appel à des modélisations d'énergie différentes. Ils sont basés sur des équations aux différences finies; le même problème peut également être résolu par l'utilisation de grammaires context-free. Une partie novatrice de l'approche proposée est une tentative de fournir à l'utilisateur du programme la possibilité de spécifier certaines parties de la structure secondaire d'une molécule d'ARN donnée. Ces algorithmes ont des complexités assez élevés (n3en général). Il est donc intéressant d'en développer des versions parallèles et d'étudier leur efficacité : par exemple, une chaîne contenant 1000 nucléotides est analysée en 2 minutes avec 8 processeurs (sur une machine Onyx à 16 processeurs). L'extrapolation de ces résultats indique qu'une chaîne de 2000 nucléotides pourrait être analysée en 4 minutes avec 64 processeurs.
An RNA molecule is a nucleotide chain. It is single-stranded whereas DNA is double-stranded and it has a helicoidal structure. The nucleotides are represented by A, C, G, U: they create bindings among themselves (an A with a U, a C with a G) to form a planar structure: this structure is called secondary structure (the actual spatial structure is called the tertiary structure but is not of interest in the present work). The topic of this internship is to study algorithms for determining this secondary structure for any RNA molecule. Two algorithms are considered: they take different energy models into account, but they are based on the same principle: the use difference equations. Another approach to solve the problem is to consider context-free grammars. A novel part of the proposed approach is an attempt to provide the user of the program with the possibility to specify desirable parts of the secondary structure of a given RNA string. These algorithms have fairly large time and space complexities (n3both in time and space for the second one): it is therefore worthwhile to consider parallel versions and estimate their efficiency. For instance, an RNA string with 1000 nucleotides can be processed in about 2 minutes using 8 processors (on a 16 processor Onyx machine). Extrapolating these results indicates that strings of 2000 nucleotides can be processed in about 4 minutes using 64 processors.