Large scale chemical reaction networks are a ubiquitous phenomenon, from the metabolism of living cells to processes in planetary atmospheres and chemical technology. At least some of these networks exhibit distinctive global features such as the “small world” behavior. The systematic study of such properties, however, suffers from substantial sampling biases in the few networks that are known in detail. A computational model for generating them is therefore required. Here we present a Toy Model that provides a consistent framework in which generic properties of extensive chemical reaction networks can be explored in detail and that at the same time preserves the “look-and-feel” of chemistry:  Molecules are represented as labeled graphs, i.e., by their structural formulas; their basic properties are derived by a caricature version of the Extended Hückel MO theory that operates directly on the graphs; chemical reaction mechanisms are implemented as graph rewriting rules acting on the structural formulas; reactivities and selectivities are modeled by a variant of the Frontier Molecular Orbital Theory based on the Extended Hückel scheme. The approach is illustrated for two types of reaction networks:  Diels−Alder reactions and the formose reaction implicated in prebiotic sugar synthesis.

Recent advances in systems biology have uncovered detailed mechanisms of  biological processes such as the cell cycle, circadian rhythms, and signaling pathways.  These mechanisms are modeled by chemical reaction networks (CRNs) which are typically simulated by converting to ordinary differential equations (ODEs), so that the goal is to closely reproduce the observed quantitative and qualitative behaviors of the modeled process. This thesis proposes two algorithmic problems related to the construction and comprehension of CRN models. The first problem focuses on reconstructing CRNs from given time series. Given multivariate time course data obtained by perturbing a given CRN, how can we systematically deduce the interconnections between the species of the network? We demonstrate how this problem can be modeled as, first, one of uncovering conditional independence relationships using buffering experiments and, second, of determining the properties of the individual chemical reactions. Experimental results demonstrate the effectiveness of our approach on both synthetic and real CRNs. The second problem this work focuses on is to aid in network comprehension, i.e., to understand the motifs underlying complex dynamical behaviors of CRNs. Specifically, we  focus on bistability---an important dynamical property of a CRN---and propose algorithms to identify the core structures responsible for conferring bistability. The approach we take is to systematically infer the instability causing structures (ICSs) of a CRN and use machine learning techniques to relate properties of the CRN to the presence of such ICSs. This work has the potential to aid in not just network comprehension but also model simplification, by helping  reduce the complexity of known bistable systems. / Ph. D.

Large chemical reaction networks often exhibit distinctive features that can be interpreted as higher-level structures. Prime examples are metabolic pathways in a biochemical context. We review mathematical approaches that exploit the stoichiometric structure, which can be seen as a particular directed hypergraph, to derive an algebraic picture of chemical organizations. We then give an alternative interpretation in terms of set-valued set functions that encapsulate the production rules of the individual reactions. From the mathematical point of view, these functions define generalized topological spaces on the set of chemical species. We show that organization-theoretic concepts also appear in a natural way in the topological language. This abstract representation in turn suggests the exploration of the chemical meaning of well-established topological concepts. As an example, we consider connectedness in some detail.

