La phylogénie permet de reconstituer l'histoire évolutive de séquences ainsi que des espèces qui les portent. Les récents progrès des méthodes de séquençage ont permis une inflation du nombre de séquences disponibles et donc du nombre d'arbres de gènes qu'il est possible de construire. La question qui se pose est alors d'optimiser la recherche d'informations dans ces arbres. Cette recherche doit être à la fois exhaustive et efficace. Pour ce faire, mon travail de thèse a consisté en l'écriture puis en l'utilisation d'un ensemble de programmes capables de parcourir et d'annoter les arbres phylogénétiques. Cet ensemble de programmes porte le nom de TPMS (Tree Pattern Matching Suite). Le premier de ces programmes (tpms_query) permet d'effectuer l'interrogation de collections à l'aide d'un formalisme dédie. Les possibilités qu'il offre sont : La détection de transferts horizontaux : Si un arbre de gènes présente une espèce branchée dans un arbre au milieu d'un groupe monophylétique d'espèces avec lesquelles elle n'est pas apparentée, on peut supposer qu'il s'agit d'un transfert horizontal, si ces organismes sont des procaryotes ou des eucaryotes unicellulaires. La détection d'orthologie : Si une partie d'un arbre de gènes correspond exactement à l'arbre des espèces, on peut alors supposer que ces gènes sont un ensemble de gènes d'orthologues. La validation de phylogénies connues : Quand l'arbre des espèces donne lieu à des débats, il peut est possible d'interroger une large collection d'arbres de gènes pour voir combien de familles de gènes correspondent à chaque hypothèse. Un autre programme, tpms_computations, permet d'effectuer des opérations en parallèle sur tous les arbres, et propose notamment l'enracinement automatique des arbres via différents critères, ainsi que l'extraction de sous arbres d'orthologues (séquence unique par espèce). Il propose aussi une méthode de détection automatique d'incongruences. La thèse présente le contexte, les différents algorithmes à la base de ces programmes, ainsi que plusieurs utilisations qui en ont été faites / Phylogeny allows to reconstruct evolutionnary history of sequences and species that carry them. Recent progress in sequencing methods produced a growing number of available sequences, and so of number of gene trees that one can build. One of the consecutive issues is to optimise the extraction of information from the trees. Such an extraction should be complete and efficient. To address this, my thesis consisted in writing and then using a suite of programs which aim to browse and annotate phylogenic trees. This program suite is named TPMS (Tree Pattern Matching Suite). It browses and annotates trees with several algorithms. The first of them, tpms_query consists in querying collections using a dedicated formalism. This allows to: Detect horizontal transfers If, in a gene tree, a species is nested in a monophyletic group of unrelated species, one can infer this is a horizontal transfer, if this organisms are prokaryotic (also concerning some unicellular eukaryotes). Orthology detection: if a part of a gene tree exactly matches to the species tree, one can suppose these genes are set of orthologues. Validating known phylogenies: when controversy exists concerning the species tree, it is possible to query a lange collection of gene trees to perform a count of families matching to each hypothesis. Another program allows to perform parallel operations on all the trees, such as automating rooting of trees via different criterions. It also allows an automatic detection of incongruencies. The thesis introduces the context, different algorithms which the programs are based on, and several using performed with it

No description available.

No description available.

