907 research outputs found
From random point processes to hierarchical cavity master equations for stochastic dynamics of disordered systems in random graphs: Ising models and epidemics
No full textWe start from the theory of random point processes to derive n-point coupled master equations describing the continuous dynamics of discrete variables in random graphs. These equations constitute a hierarchical set of approximations that generalize and improve the cavity master equation (CME), a recently obtained closure for the usual master equation representing the dynamics. Our derivation clarifies some of the hypotheses and approximations that originally led to the CME, considered now as the first order of a more general technique. We tested the scheme in the dynamics of three models defined over diluted graphs: the Ising ferromagnet, the Viana-Bray spin-glass, and the susceptible-infectious-susceptible model for epidemics. In the first two, the equations perform similarly to the best-known approaches in literature. In the latter, they outperform the well-known pair quenched mean-field approximation
Estimating the size of the solution space of metabolic networks
No full textAbstract Background Cellular metabolism is one of the most investigated system of biological interactions. While the topological nature of individual reactions and pathways in the network is quite well understood there is still a lack of comprehension regarding the global functional behavior of the system. In the last few years flux-balance analysis (FBA) has been the most successful and widely used technique for studying metabolism at system level. This method strongly relies on the hypothesis that the organism maximizes an objective function. However only under very specific biological conditions (e.g. maximization of biomass for E. coli in reach nutrient medium) the cell seems to obey such optimization law. A more refined analysis not assuming extremization remains an elusive task for large metabolic systems due to algorithmic limitations. Results In this work we propose a novel algorithmic strategy that provides an efficient characterization of the whole set of stable fluxes compatible with the metabolic constraints. Using a technique derived from the fields of statistical physics and information theory we designed a message-passing algorithm to estimate the size of the affine space containing all possible steady-state flux distributions of metabolic networks. The algorithm, based on the well known Bethe approximation, can be used to approximately compute the volume of a non full-dimensional convex polytope in high dimensions. We first compare the accuracy of the predictions with an exact algorithm on small random metabolic networks. We also verify that the predictions of the algorithm match closely those of Monte Carlo based methods in the case of the Red Blood Cell metabolic network. Then we test the effect of gene knock-outs on the size of the solution space in the case of E. coli central metabolism. Finally we analyze the statistical properties of the average fluxes of the reactions in the E. coli metabolic network. Conclusion We propose a novel efficient distributed algorithmic strategy to estimate the size and shape of the affine space of a non full-dimensional convex polytope in high dimensions. The method is shown to obtain, quantitatively and qualitatively compatible results with the ones of standard algorithms (where this comparison is possible) being still efficient on the analysis of large biological systems, where exact deterministic methods experience an explosion in algorithmic time. The algorithm we propose can be considered as an alternative to Monte Carlo sampling methods.</p
Coloring random graphs
No full textWe study the graph coloring problem over random graphs of finite average connectivity c. Given a number q of available colors, we find that graphs with low connectivity admit almost always a proper coloring, whereas graphs with high connectivity are uncolorable. Depending on q, we find the precise value of the critical average connectivity c(q). Moreover, we show that below c(q) there exists a clustering phase cis an element of[c(d),c(q)] in which ground states spontaneously divide into an exponential number of clusters and where the proliferation of metastable states is responsible for the onset of complexity in local search algorithms
Adaptive drivers in a model of urban traffic
No full textWe introduce a simple lattice model of traffic flow in a city
where drivers optimize their route selection in time in order to
avoid traffic jams, and study its phase structure as a function
of the density of vehicles and of the drivers' behavioral
parameters via numerical simulations and mean-field analytical
arguments. We identify a phase transition between a low- and a
high-density regime. In the latter, inductive drivers may
surprisingly behave worse than randomly selecting drivers
The cavity master equation: average and fixed point of the ferromagnetic model in random graphs
No full textThe cavity master equation (CME) is a closure scheme to the usual master equation representing the dynamics of discrete variables in continuous time. In this work we explore the CME for a ferromagnetic model in a random graph. We first derive and average equation of the CME that describes the dynamics of mean magnetization of the system. We show that the numerical results compare remarkably well with the Monte Carlo simulations. Then, we show that the stationary state of the CME is well described by BP-like equations (independently of the dynamic rules that let the system toward the stationary state). These equations may be rewritten exactly as the fixed point solutions of the cavity equation if one also assumes that the stationary state is well described by a Boltzmann distribution
Statistical physics approach to gene regulatory networks
No full textGene expression is a complex process that should be regulated in each cell of every organism in order to ensure the proper functioning throughout its life. It is unavoidably subject to several sources of noise, due to the low copy number of molecules or to their diffusive motion inside the cell, that impose physical limits to the reliability of regulation. The regulation is generally performed by networks of molecules (proteins or RNAs) that interact with each other, often defined as gene regulatory networks (GRNs). In this thesis we adopt a statistical physics approach to study the regulation of gene expression at several levels, in different biological contexts. We start with a theoretical treatment about the limits of information flow in simple regulatory networks in which one controller regulates the levels of multiple targets. We consider network parameters as quenched random variables and, using tools from statistical field theory, we characterize the average of the maximum mutual information and its probability distribution induced by this randomness. The relevance of this study lies in the development of an analytical approach to ensembles of simple GRNs and it shows, among other things, that the optimization of network parameters could be less significant than the optimization of the input variable (i.e., the concentration of the controller). This conclusion is made stronger in large networks, where kinetic heterogeneities can be exploited for a reliable information transmission. Since the experimental quantification of gene expression is essential for the detailed study of regulatory processes, afterwards we leave the purely theoretical approach in favor of a data-driven one. Specifically, we extend to single-cell RNA-sequencing (scRNA-seq) data an information theoretic framework that characterizes the information content of samples of complex systems. We use it to evaluate different cells’ clusterings of a scRNA-seq dataset and we show how it can be exploited to identify maximally informative partitions of data. Afterwards, we study the influence of cell-to-cell variability of gene expression (partly caused by its stochastic nature) in the pathogenesis of multiple sclerosis. We work on scRNA-seq data of monozygotic twins discordant for the disease. Working on single-cell data allows to study the variability of gene expression across cells of the same type (in our case B cells), while the monozygotic twins allow to evidence the non-genetic factors which putatively cause the disease. Relying again on the framework mentioned above, we extract lists of “critical genes” from the dataset, for each subject. We refine the method exploiting previously identified markers of the disease, obtaining also lists of critical genes that are linked to them. These results are then crossed with differential expression and differential noise analyses, leading to a list of candidate genes likely linked to multiple sclerosis, which is actually under experimental validation. Finally, the last part of the thesis regards the mathematical modeling of a RNA network based on microRNAs that controls the early stage of myogenesis. Our goal is to analyze the regulatory role played by the two microRNA biosynthesis modes, one controlled by a miRNA-decoy system, the other consisting in its production from an independent genomic locus, and that played by the presence of competition between coding and non coding RNAs to bind microRNAs. We show that the miRNA-decoy system is sufficient to tune molecular levels at steady state, while the alternative locus for miRNA transcription serves a dynamical purpose, allowing the quick concentration shifts required by the differentiation process. This study suggests that these joint regulatory mechanisms could be a common feature of other biological processes
- …
