Sampling-rate-dependent probabilistic Boolean networks

External control of a genetic regulatory network is used for the purpose of avoiding undesirable states, such as those associated with a disease. To date, intervention has mainly focused on the external control of probabilistic Boolean networks via the associated discrete-time discrete-space Markov processes. Implementation of an intervention policy derived for probabilistic Boolean networks requires nearly continuous observation of the underlying biological system since precise application requires the observation of all transitions. In medical applications, as in many engineering problems, the process is sampled at discrete time intervals and a decision to intervene or not must be made at each sample point. In this work, sampling-rate-dependent probabilistic Boolean network is proposed as an extension of probabilistic Boolean network. The proposed framework is capable of capturing the sampling rate of the underlying system.     

Dynamics of unperturbed and noisy generalized Boolean networks

For years, we have been building models of gene regulatory networks, where recent advances in molecular biology shed some light on new structural and dynamical properties of such highly complex systems. In this work, we propose a novel timing of updates in random and scale-free Boolean networks, inspired by recent findings in molecular biology. This update sequence is neither fully synchronous nor asynchronous, but rather takes into account the sequence in which genes affect each other. We have used both Kauffman's original model and Aldana's extension, which takes into account the structural properties about known parts of actual GRNs, where the degree distribution is right-skewed and long-tailed. The computer simulations of the dynamics of the new model compare favorably to the original ones and show biologically plausible results both in terms of attractors number and length. We have complemented this study with a complete analysis of our systems’ stability under transient perturbations, which is one of biological networks defining attribute. Results are encouraging, as our model shows comparable and usually even better behavior than preceding ones without loosing Boolean networks attractive simplicity.     

An analysis of the class of gene regulatory functions implied by a biochemical model

Understanding the integrated behavior of genetic regulatory networks, in which genes regulate one another's activities via RNA and protein products, is emerging as a dominant problem in systems biology. One widely studied class of models of such networks includes genes whose expression values assume Boolean values (i.e., on or off). Design decisions in the development of Boolean network models of gene regulatory systems include the topology of the network (including the distribution of input- and output-connectivity) and the class of Boolean functions used by each gene (e.g., canalizing functions, post functions, etc.). For example, evidence from simulations suggests that biologically realistic dynamics can be produced by scale-free network topologies with canalizing Boolean functions. This work seeks further insights into the design of Boolean network models through the construction and analysis of a class of models that include more concrete biochemical mechanisms than the usual abstract model, including genes and gene products, dimerization, cis-binding sites, promoters and repressors. In this model, it is assumed that the system consists of N genes, with each gene producing one protein product. Proteins may form complexes such as dimers, trimers, etc. The model also includes cis-binding sites to which proteins may bind to form activators or repressors. Binding affinities are based on structural complementarity between proteins and binding sites, with molecular binding sites modeled by bit-strings. Biochemically plausible gene expression rules are used to derive a Boolean regulatory function for each gene in the system. The result is a network model in which both topological features and Boolean functions arise as emergent properties of the interactions of components at the biochemical level. A highly biased set of Boolean functions is observed in simulations of networks of various sizes, suggesting a new characterization of the subset of Boolean functions that are likely to appear in gene regulatory networks.     

Reliability of regulatory networks and its evolution

The problem of reliability of the dynamics in biological regulatory networks is studied in the framework of a generalized Boolean network model with continuous timing and noise. Using well-known artificial genetic networks such as the repressilator, we discuss concepts of reliability of rhythmic attractors. In a simple evolution process we investigate how overall network structure affects the reliability of the dynamics. In the course of the evolution, networks are selected for reliable dynamics. We find that most networks can be easily evolved towards reliable functioning while preserving the original function.     

Modelling the evolution of genetic regulatory networks