<p><br></p><p dir="ltr">Algorithmic reaction explorations based on transition state searches can now routinely predict relatively short reaction sequences involving small molecules across a variety of chemical domains, including materials degradation, combustion chemistry, battery performance, and biomass conversion. Mature quantum chemistry tools can comprehensively characterize the reactivity of species with efficiency and broad coverage, but consecutive characterizations quickly encounter prohibitive costs of reactant proliferation, spurious characterization of irrelevant intermediates, and compounding uncertainties of quantum chemical calculations deep in a network. Application of these algorithms to deeper chemical reaction network (CRN) exploration still requires the development of more effective, comprehensive, and automated exploration policies. </p><p><br></p><p dir="ltr">This dissertation addresses the challenge of exploring deep chemical reaction networks (CRNs) in complex and chemically diverse systems by introducing Yet Another Kinetic Strategy (YAKS), an automated algorithm designed to minimize the computational costs of deep exploration and maximize coverage of important reaction channels. YAKS demonstrates that microkinetic simulations of the nascent network are cost-effective and able to iteratively build deep networks. Key features of the algorithm are the automatic incorporation of expanded elementary reaction steps, compatibility with short-lived but kinetically important species, and the incorporation of rate uncertainty into the exploration policy. The automatically induced expansion of reaction mechanisms gives YAKS access to important chemistries that other algorithms ignore, while also maintaining the ability to limit expensive forays into kinetically irrelevant regions of the CRN that would stymie previous methods. Instead of conducting a greedy exploration, YAKS biases network topography to probe beyond short-lived but kinetically important species, which enables YAKS to explore important endergonic reactions deep into the CRN. YAKS further induces rate uncertainty into an ensemble of microkinetic simulations, which positively influences intermediate prioritization deep in a network. </p><p><br></p><p dir="ltr">Algorithm effectiveness was validated in a case study of glucose pyrolysis, where the algorithm rediscovers reaction pathways previously discovered by heuristic exploration policies and also elucidates new reaction pathways to experimentally obtained products. The resulting CRN is the first to connect all major experimental pyrolysis products to glucose. Additional case studies are presented that investigate the role of reaction rules, rate uncertainty, and bimolecular reactions. These case studies show that na\"ive exponential growth estimates can vastly overestimate the actual number of kinetically relevant pathways in physical reaction networks. The excellent performance of YAKS demonstrates the ability of automated algorithmic methods to address the gaps outlined above.</p><p><br></p><p dir="ltr">The power of YAKS was then demonstrated on radically distinct chemistry from the validation study, chemical warfare agents (CWAs). Despite the almost uniform ban on the use of chemical agents and the widespread neutralization of stockpiles due to treaties, CWAs continue to pose a grave threat around the world. Rogue states, terrorist organizations, and lone wolf terrorists have all conducted CWA attacks within the past few decades. These circumstances make it necessary to prepare against and forensically evaluate the use of CWAs without direct experimentation. YAKS was applied to elucidate degradation reaction networks of three prominent CWAs, mustard gas (SM, HD), sarin (GB), and VX, and identified a range of possible degradant products of real world use cases. This dissertation also computationally interpreted the most common mechanism of action (MoA) associated with each CWA and examined their hydrolysis networks as a method to neutralize these agents. Additionally, agent stability was evaluated during extended microkinetic modeling in arid and humid scenarios, highlighting the potential for computational simulation approaches to fill a capability gap in the broader field of chemical defense. </p><p><br></p><p dir="ltr">This dissertation advanced automated CRN exploration, but considerable gaps remain. Future research directions include the accuracy gaps of both density functional theory and conformational sampling on energy calculations. Incorporation of machine learning (ML) methods can accelerate the costly reactivity characterization process, but ML models still require vast amounts of data. A recently released dataset comprehensively explored over 175,000 graphically defined reactions of moderately-sized C, H, O, and N containing molecules. While models trained on such data could readily be applied to glucose pyrolysis systems, chemical agents involve a much wider array of chemistry including Cl, S, P, and considerable quantities of radical and charged species. More comprehensive datasets are required to train a general ML model capable of accelerating geometry or energy calculations. Additionally, microkinetic modeling is hindered by software implementations that are unable to explore diverse chemistry such as multiphase reactions. In light of this, further improvements in exploration policies, reaction prediction algorithms, and simulation software make it feasible that CRNs might soon be routinely predictable in many additional contexts.</p>

This thesis develops various aspects of Algebraic Geometry and its applications in different fields of science. In Chapter 2 we characterise the feasible set of an optimisation problem relevant in chemical process engineering. We consider the polynomial dynamical system associated with mass-action kinetics of a chemical reaction network. Given an initial point, the attainable region of that point is the smallest convex and forward closed set that contains the trajectory. We show that this region is a spectrahedral shadow for a class of linear dynamical systems. As a step towards representing attainable regions we develop algorithms to compute the convex hulls of trajectories. We present an implementation of this algorithm which works in dimensions 2,3 and 4. These algorithms are based on a theory that approximates the boundary of the convex hull of curves by a family of polytopes. If the convex hull is represented as the output of our algorithms we can also check whether it is forward closed or not. Chapter 3 has two parts. In this first part, we do a case study of planar curves of degree 6. It is known that there are 64 rigid isotopy types of these curves. We construct explicit polynomial representatives with integer coefficients for each of these types using different techniques in the literature. We present an algorithm, and its implementation in software Mathematica, for determining the isotopy type of a given sextic. Using the representatives various sextics for each type were sampled. On those samples we explored the number of real bitangents, inflection points and eigenvectors. We also computed the tensor rank of the representatives by numerical methods. We show that the locus of all real lines that do not meet a given sextic is a union of up to 46 convex regions that is bounded by its dual curve. In the second part of Chapter 3 we consider a problem arising in molecular biology. In a system where molecules bind to a target molecule with multiple binding sites, cooperativity measures how the already bound molecules affect the chances of other molecules binding. We address an optimisation problem that arises while quantifying cooperativity. We compute cooperativity for the real data of molecules binding to hemoglobin and its variants. In Chapter 4, given a variety X in n-dimensional projective space we look at its image under the map that takes each point in X to its coordinate-wise r-th power. We compute the degree of the image. We also study their defining equations, particularly for hypersurfaces and linear spaces. We exhibit the set-theoretic equations of the coordinate-wise square of a linear space L of dimension k embedded in a high dimensional ambient space. We also establish a link between coordinate-wise squares of linear spaces and the study of real symmetric matrices with degenerate eigenspectrum.

