A defense-offense multi-layered regulatory switch in a pathogenic bacterium.

Cells adapt to environmental changes by efficiently adjusting gene expression programs. Staphylococcus aureus, an opportunistic pathogenic bacterium, switches between defensive and offensive modes in response to quorum sensing signal. We identified and studied the structural characteristics and dynamic properties of the core regulatory circuit governing this switch by deterministic and stochastic computational methods, as well as experimentally. This module, termed here Double Selector Switch (DSS), comprises the RNA regulator RNAIII and the transcription factor Rot, defining a double-layered switch involving both transcriptional and post-transcriptional regulations. It coordinates the inverse expression of two sets of target genes, immuno-modulators and exotoxins, expressed during the defensive and offensive modes, respectively. Our computational and experimental analyses show that the DSS guarantees fine-tuned coordination of the inverse expression of its two gene sets, tight regulation, and filtering of noisy signals. We also identified variants of this circuit in other bacterial systems, suggesting it is used as a molecular switch in various cellular contexts and offering its use as a template for an effective switching device in synthetic biology studies.

Global regulation of transcription by a small RNA: a quantitative view.

Small RNAs are integral regulators of bacterial gene expression, the majority of which act posttranscriptionally by basepairing with target mRNAs, altering translation or mRNA stability. 6S RNA, however, is a small RNA that is a transcriptional regulator, acting by binding directly to σ(70)-RNA polymerase (σ(70)-RNAP) and preventing its binding to gene promoters. At the transition from exponential to stationary phase, 6S RNA accumulates and globally downregulates the transcription of hundreds of genes. At the transition from stationary to exponential phase (outgrowth), 6S RNA is released from σ(70)-RNAP, resulting in a fast increase in free σ(70)-RNAP and transcription of many genes. The transition from stationary to exponential phase is sharp, and is thus accessible for experimental study. However, the transition from exponential to stationary phase is gradual and complicated by changes in other factors, making it more difficult to isolate 6S RNA effects experimentally at this transition. Here, we use mathematical modeling and simulation to study the dynamics of 6S RNA-dependent regulation, focusing on transitions in growth mediated by altered nutrient availability. We first show that our model reproduces the sharp increase in σ(70)-RNAP at outgrowth, as well as the behavior of two experimentally tested mutants, thus justifying its use for characterizing the less accessible dynamics of the transition from exponential to stationary phase. We characterize the dynamics of the two transitions for Escherichia coli wild-type, as well as for mutants with various 6S RNA-RNAP affinities, demonstrating that the 6S RNA regulation mechanism is generally robust to a wide range of such mutations, although the level of regulation at single promoters and their resulting expression fold change will be altered with changes in affinity. Our results provide insight into the potential advantage of transcription regulation by 6S RNA, as it enables storage and efficient release of σ(70)-RNAP during transitions in nutrient availability, which is likely to give a competitive advantage to cells encountering diverse environmental conditions.

Interactions between distant ceRNAs in regulatory networks.

Competing endogenous RNAs (ceRNAs) were recently introduced as RNA transcripts that affect each other's expression level through competition for their microRNA (miRNA) coregulators. This stems from the bidirectional effects between miRNAs and their target RNAs, where a change in the expression level of one target affects the level of the miRNA regulator, which in turn affects the level of other targets. By the same logic, miRNAs that share targets compete over binding to their common targets and therefore also exhibit ceRNA-like behavior. Taken together, perturbation effects could propagate in the posttranscriptional regulatory network through a path of coregulated targets and miRNAs that share targets, suggesting the existence of distant ceRNAs. Here we study the prevalence of distant ceRNAs and their effect in cellular networks. Analyzing the network of miRNA-target interactions deciphered experimentally in HEK293 cells, we show that it is a dense, intertwined network, suggesting that many nodes can act as distant ceRNAs of one another. Indeed, using gene expression data from a perturbation experiment, we demonstrate small, yet statistically significant, changes in gene expression caused by distant ceRNAs in that network. We further characterize the magnitude of the propagated perturbation effect and the parameters affecting it by mathematical modeling and simulations. Our results show that the magnitude of the effect depends on the generation and degradation rates of involved miRNAs and targets, their interaction rates, the distance between the ceRNAs and the topology of the network. Although demonstrated for a miRNA-mRNA regulatory network, our results offer what to our knowledge is a new view on various posttranscriptional cellular networks, expanding the concept of ceRNAs and implying possible distant cross talk within the network, with consequences for the interpretation of indirect effects of gene perturbation.

