Heuristics for the Critical Node Detection Problem in Large Complex Networks

Complex networks have recently attracted a significant amount of research attention due to their ability to model real world phenomena. One important problem often encountered is to limit diffusive processes spread over the network, for example mitigating pandemic disease or computer virus spread. A number of problem formulations have been proposed that aim to solve such problems based on desired network characteristics, such as maintaining the largest network component after node removal. The recently formulated critical node detection problem aims to remove a small subset of vertices from the network such that the residual network has minimum pairwise connectivity. Unfortunately, the problem is NP-hard and also the number of constraints is cubic in number of vertices, making very large scale problems impossible to solve with traditional mathematical programming techniques. Even many approximation algorithm strategies such as dynamic programming, evolutionary algorithms, etc. all are unusable for networks that contain thousands to millions of vertices. A computationally efficient and simple approach is required in such circumstances, but none currently exist. In this thesis, such an algorithm is proposed. The methodology is based on a depth-first search traversal of the network, and a specially designed ranking function that considers information local to each vertex. Due to the variety of network structures, a number of characteristics must be taken into consideration and combined into a single rank that measures the utility of removing each vertex. Since removing a vertex in sequential fashion impacts the network structure, an efficient post-processing algorithm is also proposed to quickly re-rank vertices. Experiments on a range of common complex network models with varying number of vertices are considered, in addition to real world networks. The proposed algorithm, DFSH, is shown to be highly competitive and often outperforms existing strategies such as Google PageRank for minimizing pairwise connectivity.

Multi-Objective Genetic Algorithms for the Single Allocation Hub Location Problem

Hub Location Problems play vital economic roles in transportation and telecommunication networks where goods or people must be efficiently transferred from an origin to a destination point whilst direct origin-destination links are impractical. This work investigates the single allocation hub location problem, and proposes a genetic algorithm (GA) approach for it. The effectiveness of using a single-objective criterion measure for the problem is first explored. Next, a multi-objective GA employing various fitness evaluation strategies such as Pareto ranking, sum of ranks, and weighted sum strategies is presented. The effectiveness of the multi-objective GA is shown by comparison with an Integer Programming strategy, the only other multi-objective approach found in the literature for this problem. Lastly, two new crossover operators are proposed and an empirical study is done using small to large problem instances of the Civil Aeronautics Board (CAB) and Australian Post (AP) data sets.

Some Travelling Wave Solutions of KdV-Burgers Equation

In this paper we study the extended Tanh method to obtain some exact solutions of KdV-Burgers equation. The principle of the Tanh method has been explained and then apply to the nonlinear KdV- Burgers evolution equation. A finnite power series in tanh is considered as an ansatz and the symbolic computational system is used to obtain solution of that nonlinear evolution equation. The obtained solutions are all travelling wave solutions.

New Contig Creation Algorithm for the de novo DNA Assembly Problem

DNA assembly is among the most fundamental and difficult problems in bioinformatics. Near optimal assembly solutions are available for bacterial and small genomes, however assembling large and complex genomes especially the human genome using Next-Generation-Sequencing (NGS) technologies is shown to be very difficult because of the highly repetitive and complex nature of the human genome, short read lengths, uneven data coverage and tools that are not specifically built for human genomes. Moreover, many algorithms are not even scalable to human genome datasets containing hundreds of millions of short reads. The DNA assembly problem is usually divided into several subproblems including DNA data error detection and correction, contig creation, scaffolding and contigs orientation; each can be seen as a distinct research area. This thesis specifically focuses on creating contigs from the short reads and combining them with outputs from other tools in order to obtain better results. Three different assemblers including SOAPdenovo [Li09], Velvet [ZB08] and Meraculous [CHS+11] are selected for comparative purposes in this thesis. Obtained results show that this thesis’ work produces comparable results to other assemblers and combining our contigs to outputs from other tools, produces the best results outperforming all other investigated assemblers.

A DFT Guided/Experimental Approach to Asymmetric Allylation and Phase-Transfer Catalysis

