A Parallel Attractor Finding Algorithm Based on Boolean Satisfiability for Genetic Regulatory Networks

In biological systems, the dynamic analysis method has gained increasing attention in the past decade. The Boolean network is the most common model of a genetic regulatory network. The interactions of activation and inhibition in the genetic regulatory network are modeled as a set of functions of the Boolean network, while the state transitions in the Boolean network reflect the dynamic property of a genetic regulatory network. A difficult problem for state transition analysis is the finding of attractors. In this paper, we modeled the genetic regulatory network as a Boolean network and proposed a solving algorithm to tackle the attractor finding problem. In the proposed algorithm, we partitioned the Boolean network into several blocks consisting of the strongly connected components according to their gradients, and defined the connection between blocks as decision node. Based on the solutions calculated on the decision nodes and using a satisfiability solving algorithm, we identified the attractors in the state transition graph of each block. The proposed algorithm is benchmarked on a variety of genetic regulatory networks. Compared with existing algorithms, it achieved similar performance on small test cases, and outperformed it on larger and more complex ones, which happens to be the trend of the modern genetic regulatory network. Furthermore, while the existing satisfiability-based algorithms cannot be parallelized due to their inherent algorithm design, the proposed algorithm exhibits a good scalability on parallel computing architectures.     

An Efficient Algorithm for Computing Attractors of Synchronous And Asynchronous Boolean Networks

Biological networks, such as genetic regulatory networks, often contain positive and negative feedback loops that settle down to dynamically stable patterns. Identifying these patterns, the so-called attractors, can provide important insights for biologists to understand the molecular mechanisms underlying many coordinated cellular processes such as cellular division, differentiation, and homeostasis. Both synchronous and asynchronous Boolean networks have been used to simulate genetic regulatory networks and identify their attractors. The common methods of computing attractors are that start with a randomly selected initial state and finish with exhaustive search of the state space of a network. However, the time complexity of these methods grows exponentially with respect to the number and length of attractors. Here, we build two algorithms to achieve the computation of attractors in synchronous and asynchronous Boolean networks. For the synchronous scenario, combing with iterative methods and reduced order binary decision diagrams (ROBDD), we propose an improved algorithm to compute attractors. For another algorithm, the attractors of synchronous Boolean networks are utilized in asynchronous Boolean translation functions to derive attractors of asynchronous scenario. The proposed algorithms are implemented in a procedure called geneFAtt. Compared to existing tools such as genYsis, geneFAtt is significantly faster in computing attractors for empirical experimental systems.

Availability

The software package is available at https://sites.google.com/site/desheng619/download.     

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.     

Boolean dynamics of biological networks with multiple coupled feedback loops

Boolean networks have been frequently used to study the dynamics of biological networks. In particular, there have been various studies showing that the network connectivity and the update rule of logical functions affect the dynamics of Boolean networks. There has been, however, relatively little attention paid to the dynamical role of a feedback loop, which is a circular chain of interactions between Boolean variables. We note that such feedback loops are ubiquitously found in various biological systems as multiple coupled structures and they are often the primary cause of complex dynamics. In this article, we investigate the relationship between the multiple coupled feedback loops and the dynamics of Boolean networks. We show that networks have a larger proportion of basins corresponding to fixed-point attractors as they have more coupled positive feedback loops, and a larger proportion of basins for limit-cycle attractors as they have more coupled negative feedback loops.     

An in silico target identification using Boolean network attractors: Avoiding pathological phenotypes

Target identification aims at identifying biomolecules whose function should be therapeutically altered to cure the considered pathology. An algorithm for in silico target identification using Boolean network attractors is proposed. It assumes that attractors correspond to phenotypes produced by the modeled biological network. It identifies target combinations which allow disturbed networks to avoid attractors associated with pathological phenotypes. The algorithm is tested on a Boolean model of the mammalian cell cycle and its applications are illustrated on a Boolean model of Fanconi anemia. Results show that the algorithm returns target combinations able to remove attractors associated with pathological phenotypes and then succeeds in performing the proposed in silico target identification. However, as with any in silico evidence, there is a bridge to cross between theory and practice. Nevertheless, it is expected that the algorithm is of interest for target identification.     

Algorithms and Complexity Analyses for Control of Singleton Attractors in Boolean Networks

A Boolean network (BN) is a mathematical model of genetic networks. We propose several algorithms for control of singleton attractors in BN. We theoretically estimate the average-case time complexities of the proposed algorithms, and confirm them by computer experiments. The results suggest the importance of gene ordering. Especially, setting internal nodes ahead yields shorter computational time than setting external nodes ahead in various types of algorithms. We also present a heuristic algorithm which does not look for the optimal solution but for the solution whose computational time is shorter than that of the exact algorithms.     