Regulation of phenotypic variability by a threshold-based mechanism underlies bacterial persistence.

In the face of antibiotics, bacterial populations avoid extinction by harboring a subpopulation of dormant cells that are largely drug insensitive. This phenomenon, termed "persistence," is a major obstacle for the treatment of a number of infectious diseases. The mechanism that generates both actively growing as well as dormant cells within a genetically identical population is unknown. We present a detailed study of the toxin-antitoxin module implicated in antibiotic persistence of Escherichia coli. We find that bacterial cells become dormant if the toxin level is higher than a threshold, and that the amount by which the threshold is exceeded determines the duration of dormancy. Fluctuations in toxin levels above and below the threshold result in coexistence of dormant and growing cells. We conclude that toxin-antitoxin modules in general represent a mixed network motif that can serve to produce a subpopulation of dormant cells and to supply a mechanism for regulating the frequency and duration of growth arrest. Toxin-antitoxin modules thus provide a natural molecular design for implementing a bet-hedging strategy.

Distribution of shortest path lengths on trees of a given size in subcritical Erdos-Rényi networks.

In the subcritical regime Erdos-Rényi (ER) networks consist of finite tree components, which are nonextensive in the network size. The distribution of shortest path lengths (DSPL) of subcritical ER networks was recently calculated using a topological expansion [E. Katzav, O. Biham, and A. K. Hartmann, Phys. Rev. E 98, 012301 (2018)2470-004510.1103/PhysRevE.98.012301]. The DSPL, which accounts for the distance ℓ between any pair of nodes that reside on the same finite tree component, was found to follow a geometric distribution of the form P(L=ℓ|L<∞)=(1-c)c^{ℓ-1}, where 0

Distribution of the number of cycles in directed and undirected random regular graphs of degree 2.

We present analytical results for the distribution of the number of cycles in directed and undirected random 2-regular graphs (2-RRGs) consisting of N nodes. In directed 2-RRGs each node has one inbound link and one outbound link, while in undirected 2-RRGs each node has two undirected links. Since all the nodes are of degree k=2, the resulting networks consist of cycles. These cycles exhibit a broad spectrum of lengths, where the average length of the shortest cycle in a random network instance scales with lnN, while the length of the longest cycle scales with N. The number of cycles varies between different network instances in the ensemble, where the mean number of cycles 〈S〉 scales with lnN. Here we present exact analytical results for the distribution P_{N}(S=s) of the number of cycles s in ensembles of directed and undirected 2-RRGs, expressed in terms of the Stirling numbers of the first kind. In both cases the distributions converge to a Poisson distribution in the large N limit. The moments and cumulants of P_{N}(S=s) are also calculated. The statistical properties of directed 2-RRGs are equivalent to the combinatorics of cycles in random permutations of N objects. In this context our results recover and extend known results. In contrast, the statistical properties of cycles in undirected 2-RRGs have not been studied before.

Competition between small RNAs: a quantitative view.

Two major classes of small regulatory RNAs--small interfering RNAs (siRNAs) and microRNA (miRNAs)--are involved in a common RNA interference processing pathway. Small RNAs within each of these families were found to compete for limiting amounts of shared components, required for their biogenesis and processing. Association with Argonaute (Ago), the catalytic component of the RNA silencing complex, was suggested as the central mechanistic point in RNA interference machinery competition. Aiming to better understand the competition between small RNAs in the cell, we present a mathematical model and characterize a range of specific cell and experimental parameters affecting the competition. We apply the model to competition between miRNAs and study the change in the expression level of their target genes under a variety of conditions. We show quantitatively that the amount of Ago and miRNAs in the cell are dominant factors contributing greatly to the competition. Interestingly, we observe what to our knowledge is a novel type of competition that takes place when Ago is abundant, by which miRNAs with shared targets compete over them. Furthermore, we use the model to examine different interaction mechanisms that might operate in establishing the miRNA-Ago complexes, mainly those related to their stability and recycling. Our model provides a mathematical framework for future studies of competition effects in regulation mechanisms involving small RNAs.

