| Publications about 'networks' |
| Articles in journal or book chapters |
| In previous work, we have developed an approach to understanding the long-term dynamics of classes of chemical reaction networks, based on rate-dependent Lyapunov functions. In this paper, we show that stronger notions of convergence can be established by proving contraction with respect to non-standard norms. This enables us to show that such networks entrain to periodic inputs. We illustrate our theory with examples from signaling pathways and genetic circuits. |
| Biological systems have been widely studied as complex dynamic systems that evolve with time in response to the internal resources abundance and external perturbations due to their common features. Integration of systems and synthetic biology provides a consolidated framework that draws system-level connections among biology, mathematics, engineering, and computer sciences. One major problem in current synthetic biology research is designing and controlling the synthetic circuits to perform reliable and robust behaviors as they utilize common transcription and translational resources among the circuits and host cells. While cellular resources are often limited, this results in a competition for resources by different genes and circuits, which affect the behaviors of synthetic genetic circuits. The manner competition impacts behavior depends on the “bottleneck” resource. With knowledge of physics laws and underlying mechanisms, the dynamical behaviors of the synthetic circuits can be described by the first principle models, usually represented by a system of ordinary differential equations (ODEs). In this work, we develop the novel embedded PINN (ePINN), which is composed of two nested loss-sharing neural networks to target and improve the unknown dynamics prediction from quantitative time series data. We apply the ePINN approach to identify the mathematical structures of competition phenotypes. Firstly, we use the PINNs approach to infer the model parameters and hidden dynamics from partially known data (including a lack of understanding of the reaction mechanisms or missing experimental data). Secondly, we test how well the algorithms can distinguish and extract the unknown dynamics from noisy data. Thirdly, we study how the synthetic and competing circuits behave in various cases when different particles become a limited resource. |
| Deep neural network autoencoders are routinely used computationally for model reduction. They allow recognizing the intrinsic dimension of data that lie in a k-dimensional subset K of an input Euclidean space $\R^n$. The underlying idea is to obtain both an encoding layer that maps $\R^n$ into $\R^k$ (called the bottleneck layer or the space of latent variables) and a decoding layer that maps $\R^k$ back into $\R^n$, in such a way that the input data from the set K is recovered when composing the two maps. This is achieved by adjusting parameters (weights) in the network to minimize the discrepancy between the input and the reconstructed output. Since neural networks (with continuous activation functions) compute continuous maps, the existence of a network that achieves perfect reconstruction would imply that K is homeomorphic to a k-dimensional subset of $\R^k$, so clearly there are topological obstructions to finding such a network. On the other hand, in practice the technique is found to "work" well, which leads one to ask if there is a way to explain this effectiveness. We show that, up to small errors, indeed the method is guaranteed to work. This is done by appealing to certain facts from differential geometry. A computational example is also included to illustrate the ideas. |
| We develop some basic principles for the design and robustness analysis of a continuous-time bilinear dynamical network, where an attacker can manipulate the strength of the interconnections/edges between some of the agents/nodes. We formulate the edge protection optimization problem of picking a limited number of attack-free edges and minimizing the impact of the attack over the bilinear dynamical network. In particular, the H2-norm of bilinear systems is known to capture robustness and performance properties analogous to its linear counterpart and provides valuable insights for identifying which edges arem ost sensitive to attacks. The exact optimization problem is combinatorial in the number of edges, and brute-force approaches show poor scalability. However, we show that the H2-norm as a cost function is supermodular and, therefore, allows for efficient greedy approximations of the optimal solution. We illustrate and compare the effectiveness of our theoretical findings via numerical simulation |
| Synthetic gene circuits require cellular resources, which are often limited. This leads to competition for resources by different genes, which alter a synthetic genetic circuit's behavior. However, the manner in which competition impacts behavior depends on the identity of the "bottleneck" resource which might be difficult to discern from input-output data. In this paper, we aim at classifying the mathematical structures of resource competition in biochemical circuits. We find that some competition structures can be distinguished by their response to different competitors or resource levels. Specifically, we show that some response curves are always linear, convex, or concave. Furthermore, high levels of certain resources protect the behavior from low competition, while others do not. We also show that competition phenotypes respond differently to various interventions. Such differences can be used to eliminate candidate competition mechanisms when constructing models based on given data. On the other hand, we show that different networks can display mathematically equivalent competition phenotypes. |
| Metastasis can occur after malignant cells transition from the epithelial phenotype to the mesenchymal phenotype. This transformation allows cells to migrate via the circulatory system and subsequently settle in distant organs after undergoing the reverse transition. The core gene regulatory network controlling these transitions consists of a system made up of coupled SNAIL/miRNA-34 and ZEB1/miRNA-200 subsystems. In this work, we formulate a mathematical model and analyze its long-term behavior. We start by developing a detailed reaction network with 24 state variables. Assuming fast promoter and mRNA kinetics, we then show how to reduce our model to a monotone four-dimensional system. For the reduced system, monotone dynamical systems theory can be used to prove generic convergence to the set of equilibria for all bounded trajectories. The theory does not apply to the full model, which is not monotone, but we briefly discuss results for singularly-perturbed monotone systems that provide a tool to extend convergence results from reduced to full systems, under appropriate time separation assumptions. |
| The emergence of and transitions between distinct phenotypes in isogenic cells can be attributed to the intricate interplay of epigenetic marks, external signals, and gene regulatory elements. These elements include chromatin remodelers, histone modifiers, transcription factors, and regulatory RNAs. Mathematical models known as Gene Regulatory Networks (GRNs) are an increasingly important tool to unravel the workings of such complex networks. In such models, epigenetic factors are usually proposed to act on the chromatin regions directly involved in the expression of relevant genes. However, it has been well-established that these factors operate globally and compete with each other for targets genome-wide. Therefore, a perturbation of the activity of a regulator can redistribute epigenetic marks across the genome and modulate the levels of competing regulators. In this paper, we propose a conceptual and mathematical modeling framework that incorporates both local and global competition effects between antagonistic epigenetic regulators in addition to local transcription factors, and show the counter-intuitive consequences of such interactions. We apply our approach to recent experimental findings on the Epithelial-Mesenchymal Transition (EMT). We show that it can explain the puzzling experimental data as well provide new verifiable predictions. |
| A design for genetically-encoded counters is proposed via repressor-based circuits. An N-bit counter reads sequences of input pulses and displays the total number of pulses, modulo $2^N$. The design is based on distributed computation, with specialized cell types allocated to specific tasks. This allows scalability and bypasses constraints on the maximal number of circuit genes per cell due to toxicity or failures due to resource limitations. The design starts with a single-bit counter. The N-bit counter is then obtained by interconnecting (using diffusible chemicals) a set of N single-bit counters and connector modules. An optimization framework is used to determine appropriate gate parameters and to compute bounds on admissible pulse widths and relaxation (inter-pulse) times, as well as to guide the construction of novel gates. This work can be viewed as a step toward obtaining circuits that are capable of finite-automaton computation, in analogy to digital central processing units. |
| This paper considers the following learning problem: given sample pairs of input and output signals generated by an unknown nonlinear system (which is not assumed to be causal or time-invariant), one wishes to find a continuous-time recurrent neural net, with activation function tanh, that approximately reproduces the underlying i/o behavior with high confidence. Leveraging earlier work concerned with matching derivatives up to a finite order of the input and output signals the problem is reformulated in familiar system-theoretic language and quantitative guarantees on the sup-norm risk of the learned model are derived, in terms of the number of neurons, the sample size, the number of derivatives being matched, and the regularity properties of the inputs, the outputs, and the unknown i/o map. |
| Long-term behaviors of biochemical reaction networks (BRNs) are described by steady states in deterministic models and stationary distributions in stochastic models. Unlike deterministic steady states, stationary distributions capturing inherent fluctuations of reactions are extremely difficult to derive analytically due to the curse of dimensionality. Here, we develop a method to derive analytic stationary distributions from deterministic steady states by transforming BRNs to have a special dynamic property, called complex balancing. Specifically, we merge nodes and edges of BRNs to match in- and out-flows of each node. This allows us to derive the stationary distributions of a large class of BRNs, including autophosphorylation networks of EGFR, PAK1, and Aurora B kinase and a genetic toggle switch. This reveals the unique properties of their stochastic dynamics such as robustness, sensitivity, and multimodality. Importantly, we provide a user-friendly computational package, CASTANET, that automatically derives symbolic expressions of the stationary distributions of BRNs to understand their long-term stochasticity. |
| An important goal of synthetic biology is to build biosensors and circuits with well-defined input-output relationships that operate at speeds found in natural biological systems. However, for molecular computation, most commonly used genetic circuit elements typically involve several steps from input detection to output signal production: transcription, translation, and post-translational modifications. These multiple steps together require up to several hours to respond to a single stimulus, and this limits the overall speed and complexity of genetic circuits. To address this gap, molecular frameworks that rely exclusively on post-translational steps to realize reaction networks that can process inputs at a time scale of seconds to minutes have been proposed. Here, we build mathematical models of fast biosensors capable of producing Boolean logic functionality. We employ protease-based chemical and light-induced switches, investigate their operation, and provide selection guidelines for their use as on-off switches. As a proof of concept, we implement a rapamycin-induced switch in vitro and demonstrate that its response qualitatively agrees with the predictions from our models. We then use these switches as elementary blocks, developing models for biosensors that can perform OR and XOR Boolean logic computation while using reaction conditions as tuning parameters. We use sensitivity analysis to determine the time-dependent sensitivity of the output to proteolytic and protein-protein binding reaction parameters. These fast protease-based biosensors can be used to implement complex molecular circuits with a capability of processing multiple inputs controllably and algorithmically. Our framework for evaluating and optimizing circuit performance can be applied to other molecular logic circuits. |
| This paper deals with the analysis of the dynamics of chemical reaction networks, developing a theoretical framework based only on graphical knowledge and applying regardless of the particular form of kinetics. This paper introduces a class of networks that are "structurally (mono) attractive", by which we mean that they are incapable of exhibiting multiple steady states, oscillation, or chaos by the virtue of their reaction graphs. These networks are characterized by the existence of a universal energy-like function which we call a Robust Lyapunov function (RLF). To find such functions, a finite set of rank-one linear systems is introduced, which form the extremals of a linear convex cone. The problem is then reduced to that of finding a common Lyapunov function for this set of extremals. Based on this characterization, a computational package, Lyapunov-Enabled Analysis of Reaction Networks (LEARN), is provided that constructs such functions or rules out their existence. An extensive study of biochemical networks demonstrates that LEARN offers a new unified framework. We study basic motifs, three-body binding, and transcriptional networks. We focus on cellular signalling networks including various post-translational modification cascades, phosphotransfer and phosphorelay networks, T-cell kinetic proofreading, ERK signaling, and the Ribosome Flow Model. |
| Starting in the early 2000s, sophisticated technologies have been developed for the rational construction of synthetic genetic networks that implement specified logical functionalities. Despite impressive progress, however, the scaling necessary in order to achieve greater computational power has been hampered by many constraints, including repressor toxicity and the lack of large sets of mutually-orthogonal repressors. As a consequence, a typical circuit contains no more than roughly seven repressor-based gates per cell. A possible way around this scalability problem is to distribute the computation among multiple cell types, which communicate among themselves using diffusible small molecules (DSMs) and each of which implements a small sub-circuit. Examples of DSMs are those employed by quorum sensing systems in bacteria. This paper focuses on systematic ways to implement this distributed approach, in the context of the evaluation of arbitrary Boolean functions. The unique characteristics of genetic circuits and the properties of DSMs require the development of new Boolean synthesis methods, distinct from those classically used in electronic circuit design. In this work, we propose a fast algorithm to synthesize distributed realizations for any Boolean function, under constraints on the number of gates per cell and the number of orthogonal DSMs. The method is based on an exact synthesis algorithm to find the minimal circuit per cell, which in turn allows us to build an extensive database of Boolean functions up to a given number of inputs. For concreteness, we will specifically focus on circuits of up to 4 inputs, which might represent, for example, two chemical inducers and two light inputs at different frequencies. Our method shows that, with a constraint of no more than seven gates per cell, the use of a single DSM increases the total number of realizable circuits by at least 7.58-fold compared to centralized computation. Moreover, when allowing two DSM's, one can realize 99.995\% of all possible 4-input Boolean functions, still with at most 7 gates per cell. The methodology introduced here can be readily adapted to complement recent genetic circuit design automation software. |
| Cell-fate networks are traditionally studied within the framework of gene regulatory networks. This paradigm considers only interactions of genes through expressed transcription factors and does not incorporate chromatin modification processes. This paper introduces a mathematical model that seamlessly combines gene regulatory networks and DNA methylation, with the goal of quantitatively characterizing the contribution of epigenetic regulation to gene silencing. The ``Basin of Attraction percentage'' is introduced as a metric to quantify gene silencing abilities. As a case study, a computational and theoretical analysis is carried out for a model of the pluripotent stem cell circuit as well as a simplified self-activating gene model. The results confirm that the methodology quantitatively captures the key role that methylation plays in enhancing the stability of the silenced gene state. |
| In biological processes such as embryonic development, hematopoietic cell differentiation, and the arising of tumor heterogeneity and consequent resistance to therapy, mechanisms of gene activation and deactivation may play a role in the emergence of phenotypically heterogeneous yet genetically identical (clonal) cellular populations. Mathematically, the variability in phenotypes in the absence of genetic variation can be modeled through the existence of multiple metastable attractors in nonlinear systems subject with stochastic switching, each one of them associated to an alternative epigenetic state. An important theoretical and practical question is that of estimating the number and location of these states, as well as their relative probabilities of occurrence. This paper focuses on a rigorous analytic characterization of multiple modes under slow promoter kinetics, which is a feature of epigenetic regulation. It characterizes the stationary distributions of Chemical Master Equations for gene regulatory networks as a mixture of Poisson distributions. As illustrations, the theory is used to tease out the role of cooperative binding in stochastic models in comparison to deterministic models, and applications are given to various model systems, such as toggle switches in isolation or in communicating populations and a trans-differentiation network. |
| The goal of many single-cell studies on eukaryotic cells is to gain insight into the biochemical reactions that control cell fate and state. This paper introduces the concept of effective stoichiometric space (ESS) to guide the reconstruction of biochemical networks from multiplexed, fixed time-point, single-cell data. In contrast to methods based solely on statistical models of data, the ESS method leverages the power of the geometric theory of toric varieties to begin unraveling the structure of chemical reaction networks (CRN). This application of toric theory enables a data-driven mapping of covariance relationships in single cell measurements into stoichiometric information, one in which each cell subpopulation has its associated ESS interpreted in terms of CRN theory. In the development of ESS we reframe certain aspects of the theory of CRN to better match data analysis. As an application of our approach we process cytomery- and image-based single-cell datasets and identify differences in cells treated with kinase inhibitors. Our approach is directly applicable to data acquired using readily accessible experimental methods such as Fluorescence Activated Cell Sorting (FACS) and multiplex immunofluorescence. |
| The study of stochastic biomolecular networks is a key part of systems biology, as such networks play a central role in engineered synthetic biology constructs as well as in naturally occurring cells. This expository paper reviews in a unified way a pair of recent approaches to the finite computation of statistics for chemical reaction networks. |
| What complicated dynamics can arise in the simplest biochemical systems, in response to a periodic input? This paper discusses two models that commonly appear as components of larger sensing and signal transduction pathways in systems biology: a simple two-species negative feedback loop, and a prototype nonlinear integral feedback. These systems have globally attracting steady states when unforced, yet, when subject to a periodic excitation, subharmonic responses and strange attractors can arise via period-doubling cascades. These behaviors are similar to those exhibited by classical forced nonlinear oscillators such as those described by van der Pol or Duffing equations. The lack of entrainment to external oscillations, in even the simplest biochemical networks, represents a level of additional complexity in molecular biology. |
| Biochemical reaction networks in cells frequently consist of reactions with disparate timescales. Stochastic simulations of such multiscale BRNs are prohibitively slow due to the high computational cost incurred in the simulations of fast reactions. One way to resolve this problem is to replace fast species by their stationary conditional expectation values conditioned on slow species. While various approximations schemes for this quasi-steady state approximation have been developed, they often lead to considerable errors. This paper considers two classes of multiscale BRNs which can be reduced by through an exact QSS rather than approximations. Specifically, we assume that fast species constitute either a feedforward network or a complex balanced network. Exact reductions for various examples are derived, and the computational advantages of this approach are illustrated through simulations. |
| Elucidating the structure of biological intracellular networks from experimental data remains a major challenge. This paper studies two types of ``response signatures'' to identify specific circuit motifs, from the observed response to periodic inputs. In particular, the objective is to distinguish negative feedback loops (NFLs) from incoherent feedforward loops (IFFLs), which are two types of circuits capable of producing exact adaptation. The theory of monotone systems with inputs is used to show that ``period skipping'' (non-harmonic responses) is ruled out in IFFL's, and a notion called ``refractory period stabilization'' is also analyzed. The approach is then applied to identify a circuit dominating cell cycle timing in yeast, and to uncover a calcium-mediated NFL circuit in \emph{C.elegans} olfactory sensory neurons. |
| Emergent responses of the immune system result from the integration of molecular and cellular networks over time and across multiple organs. High-content and high-throughput analysis technologies, concomitantly with data-driven and mechanistic modeling, hold promise for the systematic interrogation of these complex pathways. However, connecting genetic variation and molecular mechanisms to individual phenotypes and health outcomes has proven elusive. Gaps remain in data, and disagreements persist about the value of mechanistic modeling for immunology. This paper presents perspectives that emerged from the National Institute of Allergy and Infectious Disease (NIAID) workshop `Complex Systems Science, Modeling and Immunity' and subsequent discussions regarding the potential synergy of high-throughput data acquisition, data-driven modeling, and mechanistic modeling to define new mechanisms of immunological disease and to accelerate the translation of these insights into therapies. |
| Understanding how dynamical responses of biological networks are constrained by underlying network topology is one of the fundamental goals of systems biology. Here we employ monotone systems theory to formulate a theorem stating necessary conditions for non-monotonic time-response of a biochemical network to a monotonic stimulus. We apply this theorem to analyze the non-monotonic dynamics of the sigmaB-regulated glyoxylate shunt gene expression in Mycobacterium tuberculosis cells exposed to hypoxia. We first demonstrate that the known network structure is inconsistent with observed dynamics. To resolve this inconsistency we employ the formulated theorem, modeling simulations and optimization along with follow-up dynamic experimental measurements. We show a requirement for post-translational modulation of sigmaB activity in order to reconcile the network dynamics with its topology. The results of this analysis make testable experimental predictions and demonstrate wider applicability of the developed methodology to a wide class of biological systems. |
| This letter discusses a paper in the same journal which reported a method for reconstructing network topologies. Here we show that the method is a variant of a previously published method, modular response analysis. We also demonstrate that the implementation of the algorithm in that paper using statistical similarity measures as a proxy for global network responses to perturbations is erroneous and its performance is overestimated. |
| Reverse engineering of biological pathways involves an iterative process between experiments, data processing, and theoretical analysis. In this work, we engineer synthetic circuits, subject them to perturbations, and then infer network connections using a combination of nonparametric single-cell data resampling and modular response analysis. Intriguingly, we discover that recovered weights of specific network edges undergo divergent shifts under differential perturbations, and that the particular behavior is markedly different between different topologies. Investigating topological changes under differential perturbations may address the longstanding problem of discriminating direct and indirect connectivities in biological networks. |
| Chemical systems are inherently stochastic, as reactions depend on random (thermal) motion. This motivates the study of stochastic models, and specifically the Chemical Master Equation (CME), a discrete-space continuous-time Markov process that describes stochastic chemical kinetics. Exact studies using the CME are difficult, and several moment closure tools related to "mass fluctuation kinetics" and "fluctuation-dissipation" formulas can be used to obtain approximations of moments. This paper, in contrast, introduces a class of nonlinear chemical reaction networks for which exact computation is possible, by means of finite-dimensional linear differential equations. This class allows second and higher order reactions, but only under special assumptions on structure and/or conservation laws. |
| This paper gives conditions that guarantee spatial uniformity of the solutions of reaction-diffusion partial differential equations, stated in terms of the Jacobian matrix and Neumann eigenvalues of elliptic operators on the given spatial domain, and similar conditions for diffusively-coupled networks of ordinary differential equations. Also derived are numerical tests making use of linear matrix inequalities that are useful in certifying these conditions. |
| This paper describes a potential pitfall of perturbation-based approaches to network inference It is shows experimentally, and then explained mathematically, how even in the simplest signaling systems, perturbation methods may lead to paradoxical conclusions: for any given pair of two components X and Y, and depending upon the specific intervention on Y, either an activation or a repression of X could be inferred. The experiments are performed in an in vitro minimal system, thus isolating the effect and showing that it cannot be explained by feedbacks due to unknown intermediates; this system utilizes proteins from a pathway in mammalian (and other eukaryotic) cells that play a central role in proliferation, gene expression, differentiation, mitosis, cell survival, and apoptosis and is a perturbation target of contemporary therapies for various types of cancers. The results show that the simplistic view of intracellular signaling networks being made up of activation and repression links is seriously misleading, and call for a fundamental rethinking of signaling network analysis and inference methods. |
| This paper studies the direction of change of steady states to parameter perturbations in chemical reaction networks, and, in particular, to changes in conserved quantities. Theoretical considerations lead to the formulation of a computational procedure that provides a set of possible signs of such sensitivities. The procedure is purely algebraic and combinatorial, only using information on stoichiometry, and is independent of the values of kinetic constants. Two examples of important intracellular signal transduction models are worked out as an illustration. In these examples, the set of signs found is minimal, but there is no general guarantee that the set found will always be minimal in other examples. The paper also briefly discusses the relationship of the sign problem to the question of uniqueness of steady states in stoichiometry classes. |
| Complex networks of biochemical reactions, such as intracellular protein signaling pathways and genetic networks, are often conceptualized in terms of ``modules,'' semi-independent collections of components that perform a well-defined function and which may be incorporated in multiple pathways. However, due to sequestration of molecular messengers during interactions and other effects, collectively referred to as retroactivity, real biochemical systems do not exhibit perfect modularity. Biochemical signaling pathways can be insulated from impedance and competition effects, which inhibit modularity, through enzymatic ``futile cycles'' which consume energy, typically in the form of ATP. We hypothesize that better insulation necessarily requires higher energy consumption. We test this hypothesis through a combined theoretical and computational analysis of a simplified physical model of covalent cycles, using two innovative measures of insulation, as well as a new way to characterize optimal insulation through the balancing of these two measures in a Pareto sense. Our results indicate that indeed better insulation requires more energy. While insulation may facilitate evolution by enabling a modular ``plug and play'' interconnection architecture, allowing for the creation of new behaviors by adding targets to existing pathways, our work suggests that this potential benefit must be balanced against the metabolic costs of insulation necessarily incurred in not affecting the behavior of existing processes. |
| This paper studies networks of components, and shows that a contraction property on the interconnection matrix, coupled with contractivity of the individual component subsystems, suffices to insure contractivity of the overall system. |
| Synthetic biology efforts have largely focused on small engineered gene networks, yet understanding how to integrate multiple synthetic modules and interface them with endogenous pathways remains a challenge. Here we present the design, system integration, and analysis of several large scale synthetic gene circuits for artificial tissue homeostasis. Diabetes therapy represents a possible application for engineered homeostasis, where genetically programmed stem cells maintain a steady population of beta-cells despite continuous turnover. We develop a new iterative process that incorporates modular design principles with hierarchical performance optimization targeted for environments with uncertainty and incomplete information. We employ theoretical analysis and computational simulations of multicellular reaction/diffusion models to design and understand system behavior, and find that certain features often associated with robustness (e.g., multicellular synchronization and noise attenuation) are actually detrimental for tissue homeostasis. We overcome these problems by engineering a new class of genetic modules for 'synthetic cellular heterogeneity' that function to generate beneficial population diversity. We design two such modules (an asynchronous genetic oscillator and a signaling throttle mechanism), demonstrate their capacity for enhancing robust control, and provide guidance for experimental implementation with various computational techniques. We found that designing modules for synthetic heterogeneity can be complex, and in general requires a framework for non-linear and multifactorial analysis. Consequently, we adapt a 'phenotypic sensitivity analysis' method to determine how functional module behaviors combine to achieve optimal system performance. We ultimately combine this analysis with Bayesian network inference to extract critical, causal relationships between a module's biochemical rate-constants, its high level functional behavior in isolation, and its impact on overall system performance once integrated. |
| This paper studies a recently discovered remarkable feature that was shown in many adapting systems: scale invariance, which means that the initial, transient behavior stays approximately the same when the background signal level is scaled. Not every adapting system is scale-invariant: we investigate under which conditions a broadly used model of biochemical enzymatic networks will show scale invariant behavior. For all 3-node enzymatic networks, we performed a wide computational study to find candidates for scale invariance, among 16,038 possible topologies. This effort led us to discover a new necessary and sufficient mechanism that explains the behavior of all 3-node enzyme networks that have this property, which we call``uniform linearizations with fast output''. We also apply our theoretical results to a concrete biological example of order six, a model of the response of the chemotaxis signaling pathway of Dictyostelium discoideum to changes in chemoeffector cyclic adenosine monophosphate (cAMP). |
| This is a short expository article describing how the species-reaction graph (SR graph) can be used to analyze both multistability and monotonicity of biochemical networks. |
| Many reverse-engineering techniques in systems biology rely upon data on steady-state (or dynamic) perturbations --obtained from siRNA, gene knock-down or overexpression, kinase and phosphatase inhibitors, or other interventions-- in order to understand the interactions between different ``modules'' in a network. This paper first reviews one such popular such technique, introduced by the author and collaborators, and focuses on why conclusions drawn from its use may be misleading due to ``retroactivity'' (impedance or load) effects. A theoretical result characterizing stoichiometric-induced steady-state retroactivity effects is given for a class of biochemical networks. |
| In this paper, we introduce a topological redundancy measure for labeled directed networks that is formal, computationally efficient and applicable to a variety of directed networks such as cellular signaling, metabolic and social interaction networks. We demonstrate the computational efficiency of our measure by computing its value and statistical significance on a number of biological and social networks with up to several thousands of nodes and edges. Our results suggest a number of interesting observations: (1) social networks are more redundant that their biological counterparts, (2) transcriptional networks are less redundant than signaling networks, (3) the topological redundancy of the C. elegans metabolic network is largely due to its inclusion of currency metabolites, and (4) the redundancy of signaling networks is highly (negatively) correlated with monotonicity of their dynamics. |
| New checkable criteria for persistence of chemical reaction networks are proposed, which extend and complement existing ones. The new results allow the consideration of reaction rates which are time-varying, thus incorporating the effects of external signals, and also relax the assumption of existence of global conservation laws, thus allowing for inflows (production) and outflows (degradation). For time-invariant networks parameter-dependent conditions for persistence of certain classes of networks are provided. As an illustration, two networks arising in the systems biology literature are analyzed, namely a hypoxia and an apoptosis network. |
| Natural and synthetic biological networks must function reliably in the face of fluctuating stoichiometry of their molecular components. These fluctuations are caused in part by changes in relative expression efficiency and the DNA template amount of the network-coding genes. Gene product levels could potentially be decoupled from these changes via built-in adaptation mechanisms, thereby boosting network reliability. Here we show that a mechanism based on an incoherent feed-forward motif enables adaptive gene expression in mammalian cells. We modeled, synthesized, and tested transcriptional and post-transcriptional incoherent loops and found that in all cases the gene product adapts to changes in DNA template abundance. We also observed that the post-transcriptional form results in superior adaptation behavior, higher absolute expression levels, and lower intrinsic fluctuations. Our results support a previously-hypothesized endogenous role in gene dosage compensation for such motifs and suggest that their incorporation in synthetic networks will improve their robustness and reliability. |
| Biological signal transduction networks are commonly viewed as circuits that pass along in the process amplifying signals, enhancing sensitivity, or performing other signal-processing to transcriptional and other components. Here, we report on a "reverse-causality" phenomenon, which we call load-induced modulation. Through a combination of analytical and experimental tools, we discovered that signaling was modulated, in a surprising way, by downstream targets that receive the signal and, in doing so, apply what in physics is called a load. Specifically, we found that non-intuitive changes in response dynamics occurred for a covalent modification cycle when load was present. Loading altered the response time of a system, depending on whether the activity of one of the enzymes was maximal and the other was operating at its minimal rate or whether both enzymes were operating at submaximal rates. These two conditions, which we call "limit regime" and "intermediate regime," were associated with increased or decreased response times, respectively. The bandwidth, the range of frequency in which the system can process information, decreased in the presence of load, suggesting that downstream targets participate in establishing a balance between noise-filtering capabilities and a its ability to process high-frequency stimulation. Nodes in a signaling network are not independent relay devices, but rather are modulated by their downstream targets |
| We present a novel computational method, and related software, to synthesize signal transduction networks from single and double causal evidence. |
| This paper derives new results for certain classes of chemical reaction networks, linking structural to dynamical properties. In particular, it investigates their monotonicity and convergence without making assumptions on the form of the kinetics (e.g., mass-action) of the dynamical equations involved, and relying only on stoichiometric constraints. The key idea is to find an alternative representation under which the resulting system is monotone. As a simple example, the paper shows that a phosphorylation/dephosphorylation process, which is involved in many signaling cascades, has a global stability property. |
| This paper addresses the problem of giving conditions for transcriptional systems to be globally entrained to external periodic inputs. By using contraction theory, a powerful tool from dynamical systems theory, it is shown that certain systems driven by external periodic signals have the property that all solutions converge to fixed limit cycles. General results are proved, and the properties are verified in the specific case of some models of transcriptional systems. |
| This paper provides synchronization conditions for networks of nonlinear systems, where each component of the network itself consists of subsystems represented as operators in the extended L2 space. The synchronization conditions are provided by combining the input-output properties of the subsystems with information about the structure of network. The paper also explores results for state-space models as well as biochemical applications. The work is motivated by cellular networks where signaling occurs both internally, through interactions of species, and externally, through intercellular signaling. |
| Multivariate Poisson random variables subject to linear integer constraints arise in several application areas, such as queuing and biomolecular networks. This note shows how to compute conditional statistics in this context, by employing WZ Theory and associated algorithms. A symbolic computation package has been developed and is made freely available. A discussion of motivating biomolecular problems is also provided. |
| This is an expository paper about graph-theoretical properties of biochemical networks, discussing two approaches, one based on bipartite graphs and Petri net concepts, and another based on decompositions into order-preserving subsystems. Other papers on this website contain basically the same material. |
| Certain mass-action kinetics models of biochemical reaction networks, although described by nonlinear differential equations, may be partially viewed as state-dependent linear time-varying systems, which in turn may be modeled by convex compact valued positive linear differential inclusions. A result is provided on asymptotic stability of such inclusions, and applied to biochemical reaction networks with inflows and outflows. Included is also a characterization of exponential stability of general homogeneous switched systems |
| The concept of robustness of regulatory networks has been closely related to the nature of the interactions among genes, and the capability of pattern maintenance or reproducibility. Defining this robustness property is a challenging task, but mathematical models have often associated it to the volume of the space of admissible parameters. Not only the volume of the space but also its topology and geometry contain information on essential aspects of the network, including feasible pathways, switching between two parallel pathways or distinct/disconnected active regions of parameters. A method is presented here to characterize the space of admissible parameters, by writing it as a semi-algebraic set, and then theoretically analyzing its topology and geometry, as well as volume. This method provides a more objective and complete measure of the robustness of a developmental module. As a detailed case study, the segment polarity gene network is analyzed. |
| The concept of robustness of regulatory networks has received much attention in the last decade. One measure of robustness has been associated with the volume of the feasible region, namely, the region in the parameter space in which the system is functional. In recent work, we emphasized that topology and geometry matter, as well as volume. In this paper, and using the segment polarity gene network to illustrate our approach, we show that random walks in parameter space and how they exit the feasible region provide a rich perspective on the different modes of failure of a model. In particular, for the segment polarity network, we found that, between two alternative ways of activating Wingless, one is more robust. Our method provides a more complete measure of robustness to parameter variation. As a general modeling strategy, our approach is an interesting alternative to Boolean representation of biochemical networks. |
| In this expository paper, we provide a streamlined version of the key lemma on stability of interconnections due to Vidyasagar and Moylan and Hill, and then show how it its hypotheses may be verified for network structures of great interest in biology. |
| The transitive reduction problem is that of inferring a sparsest possible biological signal transduction network consistent with a set of experimental observations, with a goal to minimize false positive inferences even if risking false negatives. This paper provides computational complexity results as well as approximation algorithms with guaranteed performance. |
| In this note, we show how certain properties of Goldbeter's 1995 model for circadian oscillations can be proved mathematically, using techniques from the recently developed theory of monotone systems with inputs and outputs. The theory establishes global asymptotic stability, and in particular no oscillations, if the rate of transcription is somewhat smaller than that assumed by Goldbeter, based on the application of a tight small gain condition. This stability persists even under arbitrary delays in the feedback loop. On the other hand, when the condition is violated a Poincare'-Bendixson result allows to conclude existence of oscillations, for sufficiently high delays. |
| Strongly monotone systems of ordinary differential equations which have a certain translation-invariance property are shown to have the property that all projected solutions converge to a unique equilibrium. This result may be seen as a dual of a well-known theorem of Mierczynski for systems that satisfy a conservation law. As an application, it is shown that enzymatic futile cycles have a global convergence property. |
| This paper presents a stability test for a class of interconnected nonlinear systems motivated by biochemical reaction networks. One of the main results determines global asymptotic stability of the network from the diagonal stability of a "dissipativity matrix" which incorporates information about the passivity properties of the subsystems, the interconnection structure of the network, and the signs of the interconnection terms. This stability test encompasses the "secant criterion" for cyclic networks presented in our previous paper, and extends it to a general interconnection structure represented by a graph. A second main result allows one to accommodate state products. This extension makes the new stability criterion applicable to a broader class of models, even in the case of cyclic systems. The new stability test is illustrated on a mitogen activated protein kinase (MAPK) cascade model, and on a branched interconnection structure motivated by metabolic networks. Finally, another result addresses the robustness of stability in the presence of diffusion terms in a compartmental system made out of identical systems. |
| Modularity plays a fundamental role in the prediction of the behavior of a system from the behavior of its components, guaranteeing that the properties of individual components do not change upon interconnection. Just as electrical, hydraulic, and other physical systems often do not display modularity, nor do many biochemical systems, and specifically, genetic networks. Here, we study the effect of interconnections on the input/output dynamic characteristics of transcriptional components, focusing on a property, which we call "retroactivity," that plays a role analogous to non-zero output impedance in electrical systems. In transcriptional networks, retroactivity is large when the amount of transcription factor is comparable to, or smaller than, the amount of promoter binding sites, or when the affinity of such binding sites is high. In order to attenuate the effect of retroactivity, we propose a feedback mechanism inspired by the design of amplifiers in electronics. We introduce, in particular, a mechanism based on a phosphorylation/dephosphorylation cycle. This mechanism enjoys a remarkable insulation property, due to the fast time scales of the phosphorylation and dephosphorylation reactions. Such a mechanism, when viewed as a signal transduction system, has thus an inherent capacity to provide insulation and hence to increase the modularity of the system in which it is placed. |
| A class of distributed systems with a cyclic interconnection structure is considered. These systems arise in several biochemical applications and they can undergo diffusion driven instability which leads to a formation of spatially heterogeneous patterns. In this paper, a class of cyclic systems in which addition of diffusion does not have a destabilizing effect is identified. For these systems global stability results hold if the "secant" criterion is satisfied. In the linear case, it is shown that the secant condition is necessary and sufficient for the existence of a decoupled quadratic Lyapunov function, which extends a recent diagonal stability result to partial differential equations. For reaction-diffusion equations with nondecreasing coupling nonlinearities global asymptotic stability of the origin is established. All of the derived results remain true for both linear and nonlinear positive diffusion terms. Similar results are shown for compartmental systems. |
| This paper presents a software tool for inference and simplification of signal transduction networks. The method relies on the representation of observed indirect causal relationships as network paths, using techniques from combinatorial optimization to find the sparsest graph consistent with all experimental observations. We illustrate the biological usability of our software by applying it to a previously published signal transduction network and by using it to synthesize and simplify a novel network corresponding to activation-induced cell death in large granular lymphocyte leukemia. |
| We find that three intracellular regulatory networks contain far more positive "sign-consistent" feedback and feed-forward loops than negative loops. Negative inconsistent loops can be more easily removed from real regulatory network topologies compared to removing negative loops from shuffled networks. The abundance of positive feed-forward loops and feedback loops in real networks emerges from the presence of hubs that are enriched with either negative or positive links, and from the non-uniform connectivity distribution. Boolean dynamics applied to the signaling network further support the stability of its topology. These observations suggest that the "close-to-monotone" structure of intracellular regulatory networks may contribute to the dynamical stability observed in cellular behavior. |
| The ``reverse engineering problem'' in systems biology is that of unraveling of the web of interactions among the components of protein and gene regulatory networks, so as to map out the direct or local interactions among components. These direct interactions capture the topology of the functional network. An intrinsic difficulty in capturing these direct interactions, at least in intact cells, is that any perturbation to a particular gene or signaling component may rapidly propagate throughout the network, thus causing global changes which cannot be easily distinguished from direct effects. Thus, a major goal in reverse engineering is to use these observed global responses - such as steady-state changes in concentrations of active proteins, mRNA levels, or transcription rates - in order to infer the local interactions between individual nodes. One approach to solving this global-to-local problem is the ``Modular Response Analysis'' (MRA) method proposed in work of the author with Kholodenko et. al. (PNAS, 2002) and further elaborated in other papers. The basic method deals only with steady-state data. However, recently, quasi-steady state MRA has been used by Santos et. al. (Nature Cell Biology, 2007) for quantifying positive and negative feedback effects in the Raf/Mek/Erk MAPK network in rat adrenal pheochromocytoma (PC-12) cells. This paper presents an overview of the MRA technique, as well as a generalization of the algorithm to that quasi-steady state case. |
| Feedback loops play an important role in determining the dynamics of biological networks. In order to study the role of negative feedback loops, this paper introduces the notion of "distance to positive feedback (PF-distance)" which in essence captures the number of "independent" negative feedback loops in the network, a property inherent in the network topology. Through a computational study using Boolean networks it is shown that PF-distance has a strong influence on network dynamics and correlates very well with the number and length of limit cycles in the phase space of the network. To be precise, it is shown that, as the number of independent negative feedback loops increases, the number (length) of limit cycles tends to decrease (increase). These conclusions are consistent with the fact that certain natural biological networks exhibit generally regular behavior and have fewer negative feedback loops than randomized networks with the same numbers of nodes and connectivity. |
| This note studies the number of positive steady states in biomolecular reactions consisting of activation/deactivation futile cycles, such as those arising from phosphorylations and dephosphorylations at each level of a MAPK cascade. It is shown that: (1) for some parameter ranges, there are at least n+1 (if n is even) or n (if n is odd) steady states; (2) there never are more than 2n-1 steady states (so, for n=2, there are no more than 3 steady states); (3) for parameters near the standard Michaelis-Menten quasi-steady state conditions, there are at most n+1 steady states; and (4) for parameters far from the standard Michaelis-Menten quasi-steady state conditions, there is at most one steady state. |
| The theory of monotone dynamical systems has been found very useful in the modeling of some gene, protein, and signaling networks. In monotone systems, every net feedback loop is positive. On the other hand, negative feedback loops are important features of many systems, since they are required for adaptation and precision. This paper shows that, provided that these negative loops act at a comparatively fast time scale, the main dynamical property of (strongly) monotone systems, convergence to steady states, is still valid. An application is worked out to a double-phosphorylation "futile cycle" motif which plays a central role in eukaryotic cell signaling The workis heavily based on Fenichel-Jones geometric singular perturbation theory. |
| See abstract and pdf for ``Monotone and near-monotone biochemical networks''. |
| This paper introduces a new method of combined synthesis and inference of biological signal transduction networks. The main idea lies in representing observed causal relationships as network paths, and using techniques from combinatorial optimization to find the sparsest graph consistent with all experimental observations. The paper formalizes the approach, studies its computational complexity, proves new results for exact and approximate solutions of the computationally hard transitive reduction substep of the approach, validates the biological applicability by applying it to a previously published signal transduction network by Li et al., and shows that the algorithm for the transitive reduction substep performs well on graphs with a structure similar to those observed in transcriptional regulatory and signal transduction networks. |
| Persistency is the property, for differential equations in Rn, that solutions starting in the positive orthant do not approach the boundary. For chemical reactions and population models, this translates into the non-extinction property: provided that every species is present at the start of the reaction, no species will tend to be eliminated in the course of the reaction. This paper provides checkable conditions for persistence of chemical species in reaction networks, using concepts and tools from Petri net theory, and verifies these conditions on various systems which arise in the modeling of cell signaling pathways. |
| This paper studies a computational problem motivated by the modular response analysis method for reverse engineering of protein and gene networks. This set-cover problem is hard to solve exactly for large networks, but efficient approximation algorithms are given and their complexity is analyzed. |
| This paper investigates computational complexity aspects of a combinatorial problem that arises in the reverse engineering of protein and gene networks, showing relations to an appropriate set multicover problem with large "coverage" factor, and providing a non-trivial analysis of a simple randomized polynomial-time approximation algorithm for the problem. |
| A useful approach to the mathematical analysis of large-scale biological networks is based upon their decompositions into monotone dynamical systems. This paper deals with two computational problems associated to finding decompositions which are optimal in an appropriate sense. In graph-theoretic language, the problems can be recast in terms of maximal sign-consistent subgraphs. The theoretical results include polynomial-time approximation algorithms as well as constant-ratio inapproximability results. One of the algorithms, which has a worst-case guarantee of 87.9% from optimality, is based on the semidefinite programming relaxation approach of Goemans-Williamson. The algorithm was implemented and tested on a Drosophila segmentation network and an Epidermal Growth Factor Receptor pathway model. |
| This paper gives a theorem showing that a slow feedback adaptation, acting entirely analogously to the role of negative feedback for ordinary relaxation oscillations, leads to periodic orbits for bistable monotone systems. The proof is based upon a combination of i/o monotone systems theory and Conley Index theory. |
| It had previously been shown that generic cortical microcircuit models can perform complex real-time computations on continuous input streams, provided that these computations can be carried out with a rapidly fading memory. We investigate in this article the computational capability of such circuits in the more realistic case where not only readout neurons, but in addition a few neurons within the circuit have been trained for specific tasks. This is essentially equivalent to the case where the output of trained readout neurons is fed back into the circuit. We show that this new model overcomes the limitation of a rapidly fading memory. In fact, we prove that in the idealized case without noise it can carry out any conceivable digital or analog computation on time-varying inputs. But even with noise the resulting computational model can perform a large class of biologically relevant real-time computations that require a non-fading memory. |
| This paper provides an expository introduction to monotone and near-monotone biochemical network structures. Monotone systems respond in a predictable fashion to perturbations, and have very robust dynamical characteristics. This makes them reliable components of more complex networks, and suggests that natural biological systems may have evolved to be, if not monotone, at least close to monotone. In addition, interconnections of monotone systems may be fruitfully analyzed using tools from control theory. |
| We analyze certain chemical reaction networks and show that every solution converges to some steady state. The reaction kinetics are assumed to be monotone but otherwise arbitrary. When diffusion effects are taken into account, the conclusions remain unchanged. The main tools used in our analysis come from the theory of monotone dynamical systems. We review some of the features of this theory and provide a self-contained proof of a particular attractivity result which is used in proving our main result. |
| The network topology of neurons in the brain exhibits an abundance of feedback connections, but the computational function of these feedback connections is largely unknown. We present a computational theory that characterizes the gain in computational power achieved through feedback in dynamical systems with fading memory. It implies that many such systems acquire through feedback universal computational capabilities for analog computing with a non-fading memory. In particular, we show that feedback enables such systems to process time-varying input streams in diverse ways according to rules that are implemented through internal states of the dynamical system. In contrast to previous attractor-based computational models for neural networks, these flexible internal states are high-dimensional attractors of the circuit dynamics, that still allow the circuit state to absorb new information from online input streams. In this way one arrives at novel models for working memory, integration of evidence, and reward expectation in cortical circuits. We show that they are applicable to circuits of conductance-based Hodgkin-Huxley (HH) neurons with high levels of noise that reflect experimental data on invivo conditions. |
| This paper considers a class of systems with a cyclic structure that arises, among other examples, in dynamic models for certain biochemical reactions. We first show that a criterion for local stability, derived earlier in the literature, is in fact a necessary and sufficient condition for diagonal stability of the corresponding class of matrices. We then revisit a recent generalization of this criterion to output strictly passive systems, and recover the same stability condition using our diagonal stability result as a tool for constructing a Lyapunov function. Using this procedure for Lyapunov construction we exhibit classes of cyclic systems with sector nonlinearities and characterize their global stability properties. |
| A commonly employed measure of the signal amplification properties of an input/output system is its induced L2 norm, sometimes also known as H-infinity gain. In general, however, it is extremely difficult to compute the numerical value for this norm, or even to check that it is finite, unless the system being studied is linear. This paper describes a class of systems for which it is possible to reduce this computation to that of finding the norm of an associated linear system. In contrast to linearization approaches, a precise value, not an estimate, is obtained for the full nonlinear model. The class of systems that we study arose from the modeling of certain biological intracellular signaling cascades, but the results should be of wider applicability. |
| As a discrete approach to genetic regulatory networks, Boolean models provide an essential qualitative description of the structure of interactions among genes and proteins. Boolean models generally assume only two possible states (expressed or not expressed) for each gene or protein in the network as well as a high level of synchronization among the various regulatory processes. In this paper, we discuss and compare two possible methods of adapting qualitative models to incorporate the continuous-time character of regulatory networks. The first method consists of introducing asynchronous updates in the Boolean model. In the second method, we adopt the approach introduced by L. Glass to obtain a set of piecewise linear differential equations which continuously describe the states of each gene or protein in the network. We apply both methods to a particular example: a Boolean model of the segment polarity gene network of Drosophila melanogaster. We analyze the dynamics of the model, and provide a theoretical characterization of the model's gene pattern prediction as a function of the timescales of the various processes. |
| This paper further develops a method, originally introduced in a paper by Angeli and Sontag, for proving global attractivity of steady states in certain classes of dynamical systems. In this aproach, one views the given system as a negative feedback loop of a monotone controlled system. An auxiliary discrete system, whose global attractivity implies that of the original system, plays a key role in the theory, which is presented in a general Banach space setting. Applications are given to delay systems, as well as to systems with multiple inputs and outputs, and the question of expressing a given system in the required negative feedback form is addressed. |
| A generalization of the classical secant condition for the stability of cascades of scalar linear systems is provided for passive systems. The key is the introduction of a quantity that combines gain and phase information for each system in the cascade. For linear one-dimensional systems, the known result is recovered exactly. |
| We provide an almost-global stability result for a particular chemostat model, in which crowding effects are taken into consideration. The model can be rewritten as a negative feedback interconnection of two monotone i/o systems with well-defined characteristics, which allows the use of a small-gain theorem for feedback interconnections of monotone systems. This leads to a sufficient condition for almost-global stability, and we show that coexistence occurs in this model if the crowding effects are large enough. |
| We study a single species in a chemostat, limited by two nutrients, and separate nutrient uptake from growth. For a broad class of uptake and growth functions it is proved that a nontrivial equilibrium may exist. Moreover, if it exists it is unique and globally stable, generalizing a previous result by Legovic and Cruzado. |
| Biological complexity and limited quantitative measurements impose severe challenges to standard engineering methodologies for systems identification. This paper presents an approach, justified by the theory of universal inputs for distinguishability, based on replacing unmodeled dynamics by fictitious `dependent inputs'. The approach is particularly useful in validation experiments, because it allows one to fit model parameters to experimental data generated by a reference (wild-type) organism and then testing this model on data generated by a variation (mutant), so long as the mutations only affect the unmodeled dynamics that produce the dependent inputs. As a case study, this paper addresses the pathways that control the nitrogen uptake fluxes in baker's yeast Saccharomyces cerevisiae enabling it to optimally respond to changes in nitrogen availability. Well-defined perturbation experiments were performed on cells growing in steady-state. Time-series data of extracellular and intracellular metabolites were obtained, as well as mRNA levels. A nonlinear model was proposed, and shown to be structurally identifiable given input/output data. The identified model correctly predicted the responses of different yeast strains and different perturbations. |
| One of the fundamental problems of cell biology is the understanding of complex regulatory networks. Such networks are ubiquitous in cells, and knowledge of their properties is essential for the understanding of cellular behavior. This paper studies the effect of experimental uncertainty on the accuracy of the inferred structure of the networks determined using the method in "Untangling the wires: a novel strategy to trace functional interactions in signaling and gene networks". |
| Interactions between genes and gene products give rise to complex circuits that enable cells to process information and respond to external signals. Theoretical studies often describe these interactions using continuous, stochastic, or logical approaches. Here we propose a framework for gene regulatory networks that combines the intuitive appeal of a qualitative description of gene states with a high flexibility in incorporating stochasticity in the duration of cellular processes. We apply our methods to the regulatory network of the segment polarity genes, thus gaining novel insights into the development of gene expression patterns. For example, we show that very short synthesis and decay times can perturb the wild type pattern. On the other hand, separation of timescales between pre- and post-translational processes and a minimal prepattern ensure convergence to the wild type expression pattern regardless of fluctuations. |
| For feedback loops involving single input, single output monotone systems with well-defined I/O characteristics, a previous paper provided an approach to determining the location and stability of steady states. A result on global convergence for multistable systems followed as a consequence of the technique. The present paper extends the approach to multiple inputs and outputs. A key idea is the introduction of a reduced system which preserves local stability properties. New results characterizing strong monotonicity of feedback loops involving cascades are also presented. |
| This paper, prepared for a tutorial at the 2005 IEEE Conference on Decision and Control, presents an introduction to molecular systems biology and some associated problems in control theory. It provides an introduction to basic biological concepts, describes several questions in dynamics and control that arise in the field, and argues that new theoretical problems arise naturally in this context. A final section focuses on the combined use of graph-theoretic, qualitative knowledge about monotone building-blocks and steady-state step responses for components. |
| This paper deals with an almost global attractivity result for Lotka-Volterra systems with predator-prey interactions. These systems can be written as (negative) feedback systems. The subsystems of the feedback loop are monotone control systems, possessing particular input-output properties. We use a small-gain theorem, adapted to a context of systems with multiple equilibrium points to obtain the desired almost global attractivity result. It provides sufficient conditions to rule out oscillatory or more complicated behavior which is often observed in predator-prey systems. |
| One of the key ideas in control theory is that of viewing a complex dynamical system as an interconnection of simpler subsystems, thus deriving conclusions regarding the complete system from properties of its building blocks. Following this paradigm, and motivated by questions in molecular biology modeling, the authors have recently developed an approach based on components which are monotone systems with respect to partial orders in state and signal spaces. This paper presents a brief exposition of recent results, with an emphasis on small gain theorems for negative feedback, and the emergence of multistability and associated hysteresis effects under positive feedback. |
| Multistability is an important recurring theme in cell signaling, of particular relevance to biological systems that switch between discrete states, generate oscillatory responses, or "remember" transitory stimuli. Standard mathematical methods allow the detection of bistability in some very simple feedback systems (systems with one or two proteins or genes that either activate each other or inhibit each other), but realistic depictions of signal transduction networks are invariably much more complex than this. Here we show that for a class of feedback systems of arbitrary order, the stability properties of the system can be deduced mathematically from how the system behaves when feedback is blocked. Provided that this "open loop," feedback-blocked system is monotone and possesses a sigmoidal characteristic, the system is guaranteed to be bistable for some range of feedback strengths. We present a simple graphical method for deducing the stability behavior and bifurcation diagrams for such systems, and illustrate the method with two examples taken from recent experimental studies of bistable systems: a two-variable Cdc2/Wee1 system and a more complicated five-variable MAPK cascade. |
| This paper studies the emergence of multistability and hysteresis in those systems that arise, under positive feedback, from monotone systems with well-defined steady-state responses. Such feedback configurations appear routinely in several fields of application, and especially in biology. The results are stated in terms of directly checkable conditions which do not involve explicit knowledge of basins of attractions of each equilibria. |
| A small-gain theorem is presented for almost global stability of monotone control systems which are open-loop almost globally stable, when constant inputs are applied. The theorem assumes "negative feedback" interconnections. This typically destroys the monotonicity of the original flow and potentially destabilizes the resulting closed-loop system. |
| Weakly activated signaling cascades can be modeled as linear systems. The input-to-output transfer function and the internal gain of a linear system, provide natural measures for the propagation of the input signal down the cascade and for the characterization of the final outcome. The most efficient design of a cascade for generating sharp signals, is obtained by choosing all the off rates equal, and a "universal" finite optimal length. |
| This paper studies aspects of the dynamics of a conventional mechanism of ligand-receptor interactions, with a focus on the stability and location of steady-states. A theoretical framework is developed, and, as an application, a minimal parametrization is provided for models for two- or multi-state receptor interaction with ligand. In addition, an "affinity quotient" is introduced, which allows an elegant classification of ligands into agonists, neutral agonists, and inverse agonists. |
| We prove the global asymptotic stability of a well-known delayed negative-feedback model of testosterone dynamics, which has been proposed as a model of oscillatory behavior. We establish stability (and hence the impossibility of oscillations) even in the presence of delays of arbitrary length. |
| This paper takes a computational learning theory approach to a problem of linear systems identification. It is assumed that input signals have only a finite number k of frequency components, and systems to be identified have dimension no greater than n. The main result establishes that the sample complexity needed for identification scales polynomially with n and logarithmically with k. |
| This paper, addressed primarily to engineers and mathematicians with an interest in control theory, argues that entirely new theoretical problems arise naturally when addressing questions in the field of systems biology. Examples from the author's recent work are used to illustrate this point. |
| High-throughput technologies have facilitated the acquisition of large genomics and proteomics data sets. However, these data provide snapshots of cellular behavior, rather than help us reveal causal relations. Here, we propose how these technologies can be utilized to infer the topology and strengths of connections among genes, proteins, and metabolites by monitoring time-dependent responses of cellular networks to experimental interventions. We show that all connections leading to a given network node, e.g., to a particular gene, can be deduced from responses to perturbations none of which directly influences that node, e.g., using strains with knock-outs to other genes. To infer all interactions from stationary data, each node should be perturbed separately or in combination with other nodes. Monitoring time series provides richer information and does not require perturbations to all nodes. |
| Monotone systems constitute one of the most important classes of dynamical systems used in mathematical biology modeling. The objective of this paper is to extend the notion of monotonicity to systems with inputs and outputs, a necessary first step in trying to understand interconnections, especially including feedback loops, built up out of monotone components. Basic definitions and theorems are provided, as well as an application to the study of a model of one of the cell's most important subsystems. |
| In the early embryonic cell cycle, Cdc2-cyclin B functions like an autonomous oscillator, at whose core is a negative feedback loop: cyclins accumulate and produce active mitotic Cdc2-cyclin B Cdc2 activates the anaphase-promoting complex (APC); the APC then promotes cyclin degradation and resets Cdc2 to its inactive, interphase state. Cdc2 regulation also involves positive feedback4, with active Cdc2-cyclin B stimulating its activator Cdc25 and inactivating its inhibitors Wee1 and Myt1. Under the correct circumstances, these positive feedback loops could function as a bistable trigger for mitosis, and oscillators with bistable triggers may be particularly relevant to biological applications such as cell cycle regulation. This paper examined whether Cdc2 activation is bistable, confirming that the response of Cdc2 to non-degradable cyclin B is temporally abrupt and switchlike, as would be expected if Cdc2 activation were bistable. It is also shown that Cdc2 activation exhibits hysteresis, a property of bistable systems with particular relevance to biochemical oscillators. These findings help establish the basic systems-level logic of the mitotic oscillator. |
| This paper provides a necessary and sufficient condition for detectability, and an explicit construction of observers when this condition is satisfied, for chemical reaction networks of the Feinberg-Horn-Jackson zero deficiency type. |
| Emerging technologies have enabled the acquisition of large genomics and proteomics data sets. This paper proposes a novel quantitative method for determining functional interactions in cellular signaling and gene networks. It can be used to explore cell systems at a mechanistic level, or applied within a modular framework, which dramatically decreases the number of variables to be assayed. The topology and strength of network connections are retrieved from experimentally measured network responses to successive perturbations of all modules. In addition, the method can reveal functional interactions even when the components of the system are not all known, in which case some connections retrieved by the analysis will not be direct but correspond to the interaction routes through unidentified elements. The method is tested and illustrated using computer-generated responses of a modeled MAPK cascade and gene network. |
| errata for Structure and stability of certain chemical networks and applications to the kinetic proofreading model of T-cell receptor signal transduction |
| Given a set of differential equations whose description involves unknown parameters, such as reaction constants in chemical kinetics, and supposing that one may at any time measure the values of some of the variables and possibly apply external inputs to help excite the system, how many experiments are sufficient in order to obtain all the information that is potentially available about the parameters? This paper shows that the best possible answer (assuming exact measurements and real analiticity) is 2r+1 experiments, where r is the number of parameters. |
| This paper deals with the theory of structure, stability, robustness, and stabilization for an appealing class of nonlinear systems which arises in the analysis of chemical networks. The results given here extend, but are also heavily based upon, certain previous work by Feinberg, Horn, and Jackson, of which a self-contained and streamlined exposition is included. The theoretical conclusions are illustrated through an application to the kinetic proofreading model proposed by McKeithan for T-cell receptor signal transduction. |
| We analyze computations on temporal patterns and spatio-temporal patterns in formal network models whose temporal dynamics arises from empirically established quantitative models for short term dynamics at biological synapses. We give a complete characterization of all linear and nonlinear filters that can be approximated by such dynamic network models: it is the class of all filters that can be approximated by Volterra series. This characterization is shown to be rather stable with regard to changes in the model. For example it is shown that synaptic facilitation and one layer of neurons suffices for approximating arbitrary filters from this class. Our results provide a new complexity hierarchy for all filters that are approximable by Volterra series, which appears to be closer related to the actual cost of implementing such filters in neural hardware than preceding complexity measures. Our results also provide a new parameterization for approximations to such filters in terms of parameters that are arguable related to those that are tunable in biological neural systems. |
| We consider recurrent analog neural nets where the output of each gate is subject to Gaussian noise, or any other common noise distribution that is nonzero on a large set. We show that many regular languages cannot be recognized by networks of this type, and we give a precise characterization of those languages which can be recognized. This result implies severe constraints on possibilities for constructing recurrent analog neural nets that are robust against realistic types of analog noise. On the other hand we present a method for constructing feedforward analog neural nets that are robust with regard to analog noise of this type. |
| This paper studies controllability properties of recurrent neural networks. The new contributions are: (1) an extension of the result in "Complete controllability of continuous-time recurrent neural networks" to a slightly different model, where inputs appear in an affine form, (2) a formulation and proof of a necessary and sufficient condition, in terms of local-local controllability, and (3) a complete analysis of the 2-dimensional case for which the hypotheses made in previous work do not apply. |
| The Vapnik-Chervonenkis (VC) dimension is an integer which helps to characterize distribution-independent learning of binary concepts from positive and negative samples. This paper, based on lectures delivered at the Isaac Newton Institute in August of 1997, presents a brief introduction, establishes various elementary results, and discusses how to estimate the VC dimension in several examples of interest in neural network theory. (It does not address the learning and estimation-theoretic applications of VC dimension, and the applications to uniform convergence theorems for empirical probabilities, for which many suitable references are available.) |
| This paper provides lower and upper bounds for the VC dimension of recurrent networks. Several types of activation functions are discussed, including threshold, polynomial, piecewise-polynomial and sigmoidal functions. The bounds depend on two independent parameters: the number w of weights in the network, and the length k of the input sequence. Ignoring multiplicative constants, the main results say roughly the following: 1. For architectures whose activation is any fixed nonlinear polynomial, the VC dimension is proportional to wk. 2. For architectures whose activation is any fixed piecewise polynomial, the VC dimension is between wk and w**2k. 3. For architectures with threshold activations, the VC dimension is between wlog(k/w) and the smallest of wklog(wk) and w**2+wlog(wk). 4. For the standard sigmoid tanh(x), the VC dimension is between wk and w**4 k**2. |
| The following learning problem is considered, for continuous-time recurrent neural networks having sigmoidal activation functions. Given a ``black box'' representing an unknown system, measurements of output derivatives are collected, for a set of randomly generated inputs, and a network is used to approximate the observed behavior. It is shown that the number of inputs needed for reliable generalization (the sample complexity of the learning problem) is upper bounded by an expression that grows polynomially with the dimension of the network and logarithmically with the number of output derivatives being matched. |
| This paper provides an exposition of some recent results regarding system-theoretic aspects of continuous-time recurrent (dynamic) neural networks with sigmoidal activation functions. The class of systems is introduced and discussed, and a result is cited regarding their universal approximation properties. Known characterizations of controllability, observability, and parameter identifiability are reviewed, as well as a result on minimality. Facts regarding the computational power of recurrent nets are also mentioned. |
| This paper deals with sparse approximations by means of convex combinations of elements from a predetermined "basis" subset S of a function space. Specifically, the focus is on the rate at which the lowest achievable error can be reduced as larger subsets of S are allowed when constructing an approximant. The new results extend those given for Hilbert spaces by Jones and Barron, including in particular a computationally attractive incremental approximation scheme. Bounds are derived for broad classes of Banach spaces. The techniques used borrow from results regarding moduli of smoothness in functional analysis as well as from the theory of stochastic processes on function spaces. |
| This paper shows that neural networks which use continuous activation functions have VC dimension at least as large as the square of the number of weights w. This result settles the open question of whether whether the well-known O(w log w) bound, known for hard-threshold nets, also held for more general sigmoidal nets. Implications for the number of samples needed for valid generalization are discussed. |
| This paper suggests the use of Fourier-type activation functions in fully recurrent neural networks. The main theoretical advantage is that, in principle, the problem of recovering internal coefficients from input/output data is solvable in closed form. |
| For classes of concepts defined by certain classes of analytic functions depending on k parameters, there are nonempty open sets of samples of length 2k+2 which cannot be shattered. A slighly weaker result is also proved for piecewise-analytic functions. The special case of neural networks is discussed. |
| This paper presents a characterization of controllability for the class of control systems commonly called (continuous-time) recurrent neural networks. The characterization involves a simple condition on the input matrix, and is proved when the activation function is the hyperbolic tangent. |
| This paper deals with the problem of global stabilization of linear discrete time systems by means of bounded feedback laws. The main result proved is an analog of one proved for the continuous time case by the authors, and shows that such stabilization is possible if and only if the system is stabilizable with arbitrary controls and the transition matrix has spectral radius less or equal to one. The proof provides in principle an algorithm for the construction of such feedback laws, which can be implemented either as cascades or as parallel connections (``single hidden layer neural networks'') of simple saturation functions. |
| Recurrent perceptron classifiers generalize the usual perceptron model. They correspond to linear transformations of input vectors obtained by means of "autoregressive moving-average schemes", or infinite impulse response filters, and allow taking into account those correlations and dependences among input coordinates which arise from linear digital filtering. This paper provides tight bounds on sample complexity associated to the fitting of such models to experimental data. The results are expressed in the context of the theory of probably approximately correct (PAC) learning. |
| This paper deals with nonlinear least-squares problems involving the fitting to data of parameterized analytic functions. For generic regression data, a general result establishes the countability, and under stronger assumptions finiteness, of the set of functions giving rise to critical points of the quadratic loss function. In the special case of what are usually called "single-hidden layer neural networks", which are built upon the standard sigmoidal activation tanh(x) or equivalently 1/(1+exp(-x)), a rough upper bound for this cardinality is provided as well. |
| Blum and Rivest showed that any possible neural net learning algorithm based on fixed architectures faces severe computational barriers. This paper extends their NP-completeness result, which applied only to nets based on hard threshold activations, to nets that employ a particular continuous activation. In view of neural network practice, this is a more relevant result to understanding the limitations of backpropagation and related techniques. |
| This paper deals with finite size networks which consist of interconnections of synchronously evolving processors. Each processor updates its state by applying a "sigmoidal" function to a rational-coefficient linear combination of the previous states of all units. We prove that one may simulate all Turing Machines by such nets. In particular, one can simulate any multi-stack Turing Machine in real time, and there is a net made up of 886 processors which computes a universal partial-recursive function. Products (high order nets) are not required, contrary to what had been stated in the literature. Non-deterministic Turing Machines can be simulated by non-deterministic rational nets, also in real time. The simulation result has many consequences regarding the decidability, or more generally the complexity, of questions about recursive nets. |
| We examine the power of constant depth circuits with sigmoid threshold gates for computing boolean functions. It is shown that, for depth 2, constant size circuits of this type are strictly more powerful than constant size boolean threshold circuits (i.e. circuits with linear threshold gates). On the other hand it turns out that, for any constant depth d, polynomial size sigmoid threshold circuits with polynomially bounded weights compute exactly the same boolean functions as the corresponding circuits with linear threshold gates. |
| This paper concerns recurrent networks x'=s(Ax+Bu), y=Cx, where s is a sigmoid, in both discrete time and continuous time. Our main result is that observability can be characterized, if one assumes certain conditions on the nonlinearity and on the system, in a manner very analogous to that of the linear case. Recall that for the latter, observability is equivalent to the requirement that there not be any nontrivial A-invariant subspace included in the kernel of C. We show that the result generalizes in a natural manner, except that one now needs to restrict attention to certain special "coordinate" subspaces. |
| We consider recurrent networks with real-valued weights. If allowed exponential time for computation, they turn out to have unbounded power. However, under polynomial-time constraints there are limits on their capabilities, though being more powerful than Turing Machines. Moreover, there is a precise correspondence between nets and standard non-uniform circuits with equivalent resources, and as a consequence one has lower bound constraints on what they can compute. We note that these networks are not likely to solve polynomially NP-hard problems, as the equality "P=NP" in our model implies the almost complete collapse of the standard polynomial hierarchy. We show that a large class of different networks and dynamical system models have no more computational power than this neural (first-order) model with real weights. The results suggest the following Church-like Thesis of Time-bounded Analog Computing: "Any reasonable analog computer will have no more power (up to polynomial time) than first-order recurrent networks." |
| We present two constructions of controllers that globally stabilize linear systems subject to control saturation. We allow essentially arbitrary saturation functions. The only conditions imposed on the system are the obvious necessary ones, namely that no eigenvalues of the uncontrolled system have positive real part and that the standard stabilizability rank condition hold. One of the constructions is in terms of a "neural-network type" one-hidden layer architecture, while the other one is in terms of cascades of linear maps and saturations. |
| In this short expository survey, we sketch various known facts about uniqueness of weights in neural networks, including results about recurrent nets, and we provide a new and elementary complex-variable proof of a uniqueness result that applies in the single hidden layer case. |
| This paper has an expository introduction to two related topics: (a) Some mathematical results regarding "neural networks", and (b) so-called "neurocontrol" and "learning control" (each part can be read independently of the other). It was prepared for a short course given at the 1993 European Control Conference. |
| This paper shows that the weights of continuous-time feedback neural networks x'=s(Ax+Bu), y=Cx (where s is a sigmoid) are uniquely identifiable from input/output measurements. Under very weak genericity assumptions, the following is true: Assume given two nets, whose neurons all have the same nonlinear activation function s; if the two nets have equal behaviors as "black boxes" then necessarily they must have the same number of neurons and -except at most for sign reversals at each node- the same weights. Moreover, even if the activations are not a priori known to coincide, they are shown to be also essentially determined from the external measurements. |
| This paper compares the representational capabilities of one hidden layer and two hidden layer nets consisting of feedforward interconnections of linear threshold units. It is remarked that for certain problems two hidden layers are required, contrary to what might be in principle expected from the known approximation theorems. The differences are not based on numerical accuracy or number of units needed, nor on capabilities for feature extraction, but rather on a much more basic classification into "direct" and "inverse" problems. The former correspond to the approximation of continuous functions, while the latter are concerned with approximating one-sided inverses of continuous functions - and are often encountered in the context of inverse kinematics determination or in control questions. A general result is given showing that nonlinear control systems can be stabilized using two hidden layers, but not in general using just one. |
| This paper deals with single-hidden-layer feedforward nets, studying various aspects of classification power and interpolation capability. In particular, a worst-case analysis shows that direct input to output connections in threshold nets double the recognition but not the interpolation power, while using sigmoids rather than thresholds allows doubling both. For other measures of classification, including the Vapnik-Chervonenkis dimension, the effect of direct connections or sigmoidal activations is studied in the special case of two-dimensional inputs. |
| This paper surveys recent work by the author on learning and representational capabilities of feedforward nets. The learning results show that, among two possible variants of the so-called backpropagation training method for sigmoidal nets, both of which variants are used in practice, one is a better generalization of the older perceptron training algorithm than the other. The representation results show that nets consisting of sigmoidal neurons have at least twice the representational capabilities of nets that use classical threshold neurons, at least when this increase is quantified in terms of classification power. On the other hand, threshold nets are shown to be more useful when approximating implicit functions, as illustrated with an application to a typical control problem. |
| This paper shows the existence of a finite neural network, made up of sigmoidal neurons, which simulates a universal Turing machine. It is composed of less than 100,000 synchronously evolving processors, interconnected linearly. High-order connections are not required. (Note: this paper was placed here by special request. The results in this paper have been by now improved considerably: see the JCSS pape which among other aspects provides a polynomial time simulation. This paper, based on a unary encoding, results in an exponential slowdown). |
| Feedforward nets with sigmoidal activation functions are often designed by minimizing a cost criterion. It has been pointed out before that this technique may be outperformed by the classical perceptron learning rule, at least on some problems. In this paper, we show that no such pathologies can arise if the error criterion is of a threshold LMS type, i.e., is zero for values ``beyond'' the desired target values. More precisely, we show that if the data are linearly separable, and one considers nets with no hidden neurons, then an error function as above cannot have any local minima that are not global. In addition, the proof gives the following stronger result, under the stated hypotheses: the continuous gradient adjustment procedure is such that from any initial weight configuration a separating set of weights is obtained in finite time. This is a precise analogue of the Perceptron Learning Theorem. The results are then compared with the more classical pattern recognition problem of threshold LMS with linear activations, where no spurious local minima exist even for nonseparable data: here it is shown that even if using the threshold criterion, such bad local minima may occur, if the data are not separable and sigmoids are used. keywords = { neural networks , feedforward neural nets }, |
| Every dichotomy on a 2k-point set in Rn can be implemented by a neural net with a single hidden layer containing k sigmoidal neurons. If the neurons were of a hardlimiter (Heaviside) type, 2k-1 would be in general needed. |
| We give an example of a neural net without hidden layers and with a sigmoid transfer function, together with a training set of binary vectors, for which the sum of the squared errors, regarded as a function of the weights, has a local minimum which is not a global minimum. The example consists of a set of 125 training instances, with four weights and a threshold to be learnt. We do not know if substantially smaller binary examples exist. |
| Conference articles |
| In the context of epigenetic transformations in cancer metastasis, a puzzling effect was recently discovered, in which the elimination (knock-out) of an activating regulatory element leads to increased (rather than decreased) activity of the element being regulated. It has been postulated that this paradoxical behavior can be explained by activating and repressing transcription factors competing for binding to other possible targets. It is very difficult to prove this hypothesis in mammalian cells, due to the large number of potential players and the complexity of endogenous intracellular regulatory networks. Instead, this paper analyzes this issue through an analogous synthetic biology construct which aims to reproduce the paradoxical behavior using standard bacterial gene expression networks. The paper first reviews the motivating cancer biology work, and then describes a proposed synthetic construct. A mathematical model is formulated, and basic properties of uniqueness of steady states and convergence to equilibria are established, as well as an identification of parameter regimes which should lead to observing such paradoxical phenomena (more activator leads to less activity at steady state). A proof is also given to show that this is a steady-state property, and for initial transients the phenomenon will not be observed. This work adds to the general line of work of resource competition in synthetic circuits. |
| Motivated by the current interest in using Artificial intelligence (AI) tools in control design, this paper takes the first steps towards bridging results from gradient methods for solving the LQR control problem, and neural networks. More specifically, it looks into the case where one wants to find a Linear Feed-Forward Neural Network (LFFNN) that minimizes the Linear Quadratic Regulator (LQR) cost. This work develops gradient formulas that can be used to implement the training of LFFNNs to solve the LQR problem, and derives an important conservation law of the system. This conservation law is then leveraged to prove global convergence of solutions and invariance of the set of stabilizing networks under the training dynamics. These theoretical results are then followed by and extensive analysis of the simplest version of the problem (the ``scalar case'') and by numerical evidence of faster convergence of the training of general LFFNNs when compared to traditional direct gradient methods. These results not only serve as indication of the theoretical value of studying such a problem, but also of the practical value of LFFNNs as design tools for data-driven control applications. |
| Recent research in neural networks and machine learning suggests that using many more parameters than strictly required by the initial complexity of a regression problem can result in more accurate or faster-converging models -- contrary to classical statistical belief. This phenomenon, sometimes known as ``benign overfitting'', raises questions regarding in what other ways might overparameterization affect the properties of a learning problem. In this work, we investigate the effects of overfitting on the robustness of gradient-descent training when subject to uncertainty on the gradient estimation. This uncertainty arises naturally if the gradient is estimated from noisy data or directly measured. Our object of study is a linear neural network with a single, arbitrarily wide, hidden layer and an arbitrary number of inputs and outputs. In this paper we solve the problem for the case where the input and output of our neural-network are one-dimensional, deriving sufficient conditions for robustness of our system based on necessary and sufficient conditions for convergence in the undisturbed case. We then show that the general overparametrized formulation introduces a set of spurious equilibria which lay outside the set where the loss function is minimized, and discuss directions of future work that might extend our current results for more general formulations. |
| Systems theory can play an important in unveiling fundamental limitations of learning algorithms and architectures when used to control a dynamical system, and in suggesting strategies for overcoming these limitations. As an example, a feedforward neural network cannot stabilize a double integrator using output feedback. Similarly, a recurrent NN with differentiable activation functions that stabilizes a non-strongly stabilizable system must be itself open loop unstable, a fact that has profound implications for training with noisy, finite data. A potential solution to this problem, motivated by results on stabilization with periodic control, is the use of neural nets with periodic resets, showing that indeed systems theoretic analysis is instrumental in developing architectures capable of controlling certain classes of unstable systems. This short conference paper also argues that when the goal is to learn control oriented models, the loss function should reflect closed loop, rather than open loop model performance, a fact that can be accomplished by using gap-metric motivated loss functions. |
| In this paper, we investigate the problem of finding a sparse sensor and actuator (S/A) schedule that minimizes the approximation error between the input-output behavior of a fully sensed/actuated bilinear system and the system with the scheduling. The quality of this approximation is measuredby an H2-like metric, which is defined for a bilinear (time-varying) system with S/A scheduling based on the discrete Laplace transform of its Volterra kernels. First, we discuss the difficulties of designing S/A schedules for bilinear systems, which prevented us from finding a polynomial time algorithmfor solving the problem. We then propose a polynomial-time S/A scheduling heuristic that selects a fraction of sensors and node actuators at each time step while maintaining a small approximation error between the input-output behavior of thefully sensed/actuated system and the one with S/A scheduling in this H2-based sense. Numerical experiments illustrate the good approximation quality of our proposed methods. |
| In large-scale networks, agents and links are often vulnerable to attacks. This paper focuses on continuous-time bilinear networks, where additive disturbances model attacks or uncertainties on agents/states (node disturbances), and multiplicative disturbances model attacks or uncertainties on couplings between agents/states (link disturbances). It investigates network robustness notion in terms of the underlying digraph of the network, and structure of exogenous uncertainties and attacks. Specifically, it defines a robustness measure using the $\mathcal H_2$-norm of the network and calculates it in terms of the reachability Gramian of the bilinear system. The main result is that under certain conditions, the measure is supermodular over the set of all possible attacked links. The supermodular property facilitates the efficient solution finding of the optimization problem. Examples illustrate how different structures can make the system more or less vulnerable to malicious attacks on links. |
| When measuring importance of nodes in a network, the interconnections and dynamics are often supposed to be perfectly known. In this paper, we consider networks of agents with both uncertain couplings and dynamics. Network uncertainty is modeled by structured additive stochastic disturbances on each agent's update dynamics and coupling weights. We then study how these uncertainties change the network's centralities. Disturbances on the couplings between agents resul in bilinear dynamics, and classical centrality indices from linear network theory need to be redefined. To do that, we first show that, similarly to its linear counterpart, the squared H2 norm of bilinear systems measures the trace of the steady-state error covariance matrix subject to stochastic disturbances. This makes the H2 norm a natural candidate for a performance metric of the system. We propose a centrality index for the agents based on the H2 norm, and show how it depends on the network topology and the noise structure. Finally, we simulate a few graphs to illustrate how uncertainties on different couplings affect the agents' centrality rankings compared to a linearized model of the same system. |
| Cellular reprogramming is traditionally accomplished through an open loop control approach, wherein key transcription factors are injected in cells to steer a gene regulatory network toward a pluripotent state. Recently, a closed loop feedback control strategy was proposed in order to achieve more accurate control. Previous analyses of the controller were based on deterministic models, ignoring the substantial stochasticity in these networks, Here we analyze the Chemical Master Equation for reaction models with and without the feedback controller. We computationally and analytically investigate the performance of the controller in biologically relevant parameter regimes where stochastic effects dictate system dynamics. Our results indicate that the feedback control approach still ensures reprogramming even when analyzed using a stochastic model. |
| In the mathematical modeling of cell differentiation, it is common to think of internal states of cells (quanfitied by activation levels of certain genes) as determining different cell types. We study here the "PU.1/GATA-1 circuit" that controls the development of mature blood cells from hematopoietic stem cells (HSCs). We introduce a rigorous chemical reaction network model of the PU.1/GATA-1 circuit, which incorporates current biological knowledge and find that the resulting ODE model of these biomolecular reactions is incapable of exhibiting multistability, contradicting the fact that differentiation networks have, by definition, alternative stable steady states. When considering instead the stochastic version of this chemical network, we analytically construct the stationary distribution, and are able to show that this distribution is indeed capable of admitting a multiplicity of modes. Finally, we study how a judicious choice of system parameters serves to bias the probabilities towards different stationary states. We remark that certain changes in system parameters can be physically implemented by a biological feedback mechanism; tuning this feedback gives extra degrees of freedom that allow one to assign higher likelihood to some cell types over others. |
| This is a tutorial paper on control-theoretic methods for the analysis of biological systems. |
| We present conditions that guarantee spatial uniformity in diffusively-coupled systems. Diffusive coupling is a ubiquitous form of local interaction, arising in diverse areas including multiagent coordination and pattern formation in biochemical networks. The conditions we derive make use of the Jacobian matrix and Neumann eigenvalues of elliptic operators, and generalize and unify existing theory about asymptotic convergence of trajectories of reaction-diffusion partial differential equations as well as compartmental ordinary differential equations. We present numerical tests making use of linear matrix inequalities that may be used to certify these conditions. We discuss an example pertaining to electromechanical oscillators. The paper's main contributions are unified verifiable relaxed conditions that guarantee synchrony. |
| This is a conference version of ``A characterization of scale invariant responses in enzymatic networks. |
| Preliminary conference version of ''A contraction approach to the hierarchical analysis and design of networked systems''. |
| This is a very summarized version ofthe first part of the paper "Persistence results for chemical reaction networks with time-dependent kinetics and no global conservation laws". |
| See abstract and link to pdf in entry for Journal paper. |
| See abstract and link to pdf in entry for Journal paper. |
| This tutorial paper presents an introduction to systems and synthetic molecular biology. It provides an introduction to basic biological concepts, and describes some of the techniques as well as challenges in the analysis and design of biomolecular networks. |
| For distributed systems with a cyclic interconnection structure, a global stability result is shown to hold if the secant criterion is satisfied. |
| Strongly monotone systems of ordinary differential equations which have a certain translation-invariance property are shown to have the property that all projected solutions converge to a unique equilibrium. This result may be seen as a dual of a well-known theorem of Mierczynski for systems that satisfy a conservation law. As an application, it is shown that enzymatic futile cycles have a global convergence property. |
| This paper derives new results for certain classes of chemical reaction networks, linking structural to dynamical properties. In particular, it investigates their monotonicity and convergence without making assumptions on the structure (e.g., mass-action kinetics) of the dynamical equations involved, and relying only on stoichiometric constraints. The key idea is to find a suitable set of coordinates under which the resulting system is cooperative. As a simple example, the paper shows that a phosphorylation/dephosphorylation process, which is involved in many signaling cascades, has a global stability property. |
| This work is concerned with the study of the robustness and fragility of gene regulation networks to variability in the timescales of the distinct biological processes involved. It explores and compares two methods: introducing asynchronous updates in a Boolean model, or integrating the Boolean rules in a continuous, piecewise linear model. As an example, the segment polarity network of the fruit fly is analyzed. A theoretical characterization is given of the model's ability to predict the correct development of the segmented embryo, in terms of the specific timescales of the various regulation interactions. |
| This paper deals with global convergence to equilibria, and in particular Hirsch's generic convergence theorem for strongly monotone systems, for singular perturbations of monotone systems. |
| This paper deals with global convergence to equilibria, and in particular Hirsch's generic convergence theorem for strongly monotone systems, for singular perturbations of monotone systems. |
| We show how certain properties of Goldbeter's original 1995 model for circadian oscillations can be proved mathematically. We establish global asymptotic stability, and in particular no oscillations, if the rate of transcription is somewhat smaller than that assumed by Goldbeter, but, on the other hand, this stability persists even under arbitrary delays in the feedback loop. We are mainly interested in illustrating certain mathematical techniques, including the use of theorems concerning tridiagonal cooperative systems and the recently developed theory of monotone systems with inputs and outputs. |
| Monotone systems are dynamical systems for which the flow preserves a partial order. Some applications will be briefly reviewed in this paper. Much of the appeal of the class of monotone systems stems from the fact that roughly, most solutions converge to the set of equilibria. However, this usually requires a stronger monotonicity property which is not always satisfied or easy to check in applications. Following work of J.F. Jiang, we show that monotonicity is enough to conclude global attractivity if there is a unique equilibrium and if the state space satisfies a particular condition. The proof given here is self-contained and does not require the use of any of the results from the theory of monotone systems. We will illustrate it on a class of chemical reaction networks with monotone, but otherwise arbitrary, reaction kinetics. |
| Experimental data show that biological synapses are dynamic, i.e., their weight changes on a short time scale by several hundred percent in dependence of the past input to the synapse. In this article we explore the consequences that this synaptic dynamics entails for the computational power of feedforward neural networks. It turns out that even with just a single hidden layer such networks can approximate a surprisingly large large class of nonlinear filters: all filters that can be characterized by Volterra series. This result is robust with regard to various changes in the model for synaptic dynamics. Furthermore we show that simple gradient descent suffices to approximate a given quadratic filter by a rather small neural system with dynamic synapses. |
| This paper concerns recurrent networks x'=s(Ax+Bu), y=Cx, where s is a sigmoid, in both discrete time and continuous time. The paper establishes parameter identifiability under stronger assumptions on the activation than in "For neural networks, function determines form", but on the other hand deals with arbitrary (nonzero) initial states. |
| Recent work by H.T. Siegelmann and E.D. Sontag (1992) has demonstrated that polynomial time on linear saturated recurrent neural networks equals polynomial time on standard computational models: Turing machines if the weights of the net are rationals, and nonuniform circuits if the weights are real. Here, further connections between the languages recognized by such neural nets and other complexity classes are developed. Connections to space-bounded classes, simulation of parallel computational models such as Vector Machines, and a discussion of the characterizations of various nonuniform classes in terms of Kolmogorov complexity are presented. |
| This paper deals with analog circuits. It establishes the finiteness of VC dimension, teaching dimension, and several other measures of sample complexity which arise in learning theory. It also shows that the equivalence of behaviors, and the loading problem, are effectively decidable, modulo a widely believed conjecture in number theory. The results, the first ones that are independent of weight size, apply when the gate function is the "standard sigmoid" commonly used in neural networks research. The proofs rely on very recent developments in the elementary theory of real numbers with exponentiation. (Some weaker conclusions are also given for more general analytic gate functions.) Applications to learnability of sparse polynomials are also mentioned. |
| A conference paper. Placed here because it was requested, but contains little that is not also contained in the survey on neural nets mentioned above. |
| Given a 2-coloring of the vertices of a regular n-gon P, how many parallel lines are needed to separate the vertices into monochromatic subsets? We prove that floor(n/2) is a tight upper bound, and also provide an O(n log n) time algorithm to determine the direction that gives the minimum number of lines. If the polygon is a non-regular convex polygon, then n-3 lines may be necessary, while n-2 lines always suffice. This problem arises in machine learning and has implications about the representational capabilities of some neural networks. |
| We describe a speedup technique that uses extrapolatory methods to predict the weights in a Neural Network using Back Propagation (BP) learning. The method is based on empirical observations of the way the weights change as a function of time. We use numerical function fitting techniques to determine the parameters of an extrapolation function and then use this function to project weights into the future. Significant computational savings result by using the extrapolated weights to jump over many iterations of the standard algorithm, achieving comparable performance with fewer iterations. |
| Internal reports |
| Cell-fate networks are traditionally studied within the framework of gene regulatory networks. This paradigm considers only interactions of genes through expressed transcription factors and does not incorporate chromatin modification processes. This paper introduces a mathematical model that seamlessly combines gene regulatory networks and DNA methylation, with the goal of quantitatively characterizing the contribution of epigenetic regulation to gene silencing. The ``Basin of Attraction percentage'' is introduced as a metric to quantify gene silencing abilities. As a case study, a computational and theoretical analysis is carried out for a model of the pluripotent stem cell circuit as well as a simplified self-activating gene model. The results confirm that the methodology quantitatively captures the key role that methylation plays in enhancing the stability of the silenced gene state. |
| We consider a compartmental model for ribosome flow during RNA translation, the Ribosome Flow Model (RFM). This model includes a set of positive transition rates that control the flow from every site to the consecutive site. It has been shown that when these rates are time-varying and jointly T-periodic, the protein production rate converges to a unique T-periodic pattern. Here, we study a problem that can be roughly stated as: can periodic rates yield a higher average production rate than constant rates? We rigorously formulate this question and show via simulations, and rigorous analysis in one simple case, that the answer is no. |
| We review in a unified way results for two types of stochastic chemical reaction systems for which moments can be effectively computed: feedforward networks and complex-balanced networks. |
| The connection between optimal biological function and energy use, measured for example by the rate of metabolite consumption, is a current topic of interest in the systems biology literature which has been explored in several different contexts. In [J. P. Barton and E. D. Sontag, Biophys. J. 104, 6 (2013)], we related the metabolic cost of enzymatic futile cycles with their capacity to act as insulators which facilitate modular interconnections in biochemical networks. There we analyzed a simple model system in which a signal molecule regulates the transcription of one or more target proteins by interacting with their promoters. In this note, we consider the case of a protein with an active and an inactive form, and whose activation is controlled by the signal molecule. As in the original case, higher rates of energy consumption are required for better insulator performance. |
| Biochemical signaling pathways can be insulated from impedance and competition effects through enzymatic "futile cycles" which consume energy, typically in the form of ATP. We hypothesize that better insulation necessarily requires higher energy consumption, and provide evidence, through the computational analysis of a simplified physical model, to support this hypothesis. |
| This is a very old informal report that discusses the study of local minima of quadratic loss functions for fitting errors in sigmoidal neural net learning. It also includes several remarks concerning the growth of weights during gradient descent. There is nothing very interesting here - far better knowledge is now available - but the report was placed here by request. |
This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders.
This document was translated from BibTEX by bibtex2html