A directed graph (digraph) G can primitively positively construct another digraph H if H is homomorphically equivalent to a first order interpretation of G that only uses primitive positive formulas. In this way, we define the poset of all finite digraphs ordered by primitive positive constructability. This poset, which is the object studied in this dissertation, is important for studying the complexity of constraint satisfaction problems and for studying clones ordered by minion homomorphisms. In this thesis I will introduce the poset and amoung other results I will present the three topmost levels of the poset and I will describe the subposet consisting of digraphs without sources or sinks.

Pseudomonas aeruginosa is a ubiquitous opportunistic pathogen that is a substantial threat, particularly in hospital settings, causing severe infections in immunocompromised patients that may lead to death. Pseudomonas aeruginosa harbors a multitude of virulence factors that enable this pathogen to establish both acute and chronic infections in humans. A key determinant of acute infections is a hollow molecular needle structure used for injecting toxins into a host cell, called the type three secretion system (T3SS). The secretion machinery itself is highly complex and, together with the specific secreted factors, requires expression of more than 30 genes. Due to the high energy cost of its synthesis to the organism this system is highly regulated to finely time gene expression to coincide with host contact. ExsA, a member of the AraC-type transcription factor family, is the main transcriptional activator of all the genes necessary for expression of the T3SS. Members of the AraC family are characterized by the presence of two helix-turn-helix (HTH) motifs, which bind to the promoter DNA and activate transcription. ExsA uses its HTH containing C-terminal domain (CTD) to regulate gene expression from 10 different promoters. The N-terminal domain (NTD) of ExsA mediates dimerization and regulation of ExsA-activity. While most AraC-type activators are regulated by a small molecule ligands, ExsA is regulated by another protein, ExsD. As part of a four-protein signaling cascade, ExsD interacts directly with ExsA to prevent transcription of T3SS-associated genes under non-inducing conditions prior to host cell contact. The entire regulatory cascade includes of two additional proteins, ExsC and ExsE. ExsA, ExsC, ExsD, and ExsE follow a partner-switching mechanism to link expression of the secretion system with host cell contact. Our laboratory is working to understand this unique signaling mechanism by determining the molecular basis for the regulation of this important virulence factor. Previous studies in the laboratory have solved the structures of ExsE, ExsC and ExsD, and shed light on how these proteins interact and compete for overlapping binding sites. However, it is still unclear as to how the ExsA and ExsD interact and thus how regulation is mediated at the molecular level. In the presented study, we sought to map the molecular interface between ExsA and ExsD. First, the crystal structure of ExsA-NTD is presented wherein the dimerization interface of the protein was identified. Two of the well-studied AraC-type proteins, AraC and ToxT crystal structures have been solved by others in the presence of their respective ligands. Residues that were involved in ligand binding in AraC and ToxT were aligned with the residues in ExsA and analyzed for interaction with ExsD. However, this canonical binding pocket appeared to be not involved in the interaction between ExsA and ExsD. Structure directed site-specific mutagenesis was carried out to construct many different variants of ExsD and ExsA. Thus constructed variants were purified and analyzed in a functional assay. Using this approach, we were able to identify regions on ExsD and ExsA that are crucial for the interaction and for the regulation of ExsA-dependent transcription. It turns out that backbone interactions between the amino-terminal residues of ExsD and the beta-barrel region of the ExsA-NTD are pivotal. This result explains how ExsA and ExsC compete for ExsD binding, since both target the same regions on ExsD. / PHD / Pseudomonas aeruginosa is an opportunistic pathogen that is notorious for causing severe infections in immunocompromised individuals. Acute Pseudomonas aeruginosa infections are characterized by immediate adverse effects. An initial acute infection may become chronic, leading to long-term morbidity and mortality in affected individuals. During the initial stages of infection P. aeruginosa uses the type three secretion system, a syringe-like structure, to puncture the host cell and inject potent toxins. The activation of the genes required for forming this structure is tightly controlled by an activator protein, ExsA. When P.aeruginosa is not invading a host, ExsA is inhibited by another protein called ExsD, to prevent the needless production of the secretion apparatus. The presented work explores the mechanism of how ExsD achieves this inhibition of ExsA. This information is of potential biomedical interest because a clear understanding of the molecular basis for the interaction could inform the development of a small-molecule mimic of ExsD to be used in therapy. In Chapter 2 we report the structure of the domain of ExsA that is known to bind ExsD. Also, in this chapter and more so in Chapter 3, we performed a detailed analysis of potential interacting regions and ultimately succeeded in identifying key interacting regions in both ExsA and ExsD.