In this thesis, we investigate some problems in graph theory, namelythe graph coloring problem, the graph packing problem and tree pattern matchingfor XML query processing. The common point between these problems is that theyuse labeled graphs.In the first part, we study a new coloring parameter of graphs called the gapvertex-distinguishing edge coloring. It consists in an edge-coloring of a graph G whichinduces a vertex distinguishing labeling of G such that the label of each vertex isgiven by the difference between the highest and the lowest colors of its adjacentedges. The minimum number of colors required for a gap vertex-distinguishing edgecoloring of G is called the gap chromatic number of G and is denoted by gap(G).We will compute this parameter for a large set of graphs G of order n and we evenprove that gap(G) 2 fn E 1; n; n + 1g.In the second part, we focus on graph packing problems, which is an area ofgraph theory that has grown significantly over the past several years. However, themajority of existing works focuses on unlabeled graphs. In this thesis, we introducefor the first time the packing problem for a vertex labeled graph. Roughly speaking,it consists of graph packing which preserves the labels of the vertices. We studythe corresponding optimization parameter on several classes of graphs, as well asfinding general bounds and characterizations.The last part deal with the query processing of a core subset of XML query languages:XML twig queries. An XML twig query, represented as a small query tree,is essentially a complex selection on the structure of an XML document. Matching atwig query means finding all the occurrences of the query tree embedded in the XMLdata tree. Many holistic twig join algorithms have been proposed to match XMLtwig pattern. Most of these algorithms find twig pattern matching in two steps. Inthe first one, a query tree is decomposed into smaller pieces, and solutions againstthese pieces are found. In the second step, all of these partial solutions are joinedtogether to generate the final solutions. In this part, we propose a novel holistictwig join algorithm, called TwigStack++, which features two main improvementsin the decomposition and matching phase. The proposed solutions are shown to beefficient and scalable, and should be helpful for the future research on efficient queryprocessing in a large XML database.

La phylogénie permet de reconstituer l'histoire évolutive de séquences ainsi que des espèces qui les portent. Les récents progrès des méthodes de séquençage ont permis une inflation du nombre de séquences disponibles et donc du nombre d'arbres de gènes qu'il est possible de construire. La question qui se pose est alors d'optimiser la recherche d'informations dans ces arbres. Cette recherche doit être à la fois exhaustive et efficace. Pour ce faire, mon travail de thèse a consisté en l'écriture puis en l'utilisation d'un ensemble de programmes capables de parcourir et d'annoter les arbres phylogénétiques. Cet ensemble de programmes porte le nom de TPMS (Tree Pattern Matching Suite). Le premier de ces programmes (tpms_query) permet d'effectuer l'interrogation de collections à l'aide d'un formalisme dédie. Les possibilités qu'il offre sont : La détection de transferts horizontaux : Si un arbre de gènes présente une espèce branchée dans un arbre au milieu d'un groupe monophylétique d'espèces avec lesquelles elle n'est pas apparentée, on peut supposer qu'il s'agit d'un transfert horizontal, si ces organismes sont des procaryotes ou des eucaryotes unicellulaires. La détection d'orthologie : Si une partie d'un arbre de gènes correspond exactement à l'arbre des espèces, on peut alors supposer que ces gènes sont un ensemble de gènes d'orthologues. La validation de phylogénies connues : Quand l'arbre des espèces donne lieu à des débats, il peut est possible d'interroger une large collection d'arbres de gènes pour voir combien de familles de gènes correspondent à chaque hypothèse. Un autre programme, tpms_computations, permet d'effectuer des opérations en parallèle sur tous les arbres, et propose notamment l'enracinement automatique des arbres via différents critères, ainsi que l'extraction de sous arbres d'orthologues (séquence unique par espèce). Il propose aussi une méthode de détection automatique d'incongruences. La thèse présente le contexte, les différents algorithmes à la base de ces programmes, ainsi que plusieurs utilisations qui en ont été faites