An evolutionary model of genetic regulatory networks is developed, based on a model of network encoding and dynamics called the Artificial Genome (AG). This model derives a number of specific genes and their interactions from a string of (initially random) bases in an idealized manner analogous to that employed by natural DNA. The gene expression dynamics are determined by updating the gene network as if it were a simple Boolean network. The generic behaviour of the AG model is investigated in detail. In particular, we explore the characteristic network topologies generated by the model, their dynamical behaviours, and the typical variance of network connectivities and network structures. These properties are demonstrated to agree with a probabilistic analysis of the model, and the typical network structures generated by the model are shown to lie between those of random networks and scale-free networks in terms of their degree distribution. Evolutionary processes are simulated using a genetic algorithm, with selection acting on a range of properties from gene number and degree of connectivity through periodic behaviour to specific patterns of gene expression. The evolvability of increasingly complex patterns of gene expression is examined in detail. When a degree of redundancy is introduced, the average number of generations required to evolve given targets is reduced, but limits on evolution of complex gene expression patterns remain. In addition, cyclic gene expression patterns with periods that are multiples of shorter expression patterns are shown to be inherently easier to evolve than others. Constraints imposed by the template-matching nature of the AG model generate similar biases towards such expression patterns in networks in initial populations, in addition to the somewhat scale-free nature of these networks. The significance of these results on current understanding of biological evolution is discussed.     

The transition from differential equations to Boolean networks: a case study in simplifying a regulatory network model

Methods for modeling cellular regulatory networks as diverse as differential equations and Boolean networks co-exist, however, without much closer correspondence to each other. With the example system of the fission yeast cell cycle control network, we here discuss these two approaches with respect to each other. We find that a Boolean network model can be formulated as a specific coarse-grained limit of the more detailed differential equations model for this system. This demonstrates the mathematical foundation on which Boolean networks can be applied to biological regulatory networks in a controlled way.     

A Tutorial on Analysis and Simulation of Boolean Gene Regulatory Network Models

Driven by the desire to understand genomic functions through the interactions among genes and gene products, the research in gene regulatory networks has become a heated area in genomic signal processing. Among the most studied mathematical models are Boolean networks and probabilistic Boolean networks, which are rule-based dynamic systems. This tutorial provides an introduction to the essential concepts of these two Boolean models, and presents the up-to-date analysis and simulation methods developed for them. In the Analysis section, we will show that Boolean models are Markov chains, based on which we present a Markovian steady-state analysis on attractors, and also reveal the relationship between probabilistic Boolean networks and dynamic Bayesian networks (another popular genetic network model), again via Markov analysis; we dedicate the last subsection to structural analysis, which opens a door to other topics such as network control. The Simulation section will start from the basic tasks of creating state transition diagrams and finding attractors, proceed to the simulation of network dynamics and obtaining the steady-state distributions, and finally come to an algorithm of generating artificial Boolean networks with prescribed attractors. The contents are arranged in a roughly logical order, such that the Markov chain analysis lays the basis for the most part of Analysis section, and also prepares the readers to the topics in Simulation section.     

Stochastic Boolean networks: An efficient approach to modeling gene regulatory networks

ABSTRACT: BACKGROUND: Various computational models have been of interest due to their use in the modelling of gene regulatory networks (GRNs). As a logical model, probabilistic Boolean networks (PBNs) consider molecular and genetic noise, so the study of PBNs provides significant insights into the understanding of the dynamics of GRNs. This will ultimately lead to advances in developing therapeutic methods that intervene in the process of disease development and progression. The applications of PBNs, however, are hindered by the complexities involved in the computation of the state transition matrix and the steady-state distribution of a PBN. For a PBN with n genes and N Boolean networks, the complexity to compute the state transition matrix is O(nN22n) or O(nN2n) for a sparse matrix. RESULTS: This paper presents a novel implementation of PBNs based on the notions of stochastic logic and stochastic computation. This stochastic implementation of a PBN is referred to as a stochastic Boolean network (SBN). An SBN provides an accurate and efficient simulation of a PBN without and with random gene perturbation. The state transition matrix is computed in an SBN with a complexity of O(nL2n), where L is a factor related to the stochastic sequence length. Since the minimum sequence length required for obtaining an evaluation accuracy approximately increases in a polynomial order with the number of genes, n, and the number of Boolean networks, N, usually increases exponentially with n, L is typically smaller than N, especially in a network with a large number of genes. Hence, the computational complexity of an SBN is primarily limited by the number of genes, but not directly by the total possible number of Boolean networks. Furthermore, a time-frame expanded SBN enables an efficient analysis of the steady-state distribution of a PBN. These findings are supported by the simulation results of a simplified p53 network, several randomly generated networks and a network inferred from a T cell immune response dataset. An SBN can also implement the function of an asynchronous PBN and is potentially useful in a hybrid approach in combination with a continuous or single-molecule level stochastic model. CONCLUSIONS: Stochastic Boolean networks (SBNs) are proposed as an efficient approach to modelling gene regulatory networks (GRNs). The SBN approach is able to recover biologically-proven regulatory behaviours, such as the oscillatory dynamics of the p53-Mdm2 network and the dynamic attractors in a T cell immune response network. The proposed approach can further predict the network dynamics when the genes are under perturbation, thus providing biologically meaningful insights for a better understanding of the dynamics of GRNs. The algorithms and methods described in this paper have been implemented in Matlab packages, which are attached as Additional files.     