Maitriser les coûts de fabrication des circuits intégrés tout en augmentant leur densité est d'une importance primordiale pour maintenir une certaine rentabilité dans l’industrie du semi-conducteur. Parmi les différents composants d’un circuit, nous nous intéressons aux connections verticales et métalliques, connues sous le nom de « vias ». Durant la fabrication, un processus de lithographie complexe est utilisé pour former une disposition de vias est formée sur une plaque de silicium, à l’aide d’un un masque optique. Pour des raisons de fabrication, une distance minimum entre les vias doit être respectée. Lorsque cette distance n’est pas respectée, nous parlons de « conflit ». Afin de supprimer ces conflits, l’industrie utilise une technique qui permet de décomposer une disposition de vias cible en plusieurs sous-ensembles, où les contraintes de distance minimum sont respectées : la formation des sous-ensembles individuels se fait en séquence sur la plaque de silicium en utilisant un masque optique par sous-ensemble. Cette technique est appelée Multiple Patterning (MP). Il y a de nombreuses façons de décomposer une disposition de vias et le but est d’assigner les vias à un nombre minimum de masques, car les masques sont coûteux. Minimiser le nombre de masques est équivalent à minimiser le nombre de couleurs dans un graphe disque unitaire. Ce problème est NP-difficile, mais un certain nombre de « bonnes » heuristiques existent. Une technique récente et prometteuse basée sur l’auto-assemblage et direction des molécules, aussi connue sous le nom Directed Self Assembly (DSA), permet de grouper les vias en conflits à condition de respecter certaines contraintes. L’objectif est de trouver la meilleure façon de grouper les vias afin de minimiser le nombre de masques tout en respectant les contraintes liées à DSA. Ce problème est un problème de coloration de graphes où les sommets de chaque couleurs définissent un ensemble de chemins « indépendants » de longueurs au plus k que nous appelons aussi le problème de coloration par k-chemins. Durant la modélisation, nous avons distingué deux problèmes de coloration par k-chemins pertinents: le problème général et le problème induit. Les deux problèmes sont connus pour être NP-difficile, ce qui explique l’utilisation d’heuristiques dans l’industrie pour trouver une décomposition valide en sous-ensembles. Dans cette étude, nous nous intéressons à des méthodes exactes afin de concevoir des solutions optimales et d’évaluer la qualité de l’heuristique développée en industrie (chez Mentor Graphics). Nous présentons différentes méthodes: une approche par programmation linéaire en nombre entier (ILP) où nous étudions plusieurs formulations, une approche par programmation dynamique pour résoudre le cas induit quand k=1 ou k=2 et lorsque les graphes ont une petite longueur arborescente ; enfin, nous étudions le cas particulier des graphes lignes. Les résultats des différentes études numériques montrent que les formulations ILP « naïves » sont les meilleures. Elles listent tous les chemins possibles de longueur au plus k. Les tests sur des données industrielles ayant au plus 2000 sommets (plus grande composante connexe parmi celles qui constituent une instance) ont montré que les deux problèmes, général et induit, sont résolus en moins de 6 secondes, pour k=1 et k=2. La programmation dynamique, appliquée au problème induit de coloration par k-chemins quand k=1 et k=2, montre des résultats équivalents à ceux de la formulation ILP naïve. Cependant, nous nous attendons à de meilleurs résultats par programmation dynamique quand la valeur de k augmente. Enfin, nous montrons qu’un cas particuliers des graphes lignes peut être résolu en temps polynomial en exploitant les propriétés de l’algorithme d'Edmonds et des couplages dans les graphes bipartis. / Controlling the manufacturing costs of integrated circuits while increasing their density is of a paramount importance to maintain a certain degree of profitability in the semi-conductor industry. Among various components of a circuit, we are interested in vertical metallic connections known as “vias”. During manufacturing, a complex lithography process is used to form an arrangement of vias on a silicon wafer support, using an optical mask. For manufacturing reasons, a minimum distance between the vias must be respected. Whenever this is not the case, we are talking about a “conflict”. In order to eliminate these conflicts, the industry uses a technique that decomposes an arrangement of vias in several subsets, where minimum distance constraints are respected: the formation of the individual subsets is done, in sequence, on a silicon wafer using one optical mask per subset. This technique is called Multiple Patterning (MP). There are several ways to decompose an arrangement of vias, the goal being to assign the vias to a minimum number of masks, since the masks are expensive. Minimizing the number of masks is equivalent to minimizing the number of colors in a unit disk graph. This is a NP-hard problem however, a number of “good” heuristics exist. A recent and promising technique is based on the direction and self-assembly of the molecules called Directed Self Assembly (DSA), allows to group vias in conflict according to certain conditions. The main challenge is to find the best way of grouping vias to minimize the number of masks while respecting the constraints related to DSA. This problem is a graph coloring problem where the vertices within each color define a set of independent paths of length at most k also called a k-path coloring problem. During the graph modeling, we distinguished two k-path coloring problems: a general problem and an induced problem. Both problems are known to be NP-hard, which explains the use of heuristics in the industry to find a valid decomposition into subsets. In this study, we are interested in exact methods to design optimal solutions and evaluate the quality of heuristics developed in the industry (at Mentor Graphics). We present different methods: an integer linear programming (ILP) approach where we study several formulations, a dynamic programming approach to solve the induced case when k=1 or k=2 and when the graphs have small tree-width; finally, we study a particular case of line graphs. The results of the various numerical studies show that the naïve ILP formulations are the best, they list all possible paths of length at most k. Tests on a snippet of industrial instances of at most 2000 vertices (a largest connected component among those constituting an instance) have shown that the two problems, general and induced, are solved in less than 6 seconds, for k=1 and k=2. Dynamic programming, applied to the induced k-path coloring when k=1 and k=2, shows results equivalent to those of the naïve ILP formulation, but we expect better results by dynamic programming when the value of k increases. Finally, we show that the particular case of line graphs can be solved in polynomial time by exploiting the properties of Edmonds’ algorithm and bipartite matching.

