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     

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.     

On the long-run sensitivity of probabilistic Boolean networks

Boolean networks and, more generally, probabilistic Boolean networks, as one class of gene regulatory networks, model biological processes with the network dynamics determined by the logic-rule regulatory functions in conjunction with probabilistic parameters involved in network transitions. While there has been significant research on applying different control policies to alter network dynamics as future gene therapeutic intervention, we have seen less work on understanding the sensitivity of network dynamics with respect to perturbations to networks, including regulatory rules and the involved parameters, which is particularly critical for the design of intervention strategies. This paper studies this less investigated issue of network sensitivity in the long run. As the underlying model of probabilistic Boolean networks is a finite Markov chain, we define the network sensitivity based on the steady-state distributions of probabilistic Boolean networks and call it long-run sensitivity. The steady-state distribution reflects the long-run behavior of the network and it can give insight into the dynamics or momentum existing in a system. The change of steady-state distribution caused by possible perturbations is the key measure for intervention. This newly defined long-run sensitivity can provide insight on both network inference and intervention. We show the results for probabilistic Boolean networks generated from random Boolean networks and the results from two real biological networks illustrate preliminary applications of sensitivity in intervention for practical problems.     

Intervention in context-sensitive probabilistic Boolean networks

MOTIVATION: Intervention in a gene regulatory network is used to help it 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 essentially a finite collection of Boolean networks in which at any discrete time point the gene state vector transitions according to the rules of one of the constituent networks. For an instantaneously random PBN, the governing Boolean network is randomly chosen at each time point. For a context-sensitive PBN, the governing Boolean network remains fixed for an interval of time until a binary random variable determines a switch. The theory of automatic control has been previously applied to find optimal strategies for manipulating external (control) variables that affect the transition probabilities of an instantaneously random PBN to desirably affect its dynamic evolution over a finite time horizon. This paper extends the methods of external control to context-sensitive PBNs. RESULTS: This paper treats intervention via external control variables in context-sensitive PBNs by extending the results for instantaneously random PBNs in several directions. First, and most importantly, whereas an instantaneously random PBN yields a Markov chain whose state space is composed of gene vectors, each state of the Markov chain corresponding to a context-sensitive PBN is composed of a pair, the current gene vector occupied by the network and the current constituent Boolean network. Second, the analysis is applied to PBNs with perturbation, meaning that random gene perturbation is permitted at each instant with some probability. Third, the (mathematical) influence of genes within the network is used to choose the particular gene with which to intervene. Lastly, PBNs are designed from data using a recently proposed inference procedure that takes steady-state considerations into account. The results are applied to a context-sensitive PBN 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, since the available data suggest that disruption of this influence could reduce the chance of a melanoma metastasizing.     

A SAT-based algorithm for finding attractors in synchronous Boolean networks

This paper addresses the problem of finding attractors in synchronous Boolean networks. The existing Boolean decision diagram-based algorithms have limited capacity due to the excessive memory requirements of decision diagrams. The simulation-based algorithms can be applied to larger networks, however, they are incomplete. We present an algorithm, which uses a SAT-based bounded model checking to find all attractors in a Boolean network. The efficiency of the presented algorithm is evaluated by analyzing seven networks models of real biological processes, as well as 150,000 randomly generated Boolean networks of sizes between 100 and 7,000. The results show that our approach has a potential to handle an order of magnitude larger models than currently possible.     

Attractor analysis of asynchronous Boolean models of signal transduction networks

