In this work, we have performed comparative evolutionary analysis, functional genomics analysis, and machine learning analysis to identify the molecular factors that discriminate between multipartite and unipartite bacteria, with the goal to decipher taxon-specific factors and those that are prevalent across the taxa underlying the these traits. We assessed the roles of evolutionary mechanisms, namely, horizontal gene transfer and gene gain, in driving the divergence of bacteria with single and multiple chromosomes. In addition, we performed functional genomic analysis to garner support for our findings from comparative evolutionary analysis. We found genes such as those encoding conserved hypothetical protein DR_A0179 and hypothetical protein DR_A0109 in Deinococcus radiodurans R1, and Putative phage phi-C31 gp36 major capsid-like protein and hypothetical protein RSP_3729 in Rhodobacter sphaeroides 2.4.1, which are located on accessory chromosomes in both bacteria and were not found in the inferred ancestral sequences, and on the primary chromosomes, as well as were not found in their closest relatives with single chromosome within the same clade. These genes emphasize the important potential roles of the secondary chromosomes in helping multipartite bacteria to adapt to specialized environments or conditions. In addition, we applied machine learning algorithms to predict multipartite genomes based on gene content of multipartite genomes and their unipartite relatives, and leveraged this to identify genes that are deemed important by machine learning in discriminating between multipartite and unipartite genomes. This approach led to the identification of marker genes that could be used in discriminating between bacteria with multipartite genomes and. bacteria with single chromosome genomes Furthermore, we examined modules in gene co-expression networks of multipartite Rhodobacter sphaeroides 2.4.1 and its close unipartite relative Rhodobacter capsulatus SB 1003 that were enriched in genes differentially expressing under stressful conditions representing different experiments. This led to the identification of 6 modules in the Rhodobacter sphaeroides 2.4.1 network and 3 modules in the Rhodobacter capsulatus SB 1003 network, which were significantly enriched (2-fold or more) in differentially expressing genes, revealing the vital roles of these gene modules representing different pathways or networks of pathways (known or unknown) in enabling the bacteria to adapt to stressful conditions. Overall, our study highlights genetic factors that may be driving the evolution of multipartite bacterial genomes; future studies may focus on unraveling the specific roles of these genes in the adaptation and maintenance of multipartite genomes.

yes / An expansion of row Markov matrices in terms of matrices related to permutations with repetitions, is introduced. It generalises the Birkhoff-von Neumann expansion of doubly stochastic matrices in terms of permutation matrices (without repetitions). An interpretation of the formalism in terms of sequences of integers that open random safes described by the Markov matrices, is presented. Various quantities that describe probabilities and correlations in this context, are discussed. The Gini index is used to quantify the sparsity (certainty) of various probability vectors. The formalism is used in the context of multipartite quantum systems with finite dimensional Hilbert space, which can be viewed as quantum permutations with repetitions or as quantum safes. The scalar product of row Markov matrices, the various Gini indices, etc, are novel probabilistic quantities that describe the statistics of multipartite quantum systems. Local and global Fourier transforms are used to de ne locally dual and also globally dual statistical quantities. The latter depend on off-diagonal elements that entangle (in general) the various components of the system. Examples which demonstrate these ideas are also presented.

Le ranking multipartite est un problème d'apprentissage statistique qui consiste à ordonner les observations qui appartiennent à un espace de grande dimension dans le même ordre que les labels, de sorte que les observations avec le label le plus élevé apparaissent en haut de la liste. Cette thèse vise à comprendre la nature probabiliste du problème de ranking multipartite afin d'obtenir des garanties théoriques pour les algorithmes de ranking. Dans ce cadre, la sortie d'un algorithme de ranking prend la forme d'une fonction de scoring, une fonction qui envoie l'espace des observations sur la droite réelle et l'ordre finale est construit en utilisant l'ordre induit par la droite réelle. Les contributions de ce manuscrit sont les suivantes : d'abord, nous nous concentrons sur la caractérisation des solutions optimales de ranking multipartite. Le deuxième thème de recherche est la conception d'algorithmes pour produire des fonctions de scoring. Nous proposons deux méthodes, la première utilisant une procédure d'agrégation, la deuxième un schema d'approximation. Enfin, nous revenons au problème de ranking binaire afin d'établir des vitesse minimax adaptives de convergences. / Multipartite ranking is a statistical learning problem that consists in ordering observations that belong to a high dimensional feature space in the same order as the labels, so that the observations with the highest label appear at the top of the list. This work aims to understand the probabilistic nature of the multipartite ranking problem in order to obtain theoretical guarantees for ranking algorithms. In this context, the output of a ranking algorithm takes the form of a scoring function, a function that maps the space of the observation to the real line which order is induced using the values on the real line. The contributions of this manuscript are the following : First, we focus on the characterization of optimal solutions to multipartite ranking. The second research theme is the design of algorithms to produce scoring functions. We offer two methods, the first using an aggregation procedure, the second an approximation scheme. Finally, we return to the binary ranking problem to establish adaptive minimax rate of convergence.

