Cette thèse s’intéresse à la conception de systèmes complexes d’automatisation sûrs de fonctionnement dont l’évaluation est basée sur des scénarios. Pour déterminer un système optimal, il est important de disposer d’outils de modélisation et d’évaluation rapides ainsi que des algorithmes d’optimisation adaptés au sein d’une méthodologie globale de conception. Cette méthodologie doit également permettre d’étudier l’impact des défaillances sur le comportement final du système contrôlé. Dans ce cadre, la détermination d’un architecture matérielle, son optimisation vis-à-vis de critères comme la longueur minimale des scénarios et le nombre de combinaisons de scénarios sont considérés.Nous proposons une modélisation fonctionnelle et dysfonctionnelle utilisant les scénarios de modes de défaillances. Le niveau de détail considéré est suffisamment fin pour décrire différentes possibilités d’agencements des composants utilisables ainsi que plusieurs types de composants. Si la modélisation fonctionnelle est facile à appréhender, la modélisation dysfonctionnelle tenant compte des scénarios est plus difficile. Afin de répondre à ce problème, nous proposons un modèle graphique baptisé ”Arbre de défaillances multiples améelioré” permettant de modéliser, à l’aide d’opérateurs temporels et de relations entre modes de défaillances, ce comportement dysfonctionnel. L’applicationde cette méthodologie à un système de ferroutage est présentée. Les résultats obtenus pour les fonctionnalités liées au problème de l’incendie et du désarrimage sont comparés avec une méthode classique d’évaluation afin de montrer l’efficacité de l’approche proposée. L’intégration de ces travaux dans un logiciel dédié à la conception de systèmes d’automatisation (plate forme ALoCSyS : Atelier Logiciel de Conception de Systèmes Sûrs) est décrite. / This thesis deals with a design problem of dependable automated systems using scenarios. In order to determine an optimal system, having fast tools for modelling and evaluating dependability is important. These tools allow the set of possible architectures to be evaluated, and the impact of failures to be studied. The main considered questions include the determination of an equipment architecture, its optimization according to such criteria as the minimal length of scenarios, and its number of combinations. A new graphical model, called improved multi fault tree, which is enough accurate to model component organizations and scenarios, is proposed for this problem. This model uses temporal operators and failure relationships to model system’s behaviour in presence of multiple failures. Application of this method to the railroad piggybacking transportation system is also presented. Results obtained for a fire detection and a stowing protection system are presented. A comparison between the proposed approach and the classical dependability approach shows the benefits of this new methodology. The integration of this research in a software for designing dependable automated systems (ALoCSyS) is described.

Les documents constituent une capitalisation importante des connaissances. Généralement, ces documents sont caractérisés par un contenu peu structuré et il est alors difficile de les intégrer dans les systèmes d’information décisionnels. En conséquence, les décideurs ne peuvent pas tirer profit de ces documents. Pour répondre à cette problématique, nous proposons une approche de construction du schéma de l’entrepôt de documents XML. Cette approche se compose de deux méthodes : une méthode d’unification des structures des documents XML et une méthode de modélisation multidimensionnelle de ces documents. La méthode d’unification permet de définir une structure commune pour décrire les documents XML hétérogènes et appartenant au même domaine. Pour valider cette méthode, un outil logiciel baptisé USD (Unification of Structures of XML Documents) est développé. La méthode de modélisation multidimensionnelle a pour but de concevoir semi-automatiquement le schéma du magasin de documents, selon le modèle multidimensionnel en galaxie, à partir d’une structure XML unifiée. Afin de valider cette méthode, un outil nommé Galaxy-Gen (Galaxy Generation) est développé. / Documents represent an important knowledge capitalization. In general, these documents are characterized by unstructured content, and therefore it is difficult to integrate them in the decision information systems. As a result, decision-makers are unable to exploit these documents easily and efficiently. To alleviate this problem, we propose an approach to build the schema of the XML documents warehouse. This approach consists of two methods: a method for unification of the structures of XML documents and a method for multidimensional modeling of these documents. The unification method defines a common structure to describe heterogeneous XML documents belonging to the same domain. To validate this method, a software tool called USD (Unification of Structures of XML Documents) is developed. While the method of multidimensional modeling builds semi-automatically the schema of the documents mart as a galaxy model. To validate this method, the tool called Galaxy-Gen (Galaxy Generation) is developed.