Intervention in gene regulatory networks via greedy control policies based on long-run behavior

Background  

A salient purpose for studying gene regulatory networks is to derive intervention strategies, the goals being to identify potential drug targets and design gene-based therapeutic intervention. Optimal stochastic control based on the transition probability matrix of the underlying Markov chain has been studied extensively for probabilistic Boolean networks. Optimization is based on minimization of a cost function and a key goal of control is to reduce the steady-state probability mass of undesirable network states. Owing to computational complexity, it is difficult to apply optimal control for large networks.     

基于微阵列数据的基因网络预测方法研究进展

DNA微阵列技术可同时定量测定成千上万个基因在生物样本中的表达水平,从这一技术获得的全基因组范围表达数据为揭示基因间复杂调控关系提供了可能。研究人员试图通过数学和计算方法来构建遗传互作的模型,这些基因调控网络模型有聚类法、布尔网络、贝叶斯网络、微分方程等。文章对网络重建计算方法的研究现状进行了较为全面的综述,比较了不同模型的优缺点,并对该领域进一步的研究趋势进行了展望。     

Gene perturbation and intervention in probabilistic Boolean networks

MOTIVATION: A major objective of gene regulatory network modeling, in addition to gaining a deeper understanding of genetic regulation and control, is the development of computational tools for the identification and discovery of potential targets for therapeutic intervention in diseases such as cancer. We consider the general question of the potential effect of individual genes on the global dynamical network behavior, both from the view of random gene perturbation as well as intervention in order to elicit desired network behavior. RESULTS: Using a recently introduced class of models, called Probabilistic Boolean Networks (PBNs), this paper develops a model for random gene perturbations and derives an explicit formula for the transition probabilities in the new PBN model. This result provides a building block for performing simulations and deriving other results concerning network dynamics. An example is provided to show how the gene perturbation model can be used to compute long-term influences of genes on other genes. Following this, the problem of intervention is addressed via the development of several computational tools based on first-passage times in Markov chains. The consequence is a methodology for finding the best gene with which to intervene in order to most likely achieve desirable network behavior. The ideas are illustrated with several examples in which the goal is to induce the network to transition into a desired state, or set of states. The corresponding issue of avoiding undesirable states is also addressed. Finally, the paper turns to the important problem of assessing the effect of gene perturbations on long-run network behavior. A bound on the steady-state probabilities is derived in terms of the perturbation probability. The result demonstrates that states of the network that are more 'easily reachable' from other states are more stable in the presence of gene perturbations. Consequently, these are hypothesized to correspond to cellular functional states. AVAILABILITY: A library of functions written in MATLAB for simulating PBNs, constructing state-transition matrices, computing steady-state distributions, computing influences, modeling random gene perturbations, and finding optimal intervention targets, as described in this paper, is available on request from is@ieee.org.     

The impact of function perturbations in Boolean networks

MOTIVATION: A network is said to be robust relative to a certain network characteristic if a small change in network structure does not significantly affect the characteristic. From the perspective of network stability, robustness is desirable; however, from the perspective of intervention to exert influence on network behavior, it is undesirable. For Boolean networks, there are two fundamental types of robustness. One type pertains to perturbing the state of the network and the other to perturbing the rule-based structure. RESULTS: This article explores the impact of function perturbations in Boolean networks from two aspects: (1) analysis: predict the impact on network state transitions and attractors via analytical approaches or identify a perturbation by observing its consequences; (2) synthesis: preserve or modify the network characteristics, especially attractors, by introducing a judicious change to the functions. The results are applied to achieve intervention that structurally alters the network to achieve a more favorable steady-state distribution and to identify the function perturbation that has led to altered observed behavior. The intervention procedure is applied to a WNT5A network to reduce the risk of metastasis in melanoma, and the identification procedure is applied to a Drosophila melanogaster segmentation polarity gene network to identify regulatory function perturbation.     