Le sujet de cette thèse est une étude de tests du caractère quantique des systèmes de dimension supérieure à deux dans des conditions réalistes. La non-localité est une des propriétés quantiques utile pour des protocoles du domaine des communications quantiques. L’étude réalisée sur les effets de la décohérence (modèles de conditions réalistes) permet de rendre compte des moyens à mettre en oeuvre afin d’optimiser la conservation de la non-localité en pratique. La contextualité est une autre propriété quantique fondamentale avec un potentiel dans le domaine de traitement d’information quantique. Un test de contextualité a été développé pour toutes les dimensions de systèmes quantiques supérieures à deux. Une expérience prenant en compte les enjeux expérimentaux des tests de contextualité est aussi proposée. / The subject of this thesis is a study of tests of the quantum features of systems of dimension greater than two under realistic conditions. Non-locality is one of the quantum properties used in protocols in the field of quantum communications. The study on the effects of the decoherence (models ofrealistic conditions) address the issue of the conservation of non-locality in practice. Contextuality is another fundamental quantum property with a potential power in quantum information processing. A contextuality test has been developed for all dimensions of quantum systems greater than two. An experiment that considers the experimental issues of contextuality tests is also proposed.

We develop a datapath generator for various arithmetic function units required in the design of the geometry subsystem in the 3D graphics application. The operations considered in the geometry subsystem include coordinate transformations and lighting. The generator will automatically generate efficient designs of function units based on the requirements of area, speed and accuracy. The major function units designed in this thesis are divided into two parts: multiplier-related function units and single-value arithmetic function units. In the generation of multipliers, we consider the design of truncated multipliers to reduce the area cost. In the design of other function evaluators, we consider two table-based methods: piecewise interpolation table-based method and the multipartite table-based method.

Entanglement is one of the fundamental features of quantum information science. Though bipartite entanglement has been analyzed thoroughly in theory and shown to be an important resource in quantum computation and communication protocols, the theory of entanglement shared between more than two parties, which is called multipartite entanglement, is still not complete. Specifically, the classification of multipartite entanglement and the transformation property between different multipartite states by local operators and classical communications (LOCC) are two fundamental questions in the theory of multipartite entanglement. In this thesis, we present results related to the LOCC transformation between multipartite entangled states. Firstly, we investigate the bounds on the LOCC transformation probability between multipartite states, especially the GHZ class states. By analyzing the involvement of 3-tangle and other entanglement measures under weak two-outcome measurement, we derive explicit upper and lower bound on the transformation probability between GHZ class states. After that, we also analyze the transformation between N-party W type states, which is a special class of multipartite entangled states that has an explicit unique expression and a set of analytical entanglement monotones. We present a necessary and sufficient condition for a known upper bound of transformation probability between two N-party W type states to be achieved. We also further investigate a novel entanglement transformation protocol, the random distillation, which transforms multipartite entanglement into bipartite entanglement ii shared by a non-deterministic pair of parties. We find upper bounds for the random distillation protocol for general N-party W type states and find the condition for the upper bounds to be achieved. What is surprising is that the upper bounds correspond to entanglement monotones that can be increased by Separable Operators (SEP), which gives the first set of analytical entanglement monotones that can be increased by SEP. Finally, we investigate the idea of a new class of multipartite entangled states, the Absolutely Maximal Entangled (AME) states, which is characterized by the fact that any bipartition of the states would give a maximal entangled state between the two sets. The relationship between AME states and Quantum secret sharing (QSS) protocols is exhibited and the application of AME states in novel quantum communication protocols is also explored.