Plusieurs approches ont, jusqu'à présent, été utilisées pour l'identification de nouvelles souches ainsi que pour la caractérisation et la classification des différentes espèces au sein des Bacillaceae. Cependant, la plupart de ces méthodologies présentent certaines insuffisances. L'objectif de cette étude est d'établir et d'évaluer des classifications phylogénétiques des Bacillaceae basées sur divers gènes, d'analyser l'effet de l'hétérogénéité alléliques sur celles-ci, ainsi que d'étudier la distribution des mutations. Seuls les Bacillaceae dont le génome est complètement séquencé ont été considérés. Dans ce travail, tous les allèles des trois gènes de l'opéron ribosomal ont été utilisés. Trois gènes codant pour des protéines ont également été choisis pour la construction de phylogénies et la comparaison avec celles basées sur l'opéron ribosomal. L'analyse phylogénétique de dix souches de Bacillaceae a été réalisée suivant la méthode de Neighbour-Joining (NJ) en utilisant les paramètres de Kimura. La fiabilité et la robustesse de la classification ont été évaluées à l'aide de la méthode "Bootstrap". L'analyse basée sur tous les allèles des trois gènes de l'opéron ribosomal (16S, 23S et 5S) montre que les arbres obtenus présentent la même topologie et répartissent les Bacillaceae en trois groupes et deux sous-groupes. Aucun des gènes n'a permis la discrimination des espèces ou des souches au sein du groupe cereus au sens large. L'analyse phylogénétique des Bacillaceae pourrait donc se limiter à l'un des gènes de l'opéron ribosomal puisque aucune information additionnelle n'est apportée par l'utilisation d'un gène en particulier. Les régions inter géniques lTS1 (16S-23S) et ITS2 (23S-5S) n'ont pas permis, non plus, de discriminer au sein du groupe cereus au sens large. Mais elles ont, néanmoins, mis en évidence l'hétérogénéité alléliques. L'approche basée sur les séquences nucléotidiques des gènes de ménage: adénylate kinase (adk) , shikimate 5-déshydrogénase (aroE) et la sous-unité B de l'ADN gyrase (gyrB), ainsi que de leurs séquences concaténées, a permis une meilleure discrimination notamment au sein du groupe cereus au sens large. Les Bacillaceae sont répartis en trois groupes et sept sous-groupes dont cinq au sein du groupe cereus au sens large. L'utilisation des séquences en acides aminées des protéines codées par les gènes adk, aroE et gyrB et de leurs séquences concaténées a généré, quant à elle, des classifications incongruentes. De plus, elle n'a pas permis une meilleure discrimination des Bacillaceae au sein du groupe cereus au sens large. Plusieurs espèces se retrouvent dans un même faisceau secondaire. Un tel regroupement trouve son explication dans la dégénérescence du code génétique. L'utilisation des séquences nucléotidiques des gènes de ménage serait donc une meilleure approche pour la classification phylogénétique des Bacillaceae. L'analyse de tous les allèles des différents gènes de l'opéron ribosomal (16S, 23S et 5S) montre qu'ils sont hétérogènes et que cette hétérogénéité n'a pas d'effet notable sur la classification phylogénétique. Il est donc justifié de se limiter à un seul allèle de l'un des trois gènes de l'opéron ribosomal lors de l'étude phylogénétique des Bacillaceae. L'étude de la distribution des mutations au sein des trois gènes de l'opéron ribosomal (16S, 23S et 5S) pour les Bacillaceae montre qu'elle n'est pas uniforme et qu'il existe au sein de ces gènes des régions hypervariables dans lesquels se concentrent les mutations. La comparaison de la distribution des mutations au sein du gène 16S pour les Bacillaceae et les y-protéobactéries montre que ces régions hypervariables sont spécifiques pour chaque groupe de bactéries. L'étude phylogénétique basée sur la concaténation des régions hypervariables du gène 16S pour les Bacillaceae a révélé que la topologie de l'arbre découlerait de la structure de ces régions. L'étude phylogénétique des Bacillaceae basée le gène 16S pourrait se limiter à l'analyse des régions hypervariables de ce gène. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Adénylate kinase (adk), ARN 16S, ARN 23S, ARN 5S, Bacillaceae, Classification phylogénétique, Distribution des mutations, Gènes de ménage, Hétérogénéité alléliques, Régions hypervariables, y-protéobactéries, shikimate5-déshydrogénase (aroE) et sous-unité B de l'ADN gyrase (gyrB).