Die Aufgabe des Proteins Arrestin ist die Beendigung der Signalweitergabe über den GPCR Signalweg. In Stäbchenzellen bindet Arrestin an Licht-aktiviertes phosphoriliertes Rhodopsin um die Signalweitergabe zu unterdrücken. Die Bindung von Arrestin an Rhodopsin erfolgt in zwei Schritten. Zunächst wechselwirkt Arrestin mit dem phosphorilierten C-Terminus von Rhodopsin und bildet einen prä-Komplex, dies induziert Konformationsänderungen im Arrestin wodurch die Bildung eines High-affinity Komplex unter Kopplung an den helikalen Kern des aktivierten Rezeptors erfolgen kann. Biochemische Untersuchungen und Kristallstrukturen haben einen Einblick in die Konformation des Komplexes aus Arrestin und Rhodopsin ermöglicht. In dieser Arbeit werden site-directed Fluorezenz Experimente angewandt um die strukturellen Änderungen zu untersuchen, die bei der Bindung von Arrestin an Rhodopsin ablaufen und der nterschiedlichen Bindungsmodi innerhalb der Wechselwirkung zwischen Arrestin und Rhodopsin. Insbesondere wird hier eine, bisher nicht beschriebene, Assoziation von Arrestin an die Membran untersucht. Des Weiteren wurden Erkenntnisse über die Struktur des prä-Komplexes gewonnen. Die Konformation vom Arrestin im prä-Komplex scheint die Konformation im Basalzustand nachzubilden unter Beteiligung zweier Kontaktstellen: Interaktion mit dem phosphorilierten C-Terminus des Rezeptors und Assoziation mit der Membran. Beim Übergang in den High-affinity Komplex durchläuft Arrestin eine Konformationsänderung in eine aktivere Konformation: der C-Terminus wird verdrängt, es erfolgt eine Neuausrichtung der zentralen flexiblen Schleifen und die Orientierung des Membranankers ändert sich. Die Aufgabe des prä-Komplexes ist somit Arrestin und den Rezeptor zusammen zu bringen sowie die korrekte Orientierung sicherzustellen um einen schnellen Übergang in den High-affinity Komplex zu ermöglichen. / The protein arrestin is responsible for termination of GPCR signalling. In the rod cell, arrestin binds light-activated phosphorylated rhodopsin in order to block further signal transduction. The binding of arrestin to rhodopsin is a two-step process. Arrestin first interacts with the phosphorylated receptor C-terminus in a pre-complex, which induces conformational changes in arrestin that allow coupling to the helical core of the active receptor in a high-affinity complex. Biochemical studies and crystal structures have provided insights into the conformation of the arrestin-rhodopsin complex. This dissertation describes site-directed fluorescence experiments, which were carried out to further investigate the conformational changes occurring upon arrestin binding to rhodopsin and the nature of different binding modes of the arrestin-rhodopsin interaction. In particular this involved characterization of a previously unidentified association of arrestin with the membrane, as well as further elucidation of the structure of the pre-complex. The conformation of arrestin in the pre-complex is indicated to resemble that of the basal state of arrestin, and involves two sites of contact: interaction with the phosphorylated receptor C-terminus, and association with the membrane. Upon transition to the high-affinity complex, arrestin undergoes a conformational change to a more active conformation: the auto-inhibitory C-tail is displaced, there is movement within the central flexible loops, and the orientation of the membrane anchor changes. The pre-complex therefore most likely functions to bring arrestin and the receptor into close contact, and in the correct orientation, to allow for fast transition to the high-affinity complex.