Structure of networks that evolve under a combination of growth and contraction.

We present analytical results for the emerging structure of networks that evolve via a combination of growth (by node addition and random attachment) and contraction (by random node deletion). To this end we consider a network model in which at each time step a node addition and random attachment step takes place with probability P_{add} and a random node deletion step takes place with probability P_{del}=1-P_{add}. The balance between the growth and contraction processes is captured by the parameter η=P_{add}-P_{del}. The case of pure network growth is described by η=1. In the case that 0<η<1, the rate of node addition exceeds the rate of node deletion and the overall process is of network growth. In the opposite case, where -1<η<0, the overall process is of network contraction, while in the special case of η=0 the expected size of the network remains fixed, apart from fluctuations. Using the master equation and the generating function formalism, we obtain a closed-form expression for the time-dependent degree distribution P_{t}(k). The degree distribution P_{t}(k) includes a term that depends on the initial degree distribution P_{0}(k), which decays as time evolves, and an asymptotic distribution P_{st}(k) which is independent of the initial condition. In the case of pure network growth (η=1), the asymptotic distribution P_{st}(k) follows an exponential distribution, while for -1<η<1 it consists of a sum of Poisson-like terms and exhibits a Poisson-like tail. In the case of overall network growth (0<η<1) the degree distribution P_{t}(k) eventually converges to P_{st}(k). In the case of overall network contraction (-1<η<0) we identify two different regimes. For -1/3<η<0 the degree distribution P_{t}(k) quickly converges towards P_{st}(k). In contrast, for -1<η<-1/3 the convergence of P_{t}(k) is initially very slow and it gets closer to P_{st}(k) only shortly before the network vanishes. Thus, the model exhibits three phase transitions: a structural transition between two functional forms of P_{st}(k) at η=1, a transition between an overall growth and overall contraction at η=0, and a dynamical transition between fast and slow convergence towards P_{st}(k) at η=-1/3. The analytical results are found to be in very good agreement with the results obtained from computer simulations.

Binomial moment equations for stochastic reaction systems.

A highly efficient formulation of moment equations for stochastic reaction networks is introduced. It is based on a set of binomial moments that capture the combinatorics of the reaction processes. The resulting set of equations can be easily truncated to include moments up to any desired order. The number of equations is dramatically reduced compared to the master equation. This formulation enables the simulation of complex reaction networks, involving a large number of reactive species much beyond the feasibility limit of any existing method. It provides an equation-based paradigm to the analysis of stochastic networks, complementing the commonly used Monte Carlo simulations.

Fate of articulation points and bredges in percolation.

We investigate the statistics of articulation points and bredges (bridge edges) in complex networks in which bonds are randomly removed in a percolation process. Because of the heterogeneous structure of a complex network, the probability of a node to be an articulation point or the probability of an edge to be a bredge will not be homogeneous across the network. We therefore analyze full distributions of articulation point probabilities as well as bredge probabilities, using a message-passing or cavity approach to the problem. Our methods allow us to obtain these distributions both for large single instances of networks and for ensembles of networks in the configuration model class in the thermodynamic limit, through a single unified approach. We also evaluate deconvolutions of these distributions according to degrees of the node or the degrees of both adjacent nodes in the case of bredges. We obtain closed form expressions for the large mean degree limit of Erdos-Rényi networks. Moreover, we reveal and are able to rationalize a significant amount of structure in the evolution of articulation point and bredge probabilities in response to random bond removal. We find that full distributions of articulation point and bredge probabilities in real networks and in their randomized counterparts may exhibit significant differences even where average articulation point and bredge probabilities do not. We argue that our results could be exploited in a variety of applications, including approaches to network dismantling or to vaccination and islanding strategies to prevent the spread of epidemics or of blackouts in process networks.

