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.     

An Evaluation of Methods for Inferring Boolean Networks from Time-Series Data

Regulatory networks play a central role in cellular behavior and decision making. Learning these regulatory networks is a major task in biology, and devising computational methods and mathematical models for this task is a major endeavor in bioinformatics. Boolean networks have been used extensively for modeling regulatory networks. In this model, the state of each gene can be either ‘on’ or ‘off’ and that next-state of a gene is updated, synchronously or asynchronously, according to a Boolean rule that is applied to the current-state of the entire system. Inferring a Boolean network from a set of experimental data entails two main steps: first, the experimental time-series data are discretized into Boolean trajectories, and then, a Boolean network is learned from these Boolean trajectories. In this paper, we consider three methods for data discretization, including a new one we propose, and three methods for learning Boolean networks, and study the performance of all possible nine combinations on four regulatory systems of varying dynamics complexities. We find that employing the right combination of methods for data discretization and network learning results in Boolean networks that capture the dynamics well and provide predictive power. Our findings are in contrast to a recent survey that placed Boolean networks on the low end of the “faithfulness to biological reality” and “ability to model dynamics” spectra. Further, contrary to the common argument in favor of Boolean networks, we find that a relatively large number of time points in the time-series data is required to learn good Boolean networks for certain data sets. Last but not least, while methods have been proposed for inferring Boolean networks, as discussed above, missing still are publicly available implementations thereof. Here, we make our implementation of the methods available publicly in open source at http://bioinfo.cs.rice.edu/.     

An Attractor-Based Complexity Measurement for Boolean Recurrent Neural Networks

We provide a novel refined attractor-based complexity measurement for Boolean recurrent neural networks that represents an assessment of their computational power in terms of the significance of their attractor dynamics. This complexity measurement is achieved by first proving a computational equivalence between Boolean recurrent neural networks and some specific class of -automata, and then translating the most refined classification of -automata to the Boolean neural network context. As a result, a hierarchical classification of Boolean neural networks based on their attractive dynamics is obtained, thus providing a novel refined attractor-based complexity measurement for Boolean recurrent neural networks. These results provide new theoretical insights to the computational and dynamical capabilities of neural networks according to their attractive potentialities. An application of our findings is illustrated by the analysis of the dynamics of a simplified model of the basal ganglia-thalamocortical network simulated by a Boolean recurrent neural network. This example shows the significance of measuring network complexity, and how our results bear new founding elements for the understanding of the complexity of real brain circuits.     

A novel generalized design methodology and realization of Boolean operations using DNA

The biological deoxyribonucleic acid (DNA) strand has been increasingly seen as a promising computing unit. A new algorithm is formulated in this paper to design any DNA Boolean operator with molecular beacons (MBs) as its input. Boolean operators realized using the proposed design methodology is presented. The developed operators adopt a uniform representation for logical 0 and 1 for any Boolean operator. The Boolean operators designed in this work employ only a hybridization operation at each stage. Further, this paper for the first time brings out the realization of a binary adder and subtractor using molecular beacons. Simulation results of the DNA-based binary adder and subtractor are given to validate the design.     

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.     

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.     

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.     

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.     

Mean-field Boolean network model of a signal transduction network

In this paper we provide a mean-field Boolean network model for a signal transduction network of a generic fibroblast cell. The network consists of several main signaling pathways, including the receptor tyrosine kinase, the G-protein coupled receptor, and the Integrin signaling pathway. The network consists of 130 nodes, each representing a signaling molecule (mainly proteins). Nodes are governed by Boolean dynamics including canalizing functions as well as totalistic Boolean functions that depend only on the overall fraction of active nodes. We categorize the Boolean functions into several different classes. Using a mean-field approach we generate a mathematical formula for the probability of a node becoming active at any time step. The model is shown to be a good match for the actual network. This is done by iterating both the actual network and the model and comparing the results numerically. Using the Boolean model it is shown that the system is stable under a variety of parameter combinations. It is also shown that this model is suitable for assessing the dynamics of the network under protein mutations. Analytical results support the numerical observations that in the long-run at most half of the nodes of the network are active.     

DNA algorithm for an unbounded fan-in Boolean circuit

In this paper, we present a new DNA-based evaluation algorithm for a Boolean circuit that employs standard bio-molecular techniques. The algorithm operates on an unbounded fan-in Boolean circuit consisting of AND and OR gates. The whole simulation of our algorithm is proposed in a single test tube in O(1) time complexity and is much easier to implement in the laboratory than previously described models. Furthermore, the algorithm allows for evaluating any number of Boolean circuits in parallel in a single test tube.     

Integration of Boolean models exemplified on hepatocyte signal transduction

The number of mathematical models for biological pathways is rapidly growing. In particular, Boolean modelling proved to be suited to describe large cellular signalling networks. Systems biology is at the threshold to holistic understanding of comprehensive networks. In order to reach this goal, connection and integration of existing models of parts of cellular networks into more comprehensive network models is necessary. We discuss model combination approaches for Boolean models. Boolean modelling is qualitative rather than quantitative and does not require detailed kinetic information. We show that these models are useful precursors for large-scale quantitative models and that they are comparatively easy to combine. We propose modelling standards for Boolean models as a prerequisite for smooth model integration. Using these standards, we demonstrate the coupling of two logical models on two different examples concerning cellular interactions in the liver. In the first example, we show the integration of two Boolean models of two cell types in order to describe their interaction. In the second example, we demonstrate the combination of two models describing different parts of the network of a single cell type. Combination of partial models into comprehensive network models will take systems biology to the next level of understanding. The combination of logical models facilitated by modelling standards is a valuable example for the next step towards this goal.     

Mapping multivalued onto Boolean dynamics

This paper deals with the generalized logical framework defined by René Thomas in the 70's to qualitatively represent the dynamics of regulatory networks. In this formalism, a regulatory network is represented as a graph, where nodes denote regulatory components (basically genes) and edges denote regulations between these components. Discrete variables are associated to regulatory components accounting for their levels of expression. In most cases, Boolean variables are enough, but some situations may require further values. Despite this fact, the majority of tools dedicated to the analysis of logical models are restricted to the Boolean case. A formal Boolean mapping of multivalued logical models is a natural way of extending the applicability of these tools.Three decades ago, a multivalued to Boolean variable mapping was proposed by P. Van Ham. Since then, all works related to multivalued logical models and using a Boolean representation rely on this particular mapping. We formally show in this paper that this mapping is actually the sole, up to cosmetic changes, that could preserve the regulatory structures of the underlying graphs as well as their dynamical behaviours.     

A Full Bayesian Approach for Boolean Genetic Network Inference

Boolean networks are a simple but efficient model for describing gene regulatory systems. A number of algorithms have been proposed to infer Boolean networks. However, these methods do not take full consideration of the effects of noise and model uncertainty. In this paper, we propose a full Bayesian approach to infer Boolean genetic networks. Markov chain Monte Carlo algorithms are used to obtain the posterior samples of both the network structure and the related parameters. In addition to regular link addition and removal moves, which can guarantee the irreducibility of the Markov chain for traversing the whole network space, carefully constructed mixture proposals are used to improve the Markov chain Monte Carlo convergence. Both simulations and a real application on cell-cycle data show that our method is more powerful than existing methods for the inference of both the topology and logic relations of the Boolean network from observed data.     

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.     

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     

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.     

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.