Prior work on the dynamics of Boolean networks, including analysis of the state space attractors and the basin of attraction of each attractor, has mainly focused on synchronous update of the nodes’ states. Although the simplicity of synchronous updating makes it very attractive, it fails to take into account the variety of time scales associated with different types of biological processes. Several different asynchronous update methods have been proposed to overcome this limitation, but there have not been any systematic comparisons of the dynamic behaviors displayed by the same system under different update methods. Here we fill this gap by combining theoretical analysis such as solution of scalar equations and Markov chain techniques, as well as numerical simulations to carry out a thorough comparative study on the dynamic behavior of a previously proposed Boolean model of a signal transduction network in plants. Prior evidence suggests that this network admits oscillations, but it is not known whether these oscillations are sustained. We perform an attractor analysis of this system using synchronous and three different asynchronous updating schemes both in the case of the unperturbed (wild-type) and perturbed (node-disrupted) systems. This analysis reveals that while the wild-type system possesses an update-independent fixed point, any oscillations eventually disappear unless strict constraints regarding the timing of certain processes and the initial state of the system are satisfied. Interestingly, in the case of disruption of a particular node all models lead to an extended attractor. Overall, our work provides a roadmap on how Boolean network modeling can be used as a predictive tool to uncover the dynamic patterns of a biological system under various internal and environmental perturbations.     

Reverse engineering of gene regulatory networks: a finite state linear model

We propose a new model for describing gene regulatory networks that can capture discrete (Boolean) and continuous (differential) aspects of gene regulation. After giving some illustrations of the model, we study the problem of the reverse engineering of such networks, i.e., how to construct a network from gene expression data. We prove that for our model there exists an algorithm finding a network compatible with the given data. We demonstrate the model by simulating lambda-phage. We also describe some generalizations of the model, discuss their relevance to the real-world gene networks and formulate a number of open problems.     

Algorithms for identifying Boolean networks and related biological networks based on matrix multiplication and fingerprint function.

Due to the recent progress of the DNA microarray technology, a large number of gene expression profile data are being produced. How to analyze gene expression data is an important topic in computational molecular biology. Several studies have been done using the Boolean network as a model of a genetic network. This paper proposes efficient algorithms for identifying Boolean networks of bounded indegree and related biological networks, where identification of a Boolean network can be formalized as a problem of identifying many Boolean functions simultaneously. For the identification of a Boolean network, an O(mnD+1) time naive algorithm and a simple O (mnD) time algorithm are known, where n denotes the number of nodes, m denotes the number of examples, and D denotes the maximum in degree. This paper presents an improved O(momega-2nD + mnD+omega-3) time Monte-Carlo type randomized algorithm, where omega is the exponent of matrix multiplication (currently, omega < 2.376). The algorithm is obtained by combining fast matrix multiplication with the randomized fingerprint function for string matching. Although the algorithm and its analysis are simple, the result is nontrivial and the technique can be applied to several related problems.     

Dynamical properties of model gene networks and implications for the inverse problem

We study the inverse problem, or the "reverse-engineering" problem, for two abstract models of gene expression dynamics, discrete-time Boolean networks and continuous-time switching networks. Formally, the inverse problem is similar for both types of networks. For each gene, its regulators and its Boolean dynamics function must be identified. However, differences in the dynamical properties of these two types of networks affect the amount of data that is necessary for solving the inverse problem. We derive estimates for the average amounts of time series data required to solve the inverse problem for randomly generated Boolean and continuous-time switching networks. We also derive a lower bound on the amount of data needed that holds for both types of networks. We find that the amount of data required is logarithmic in the number of genes for Boolean networks, matching the general lower bound and previous theory, but are superlinear in the number of genes for continuous-time switching networks. We also find that the amount of data needed scales as 2(K), where K is the number of regulators per gene, rather than 2(2K), as previous theory suggests.     

On finite-horizon control of genetic regulatory networks with multiple hard-constraints

Background

Probabilistic Boolean Networks (PBNs) provide a convenient tool for studying genetic regulatory networks. There are three major approaches to develop intervention strategies: (1) resetting the state of the PBN to a desirable initial state and letting the network evolve from there, (2) changing the steady-state behavior of the genetic network by minimally altering the rule-based structure and (3) manipulating external control variables which alter the transition probabilities of the network and therefore desirably affects the dynamic evolution. Many literatures study various types of external control problems, with a common drawback of ignoring the number of times that external control(s) can be applied.

