No description available.

No description available.

The Boolean satisfiability (SAT) problem is central to many applications involving the verification and optimization of digital systems. These combinatorial problems are typically solved by using a decision-based approach, however the lengthy compute time of SAT can make it prohibitively impractical for some applications. We discuss how the underlying physical characteristics of various technologies affect the practicality of SAT solvers. Power dissipation and other physical limitations are increasingly restricting the improvement in performance of conventional software on CPUs. We use heterogeneous computing to maximize the strengths of different underlying technologies as well as different computing architectures. In this thesis, we present a custom hardware architecture for accelerating the common computation within a SAT solver. Algorithms and data structures must be fundamentally redesigned in order to maximize the strengths of customized computing. Generalizable optimizations are proposed to maximize the throughput, minimize communication latencies, and aggressively compact the memory. We tightly integrate as well as jointly optimize the hardware accelerator and the software host. Our fully implemented system is significantly faster than pure software on real-life SAT problems. Due to our insights and optimizations, we are able to benchmark SAT in uncharted territory. / Thesis / Doctor of Philosophy (PhD)

<p> In this thesis we introduce the concept of a dense extension of a partially ordered set and study some of the properties of the resulting class of extensions. In particular we study the dense distributive extensions, dense Boolean extensions and dense meet continuous extensions of distributive, Boolean and meet continuous lattices respectively.</p> / Thesis / Doctor of Philosophy (PhD)

No description available.

A transition calculus is developed for describing and analyzing the dynamic behavior of logic circuits. Boolean partial derivatives are introduced that are more powerful and applicable to a wider class of problems than the Boolean difference. The partial derivatives are used to define a Boolean differential which provides a concise method for describing the effect on a switching function of changes in its variables. It is shown that a nonconstant function is uniquely determined by its differential, and integration techniques are developed for finding a function when its differential is known. The useful concepts of exact integrals, compatible integrals, and integration by parts are introduced and the conditions for their existence are established. Algorithms for both differentiation and integration are simply implemented using Karnaugh maps. / Ph. D.

In eukaryotes, distinct nutrient signals are integrated in order to produce robust cellular responses to fluctuations in the environment. This process of signal integration is attributed to the crosstalk between nutrient specific signaling pathways, as well as the large degree of overlap between their regulatory targets. In the budding yeast Saccharomyces cerevisiae, these distinct pathways have been well characterized. However, the significant overlap between these pathways confounds the interpretation of the overall regulatory logic in terms of nutrient-dependent cell state determination. Here, we propose a literature-curated molecular mechanism of the integrated nutrient signaling pathway in budding yeast, focussing on carbon and nitrogen signaling. We build a computational model of this pathway to reconcile the available experimental data with our proposed molecular mechanism. We evaluate the robustness of the model fit to data with respect to the variations in the values of kinetic parameters used to calibrate the model. Finally, we use the model to make novel, experimentally testable predictions of transcription factor activities in mutant strains undergoing complex nutrient shifts. We also propose a novel framework, called BoolODE for utilizing published Boolean models to generate synthetic datasets used to benchmark the performance of algorithms performing gene regulatory network inference from single cell RNA sequencing data. / Doctor of Philosophy / An important problem in biology is how organisms sense and adapt to ever changing environments. A good example of an environmental cue that affects animal behavior is the availability of food; scarcity of food forces animals to search for food-rich habitats, or go into hibernation. At the level of single cells, a range of behaviors are observed depending on the amount of food, or nutrients present in the environment. Moreover, different types of nutrients are important for different biological functions in single cells, and each different nutrient type will have to be available in the right quantities to support cellular growth. At the subcellular level, intricate molecular machineries exist which sense the amounts of each nutrient type, and interpret this information in order to make a decision on how best to respond. This interpretation and integration of nutrient information is a complex, poorly understood process even in a simple unicellular organism like the budding yeast. In order to understand this process, termed nutrient signaling, we propose a mathematical model of how yeasts respond to nutrient availability in the environment. Our model advances the state of knowledge by presenting the first comprehensive mathematical model of the nutrient signaling machinery, accounting for a variety of experimental observations from the last three decades of yeast nutrient signaling. We use our model to make predictions on how yeasts might behave when supplied with different combinations of nutrients, which can be verified by experiments. Finally, the cellular machinery that helps yeasts respond to nutrient availability in the environment is very similar to the machinery in cancer cells that causes them to grow rapidly. Our proposed model can serve as a stepping stone towards the construction of a model of cancer's responses to its nutritional environment.