On the dynamics of random Boolean networks subject to noise: Attractors, ergodic sets and cell types

The asymptotic dynamics of random Boolean networks subject to random fluctuations is investigated. Under the influence of noise, the system can escape from the attractors of the deterministic model, and a thorough study of these transitions is presented. We show that the dynamics is more properly described by sets of attractors rather than single ones. We generalize here a previous notion of ergodic sets, and we show that the Threshold Ergodic Sets so defined are robust with respect to noise and, at the same time, that they do not suffer from a major drawback of ergodic sets. The system jumps from one attractor to another of the same Threshold Ergodic Set under the influence of noise, never leaving it. By interpreting random Boolean networks as models of genetic regulatory networks, we also propose to associate cell types to Threshold Ergodic Sets rather than to deterministic attractors or to ergodic sets, as it had been previously suggested. We also propose to associate cell differentiation to the process whereby a Threshold Ergodic Set composed by several attractors gives rise to another one composed by a smaller number of attractors. We show that this approach accounts for several interesting experimental facts about cell differentiation, including the possibility to obtain an induced pluripotent stem cell from a fully differentiated one by overexpressing some of its genes.     

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.     

Detecting controlling nodes of boolean regulatory networks

Boolean models of regulatory networks are assumed to be tolerant to perturbations. That qualitatively implies that each function can only depend on a few nodes. Biologically motivated constraints further show that functions found in Boolean regulatory networks belong to certain classes of functions, for example, the unate functions. It turns out that these classes have specific properties in the Fourier domain. That motivates us to study the problem of detecting controlling nodes in classes of Boolean networks using spectral techniques. We consider networks with unbalanced functions and functions of an average sensitivity less than ?k, where k is the number of controlling variables for a function. Further, we consider the class of 1-low networks which include unate networks, linear threshold networks, and networks with nested canalyzing functions. We show that the application of spectral learning algorithms leads to both better time and sample complexity for the detection of controlling nodes compared with algorithms based on exhaustive search. For a particular algorithm, we state analytical upper bounds on the number of samples needed to find the controlling nodes of the Boolean functions. Further, improved algorithms for detecting controlling nodes in large-scale unate networks are given and numerically studied.     

Generating Boolean networks with a prescribed attractor structure

MOTIVATION: Dynamical modeling of gene regulation via network models constitutes a key problem for genomics. The long-run characteristics of a dynamical system are critical and their determination is a primary aspect of system analysis. In the other direction, system synthesis involves constructing a network possessing a given set of properties. This constitutes the inverse problem. Generally, the inverse problem is ill-posed, meaning there will be many networks, or perhaps none, possessing the desired properties. Relative to long-run behavior, we may wish to construct networks possessing a desirable steady-state distribution. This paper addresses the long-run inverse problem pertaining to Boolean networks (BNs). RESULTS: The long-run behavior of a BN is characterized by its attractors. The rest of the state transition diagram is partitioned into level sets, the j-th level set being composed of all states that transition to one of the attractor states in exactly j transitions. We present two algorithms for the attractor inverse problem. The attractors are specified, and the sizes of the predictor sets and the number of levels are constrained. Algorithm complexity and performance are analyzed. The algorithmic solutions have immediate application. Under the assumption that sampling is from the steady state, a basic criterion for checking the validity of a designed network is that there should be concordance between the attractor states of the model and the data states. This criterion can be used to test a design algorithm: randomly select a set of states to be used as data states; generate a BN possessing the selected states as attractors, perhaps with some added requirements such as constraints on the number of predictors and the level structure; apply the design algorithm; and check the concordance between the attractor states of the designed network and the data states. AVAILABILITY: The software and supplementary material is available at http://gsp.tamu.edu/Publications/BNs/bn.htm     

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.     

An efficient algorithm for identifying primary phenotype attractors of a large-scale Boolean network

Background

Boolean network modeling has been widely used to model large-scale biomolecular regulatory networks as it can describe the essential dynamical characteristics of complicated networks in a relatively simple way. When we analyze such Boolean network models, we often need to find out attractor states to investigate the converging state features that represent particular cell phenotypes. This is, however, very difficult (often impossible) for a large network due to computational complexity.

Results

There have been some attempts to resolve this problem by partitioning the original network into smaller subnetworks and reconstructing the attractor states by integrating the local attractors obtained from each subnetwork. But, in many cases, the partitioned subnetworks are still too large and such an approach is no longer useful. So, we have investigated the fundamental reason underlying this problem and proposed a novel efficient way of hierarchically partitioning a given large network into smaller subnetworks by focusing on some attractors corresponding to a particular phenotype of interest instead of considering all attractors at the same time. Using the definition of attractors, we can have a simplified update rule with fixed state values for some nodes. The resulting subnetworks were small enough to find out the corresponding local attractors which can be integrated for reconstruction of the global attractor states of the original large network.