The Dudding group is interested in the application of Density Functional Theory (DFT) in developing asymmetric methodologies, and thus the focus of this dissertation will be on the integration of these approaches. Several interrelated subsets of computer aided design and implementation in catalysis have been addressed during the course of these studies. The first of the aims rested upon the advancement of methodologies for the synthesis of biological active C(1)-chiral 3-methylene-indan-1-ols, which in practice lead to the use of a sequential asymmetric Yamamoto-Sakurai-Hosomi allylation/Mizoroki Heck reaction sequence. An important aspect of this work was the utilization of ortho-substituted arylaldehyde reagents which are known to be a problematic class of substrates for existing asymmetric allylation approaches. The second phase of my research program lead to the further development of asymmetric allylation methods using o-arylaldehyde substrates for synthesis of chiral C(3)-substituted phthalides. Apart from the de novo design of these chemistries in silico, which notably utilized water-tolerant, inexpensive, and relatively environmental benign indium metal, this work represented the first computational study of a stereoselective indium-mediated process. Following from these discoveries was the advent of a related, yet catalytic, Ag(I)-catalyzed approach for preparing C(3)-substituted phthalides that from a practical standpoint was complementary in many ways. Not only did this new methodology build upon my earlier work with the integrated (experimental/computational) use of the Ag(I)-catalyzed asymmetric methods in synthesis, it provided fundamental insight arrived at through DFT calculations, regarding the Yamamoto-Sakurai-Hosomi allylation. The development of ligands for unprecedented asymmetric Lewis base catalysis, especially asymmetric allylations using silver and indium metals, followed as a natural extension from these earlier discoveries. To this end, forthcoming as well was the advancement of a family of disubstituted (N-cyclopropenium guanidine/N-imidazoliumyl substituted cyclopropenylimine) nitrogen adducts that has provided fundamental insight into chemical bonding and offered an unprecedented class of phase transfer catalysts (PTC) having far-reaching potential. Salient features of these disubstituted nitrogen species is unprecedented finding of a cyclopropenium based C-H•••πaryl interaction, as well, the presence of a highly dissociated anion projected them to serve as a catalyst promoting fluorination reactions. Attracted by the timely development of these disubstituted nitrogen adducts my last studies as a PhD scholar has addressed the utility of one of the synthesized disubstituted nitrogen adducts as a valuable catalyst for benzylation of the Schiff base N-diphenyl methylene glycine ethyl ester. Additionally, the catalyst was applied for benzylic fluorination, emerging from this exploration was successful fluorination of benzyl bromide and its derivatives in high yields. A notable feature of this protocol is column-free purification of the product and recovery of the catalyst to use in a further reaction sequence.

Perceived Deservingness and the Toleration of Human Rights Violations: The Problem and a Possible Solution

Despite general endorsement of universal human rights, people continue to tolerate specific human rights violations. I conducted a two-part study to investigate this issue. For Part I, I examined whether people tolerated torture (a human rights violation) based on the morality and deservingness of the target. Participants tolerated torture more when the target had committed a highly morally reprehensible transgression. This effect was mediated by the target’s perceived deservingness for harsh treatment, and held over and above participants’ abstract support for the right to humane treatment. For Part II, hypocrisy induction was used in an attempt to reduce participants’ toleration of the torture. Participants were assigned to either the hypocrisy induction or control condition. Unexpectedly, participants who tolerated the torture more in Part I reduced their toleration the most in the control condition, possibly because of consistency and floor effects. Limitations and implications of the findings are discussed.

Diastereoselective Synthesis of Planar Chiral N-Substituted Ferrocenes Derived from Epimeric Imidazolones and their Application to Asymmetric Hydrogenation of Quinolines