A multi-objective differential evolutionary approach toward more stable gene regulatory networks

Models are of central importance in many scientific contexts. Mathematical and computational modeling of genetic regulatory networks promises to uncover the fundamental principles of living systems. Biological models, such as gene regulatory models, can help us better understand interactions among genes and how cells regulate their production of proteins and enzymes. One feature shared among living systems is their ability to cope with perturbations and remain stable, a property that is the result of evolutionary fine-tuning over many generations. In this study we use random Boolean networks (RBNs) as an abstract model of gene regulatory systems. By applying Differential Evolution (DE), an evolution-based optimization technique, we produce networks with increased stability. DE requires relatively few user-specified parameters, has fast convergence and does not rely on initial conditions to find the global minima within multi-dimensional search spaces.     

Intervention in Context-Sensitive Probabilistic Boolean Networks Revisited

An approximate representation for the state space of a context-sensitive probabilistic Boolean network has previously been proposed and utilized to devise therapeutic intervention strategies. Whereas the full state of a context-sensitive probabilistic Boolean network is specified by an ordered pair composed of a network context and a gene-activity profile, this approximate representation collapses the state space onto the gene-activity profiles alone. This reduction yields an approximate transition probability matrix, absent of context, for the Markov chain associated with the context-sensitive probabilistic Boolean network. As with many approximation methods, a price must be paid for using a reduced model representation, namely, some loss of optimality relative to using the full state space. This paper examines the effects on intervention performance caused by the reduction with respect to various values of the model parameters. This task is performed using a new derivation for the transition probability matrix of the context-sensitive probabilistic Boolean network. This expression of transition probability distributions is in concert with the original definition of context-sensitive probabilistic Boolean network. The performance of optimal and approximate therapeutic strategies is compared for both synthetic networks and a real case study. It is observed that the approximate representation describes the dynamics of the context-sensitive probabilistic Boolean network through the instantaneously random probabilistic Boolean network with similar parameters.     

Probabilistic Boolean Networks: a rule-based uncertainty model for gene regulatory networks

MOTIVATION: Our goal is to construct a model for genetic regulatory networks such that the model class: (i) incorporates rule-based dependencies between genes; (ii) allows the systematic study of global network dynamics; (iii) is able to cope with uncertainty, both in the data and the model selection; and (iv) permits the quantification of the relative influence and sensitivity of genes in their interactions with other genes. RESULTS: We introduce Probabilistic Boolean Networks (PBN) that share the appealing rule-based properties of Boolean networks, but are robust in the face of uncertainty. We show how the dynamics of these networks can be studied in the probabilistic context of Markov chains, with standard Boolean networks being special cases. Then, we discuss the relationship between PBNs and Bayesian networks--a family of graphical models that explicitly represent probabilistic relationships between variables. We show how probabilistic dependencies between a gene and its parent genes, constituting the basic building blocks of Bayesian networks, can be obtained from PBNs. Finally, we present methods for quantifying the influence of genes on other genes, within the context of PBNs. Examples illustrating the above concepts are presented throughout the paper.     

Steady-state analysis of genetic regulatory networks modelled by probabilistic boolean networks

Probabilistic Boolean networks (PBNs) have recently been introduced as a promising class of models of genetic regulatory networks. The dynamic behaviour of PBNs can be analysed in the context of Markov chains. A key goal is the determination of the steady-state (long-run) behaviour of a PBN by analysing the corresponding Markov chain. This allows one to compute the long-term influence of a gene on another gene or determine the long-term joint probabilistic behaviour of a few selected genes. Because matrix-based methods quickly become prohibitive for large sizes of networks, we propose the use of Monte Carlo methods. However, the rate of convergence to the stationary distribution becomes a central issue. We discuss several approaches for determining the number of iterations necessary to achieve convergence of the Markov chain corresponding to a PBN. Using a recently introduced method based on the theory of two-state Markov chains, we illustrate the approach on a sub-network designed from human glioma gene expression data and determine the joint steadystate probabilities for several groups of genes.     

Intervention in a family of Boolean networks