Das Enzym Tryptophan Synthase ist ein ausgezeichnetes Beispiel einer molekularen Fabrik auf der Nanoskala mit zwei katalytischen Zentren. Der katalytische Zyklus des Moleküls beruht zudem auf zahlreichen allosterischen Wechselwirkungen sowie der Übertragung des Intermediats Indol durch einen intramolekularen Tunnel. In dieser Arbeit wird das erste kinetische Modell eines einzelnen Tryptophan Synthase Moleküls konstruiert und analysiert. Simulationen zeigen starke Korrelationen zwischen den Zuständen der Katalysezentren sowie die Ausbildung von Synchronisation. Mit stochastischer Thermodynamik wird die experimentell unzugängliche Reaktionskonstante für die Rückübertragung des Indols aus Messdaten rekonstuiert. Methoden, die den Informationsaustausch in bipartiten Markovnetzwerken charakterisieren, werden auf beliebige Markovnetzwerke verallgemeinert und auf das Modell angewendet. Der abschließende Teil befasst sich mit chemischen Reaktionsnetzwerken von Metaboliten und Enzymen. Es werden algebraische Modelle (Halbgruppen) konstruiert, welche aufeinanderfolgende und simultane katalytische Funktionen von Enzymen und von Unternetzwerken erfassen. Diese Funktionen werden genutzt, um eine natürliche Dynamikum sowie hinreichende und notwendige Bedingungen für seine Selbsterhaltung zu formulieren. Anschließend werden die algebraischen Modelle dazu genutzt, um eine Korrespondenz zwischen Halbgruppenkongruenzen und Skalenübergängen auf den Reaktionsnetzwerken herzustellen. Insbesondere wird eine Art von Kongruenzen erörtert, welche dem Ausspuren der globalen Struktur des Netzwerkes unter vollständiger Beibehaltung seiner lokalen Komponenten entspicht. Während klassische Techniken eine bestimmte lokale Komponente fixieren und sämtliche Informationen über ihre Umgebung ausspuren, sind bei dem algebraischen Verfahren alle lokalen Komponenten zugleich sichtbar und eine Verknüpfung von Funktionen aus verschiedenen Komponenten ist problemlos möglich. / The channeling enzyme tryptophan synthase provides a paradigmatic example of a chemical nanomachine with two distinct catalytic subunits. It catalyzes the biosynthesis of tryptophan, whereby the catalytic activity in a subunit is enhanced or inhibited depending on the state of the other subunit, gates control the accessibility of the reactive sites and the intermediate product indole is directly channeled within the protein. The first single-molecule kinetic model of the enzyme is constructed. Simulations reveal strong correlations in the states of the active centers and the emergent synchronization. Thermodynamic data is used to calculate the rate constant for the reverse indole channeling. Using the fully reversible single-molecule model, the stochastic thermodynamics of the enzyme is closely examined. The current methods describing information exchange in bipartite systems are extended to arbitrary Markov networks and applied to the kinetic model. They allow the characterization of the information exchange between the subunits resulting from allosteric cross-regulations and channeling. The final part of this work is focused on chemical reaction networks of metabolites and enzymes. Algebraic semigroup models are constructed based on a formalism that emphasizes the catalytic function of reactants within the network. A correspondence between coarse-graining procedures and semigroup congruences respecting the functional structure is established. A family of congruences that leads to a rather unusual coarse-graining is analyzed: The network is covered with local patches in a way that the local information on the network is fully retained, but the environment of each patch is not resolved. Whereas classical coarse-graining procedures would fix a particular patch and delete information about the environment, the algebraic approach keeps the structure of all local patches and allows the interaction of functions within distinct patches.

