The decline of Moore's law has catalyzed a significant effort to identify beyond-CMOS devices and architectures for the coming decades. A multitude of classical and quantum systems have been proposed to address this challenge, and spintronics has emerged as a promising approach for these post-Moore systems. Many of these architectures are tailored specifically for applications in combinatorial optimization and machine learning. Here we propose the use of spintronics for such applications by exploring two distinct but related computing paradigms. First, the use of spin-currents to manipulate and control quantum information is investigated with demonstrated high-fidelity gate operation. This control is accomplished through repeated entanglement and measurement of a stationary qubit with a flying-spin through spin-torque like effects. Secondly, by transitioning from single-spin quantum bits to larger spin ensembles, we then explore the use of stochastic nanomagnets to realize a probabilistic system that is intrinsically governed by Boltzmann statistics. The nanomagnets explore the search space at rapid speeds and can be used in a wide-range of applications including optimization and quantum emulation by encoding the solution to a given problem as the ground state of the equivalent Boltzmann machine. These applications are demonstrated through hardware emulation using an all-digital autonomous probabilistic circuit.

The Aldous order is an ordering of representations of the symmetric group motivated by the Aldous Conjecture, a conjecture about random processes proved in 2009. In general, the Aldous order is very difficult to compute, and the proper relations have yet to be determined even for small cases. However, by restricting the problem down to Young-Jucys-Murphy elements, the problem becomes explicitly combinatorial. This approach has led to many novel insights, whose proofs are simple and elegant. However, there remain many open questions related to the Aldous Order, both in general and for the Young-Jucys-Murphy elements.