MOTIVATION: Intervention in a gene regulatory network is used to avoid undesirable states, such as those associated with a disease. Several types of intervention have been studied in the framework of a probabilistic Boolean network (PBN), which is a collection of Boolean networks in which the gene state vector transitions according to the rules of one of the constituent networks and where network choice is governed by a selection distribution. The theory of automatic control has been applied to find optimal strategies for manipulating external control variables that affect the transition probabilities to desirably affect dynamic evolution over a finite time horizon. In this paper we treat a case in which we lack the governing probability structure for Boolean network selection, so we simply have a family of Boolean networks, but where these networks possess a common attractor structure. This corresponds to the situation in which network construction is treated as an ill-posed inverse problem in which there are many Boolean networks created from the data under the constraint that they all possess attractor structures matching the data states, which are assumed to arise from sampling the steady state of the real biological network. RESULTS: Given a family of Boolean networks possessing a common attractor structure composed of singleton attractors, a control algorithm is derived by minimizing a composite finite-horizon cost function that is a weighted average over all the individual networks, the idea being that we desire a control policy that on average suits the networks because these are viewed as equivalent relative to the data. The weighting for each network at any time point is taken to be proportional to the instantaneous estimated probability of that network being the underlying network governing the state transition. The results are applied to a family of Boolean networks derived from gene-expression data collected in a study of metastatic melanoma, the intent being to devise a control strategy that reduces the WNT5A gene's action in affecting biological regulation. AVAILABILITY: The software is available on request. SUPPLEMENTARY INFORMATION: The supplementary Information is available at http://ee.tamu.edu/~edward/tree     

Robustness and state-space structure of Boolean gene regulatory models

Robustness to perturbation is an important characteristic of genetic regulatory systems, but the relationship between robustness and model dynamics has not been clearly quantified. We propose a method for quantifying both robustness and dynamics in terms of state-space structures, for Boolean models of genetic regulatory systems. By investigating existing models of the Drosophila melanogaster segment polarity network and the Saccharomyces cerevisiae cell-cycle network, we show that the structure of attractor basins can yield insight into the underlying decision making required of the system, and also the way in which the system maximises its robustness. In particular, gene networks implementing decisions based on a few genes have simple state-space structures, and their attractors are robust by virtue of their simplicity. Gene networks with decisions that involve many interacting genes have correspondingly more complicated state-space structures, and robustness cannot be achieved through the structure of the attractor basins, but is achieved by larger attractor basins that dominate the state space. These different types of robustness are demonstrated by the two models: the D. melanogaster segment polarity network is robust due to simple attractor basins that implement decisions based on spatial signals; the S. cerevisiae cell-cycle network has a complicated state-space structure, and is robust only due to a giant attractor basin that dominates the state space.     

From Genes to Flower Patterns and Evolution: Dynamic Models of Gene Regulatory Networks

Genes and proteins form complex dynamical systems or gene regulatory networks (GRN) that can reach several steady states (attractors). These may be associated with distinct cell types. In plants, the ABC combinatorial model establishes the necessary gene combinations for floral organ cell specification. We have developed dynamic gene regulatory network (GRN) models to understand how the combinatorial selection of gene activity is established during floral organ primordia specification as a result of the concerted action of ABC and non-ABC genes. Our analyses have shown that the floral organ specification GRN reaches six attractors with gene configurations observed in primordial cell types during early stages of flower development and four that correspond to regions of the inflorescence meristem. This suggests that it is the overall GRN dynamics rather than precise signals that underlie the ABC model. Furthermore, our analyses suggest that the steady states of the GRN are robust to random alterations of the logical functions that define the gene interactions. Here we have updated the GRN model and have systematically altered the outputs of all the logical functions and addressed in which cases the original attractors are recovered. We then reduced the original three-state GRN to a two-state (Boolean) GRN and performed the same systematic perturbation analysis. Interestingly, the Boolean GRN reaches the same number and type of attractors as reached by the three-state GRN, and it responds to perturbations in a qualitatively identical manner as the original GRN. These results suggest that a Boolean model is sufficient to capture the dynamical features of the floral network and provide additional support for the robustness of the floral GRN. These findings further support that the GRN model provides a dynamical explanation for the ABC model and that the floral GRN robustness could be behind the widespread conservation of the floral plan among eudicotyledoneous plants. Other aspects of evolution of flower organ arrangement and ABC gene expression patterns are discussed in the context of the approach proposed here. álvaro Chaos, Max Aldana and Elena Alvarez-Buylla contributed equally to this work.