Dans la partie frontale d'un compilateur, il est souvent usuel de transformer l'arbre syntaxique concret correspondant à la grammaire utilisée lors de l'analyse syntaxique en un arbre simplifié appelé arbre syntaxique abstrait qui retient uniquement l'essentiel des éléments de l'arbre syntaxique concret et qui par ailleurs est plus approprié pour les étapes ultérieures de la compilation. La réalisation d'une telle transformation avec les générateurs de compilateurs traditionnels peut nécessiter d'écrire une quantité considérable de code répétitif et très enclin aux erreurs dans la grammaire. Dans ce mémoire, nous introduisons un nouveau mécanisme pour spécifier des transformations d'un arbre syntaxique concret vers un arbre syntaxique abstrait durant l'analyse syntaxique. Doté d'une syntaxe intuitive, ce mécanisme permet la spécification de transformations ascendantes de manière efficace et déterministe. De plus, des vérifications effectuées sur ces transformations garantissent leur exactitude. Nous avons implanté ce mécanisme à l'intérieur de l'outil SableCC, un générateur de compilateurs. Le résultat est un outil capable de générer des analyseurs lexicaux et syntaxiques dans lesquelles sont enchâssées des actions de construction d'arbres syntaxiques et des classes utilitaires (incluant des visiteurs) à partir de simples spécifications grammaticales. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Arbre syntaxique concret, Arbre syntaxique abstrait, Générateur de compilateurs, Analyse syntaxique.

Les bactéries se prêtent très bien aux analyses phylogénétiques en raison du fait que plusieurs génomes ont été entièrement séquencés -et leur nombre continue d'augmenter -et leurs génomes sont petits et ne contiennent que peu d'ADN répétitif en contraste avec les génomes des eucaryotes. La molécule d'ARNr 16S, l'ARN composant de la petite sous-unité du ribosome, a été établie comme la macromolécule de choix pour les analyses phylogénétiques et l'identification des espèces bactériennes. En dépit de sa position centrale, l'utilisation de l'ARNr 16S n'est pas sans inconvénients. En effet, l'évolution d'un seul gène n'est pas nécessairement représentative de l'évolution d'un génome entier, des hétérogénéités entre des copies du gène d'ARNr 16S -des allèles -ne sont pas exceptionnelles, et des copies paralogues peuvent suggérer des phylogénies différentes. De plus, au cours des dernières années, des analyses phylogénétiques basées sur des séquences codant pour des protéines conservées -telles des gènes de ménage (house-keeping genes) -ont donné des résultats discordants. Parmi les bactéries, les y-protéobactéries avec 33 génomes entièrement séquencés sont les plus étudiées, certainement en raison de leurs importances cliniques et biologiques. L'objectif de mon travail a été, d'une part d'étudier l'hétérogénéité des séquences des allèles de l'ARNr 16S chez 33 y-protéobactéries et de déterminer si un seul allèle par bactérie est suffisant pour établir une phylogénie, d'autre part de construire les arbres phylogénétiques de ces 33 y-protéobactéries à partir de l'analyse comparée des séquences de certains gènes de ménage à savoir: l'adénylate kinase (adk), la shikimate déshydrogénase (aroE), la glucose-6-phosphate déshydrogénase (gdh) et de leurs séquences concaténées. Ces phylogénies seront comparées entre elles et aussi à celle établie à partir du gène de l'ARNr 16S. Les analyses phylogénétiques ont démontré que la plupart des séquences alléliques d'une même souche sont identiques ou quasi identiques et sont regroupées à l'intérieur d'un même genre et d'une même espèce. À cause de leurs homogénéités, un seul allèle du gène de l'ARNr 16S est suffisant pour construire la phylogénie des y-protéobactéries au niveau du genre et de l'espèce. Les arbres phylogénétiques construits à partir de chacun des trois gènes de ménage -adk, aroE et gdh -et des séquences concaténées des trois gènes sont, en général, similaires à l'arbre construit à partir du gène de l'ARNr 16S, aux niveaux de la famille, du genre, de l'espèce et de la souche, avec certaines exceptions. Les gènes de ménage, cependant, montrent un plus haut taux de substitutions nucléotidiques que le gène de l'ARNr 16S. De plus, parce que les trois gènes de ménage ont chacun un pourcentage plus bas de similarité de séquences que le gène de l'ARNr 16S, ils ont montré une meilleure différenciation des neuf souches de bactéries entériques Escherichia-Shigella-Salmonella. Ils peuvent potentiellement révéler des relations sur des branches plus profondes d'un arbre phylogénétique que ne le peut le gène de l'ARNr 16S. De plus, puisque ces gènes de ménage sont utilisés dans les typages de séquence multi-locus "multilocus sequence typing (MLST)", nous pouvons nous attendre à ce que le nombre de séquences disponibles dans le domaine public pour ces trois gènes de ménage augmente rapidement les rendant ainsi d'autant plus utiles pour complémenter le gène de l'ARNr 16S dans des études phylogénétiques, ou pour certaines autres analyses phylogénétiques très ciblées. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : y-protéobactéries, Gènes de ménage, Phylogénie, ARNr 16S.