Flavonoids are secondary metabolites that are important in plant defense, protection and human health. Most naturally-occurring flavonoids are found in glucosylated form. Glucosyltransferases (GTs) are enzymes that catalyze the transfer of glucose from a high energy sugar donor to an acceptor molecule. A flavonol-specific 3-O-GT enzyme has been identified and cloned from leaf tissues of grapefruit. The enzyme shows rigid substrate specificity and regiospecificity. F3-O-GTs from grape (Vitis vinifera) and grapefruit (Citrus paradisi) were modeled against F7-O-GTs from Crocus sativus and Scrutellaria biacalensis, and several non-conservative amino acid differences were identified that may impact regioselectivity. This research is designed to test the hypothesis that specific amino acid residues impart the regiospecificity of the grapefruit enzyme. Site-directed mutagenesis was performed on three potentially key amino acid residues within the grapefruit F3-O-GT that were identified through homology modeling. Analyses of the enzyme activity of the mutant F3-O-GT proteins revealed that the single point mutations of serine 20 to leucine (S20L) and proline 297 to phenylalanine (P297F) rendered the recombinant enzyme inactive with flavonol substrates. Mutation of glycine 392 to glutamate (G392E) was active at 80% relative to the wild type. The mutant enzyme also did not show broadened acceptor specificity as it also favored flavonols as the preferred acceptor substrate. The glucosylation products of the active mutant enzyme will be analyzed to determine if this resulted in a change in regiospecificity.