Interaction of atomic and molecular hydrogen with tholin surfaces at low temperatures.

We study the interaction of atomic and molecular hydrogen with a surface of tholin, a man-made polymer considered to be an analogue of aerosol particles present in Titan's atmosphere, using thermal programmed desorption at low temperatures below 30 K. The results are fitted and analyzed using a fine-grained rate equation model that describes the diffusion, reaction, and desorption processes. We obtain the energy barriers for diffusion and desorption of atomic and molecular hydrogen. These barriers are found to be in the range of 30-60 meV, indicating that atom/molecule-surface interactions in this temperature range are dominated by weak adsorption forces. The implications of these results for the understanding of the atmospheric chemistry of Titan are discussed.

Analysis of the convergence of the degree distribution of contracting random networks towards a Poisson distribution using the relative entropy.

We present analytical results for the structural evolution of random networks undergoing contraction processes via generic node deletion scenarios, namely, random deletion, preferential deletion, and propagating deletion. Focusing on configuration model networks, which exhibit a given degree distribution P_{0}(k) and no correlations, we show using a rigorous argument that upon contraction the degree distributions of these networks converge towards a Poisson distribution. To this end, we use the relative entropy S_{t}=S[P_{t}(k)||π(k|〈K〉_{t})] of the degree distribution P_{t}(k) of the contracting network at time t with respect to the corresponding Poisson distribution π(k|〈K〉_{t}) with the same mean degree 〈K〉_{t} as a distance measure between P_{t}(k) and Poisson. The relative entropy is suitable as a distance measure since it satisfies S_{t}≥0 for any degree distribution P_{t}(k), while equality is obtained only for P_{t}(k)=π(k|〈K〉_{t}). We derive an equation for the time derivative dS_{t}/dt during network contraction and show that the relative entropy decreases monotonically to zero during the contraction process. We thus conclude that the degree distributions of contracting configuration model networks converge towards a Poisson distribution. Since the contracting networks remain uncorrelated, this means that their structures converge towards an Erdos-Rényi (ER) graph structure, substantiating earlier results obtained using direct integration of the master equation and computer simulations [Tishby et al., Phys. Rev. E 100, 032314 (2019)2470-004510.1103/PhysRevE.100.032314]. We demonstrate the convergence for configuration model networks with degenerate degree distributions (random regular graphs), exponential degree distributions, and power-law degree distributions (scale-free networks).

Statistical analysis of edges and bredges in configuration model networks.