Depuis une quarantaine d'années, de nombreux algorithmes et logiciels ont été développés pour inférer des arbres phylogénétiques. Cependant, certains phénomènes biologiques comme l'hybridation ou le transfert latéral de gènes ne peuvent pas être représentés sous la forme d'un arbre. On utilise ainsi de plus en plus des réseaux phylogénétiques. Les recherches sur ce sujet ont débuté il y a une dizaine d'années et les outils disponibles actuellement pour déterminer des réseaux phylogénétiques sont beaucoup moins performants que dans le cas des arbres. L'objectif principal de mes recherches consiste ainsi à développer une nouvelle méthode pour inférer des réseaux phylogénétiques en se limitant au cas de l'hybridation. J'ai ainsi développé un nouvel algorithme qui permet de retrouver tous les arbres phylogénétiques et de détecter tous les hybrides entre des branches voisines. Quand les parents des hybrides ne sont pas voisins, il trouve les bons hybrides avec des taux de détection proches de 100%, mais il trouve trop d'hybrides et n'identifie pas toujours les bons parents de ces hybrides. Ce nouvel algorithme est itératif et est basé sur le critère des moindres carrés qui permet de déterminer la configuration optimale à chaque itération. Il a été implémenté dans le langage C++ et plusieurs centaines de simulations ont été effectuées pour tester ses fonctionnalités. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : arbre phylogénétique, inférence phylogénétique, réseau réticulé, hybridation, critère des moindres carrés.

Le transfert horizontal de gènes (THG, ou transfert latéral de gènes) est un mécanisme d'évolution naturel qui consiste en le transfert direct du matériel génétique d'une espèce à une autre. La possibilité que le transfert horizontal de gènes puisse jouer un rôle clé dans l'évolution biologique est un changement fondamental dans notre perception des aspects généraux de la biologie évolutive survenu ces dernières années. Par exemple, les bactéries et les virus possèdent des mécanismes sophistiqués d'acquisition de nouveaux gènes par transfert horizontal leur permettant de s'adapter et d'évoluer adéquatement dans leur environnement. Jusqu'à tout récemment, les méthodes de détection de ce mécanisme reposaient essentiellement sur l'analyse de séquences et étaient très rarement automatisées. Il est impossible de représenter l'évolution d'organismes ayant subi des THG à l'aide d'arbres phylogénétiques acycliques. La présentation adéquate est celle d'un réseau. Dans cette thèse, nous décrivons un nouveau modèle de ce mécanisme d'évolution, en se basant sur l'étude de différences topologiques et métriques entre un arbre d'espèces et un arbre du gène inférés pour le même ensemble d'espèces. Les méthodes qui en découlent ont été appliquées à des jeux de données réelles où des hypothèses de transferts latéraux de gènes étaient plausibles. Des simulations Monté-Carlo ont été menées afin d'évaluer la qualité des résultats par rapport à des méthodes existantes. Nous présentons également une généralisation du modèle de transferts horizontaux complets qui est applicable pour détecter des transferts partiels et identifier des gènes mosaïques. Dans ce dernier modèle, on suppose qu'une partie seulement du gène a été transférée. Enfin, nous présentons une application de ces nouvelles méthodes servant à modéliser des emprunts de mots survenus durant l'évolution des langues indo-européennes. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : arbre phylogénétique, réseau réticulé, transfert horizontal de gènes, critère des moindres carrés, distance de Robinson et Foulds, dissimilarité de bipartitions, biolinguistique.

