Algorithmes de graphes pour la recherche de motifs récurrents dans les structures tertiaires d'ARN

Understanding space folding is a key issue to determine the function of a RNA molecule. A RNA tertiary structure can be modelized by a graph, with labels on edges and vertices. According to this model, a set of repetitive motifs is a set of similar subgraphs with a common structure, not known a priori. Searching for such a structure necessitates the search of a maximal common subgraph, that is known to be NP-hard. The two main contributions of my thesis are (1) a new similarity measure for graphs that allows for identification of occurrences that are similar to a motif candidate. This measure is computed by an algorithm that detects a maximum common subgraph with some specific properties. (2) a new method to automatically extract and classify (families of) similar RNA motifs. Basically, one extracts a RNA graph that represents the tertiary structure for subgraphs that may contain motifs. Then, similar subgraphs are grouped in distinct clusters, according to the newly defined measure. Exist two types of recurrent tertiary motifs:local motifs that are inserted in secondary structure elements and interaction motifs that take into account two or more elements from a secondary structure. Up to a small adaptation, proposed similarity measure adapts successfully to both types. Classification and extraction methods have been tested on a representative sample of RNA structures. Results have been expertised by biochimists from IMBC (Strasbourg) and are available on line.Le repliement d'une molécule d'ARN non-codant est initié et stabilisé par ce qu'on appelle les motifs tertiaires. Ces motifs sont présents de manière récurrente dans les ARN de différents organismes vivants; ce qui suggère que leur rôle biologique a été conservé à travers l'évolution. Un recensement exhaustif et détaillé de ces motifs récurrents, incluant nombre d'occurrences et variantes, est donc une étape essentielle pour une meilleure compréhension du phénomène de repliement. Ce recensement peut être obtenu de manière efficace grâce à des méthodes automatiques d'extraction. Un inconvénient majeur des méthodes existantes est que la récurrence d'un motif est démontrée lorsque les occurrences trouvées sont strictement identiques. Dans la réalité, ces occurrences ne sont pas toujours identiques mais similaires en ce sens qu'elles possèdent une sous-structure commune ayant des propriétés biologiques spécifiques. Dans notre approche, une structure tertiaire d'ARN est modélisée par un graphe général étiqueté sur les sommets et les arêtes. Les sommets représentent les nucléotides étiquetés par leur base et leur numéro dans la séquence. Les arêtes représentent les interactions entre les bases étiquetées par leur type d'interaction. Les occurrences d'un motif récurrent deviennent, selon ce modèle, des sous-graphes similaires dont la structure commune est a priori inconnue. Ce type de recherche fait appel au problème du sous-graphe commun maximum bien connu en complexité algorithmique pour être NP-difficile et inapproximable. Ce travail propose (1) une nouvelle mesure de similarité de graphe permettant d'identifier des occurrences similaires d'un motif tertiaire potentiel. Cette mesure est obtenue par un algorithme de calcul d'un sous-graphe commun maximum ayant des propriétés structurales spécifiques, (2) une nouvelle méthode automatique d'extraction et de classification de (familles de) motifs d'ARN récurrents utilisant la nouvelle mesure de similarité. Il existe deux types de motifs tertiaires récurrents : les motifs locaux incrustés dans des éléments de structure secondaire et les motifs d'interaction faisant intervenir deux ou plusieurs éléments de structure secondaire. La méthode d'extraction et classification proposée a été appliquée à un échantillon représentatif de structures d'ARN. Les résultats obtenus ont été expertisés par des biochimistes de l'Institut de Biologie Moléculaire et Cellulaire (IBMC) de Strasbourg