The behavior of the Deoxyribonucleic Acid (DNA) molecule can be exploited to perform useful computation. It can also be ”programmed” using the language of Chemical Reaction Networks (CRNs). One specialized CRN construct is the Surface Chemical Reaction Network (SCRN). The SCRN construct can implement asynchronous cellular automata, which can in turn be used to implement digital logic circuits. SCRN based digital logic circuits are thought to have several advantages over regular CRN circuits. One of these proposed advantages is their scalability. This thesis investigates the scalability of SCRN based adder circuits, how does an increase in the number of bits affect the time required for the circuit to produce a correct result? Additionally, how is the throughput of the circuit affected when multiple additions are performed in a pipelined fashion? These questions are studied through experiments where the execution of optimized SCRN adder circuits is simulated. Due to the stochastic nature of SCRNs each such execution is all but guaranteed to be unique, requiring the simulation of the circuits to be repeated until a sufficiently large statistical sample has been collected. The results show these samples to follow a Gaussian distribution, regardless of the number of bits or the number of pipelined operations. The experiments show the simulated latency of the studied SCRN adder circuits to scale linearly with the number of input bits. The results also show that the throughput can be greatly improved through the pipelining of multiple operations. However, the results are inconclusive as to the maximum possible throughput of SCRN adder circuits. A conclusion of the project is that SCRN digital logic circuit design could conceivably benefit from the implementation of specialized components beyond the standard logic gates. / DNA-molekylen kan utnyttjas för att genomföra användbara beräkningar. Den kan också ”programmeras” via abstraktionen kemiska reaktionsnätverk. Ytbundna Kemiska Reaktionsnätverk (YKR) är i sin tur en vidare specialisering av sådana reaktionsnätverk. Ett YKR kan implementera en asynkrona cellulära automat, som i sin tur kan implementera kretsar för digital logik. Kretsar för digital logik byggda med YKR anses ha flera fördelar gentemot motsvarande kretsar byggda från vanliga kemiska reaktionsnätverk. En av dessa tilltänkta fördelar ligger i deras skalbarhet. Detta examensarbete undersöker skalbarheten hos YKR-baserade additions-kretsar, hur påverkar ett ökat antal bitar tiden som krävs för att kretsen ska producera ett korrekt resultat? Vidare, hur påverkas genomströmningen när flera operationer matas in direkt och genomför efter varandra i en pipeline? Dessa frågor studeras genom experiment där körningar av optimerande YKR-baserade additionskretsar simuleras. På grund av de stokastiska egenskaperna hos YKR är varje sådan körning i princip garanterad att vara unik, vilket kräver upprepade simuleringar av varje krets tills ett tillräckligt stort statistiskt urval har insamlats. Dessa resultat visar sig följa en normalfördelningskurva, oavsett antalet bitar eller antalet operationer som matats in i en pipeline. Experimenten visar att den simulerade latensen skalar linjärt med antalet indata-bitar för de studerade additionskretsarna. Resultaten visar även att genomströmningen förbättras avsevärt när flera operationer körs direkt efter varandra i en pipeline. Resultaten är dock ofullständiga när det gäller uppmätandet av additionskretsarna högsta möjliga genomströmning. En slutsats av projektet är att YKR-baserade kretsar för digital logik möjligen skulle kunna gagnas av implementerandet av specialiserade komponenter utöver de vanliga logikgrindarna.

Dynamical structure functions were developed as a partial structure representation of linear time-invariant systems to be used in the reconstruction of biological networks. Dynamical structure functions contain more information about structure than a system's transfer function, while requiring less a priori information for reconstruction than the complete computational structure associated with the state space realization. Early sufficient conditions for network reconstruction with dynamical structure functions severely restricted the possible applications of the reconstruction process to networks where each input independently controls a measured state. The first contribution of this thesis is to extend the previously established sufficient conditions to incorporate both necessary and sufficient conditions for reconstruction. These new conditions allow for the reconstruction of a larger number of networks, even networks where independent control of measured states is not possible. The second contribution of this thesis is to extend the robust reconstruction algorithm to all reconstructible networks. This extension is important because it allows for the reconstruction of networks from real data, where noise is present in the measurements of the system. The third contribution of this thesis is a Matlab toolbox that implements the robust reconstruction algorithm discussed above. The Matlab toolbox takes in input-output data from simulations or real-life perturbation experiments and returns the proposed Boolean structure of the network. The final contribution of this thesis is to increase the applicability of dynamical structure functions to more than just biological networks by applying our reconstruction method to wireless communication networks. The reconstruction of wireless networks produces a dynamic interference map that can be used to improve network performance or interpret changes of link rates in terms of changes in network structure, enabling novel anomaly detection and security schemes.