Entanglement is one of the fundamental features of quantum information science. Though bipartite entanglement has been analyzed thoroughly in theory and shown to be an important resource in quantum computation and communication protocols, the theory of entanglement shared between more than two parties, which is called multipartite entanglement, is still not complete. Specifically, the classification of multipartite entanglement and the transformation property between different multipartite states by local operators and classical communications (LOCC) are two fundamental questions in the theory of multipartite entanglement. In this thesis, we present results related to the LOCC transformation between multipartite entangled states. Firstly, we investigate the bounds on the LOCC transformation probability between multipartite states, especially the GHZ class states. By analyzing the involvement of 3-tangle and other entanglement measures under weak two-outcome measurement, we derive explicit upper and lower bound on the transformation probability between GHZ class states. After that, we also analyze the transformation between N-party W type states, which is a special class of multipartite entangled states that has an explicit unique expression and a set of analytical entanglement monotones. We present a necessary and sufficient condition for a known upper bound of transformation probability between two N-party W type states to be achieved. We also further investigate a novel entanglement transformation protocol, the random distillation, which transforms multipartite entanglement into bipartite entanglement ii shared by a non-deterministic pair of parties. We find upper bounds for the random distillation protocol for general N-party W type states and find the condition for the upper bounds to be achieved. What is surprising is that the upper bounds correspond to entanglement monotones that can be increased by Separable Operators (SEP), which gives the first set of analytical entanglement monotones that can be increased by SEP. Finally, we investigate the idea of a new class of multipartite entangled states, the Absolutely Maximal Entangled (AME) states, which is characterized by the fact that any bipartition of the states would give a maximal entangled state between the two sets. The relationship between AME states and Quantum secret sharing (QSS) protocols is exhibited and the application of AME states in novel quantum communication protocols is also explored.

A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number γt(G). The graph G is 3t-critical if γt(G)=3 and γt(G+e)=2 for every edge e in the complement of G. We show that no bipartite graph is 3t-critical. The tripartite 3 t-critical graphs are characterized. For every k<3, we prove that there are only a finite number of 3t-critical k-partite graphs. We show that the 5-cycle is the only 3t-critical K3-free graph and that there are only a finite number of 3t-critical K4-free graphs.

Yes / A multipartite system comprised of n subsystems, each of which is described with ‘local variables’ in Z(d) and with a d-dimensional Hilbert space H(d), is considered. Local Fourier transforms in each subsystem are defined and related phase space methods are discussed (displacement operators, Wigner and Weyl functions, etc). A holistic view of the same system might be more appropriate in the case of strong interactions, which uses ‘global variables’ in Z(dn) and a dn-dimensional Hilbert space H(dn). A global Fourier transform is then defined and related phase space methods are discussed. The local formalism is compared and contrasted with the global formalism. Depending on the values of d, n the local Fourier transform is unitarily inequivalent or unitarily equivalent to the global Fourier transform. Time evolution of the system in terms of both local and global variables, is discussed. The formalism can be useful in the general area of Fast Fourier transforms.

Large graph-based datasets are common to many applications because of the additional structure provided to data by graphs. Patterns extracted from graphs must adhere to these structural properties, making them a more complex class of patterns to identify. The role of graph mining is to efficiently extract these patterns and quantify their significance. In this thesis, we focus on two application domains and demonstrate the design of graph mining algorithms in these domains. First, we investigate the use of graph grammar mining as a tool for diagnosing potential memory leaks from Java heap dumps. Memory leaks occur when memory that is no longer in use fails to be reclaimed, resulting in significant slowdowns, exhaustion of available storage, and eventually application crashes. Analyzing the heap dump of a program is a common strategy used in memory leak diagnosis, but our work is the first to employ a graph mining approach to the problem. Memory leaks accumulate in the heap as classes of subgraphs and the allocation paths from which they emanate can be explored to contextualize the leak source. We show that it suffices to mine the dominator tree of the heap dump, which is significantly smaller than the underlying graph. We demonstrate several synthetic as well as real-world examples of heap dumps for which our approach provides more insight into the problem than state-of-the-art tools such as Eclipse's MAT. Second, we study the problem of multipartite graph clustering as an approach to database summarization on an integrated biological database. Construction of such databases has become a common theme in biological research, where heterogeneous data is consolidated into a single, centralized repository that provides a structured forum for data analysis. We present an efficient approximation algorithm for identifying clusters that form multipartite cliques spanning multiple database tables. We show that our algorithm computes a lossless compression of the database by summarizing it into a reduced set of biologically meaningful clusters. Our algorithm is applied to data from C. elegans, but we note its applicability to general relational databases. / Master of Science