The study of networks has seen a tremendous breed of researches due to the explosive spectrum of practical problems that involve networks as the access point. Those problems widely range from detecting functionally correlated proteins in biology to finding people to give discounts and gain maximum popularity of a product in economics. Thus, understanding and further being able to manipulate/control the development and evolution of the networks become critical tasks for network scientists. Despite the vast research effort putting towards these studies, the present state-of-the-arts largely either lack of high quality solutions or require excessive amount of time in real-world `Big Data' requirement. This research aims at affirmatively boosting the modern algorithmic efficiency to approach practical requirements. That is developing a ground-breaking class of algorithms that provide simultaneously both provably good solution qualities and low time and space complexities. Specifically, I target the important yet challenging problems in the three main areas: Information Diffusion: Analyzing and maximizing the influence in networks and extending results for different variations of the problems. Community Detection: Finding communities from multiple sources of information. Security and Privacy: Assessing organization vulnerability under targeted-cyber attacks via social networks.

Depuis la fin du XXème siècle, la chimie combinatoire dynamique permet de synthétiser sous contrôle thermodynamique des récepteurs macrocycliques pour des molécules invités cibles. Ainsi, de nombreux hôtes supramoléculaires capables d’effectuer de la reconnaissance de molécules d’intérêt biologique dans l’eau ont été reportés dans la littérature. Nous avons décrit une nouvelle famille de récepteurs macrocycliques hydrosolubles appelés dyn[n]arènes polycarboxylates. Leur propriété de reconnaissance moléculaire vis-à-vis des polyamines, des métaux et des acides aminés ont permis d’envisager des applications biologiques. D’un point de vue fondamental, le rôle des divers paramètres, dont le solvant, a été étudié pour identifier les forces motrices responsables des associations. Des expériences in cellulo ont permis de démontrer un effet cytostatique anti-prolifératif transitoire du dyn[4]arène sur les cellules cancéreuses HeLa. Dans le but de moduler leurs propriétés de reconnaissance moléculaire, des réactions d’extrusion de soufre ont été envisagées pour synthétiser des dérivés plus robustes des dyn[n]arènes. Enfin, une famille d’objets macrocycliques apparentée a été envisagée basée sur le motif imino-1,5-dithiocines. Des études synthétiques et physico-chimiques pour l’élaboration de ces nouveaux cavitands laissent entrevoir de possibles applications biologiques similaires à celle de leurs analogues, les bases de Tröger / Since the end of the 20th century, dynamic combinatorial chemistry under thermodynamic control has enabled the synthesis of macrocyclic receptors towards targeted guest. So, many supramolecular hosts have been reported to be efficent in the molecular recognition of biologically relevant molecules in water. We describe a new family of hydrosoluble macrocycles called polycarboxylated dyn[n]renes. Their molecular recognition properties with polyamines, amino acids and metals allow biological studies. From the fundamental view, the role of each parameters, including the solvent, has been deeply studied to identify the strength of the association. In cellulo experiments have shown an antiproliferative and cytostatic effect of the dyn[4]arene on HeLa cancer cells for several hours. In order to modulate their molecular recognition properties, sulfur extrusion process has been carried out to synthesize more robust derivatives of dynarenes. Finally, a new family of similar macrocycles has been studied, based on imino-1,5-dithiocines. Syntheses and physico-chemical studies for the design of futurs cavitands pave the way for similar biological applications as described for Tröger’s bases

Depuis les années 1990, la chimie combinatoire dynamique permet la découverte et la préparation de nouveaux récepteurs synthétiques à partir de briques moléculaires simples sous contrôle thermodynamique. Dans ce contexte, nous avons récemment décrit une nouvelle famille de para-cyclophanes dynamiques: les dyn[n]arènes. Ces macrocycles, composés de briques moléculaires 1,4-bisthiophénoliques fonctionnalisées, ont pu être obtenus à l'échelle du gramme à partir d'une procédure simple ne mettant pas en jeu de purification par chromatographie. Cette accessibilité synthétique a rendu possible une étude structurale permettant la rationalisation des forces motrices mises en jeu lors des processus d'auto-assemblage, mais aussi de leurs propriétés de reconnaissance moléculaire vis-à-vis de molécules ioniques. A partir de données expérimentales et de calculs réalisés en chimie théorique, les phénomènes physiques responsables de la sélectivité et de l'affinité remarquables observées entre l'un des membres de cette famille, un dyn[4]arène poly anionique, et une série d'a,?-alkyle-diamines ont été étudiés. Finalement, au cours de cette étude, nous avons redécouvert une voie de synthèse simple menant à une famille de molécules encore peu étudiée : les dithiocines. La fonctionnalisation de ces objets a été explorée dans le but d'obtenir une plateforme multifonctionnelle pour des applications biologiques / Since the 1990s, dynamic combinatorial chemistry has allowed the discovery and preparation of new synthetic receptors from simple building blocks under thermodynamic control. In this context, we have recently described a new family of dynamic para cyclophanes, the so-called dyn[n]arenes. These macrocycles, made from functionalized 1,4-bisthiophenolic building blocks, could be obtained on a gram scale from a simple purification procedure, and without any chromatography. Their synthetic accessibility allows us to study the driving forces behind their self-assembly, as well as their molecular recognition properties towards ionic guest molecules. Experimental and computational experiments were also conducted to reveal the subtle physical phenomena that are responsible for the remarkable selectivity and affinity observed between a poly-anionic dyn[4]arene and a series of a,?-alkyl-diamines. During these previous studies, we rediscovered a simple synthetic route towards a family of molecules that is unexploited so far: the dithiocins. The functionalization of these molecular objects has been explored in order to generate versatile platforms for biological applications

[pt] Desde a sua origem, as abordagens a problemas de Otimização Combinatória polarizam-se entre métodos exatos e heurísticos. Recentemente, porém, estratégias que combinam ambos os métodos têm sido propostas para os mais variados problemas, apresentando resultados promissores. Nesse contexto, destacam-se os conceitos de vizinhaças de bola e elipsoidal, que realizam buscas em relação a uma ou mais soluções de referência. Este trabalho estuda a aplicação de tais vizinhanças para o Problema de Roteamento de Veículos com Restrição de Capacidade (CVRP), sobre o algoritmo de Branch-and-Cut-and-Price Robusto. Experimentos foram realizados e seus resultados analisados. / [en] Since its inception, approaches to Combinatorial Optimization were polarized between exact and heuristic methods. Recently, however, strategies that combine both methods have been proposed for various problems, showing promising results. In this context, the concepts of ball and ellipsoidal neighborhood appear, which perform a search regarding one or more reference solutions. This work studies the application of such neighborhoods for the Capacitated Vehicle Routing Problem (CVRP), using the Robust Branchand- Cut-and-Price algorithm. Experiments were made and its results were analyzed.

<p>Games on graphs have become an indispensable tool in modern computer science. They provide powerful and expressive models for numerous phenomena and are extensively used in computer- aided verification, automata theory, logic, complexity theory, computational biology, etc.</p><p>The infinite games on finite graphs we study in this thesis have their primary applications in verification, but are also of fundamental importance from the complexity-theoretic point of view. They include parity, mean payoff, and simple stochastic games.</p><p>We focus on solving graph games by using iterative strategy improvement and methods from linear programming and combinatorial optimization. To this end we consider old strategy evaluation functions, construct new ones, and show how all of them, due to their structural similarities, fit into a unifying combinatorial framework. This allows us to employ randomized optimization methods from combinatorial linear programming to solve the games in expected subexponential time.</p><p>We introduce and study the concept of a controlled optimization problem, capturing the essential features of many graph games, and provide sufficent conditions for solvability of such problems in expected subexponential time.</p><p>The discrete strategy evaluation function for mean payoff games we derive from the new controlled longest-shortest path problem, leads to improvement algorithms that are considerably more efficient than the previously known ones, and also improves the efficiency of algorithms for parity games.</p><p>We also define the controlled linear programming problem, and show how the games are translated into this setting. Subclasses of the problem, more general than the games considered, are shown to belong to NP intersection coNP, or even to be solvable by subexponential algorithms.</p><p>Finally, we take the first steps in investigating the fixed-parameter complexity of parity, Rabin, Streett, and Muller games.</p>

An important part of gene regulation is mediated by specific proteins, called transcription factors, which influence the transcription of a particular gene by binding to specific sites on DNA sequences, called transcription factor binding sites (TFBS) or, simply, motifs. Such binding sites are relatively short segments of DNA, normally 5 to 25 nucleotides long, over- represented in a set of co-regulated DNA sequences. There are two different problems in this setup: motif representation, accounting for the model that describes the TFBS's; and motif discovery, focusing in unravelling TFBS's from a set of co-regulated DNA sequences. This thesis proposes a discriminative scoring criterion that culminates in a discriminative mixture of Bayesian networks to distinguish TFBS's from the background DNA. This new probabilistic model supports further evidence in non-additivity among binding site positions, providing a superior discriminative power in TFBS's detection. On the other hand, extra knowledge carefully selected from the literature was incorporated in TFBS discovery in order to capture a variety of characteristics of the TFBS's patterns. This extra knowledge was combined during the process of motif discovery leading to results that are considerably more accurate than those achieved by methods that rely in the DNA sequence alone.

The bacterium Escherichia coli (E. coli) is in many situations an ideal host for production of recombinant proteins, since it generally provides a rapid and economical means to achieve sufficiently high product quantities. However, there are several factors that may limit this host’s ability to produce large amounts of heterologous proteins in a soluble and native form. For many applications a high purity of the recombinant protein is demanded, which implies a purification strategy where the product efficiently can be isolated from the complex milieu of host cell contaminants. In this thesis, different strategies based on both rational and combinatorial genetic engineering principles have been investigated, aiming at improving and facilitating recombinant E. coli protein production and purification. One objective was to improve the PEG/salt aqueous two-phase system (ATPS) purification process of the lipase cutinase, by increasing the selectivity of the protein for the system top-phase. Peptide tags, with varying properties, were designed and genetically fused to the C-terminal end of ZZ-cutinase. Greatly increased partitioning values were observed for purified protein variants fused to tryptophan containing peptide tags, particularly a (WP)4 peptide. The partitioning properties of the ZZ-cutinase-(WP)4 protein were also retained when added to the ATPS directly from an E. coli total cell disintegrate, emphasizing the applicability of this genetic engineering strategy for primary protein purification in ATPSs. Further on, a combinatorial library approach using phage display technology was investigated as a tool for identification of peptide tags capable of improving partitioning properties of ZZ-cutinase in an ATPS. Repeated ATPS-based partitioning-selection cycles of a large phagemid (pVIII) peptide library, resulted in isolation of phage particles preferentially decorated with peptides rich in tyrosine and proline residues. Both a peptide corresponding to a phage library derived peptide sequence as well as peptides designed based on information of amino acid appearance frequencies in later selection rounds, were shown to improve partitioning several-fold when genetically fused to the C-terminal end of ZZ-cutinase. From the two- to four–fold increased production yields observed for these fusion proteins compared to ZZ-cutinase-(WP)4, it was concluded that the selection system used allowed for selection of desired peptide properties related to both partitioning and E. coli protein production parameters. Bacterial protein production is affected by several different mRNA and protein sequence-related features. Attempts to address single parameters in this respect are difficult due to the inter-dependence of many features, for example between codon optimization and mRNA secondary structure effects. Two combinatorial expression vector libraries (ExLib1 and ExLib2) were constructed using a randomization strategy that potentially could lead to variations in many of these sequence-related features and which would allow a pragmatic search of vector variants showing positive net effects on the level of soluble protein production. ExLib1 was constructed to encode all possible synonymous codons of an eight amino acid N-terminal extension of protein Z, fused to the N-terminal of an enhanced green fluorescent reporter protein (EGFP). In ExLib2, the same eight positions were randomized using an (NNG/T) degeneracy code, which could lead to various effects on both the nucleotide and protein level, through the introduction of nucleotide sequences functional as e.g. alternative ribosome binding or translation initiation sites or as translated codons for an Nterminal extension of the target protein by a peptide sequence. Flow cytometric analyses and sorting of library cell cultures resulted in isolation of clones displaying several-fold increases in whole cell fluorescence compared to a reference clone. SDS-PAGE and western blot analyses verified that this was a result of increases (up to 24-fold) in soluble intracellular ZEGFP product protein content. Both position specific codon bias effects and the appearance of new ribosomal binding sites in the library sequences were concluded to have influenced the protein production. To explore the possibility of applying the same combinatorial library strategy for improving soluble intracellular production of heterologous proteins proven difficult to express in E. coli, three proteins with either bacterial (a transcriptional regulator (DntR)) or human (progesterone receptor ligand binding domain (PRLBD) and 11-β Hydroxysteroid dehydrogenase type I (11-β)) origin, were cloned into the ExLib2 library. Flow cytometric sorting of libraries resulted in isolation of DntR library clones showing increased soluble protein production levels and PR-LBD library clones with up to ten-fold increases in whole cell fluorescence, although the product under these conditions co-separated with the insoluble cell material. / QC 20100623

No description available.