This thesis describes the synthesis and use of an N-substituted ferrocene bearing a proline-derived chiral directing group and diastereoselective lithiation-electrophile quench of the pro-Sp hydrogen of the ferrocene to give planar chiral products in >95:5 dr. The auxiliary group is found to be stable to lithium bases of types RLi and R2NLi giving the same diastereoselectivity. The anti- epimer of the previously mentioned syn auxiliary induces lithiation of pro Rp rather than pro Sp hydrogen in >95:5 dr. Upon electrophile quench and elimination, the enantiomer of the syn-derived planar chiral imidazolone is obtained. Hence, this method provides a practical way to prepare planar chiral enantiomers in this series without the use of a more expensive D-proline derived starting material. The syn and anti epimers have β, γ-stereogenic centers and the origin of stereoselectivity in lithiation appears to be driven by the conformational bias exerted by the β-silyloxy moiety in each chiral auxiliary. In the thesis, this conclusion is supported using insensitivity of lithiation selectivity to the bulkiness of the base, comparison of enantiomers, deuteration experiments, nOe difference studies and computational modeling of the ground states and lithiation transition states for both substrates. The products are then converted to ligand precursors to make iridium and rhodium complexes. Among them, one of the cationic iridium complex is found to be effective in the asymmetric hydrogenation of 2-substituted quinolines with enantioselectivities up to 80% at pressures as low as 5 atm.

A Bicyclic L-Proline Derived Chiral Auxiliary for Asymmetric Synthesis

This thesis describes the use of an L−proline-derived chiral auxiliary for diastereoselective lithiation and ligand synthesis. Such compounds have been utilized in the Metallinos research group previously for the synthesis of N−substituted planar chiral ferrocenes. The first project describes the use of this chiral auxiliary as a directing group for N−benzyl substitution, providing products in up to 10:1 diastereomeric ratio (dr). These derivatives may serve as chiral ylidene precursors to serve as ligands in transition metal catalysis. In addition, an N−substituted planar chiral ferrocene ylidene ligand derived from the same chiral auxiliary was used to prepare rhodium complexes that were explored as potential catalysts for asymmetric hydroformylation.

Mirroring Enzymes: The Role of H-Bonding In HQuin-BAM Catalyzed Asymmetric Aza-Henry Reactions: A DFT Study into the Reactivity, Mechanism, and Origins of Selectivity

The exact mechanistic understanding of various organocatalytic systems in asymmetric reactions such as Henry and aza-Henry transformations is important for developing and designing new synthetic organocatalysts. The focus of this dissertation will be on the use of density functional theory (DFT) for studying the asymmetric aza-Henry reaction. The first part of the thesis is a detailed mechanistic investigation of a poorly understood chiral bis(amidine) (BAM) Brønsted acid catalyzed aza-Henry reaction between nitromethane and N-Boc phenylaldimine. The catalyst, in addition to acting as a Brønsted base, serves to simultaneously activate both the electrophile and the nucleophile through dual H-bonding during C-C bond formation and is thus essential for both reaction rate and selectivity. Analysis of the H-bonding interactions revealed that there was a strong preference for the formation of a homonuclear positive charge-assisted H-bond, which in turn governed the relative orientation of substrate binding. Attracted by this well-defined mechanistic investigation, the other important aspect of my PhD research addressed a detailed theoretical analysis accounting for the observed selectivity in diastereoselective versions of this reaction. A detailed inspection of the stereodetermining C-C bond forming transition states for monoalkylated nitronate addition to a range of electronically different aldimines, revealed that the origins of stereoselectivity were controlled by a delicate balance of different factors such as steric, orbital interactions, and the extent of distortion in the catalyst and substrates. The structural analysis of different substituted transition states established an interesting dependency on matching the shape and size of the catalyst (host molecule) and substrates (guest molecules) upon binding, both being key factors governing selectivity, in essence, offering an analogy to positive cooperative binding effect of catalytic enzymes and substrates in Nature. In addition, both intra-molecular (intra-host) and inter-molecular (host-guest, guest-guest) stabilizing interactions play a key role to the high π-facial selectivity. The application of dispersion-corrected functionals (i.e., ωB97X-D and B3LYP-D3) was essential for accurately modeling these stabilizing interactions, indicating the importance of dispersion effects in enantioselectivity. As a brief prelude to more extensive future studies, the influence of a triflate counterion on both reactivity and selectivity in this reaction was also addressed.