Identification de motifs au sein des structures biologiques arborescentes

The explosion of available biological data urges the need for bioinformatics methods. Many biological structures are modeled by tree structures such as RNA secondary structure and plants architecture. These structures contain repeating units within their structure, but also between different structures. We propose to exploit this fundamental property to improve storage and treatment of such objects. Following the principle of sequence filtering, we define a filtering method on ordered trees to efficiently retrieve in a database a set of ordered trees close from a query. The method is based on a decomposition of the tree into seeds and the detection of shared seeds between these structures. We define and solve the maximum chaining problem on trees. We propose for RNA secondary structure applications a definition of (l−d) centered seed. Based on instantiation techniques used for instance in computer graphics and the repetitiveness of biological structures, we present a compression method which reduces the memory space required for plant architecture storage. A more compact data structure is used in order to represent plant architecture. The construction of this data structure require the identification of internal redundancies and taking into account both topological and geometrical informations.Avec l'explosion de la quantité de données biologiques disponible, développer de nouvelles méthodes de traitements efficaces est une problématique majeure en bioinformatique. De nombreuses structures biologiques sont modélisées par des structures arborescentes telles que les structures secondaires d'ARN et l'architecture des plantes. Ces structures contiennent des motifs répétés au sein même de leur structure mais également d'une structure à l'autre. Nous proposons d'exploiter cette propriété fondamentale afin d'améliorer le stockage et le traitement de tels objets. En nous inspirant du principe de filtres sur les séquences, nous définissons dans cette thèse une méthode de filtrage sur les arborescences ordonnées, permettant de rechercher efficacement dans une base de données, un ensemble d'arborescences ordonnées proches d'une arborescence requête. La méthode se base sur un découpage de l'arborescence en graines et sur une recherche de graines communes entre les structures. Nous définissons et résolvons le problème de chaînage maximum sur des arborescences. Nous proposons dans le cas des structures secondaires d'ARN une définition de graines (l−d) centrées. Dans un second temps, en nous basant sur des techniques d'instanciations utilisées, par exemple, en infographie et sur la connaissance des propriétés de redondances au sein des structures biologiques, nous présentons une méthode de compression permettant de réduire l'espace mémoire nécessaire pour le stockage d'arborescences non-ordonnées. Après une détermination des redondances, nous utilisons une structure de données plus compacte pour représenter notamment l'architecture de la plante, celle-ci pouvant contenir des informations topologiques mais également géométriques