Results

This paper studies the intervention problem by manipulating multiple external controls in a finite time interval in a PBN. The maximum numbers of times that each control method can be applied are given. We treat the problem as an optimization problem with multi-constraints. Here we introduce an algorithm, the "Reserving Place Algorithm'', to find all optimal intervention strategies. Given a fixed number of times that a certain control method is applied, the algorithm can provide all the sub-optimal control policies. Theoretical analysis for the upper bound of the computational cost is also given. We also develop a heuristic algorithm based on Genetic Algorithm, to find the possible optimal intervention strategy for networks of large size.

Conclusions

Studying the finite-horizon control problem with multiple hard-constraints is meaningful. The problem proposed is NP-hard. The Reserving Place Algorithm can provide more than one optimal intervention strategies if there are. Moreover, the algorithm can find all the sub-optimal control strategies corresponding to the number of times that certain control method is conducted. To speed up the computational time, a heuristic algorithm based on Genetic Algorithm is proposed for genetic networks of large size.

     

Inferring qualitative relations in genetic networks and metabolic pathways

MOTIVATION: Inferring genetic network architecture from time series data of gene expression patterns is an important topic in bioinformatics. Although inference algorithms based on the Boolean network were proposed, the Boolean network was not sufficient as a model of a genetic network. RESULTS: First, a Boolean network model with noise is proposed, together with an inference algorithm for it. Next, a qualitative network model is proposed, in which regulation rules are represented as qualitative rules and embedded in the network structure. Algorithms are also presented for inferring qualitative relations from time series data. Then, an algorithm for inferring S-systems (synergistic and saturable systems) from time series data is presented, where S-systems are based on a particular kind of nonlinear differential equation and have been applied to the analysis of various biological systems. Theoretical results are shown for Boolean networks with noises and simple qualitative networks. Computational results are shown for Boolean networks with noises and S-systems, where real data are not used because the proposed models are still conceptual and the quantity and quality of currently available data are not enough for the application of the proposed methods.     

Inferring gene regulatory networks with time delays using a genetic algorithm

Recently a state-space model with time delays for inferring gene regulatory networks was proposed. It was assumed that each regulation between two internal state variables had multiple time delays. This assumption caused underestimation of the model with many current gene expression datasets. In biological reality, one regulatory relationship may have just a single time delay, and not multiple time delays. This study employs Boolean variables to capture the existence of the time-delayed regulatory relationships in gene regulatory networks in terms of the state-space model. As the solution space of time delayed relationships is too large for an exhaustive search, a genetic algorithm (GA) is proposed to determine the optimal Boolean variables (the optimal time-delayed regulatory relationships). Coupled with the proposed GA, Bayesian information criterion (BIC) and probabilistic principle component analysis (PPCA) are employed to infer gene regulatory networks with time delays. Computational experiments are performed on two real gene expression datasets. The results show that the GA is effective at finding time-delayed regulatory relationships. Moreover, the inferred gene regulatory networks with time delays from the datasets improve the prediction accuracy and possess more of the expected properties of a real network, compared to a gene regulatory network without time delays.     

From biological pathways to regulatory networks

This paper presents a general theoretical framework for generating Boolean networks whose state transitions realize a set of given biological pathways or minor variations thereof. This ill-posed inverse problem, which is of crucial importance across practically all areas of biology, is solved by using Karnaugh maps which are classical tools for digital system design. It is shown that the incorporation of prior knowledge, presented in the form of biological pathways, can bring about a dramatic reduction in the cardinality of the network search space. Constraining the connectivity of the network, the number and relative importance of the attractors, and concordance with observed time-course data are additional factors that can be used to further reduce the cardinality of the search space. The networks produced by the approaches developed here should facilitate the understanding of multivariate biological phenomena and the subsequent design of intervention approaches that are more likely to be successful in practice. As an example, the results of this paper are applied to the widely studied p53 pathway and it is shown that the resulting network exhibits dynamic behavior consistent with experimental observations from the published literature.     