Aujourd'hui, les outils de lithographie utilisés dans l'industrie arrivent à leur limite de résolution en simple exposition. Pour continuer à diminuer les dimensions, il faut utiliser des techniques de double exposition, mais cela entraîne une explosion des coûts de fabrication. Cette thèse se focalise sur les aspects de modélisation de deux techniques, Sidewall Image Transfer et Directed Self-Assembly, qui sont pressenties pour permettre à l'industrie de continuer la réduction des dimensions des transistors, tout en minimisant les coûts. / Today, the lithographic tools used in industry came to their resolution limit in single patterning. In order to continue the reduction of dimensions, it is necessary to use double patterning, but this increase drastically the cost of manufacturing. This thesis focus on the modelisation aspects of two techniques, Sidewal Image Transfer and Directed Self-Assembly, that can help the industry continuing making transistors even smaller, while keeping the costs manageable.

No description available.

No description available.

Doctor of Philosophy / Department of Counseling and Educational Psychology / Kenneth F. Hughey / This study examined the impact of two career interventions on the dysfunctional career thoughts (DCTs) and vocational identity (VI) of 55 high school seniors. Research has shown an inverse relationship between levels of DCTs and VI. One intervention was based on the Cognitive Information Processing approach (Peterson, Sampson, & Reardon, 1991; Peterson, Sampson, Lenz, & Reardon, 2002; Peterson, Sampson, Reardon, & Lenz, 1996; Sampson, Reardon, Peterson, & Lenz, 2004) and incorporated Improving Your Career Thoughts: A Workbook for the Career Thoughts Inventory (CTI workbook; Sampson, Peterson, Lenz, Reardon, & Saunders, 1996c) and the Self-Directed Search (SDS; Holland, 1994). The second intervention employed only the SDS. A control group used neither activity. Levels of DCTs and VI were assessed pre-intervention and post-intervention using the Career Thoughts Inventory (Sampson, Peterson, Lenz, Reardon, & Saunders, 1996a) and the Vocational Identity scale of My Vocational Situation (Holland, Daiger, & Power, 1980a). Earlier studies indicated improvements in levels of dysfunctional career thinking after CIP-based interventions (e.g., Kilk, 1998; Morano, 2005; Reed, 2006), but no previous studies employed the complete CTI workbook. Additional studies (e.g., Loughead & Black, 1990; Mau,1999; Wiggins, 1987) indicated that levels of vocational identity could be increased by using the SDS as an intervention. The combined use of the CTI workbook and SDS produced significant improvements in all five measures of DCTs and VI. It was also shown that use of the SDS as a stand-alone intervention did improve levels of VI, but not to the extent of the improvements shown by combined use of the SDS and CTI workbook. Use of the SDS as a stand-alone intervention did not produce improvements in levels of DCTs. The control group, which employed neither the CTI workbook nor the SDS, unexpectedly showed significant improvements in scores for two CTI scales which may have been due to the influence of confounding variables.

The closed neighbourhood of a vertex in a graph is the vertex together with the set of adjacent vertices. A di®erentiating-dominating set, or identifying code, is a collection of vertices whose intersection with the closed neighbour- hoods of each vertex is distinct and nonempty. A di®erentiating-dominating set in a graph serves to uniquely identify all the vertices in the graph. Chapter 1 begins with the necessary de¯nitions and background results and provides motivation for the following chapters. Chapter 1 includes a summary of the lower identi¯cation parameters, °L and °d. Chapter 2 de- ¯nes co-distinguishable graphs and determines bounds on the number of edges in graphs which are distinguishable and co-distinguishable while Chap- ter 3 describes the maximum number of vertices needed in order to identify vertices in a graph, and includes some Nordhaus-Gaddum type results for the sum and product of the di®erentiating-domination number of a graph and its complement. Chapter 4 explores criticality, in which any minor modi¯cation in the edge or vertex set of a graph causes the di®erentiating-domination number to change. Chapter 5 extends the identi¯cation parameters to allow for orientations of the graphs in question and considers the question of when adding orientation helps reduce the value of the identi¯cation parameter. We conclude with a survey of complexity results in Chapter 6 and a collection of interesting new research directions in Chapter 7. / Mathematical Sciences / PhD (Mathematics)