Conclusions

The proposed approach can substantially extend the current limit of Boolean network modeling for converging state analysis of biological networks.

     

Diversity of temporal correlations between genes in models of noisy and noiseless gene networks

Gene regulatory networks (GRNs) are parallel information processing systems, binding past events to future actions. Since cell types stably remain in restricted subsets of the possible states of the GRN, they are likely the dynamical attractors of the GRN. These attractors differ in which genes are active and in the amount of information propagating within the network. Using mutual information (I) as a measure of information propagation between genes in a GRN, modeled as finite-sized Random Boolean Networks (RBN), we study how the dynamical regime of the GRN affects I within attractors (I(A)). The spectra of I(A) of individual RBNs are found to be scattered and diverse, and distributions of I(A) of ensembles are non-trivial and change shape with mean connectivity. Mean and diversity of I(A) values maximize in the chaotic near-critical regime, whereas ordered near-critical networks are the best at retaining the distinctiveness of each attractor's I(A) with noise. The results suggest that selection likely favors near-critical GRNs as these both maximize mean and diversity of I(A), and are the most robust to noise. We find similar I(A) distributions in delayed stochastic models of GRNs. For a particular stochastic GRN, we show that both mean and variance of I(A) have local maxima as its connectivity and noise levels are varied, suggesting that the conclusions for the Boolean network models may be generalizable to more realistic models of GRNs.     

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.     

Dynamics of Random Boolean Networks under Fully Asynchronous Stochastic Update Based on Linear Representation

A novel algebraic approach is proposed to study dynamics of asynchronous random Boolean networks where a random number of nodes can be updated at each time step (ARBNs). In this article, the logical equations of ARBNs are converted into the discrete-time linear representation and dynamical behaviors of systems are investigated. We provide a general formula of network transition matrices of ARBNs as well as a necessary and sufficient algebraic criterion to determine whether a group of given states compose an attractor of length in ARBNs. Consequently, algorithms are achieved to find all of the attractors and basins in ARBNs. Examples are showed to demonstrate the feasibility of the proposed scheme.     

Rhythmic and non-rhythmic attractors in asynchronous random Boolean networks

In multi-component, discrete systems, such as Boolean networks and cellular automata, the scheme of updating of the individual elements plays a crucial role in determining their dynamic properties and their suitability as models of complex phenomena. Many interesting properties of these systems rely heavily on the use of synchronous updating of the individual elements. Considerations of parsimony have motivated the claim that, if the natural systems being modelled lack any clear evidence of synchronously driven elements, then random asynchronous updating should be used by default. The introduction of a random element precludes the possibility of strictly cyclic behaviour. In principle, this poses the question of whether asynchronously driven Boolean networks, cellular automata, etc., are inherently bad choices at the time of modelling rhythmic phenomena. This paper focuses on this subsidiary issue for the case of Asynchronous Random Boolean Networks (ARBNs). It defines measures of pseudo-periodicity between states and sufficiently relaxed statistical constraints. These measures are used to guide a genetic algorithm to find appropriate examples. Success in this search for a number of cases, and the subsequent statistical analysis lead to the conclusion that ARBNs can indeed be used as models of co-ordinated rhythmic phenomena, which may be stronger precisely because of their in-built asynchrony. The same technique is used to find non-stationary attractors that show no rhythm. Evidence suggests that the latter are more abundant than rhythmic attractor. The methodology is flexible, and allows for more demanding statistical conditions for defining pseudo-periodicity, and constraining the evolutionary search.     

From dissimilarities among species to dissimilarities among communities: a double principal coordinate analysis

This paper proposes a new method to reverse engineer gene regulatory networks from experimental data. The modeling framework used is time-discrete deterministic dynamical systems, with a finite set of states for each of the variables. The simplest examples of such models are Boolean networks, in which variables have only two possible states. The use of a larger number of possible states allows a finer discretization of experimental data and more than one possible mode of action for the variables, depending on threshold values. Furthermore, with a suitable choice of state set, one can employ powerful tools from computational algebra, that underlie the reverse-engineering algorithm, avoiding costly enumeration strategies. To perform well, the algorithm requires wildtype together with perturbation time courses. This makes it suitable for small to meso-scale networks rather than networks on a genome-wide scale. An analysis of the complexity of the algorithm is performed. The algorithm is validated on a recently published Boolean network model of segment polarity development in Drosophila melanogaster.     

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 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