Generalized concept of minimal cut sets in biochemical networks

Recently, the concept of minimal cut sets has been introduced for studying structural fragility and identifying knock-out strategies in biochemical reaction networks. A minimal cut set (MCS) has been defined as a minimal set of reactions whose removal blocks the operation of a chosen objective reaction. In this report the theoretical framework of MCSs is refined and extended increasing the practical applicability significantly. An MCS is now defined as a minimal (irreducible) set of structural interventions (removal of network elements) repressing a certain functionality specified by a deletion task. A deletion task describes unambiguously the flux patterns (or the functionality) to be repressed. It is shown that the MCSs can be computed from the set of target modes, which comprises all elementary modes that exhibit the functionality to be attacked. Since a deletion task can be specified by several Boolean rules, MCSs can now be determined for a large variety of complex deletion problems and may be utilized for inhibiting very special flux patterns. It is additionally shown that the other way around is also possible: the elementary modes belonging to a certain functionality can be computed from the respective set of MCSs. Therefore, elementary modes and MCSs can be seen as dual representations of network functions and both can be converted into each other. Moreover, there exist a strong relationship to minimal hitting sets known from set theory: the MCSs are the minimal hitting sets of the collection of target modes and vice versa. Another generalization introduced herein is that MCSs need not to be restricted to the removal of reactions they may also contain network nodes. In the light of the extended framework of MCSs, applications for assessing, manipulating, and designing metabolic networks in silico are discussed.     

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.     

Finite-time synchronization of coupled neural networks via discontinuous controllers

This paper investigates finite-time synchronization of an array of coupled neural networks via discontinuous controllers. Based on Lyapunov function method and the discontinuous version of finite-time stability theory, some sufficient criteria for finite-time synchronization are obtained. Furthermore, we propose switched control and adaptive tuning parameter strategies in order to reduce the settling time. In addition, pinning control scheme via a single controller is also studied in this paper. With the hypothesis that the coupling network topology contains a directed spanning tree and each of the strongly connected components is detail-balanced, we prove that finite-time synchronization can be achieved via pinning control. Finally, some illustrative examples are given to show the validity of the theoretical results.     

Intrinsic properties of Boolean dynamics in complex networks

We study intrinsic properties of attractor in Boolean dynamics of complex networks with scale-free topology, comparing with those of the so-called Kauffman's random Boolean networks. We numerically study both frozen and relevant nodes in each attractor in the dynamics of relatively small networks (20?N?200). We investigate numerically robustness of an attractor to a perturbation. An attractor with cycle length of ?_c in a network of size N consists of ?_c states in the state space of 2^N states; each attractor has the arrangement of N nodes, where the cycle of attractor sweeps ?_c states. We define a perturbation as a flip of the state on a single node in the attractor state at a given time step. We show that the rate between unfrozen and relevant nodes in the dynamics of a complex network with scale-free topology is larger than that in Kauffman's random Boolean network model. Furthermore, we find that in a complex scale-free network with fluctuation of the in-degree number, attractors are more sensitive to a state flip for a highly connected node (i.e. input-hub node) than to that for a less connected node. By some numerical examples, we show that the number of relevant nodes increases, when an input-hub node is coincident with and/or connected with an output-hub node (i.e. a node with large output-degree) one another.     

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.     

景观生态网络研究进展

作为生态学重要的概念与方法,生态网络是景观生态学研究的热点问题,也是耦合景观结构、生态过程和功能的重要途径。景观生态网络对于保护生物多样性、维持生态平衡、增加景观连接度具有重要意义。从景观生态网络的相关理论、研究进展、研究方法模型等进行分析,并对其应用前景进行展望,主要介绍了传统景观格局分析、网络分析、模型模拟等方法的适用性与特点,并分析了景观生态网络在城市景观格局优化、自然保护区规划、生物多样性保护、土地规划等领域的应用,最后提出了研究的主要问题。