L'objectif de ce projet de maîtrise est de développer un nouvel algorithme permettant de retrouver les relations phylogénétiques entre un arbre de référence (par exemple, l'arbre de la distribution géographique des espèces ou des paramètres climatiques) et un arbre caractérisant un fragment de l'alignement de séquences multiples (ASM). Pour ce faire, nous récupérerons d'abord les différents fragments d'un ASM donné. Nous les soumettrons par la suite aux différents programmes du paquet PHYLIP (Seqboot, ProtDist ou DnaDist, Neighbor et Consense) et le programme PhyML afin d'obtenir un arbre consensus avec les valeurs de bootstrap sur ses branches. À partir de chaque arbre consensus, nous calculerons son bootstrap moyen. De plus, nous comparerons topologiquement l'arbre consensus obtenu à l'arbre de référence pour connaître la distance de Robinson et Foulds (RF) normalisée entre eux. Pour chaque fragment d'un ASM, nous conserverons uniquement les données relatives à des fragments correspondant à la distance RF normalisée la plus petite (i.e., celle qui représente la plus grande similitude entre les deux arbres). Dans le cas où plusieurs fragments correspondront à la même valeur de la distance RF normalisée, l'estimation se poursuivra sur l'arbre consensus ayant le score de bootstrap le plus élevé (i.e., meilleur support de l'arbre). Pour connaître la performance de notre algorithme, nous utiliserons un jeu de données de 52 espèces appartenant au groupe des Carnivores se localisant en Amérique du Nord. Nous récupérons aussi 21 protéines issues de la base de données GenBank. La construction des arbres de référence se fera à partir de données climatiques de l'habitat de ces espèces (i.e., température, précipitation et altitude). Notre algorithme permettra de trouver des sous-séquences des gènes donnant une similarité topologique accrue entre l'arbre de référence et l'arbre phylogénétique obtenu à partir des séquences. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : arbre phylogénétique, phylogéographie, distance de Robinson et Foulds, bootstrap, alignement de séquences multiples, paquet PHYLIP, GenBank.

L’arbre est un objet de droit particulier en raison de l’importance qu’il revêt à la fois pour l’environnement, l’économie et la qualité de vie. Il se trouve ainsi au carrefour de divers droits : droit de l’environnement, forestier, rural, de l’urbanisme, civil, fiscal, européen et international… Il est dès lors appréhendé de façon différente selon son lieu de situation mais également de la qualité de son propriétaire (personne privée ou personne publique). Alors qu’il est reconnu comme appartenant au patrimoine commun de la nation, les possibilités de protection qu’offre le droit applicable en France manque globalement d’efficacité et de réalisme. Pour palier cette situation, il est envisagé de doter la reconnaissance de l’appartenance de l’arbre au patrimoine commun de la nation de conséquences juridiques contraignantes et par là même de le doter d’un statut qui transcende le droit de propriété et les différentes branches du droit. / The tree is a special legal object because of its importance to the environment, the economy and the quality of life. It is therefore at the crossroads of various rights : environmental, forestry, rural, town planning, civil, tax, european and international laws. Thus, it is apprehended according to its place of situation but also the quality of its owner (private person or public person).While it is recognized as belonging to the common heritage of the nation, the possibilities of protection offered by the rights which are applicable in France generally lack efficiency and realism. To overcome this situation, it is envisaged to link the belonging of the tree to the common heritage of the Nation with binding legal consequences and thus confer on it a status that transcends property rights and the different areas of law.

Nous etudions certains processus stochastiques de coalescence ou de fragmentation a l'aide de codages par des arbres aleatoires ou des processus de Levy. Dans un premier temps, nous decrivons le semigroupe d'une classe de fragmentations "ordonnees" associees a des excursions de processus de Levy sans sauts positifs, et reliees au processus de coalescence stochastique additif. Nous demontrons des resultats negatifs sur le semigroupe de certaines fragmentations dites auto-similaires, introduites par Bertoin. Puis, nous etudions deux processus de fragmentation auto-similaires "duaux" obtenus a partir de l'arbre continu stable de Duquesne et Le Gall. Nous obtenons une caracterisation complete de leurs lois. Nous codons egalement la genealogie de toute fragmentation auto-similaire d'indice negatif dans un arbre continu. Enfin, nous etudions les arbres continus inhomogenes d'Aldous, Camarri et Pitman, obtenus comme limite continue des p-arbres discrets. Nous donnons l'expression de leurs processus de hauteur et de largeur a l'aide de ponts a accroissements echangeables. Nous obtenons egalement des resultats asymptotiques, formules en termes d'un pont brownien reflechi, sur le modele des p-applications a l'aide de leurs liens avec les p-arbres.