A bredge (bridge-edge) in a network is an edge whose deletion would split the network component on which it resides into two separate components. Bredges are vulnerable links that play an important role in network collapse processes, which may result from node or link failures, attacks, or epidemics. Therefore, the abundance and properties of bredges affect the resilience of the network to these collapse scenarios. We present analytical results for the statistical properties of bredges in configuration model networks. Using a generating function approach based on the cavity method, we calculate the probability P[over ̂](e∈B) that a random edge e in a configuration model network with degree distribution P(k) is a bredge (B). We also calculate the joint degree distribution P[over ̂](k,k^{'}|B) of the end-nodes i and i^{'} of a random bredge. We examine the distinct properties of bredges on the giant component (GC) and on the finite tree components (FC) of the network. On the finite components all the edges are bredges and there are no degree-degree correlations. We calculate the probability P[over ̂](e∈B|GC) that a random edge on the giant component is a bredge. We also calculate the joint degree distribution P[over ̂](k,k^{'}|B,GC) of the end-nodes of bredges and the joint degree distribution P[over ̂](k,k^{'}|NB,GC) of the end-nodes of nonbredge edges on the giant component. Surprisingly, it is found that the degrees k and k^{'} of the end-nodes of bredges are correlated, while the degrees of the end-nodes of nonbredge edges are uncorrelated. We thus conclude that all the degree-degree correlations on the giant component are concentrated on the bredges. We calculate the covariance Γ(B,GC) of the joint degree distribution of end-nodes of bredges and show it is negative, namely bredges tend to connect high degree nodes to low degree nodes. We apply this analysis to ensembles of configuration model networks with degree distributions that follow a Poisson distribution (Erdos-Rényi networks), an exponential distribution and a power-law distribution (scale-free networks). The implications of these results are discussed in the context of common attack scenarios and network dismantling processes.

Convergence towards an Erdos-Rényi graph structure in network contraction processes.

In a highly influential paper twenty years ago, Barabási and Albert [Science 286, 509 (1999)SCIEAS0036-807510.1126/science.286.5439.509] showed that networks undergoing generic growth processes with preferential attachment evolve towards scale-free structures. In any finite system, the growth eventually stalls and is likely to be followed by a phase of network contraction due to node failures, attacks, or epidemics. Using the master equation formulation and computer simulations, we analyze the structural evolution of networks subjected to contraction processes via random, preferential, and propagating node deletions. We show that the contracting networks converge towards an Erdos-Rényi network structure whose mean degree continues to decrease as the contraction proceeds. This is manifested by the convergence of the degree distribution towards a Poisson distribution and the loss of degree-degree correlations.

Generating random networks that consist of a single connected component with a given degree distribution.

We present a method for the construction of ensembles of random networks that consist of a single connected component with a given degree distribution. This approach extends the construction toolbox of random networks beyond the configuration model framework, in which one controls the degree distribution but not the number of components and their sizes. Unlike configuration model networks, which are completely uncorrelated, the resulting single-component networks exhibit degree-degree correlations. Moreover, they are found to be disassortative, namely, high-degree nodes tend to connect to low-degree nodes and vice versa. We demonstrate the method for single-component networks with ternary, exponential, and power-law degree distributions.

Regulation of gene expression by small non-coding RNAs: a quantitative view.

The importance of post-transcriptional regulation by small non-coding RNAs has recently been recognized in both pro- and eukaryotes. Small RNAs (sRNAs) regulate gene expression post-transcriptionally by base pairing with the mRNA. Here we use dynamical simulations to characterize this regulation mode in comparison to transcriptional regulation mediated by protein-DNA interaction and to post-translational regulation achieved by protein-protein interaction. We show quantitatively that regulation by sRNA is advantageous when fast responses to external signals are needed, consistent with experimental data about its involvement in stress responses. Our analysis indicates that the half-life of the sRNA-mRNA complex and the ratio of their production rates determine the steady-state level of the target protein, suggesting that regulation by sRNA may provide fine-tuning of gene expression. We also describe the network of regulation by sRNA in Escherichia coli, and integrate it with the transcription regulation network, uncovering mixed regulatory circuits, such as mixed feed-forward loops. The integration of sRNAs in feed-forward loops provides tight repression, guaranteed by the combination of transcriptional and post-transcriptional regulations.

Validity of rate equation results for reaction rates in reaction networks with fluctuations.

Systems of reacting particles, which are well mixed or distributed homogeneously in space, are commonly modeled by deterministic rate equations. These equations, which are based on the mean-field approximation, are valid for macroscopic systems. However, they neglect fluctuations in the particle populations. As a result, under conditions of strong fluctuations, the reaction rates obtained from the rate equations are highly inaccurate. To account for the fluctuations, stochastic methods are required. However, these methods are computationally intensive and may become infeasible for complex reaction networks. Therefore, it is useful to identify the conditions under which the rate equations provide accurate results. Naively, one expects strong fluctuations when the average population sizes of some of the reactants are of order one or lower. Here we present a systematic approach, for testing the validity of the rate equations, in which we define characteristic scales in terms of the rate constants of the network. We show that the rate equations fail to accurately reproduce the reaction rates when the system size is reduced below these scales. Surprisingly, the rate equations are found to be applicable in a wider range than expected. Their validity depends not only on the population sizes of the reactive species but also on the kinetic properties of the reaction network.

Calculation of switching times in the genetic toggle switch and other bistable systems.

Genetic circuits with feedback such as the toggle switch often exhibit bistability, namely, two stable states with rare spontaneous transitions between them. These systems can be characterized by the average time between such transitions (referred to as the switching time). However, commonly used deterministic models, based on rate equations, do not account for these fluctuation-induced transitions. Stochastic methods, such as the direct integration of the master equation, do account for the transitions. However, they cannot be used to evaluate the switching time. In order to obtain the switching time, one needs to use Monte Carlo simulations. These methods require the accumulation of statistical data, which limits their accuracy. They may become infeasible when the switching time is long. Here we present an accurate and efficient method for the calculation of the switching time. The method consists of coupled recursion equations for the transition times between microscopic states of the system. Using a suitable definition of the two macroscopic bistable states (in terms of the microscopic states) and the probabilities obtained from the master equation, the method provides the switching time between the two states of the system. The method is demonstrated for the genetic toggle switch. It can be used to evaluate the switching times in a broad range of bistable and multistable systems. We also show that it is suitable for the evaluation of the oscillation periods in oscillatory systems such as the repressilator.

Distribution of shortest path lengths in subcritical Erdos-Rényi networks.

Networks that are fragmented into small disconnected components are prevalent in a large variety of systems. These include the secure communication networks of commercial enterprises, government agencies, and illicit organizations, as well as networks that suffered multiple failures, attacks, or epidemics. The structural and statistical properties of such networks resemble those of subcritical random networks, which consist of finite components, whose sizes are nonextensive. Surprisingly, such networks do not exhibit the small-world property that is typical in supercritical random networks, where the mean distance between pairs of nodes scales logarithmically with the network size. Unlike supercritical networks whose structure has been studied extensively, subcritical networks have attracted relatively little attention. A special feature of these networks is that the statistical and geometric properties vary between different components and depend on their sizes and topologies. The overall statistics of the network can be obtained by a summation over all the components with suitable weights. We use a topological expansion to perform a systematic analysis of the degree distribution and the distribution of shortest path lengths (DSPL) on components of given sizes and topologies in subcritical Erdos-Rényi (ER) networks. From this expansion we obtain an exact analytical expression for the DSPL of the entire subcritical network, in the asymptotic limit. The DSPL, which accounts for all the pairs of nodes that reside on the same finite component (FC), is found to follow a geometric distribution of the form P_{FC}(L=ℓ|L<∞)=(1-c)c^{ℓ-1}, where c<1 is the mean degree. Using computer simulations we calculate the DSPL in subcritical ER networks of increasing sizes and confirm the convergence to this asymptotic result. We also obtain exact asymptotic results for the mean distance, 〈L〉_{FC}, and for the standard deviation of the DSPL, σ_{L,FC}, and show that the simulation results converge to these asymptotic results. Using the duality relations between subcritical and supercritical ER networks, we obtain the DSPL on the nongiant components of ER networks above the percolation transition.

Revealing the microstructure of the giant component in random graph ensembles.

The microstructure of the giant component of the Erdos-Rényi network and other configuration model networks is analyzed using generating function methods. While configuration model networks are uncorrelated, the giant component exhibits a degree distribution which is different from the overall degree distribution of the network and includes degree-degree correlations of all orders. We present exact analytical results for the degree distributions as well as higher-order degree-degree correlations on the giant components of configuration model networks. We show that the degree-degree correlations are essential for the integrity of the giant component, in the sense that the degree distribution alone cannot guarantee that it will consist of a single connected component. To demonstrate the importance and broad applicability of these results, we apply them to the study of the distribution of shortest path lengths on the giant component, percolation on the giant component, and spectra of sparse matrices defined on the giant component. We show that by using the degree distribution on the giant component one obtains high quality results for these properties, which can be further improved by taking the degree-degree correlations into account. This suggests that many existing methods, currently used for the analysis of the whole network, can be adapted in a straightforward fashion to yield results conditioned on the giant component.