Cette thèse se situe dans le domaine de graphes et de leurs applications, Elleest constitué de trois grandes parties, la première est consacrée à l’étude d’unnouveau type de coloration sommets distinguantes, les arête-colorations sommetsdistinguantespar écarte. Il consiste de trouver une valuation des arêtes qui permettede distinguer les sommets de graphes telle que chaque sommet v du graphe est identifiéde façon unique par la différence entre la plus grande et la plus petite des valeursincidentes à v. Le plus entier pour lequel le graphe G admet une arête-colorationsommets-distinguantes par écarte est le nombre chromatique par écart de G, notégap(G). Nous avons étudié ce paramètre pour diverses familles de graphes. Uneconjecture intéressante, proposée dans cette partie, suggère que le nombre chromatiquepar écart de tout graphe connexe d’ordre n > 2 vaut n - 1, n ou n + 1.La deuxième partie du manuscrit concerne le problème du placement de graphes.Nous proposons un état de l’art des problèmes de placement de graphes, puis nousintroduisons la nouvelle notion de placement de graphes étiquetés. Il s’agit d’unplacement de graphes qui préserve les étiquettes des sommets. Ensuite, nous proposonsdes encadrements de ce nouveau paramètre pour plusieurs classes de graphes.La troisième partie de la thèse s’intéresse au problème d’appariement d’arbres dansle cadre de la recherche d’information dans des documents structurés de type XML.Les algorithmes holistique de jointure structurelle est l’une des premières méthodesproposées pour résoudre l’appariement exact des documents XML. Ces algorithmessont souvent divisés en deux grandes étapes. La première étape permet de décomposerl’arbre de la requête en un ensemble de petites composantes connexes. Ensuite,des solutions intermédiaires pour chaque composante de la requête sont trouvées, cesrésultats intermédiaires sont joints pour obtenir la solution finale. Nous proposonsdans cette partie un nouvel algorithme appelé TwigStack++ qui vise principalementà diminuer le coût de la jointure et le calcule inutile recherche. Notre algorithmeobtient de meilleurs résultats en comparaison avec deux autres méthodes de l’étatde l’art. / In this thesis, we investigate some problems in graph theory, namelythe graph coloring problem, the graph packing problem and tree pattern matchingfor XML query processing. The common point between these problems is that theyuse labeled graphs.In the first part, we study a new coloring parameter of graphs called the gapvertex-distinguishing edge coloring. It consists in an edge-coloring of a graph G whichinduces a vertex distinguishing labeling of G such that the label of each vertex isgiven by the difference between the highest and the lowest colors of its adjacentedges. The minimum number of colors required for a gap vertex-distinguishing edgecoloring of G is called the gap chromatic number of G and is denoted by gap(G).We will compute this parameter for a large set of graphs G of order n and we evenprove that gap(G) 2 fn E 1; n; n + 1g.In the second part, we focus on graph packing problems, which is an area ofgraph theory that has grown significantly over the past several years. However, themajority of existing works focuses on unlabeled graphs. In this thesis, we introducefor the first time the packing problem for a vertex labeled graph. Roughly speaking,it consists of graph packing which preserves the labels of the vertices. We studythe corresponding optimization parameter on several classes of graphs, as well asfinding general bounds and characterizations.The last part deal with the query processing of a core subset of XML query languages:XML twig queries. An XML twig query, represented as a small query tree,is essentially a complex selection on the structure of an XML document. Matching atwig query means finding all the occurrences of the query tree embedded in the XMLdata tree. Many holistic twig join algorithms have been proposed to match XMLtwig pattern. Most of these algorithms find twig pattern matching in two steps. Inthe first one, a query tree is decomposed into smaller pieces, and solutions againstthese pieces are found. In the second step, all of these partial solutions are joinedtogether to generate the final solutions. In this part, we propose a novel holistictwig join algorithm, called TwigStack++, which features two main improvementsin the decomposition and matching phase. The proposed solutions are shown to beefficient and scalable, and should be helpful for the future research on efficient queryprocessing in a large XML database.

Tato práce se zabývá problematikou popisu síťového provozu pomocí automaticky vytvořeného modelu komunikace. Hlavním zaměřením jsou komunikace v řídicích systémech , které využívají speciální protokoly, jako je například IEC 60870-5-104 . V této práci představujeme metodu charakteristiky síťového provozu z pohledu obsahu komunikace i chování v čase. Tato metoda k popisu využívá deterministické konečné automaty , prefixové stromy  a analýzu opakovatelnosti. Ve druhé části této diplomové práce se zaměřujeme na implementaci programu, který je schopný na základě takového modelu komunikace verifikovat síťový provoz v reálném čase.