Synthetic genetic circuits have revolutionized numerous fields, ranging from academic research and point-of-care diagnostics to disease therapeutics and industrial biomanufacturing. These circuits provide a powerful tool for precise spatiotemporal control over biological and biochemical interactions, thereby enhancing our understanding of these complex systems and expanding their applicability. The last few decades have witnessed a surge in research efforts, both in cell-free and cellular systems. These endeavors include those to improve the sensitivity and specificity of diagnostics and optimize the safety, efficacy, and tunability of existing treatments. This dissertation delves into the exploration of Boolean logic gates in the cell-free realm: the development of a 'Cell-Free Recombinase Integrated Boolean Operating System' (CRIBOS) for expanding the capabilities of cell-free sensing applications. Applications of Boolean logic gates have flourished within cellular systems and animal models. However, a persisting gap in the field is in their exploration within the cell-free system. This deficiency has resulted in a constrained toolkit for studying and applying Boolean logic gates in cell-free settings. Recognizing this limitation in the field and aiming to extend the frontiers of genetic circuits beyond traditional boundaries, I introduce CRIBOS, leveraging the advantages of recombinase, known for its high orthogonality, efficiency, and sensitivity. I designed more than 20 multi-input-multi-output recombinase Boolean logic gates in a cell-free context, from which a set of critical rules crucial for building genetic circuits in the cell-free environment was also established. In addition, integrating allosteric transcription factor (aTF)-based sensors with CRIBOS enabled multiplex environmental sensing within the cell-free environment. Moreover, the CRIBOS system showcased its versatility by facilitating the creation of a biological memory storage device, demonstrating robust functionality with high stability over four months. Implementing CRIBOS not only expands the application of multiplex Boolean logic gates from cellular systems to the cell-free environment but also expands their overall versatility, opening new avenues for the design and application of sophisticated genetic circuits.

All high-level living organisms are made of small cell units, containing DNA, RNA, genes, proteins etc. Genes are important components of the cells and it is necessary to understand the inter-gene relations, in order to comprehend, predict and ultimately intervene in the cells’ dynamics. Genetic regulatory networks (GRN) represent the gene interactions that dictate the cell behavior. Translational genomics aims to mathematically model GRNs and one of the main goals is to alter the networks’ behavior away from undesirable phenotypes such as cancer. The mathematical framework that has been often used for modeling GRNs is the probabilistic Boolean network (PBN), which is a collection of constituent Boolean networks with perturbation, BNp. This dissertation uses BNps, to model gene regulatory networks with an intent of designing stationary control policies (CP) for the networks to shift their dynamics toward more desirable states. Markov Chains (MC) are used to represent the PBNs and stochastic control has been employed to find stationary control policies to affect steady-state distribution of the MC. However, as the number of genes increases, it becomes computationally burdensome, or even infeasible, to derive optimal or greedy intervention policies. This dissertation considers the problem of modeling and intervening in large GRNs. To overcome the computational challenges associated with large networks, two approaches are proposed: first, a reduction mapping that deletes genes from the network; and second, a greedy control policy that can be directly designed on large networks. Simulation results show that these methods achieve the goal of controlling large networks by shifting the steady-state distribution of the networks toward more desirable states. Furthermore, a new inference method is used to derive a large 17-gene Boolean network from microarray experiments on gastrointestinal cancer samples. The new algorithm has similarities to a previously developed well-known inference method, which uses seed genes to grow subnetworks, out of a large network; however, it has major differences with that algorithm. Most importantly, the objective of the new algorithm is to infer a network from a seed gene with an intention to derive the Gene Activity Profile toward more desirable phenotypes. The newly introduced reduction mappings approach is used to delete genes from the 17-gene GRN and when the network is small enough, an intervention policy is designed for the reduced network and induced back to the original network. In another experiment, the greedy control policy approach is used to directly design an intervention policy on the large 17-gene network to beneficially change the long-run behavior of the network. Finally, a novel algorithm is developed for selecting only non-isomorphic BNs, while generating synthetic networks, using a method that generates synthetic BNs, with a prescribed set of attractors. The goal of the new method described in this dissertation is to discard isomorphic networks.

In recent years Boolean Networks (BN) and Probabilistic Boolean Networks (PBN) have become popular paradigms for modeling gene regulation. A PBN is a collection of BNs in which the gene state vector transitions according to the rules of one of the constituent BNs, and the network choice is governed by a selection distribution. Intervention in the context of PBNs was first proposed with an objective of avoid- ing undesirable states, such as those associated with a disease. The early methods of intervention were ad hoc, using concepts like mean first passage time and alteration of rule based structure. Since then, the problem has been recognized and posed as one of optimal control of a Markov Network, where the objective is to find optimal strategies for manipulating external control variables to guide the network away from the set of undesirable states towards the set of desirable states. This development made it possible to use the elegant theory of Markov decision processes (MDP) to solve an array of problems in the area of control in gene regulatory networks, the main theme of this work. We first introduce the optimal control problem in the context of PBN models and review our solution using the dynamic programming approach. We next discuss a case in which the network state is not observable but for which measurements that are probabilistically related to the underlying state are available. We then address the issue of terminal penalty assignment, considering long term prospective behavior and the special attractor structure of these networks. We finally discuss our recent work on optimal intervention for the case of a family of BNs. Here we consider simultaneously controlling a set of Boolean Models that satisfy the constraints imposed by the underlying biology and the data. This situation arises in a case where the data is assumed to arise by sampling the steady state of the real biological network.