Maximum Number of Fixed Points in Regulatory Boolean Networks

Boolean networks (BNs) have been extensively used as mathematical models of genetic regulatory networks. The number of fixed points of a BN is a key feature of its dynamical behavior. Here, we study the maximum number of fixed points in a particular class of BNs called regulatory Boolean networks, where each interaction between the elements of the network is either an activation or an inhibition. We find relationships between the positive and negative cycles of the interaction graph and the number of fixed points of the network. As our main result, we exhibit an upper bound for the number of fixed points in terms of minimum cardinality of a set of vertices meeting all positive cycles of the network, which can be applied in the design of genetic regulatory networks.     

Majority Rules with Random Tie-Breaking in Boolean Gene Regulatory Networks

We consider threshold Boolean gene regulatory networks, where the update function of each gene is described as a majority rule evaluated among the regulators of that gene: it is turned ON when the sum of its regulator contributions is positive (activators contribute positively whereas repressors contribute negatively) and turned OFF when this sum is negative. In case of a tie (when contributions cancel each other out), it is often assumed that the gene keeps it current state. This framework has been successfully used to model cell cycle control in yeast. Moreover, several studies consider stochastic extensions to assess the robustness of such a model.Here, we introduce a novel, natural stochastic extension of the majority rule. It consists in randomly choosing the next value of a gene only in case of a tie. Hence, the resulting model includes deterministic and probabilistic updates. We present variants of the majority rule, including alternate treatments of the tie situation. Impact of these variants on the corresponding dynamical behaviours is discussed. After a thorough study of a class of two-node networks, we illustrate the interest of our stochastic extension using a published cell cycle model. In particular, we demonstrate that steady state analysis can be rigorously performed and can lead to effective predictions; these relate for example to the identification of interactions whose addition would ensure that a specific state is absorbing.     

A Semiquantitative Framework for Gene Regulatory Networks: Increasing the Time and Quantitative Resolution of Boolean Networks

Boolean models have been instrumental in predicting general features of gene networks and more recently also as explorative tools in specific biological applications. In this study we introduce a basic quantitative and a limited time resolution to a discrete (Boolean) framework. Quantitative resolution is improved through the employ of normalized variables in unison with an additive approach. Increased time resolution stems from the introduction of two distinct priority classes. Through the implementation of a previously published chondrocyte network and T helper cell network, we show that this addition of quantitative and time resolution broadens the scope of biological behaviour that can be captured by the models. Specifically, the quantitative resolution readily allows models to discern qualitative differences in dosage response to growth factors. The limited time resolution, in turn, can influence the reachability of attractors, delineating the likely long term system behaviour. Importantly, the information required for implementation of these features, such as the nature of an interaction, is typically obtainable from the literature. Nonetheless, a trade-off is always present between additional computational cost of this approach and the likelihood of extending the model’s scope. Indeed, in some cases the inclusion of these features does not yield additional insight. This framework, incorporating increased and readily available time and semi-quantitative resolution, can help in substantiating the litmus test of dynamics for gene networks, firstly by excluding unlikely dynamics and secondly by refining falsifiable predictions on qualitative behaviour.     

Polynomial-Time Algorithm for Controllability Test of a Class of Boolean Biological Networks

In recent years, Boolean-network-model-based approaches to dynamical analysis of complex biological networks such as gene regulatory networks have been extensively studied. One of the fundamental problems in control theory of such networks is the problem of determining whether a given substance quantity can be arbitrarily controlled by operating the other substance quantities, which we call the controllability problem. This paper proposes a polynomial-time algorithm for solving this problem. Although the algorithm is based on a sufficient condition for controllability, it is easily computable for a wider class of large-scale biological networks compared with the existing approaches. A key to this success in our approach is to give up computing Boolean operations in a rigorous way and to exploit an adjacency matrix of a directed graph induced by a Boolean network. By applying the proposed approach to a neurotransmitter signaling pathway, it is shown that it is effective.     

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.     

SMETANA: Accurate and Scalable Algorithm for Probabilistic Alignment of Large-Scale Biological Networks

In this paper we introduce an efficient algorithm for alignment of multiple large-scale biological networks. In this scheme, we first compute a probabilistic similarity measure between nodes that belong to different networks using a semi-Markov random walk model. The estimated probabilities are further enhanced by incorporating the local and the cross-species network similarity information through the use of two different types of probabilistic consistency transformations. The transformed alignment probabilities are used to predict the alignment of multiple networks based on a greedy approach. We demonstrate that the proposed algorithm, called SMETANA, outperforms many state-of-the-art network alignment techniques, in terms of computational efficiency, alignment accuracy, and scalability. Our experiments show that SMETANA can easily align tens of genome-scale networks with thousands of nodes on a personal computer without any difficulty. The source code of SMETANA is available upon request. The source code of SMETANA can be downloaded from http://www.ece.tamu.edu/~bjyoon/SMETANA/.     

Quantum Transport in Networks and Photosynthetic Complexes at the Steady State

Recently, several works have analysed the efficiency of photosynthetic complexes in a transient scenario and how that efficiency is affected by environmental noise. Here, following a quantum master equation approach, we study the energy and excitation transport in fully connected networks both in general and in the particular case of the Fenna–Matthew–Olson complex. The analysis is carried out for the steady state of the system where the excitation energy is constantly “flowing” through the system. Steady state transport scenarios are particularly relevant if the evolution of the quantum system is not conditioned on the arrival of individual excitations. By adding dephasing to the system, we analyse the possibility of noise-enhancement of the quantum transport.     

Boolean Models of Genomic Regulatory Networks: Reduction Mappings,Inference, and External Control

Computational modeling of genomic regulation has become an important focus of systems biology and genomic signal processing for the past several years. It holds the promise to uncover both the structure and dynamical properties of the complex gene, protein or metabolic networks responsible for the cell functioning in various contexts and regimes. This, in turn, will lead to the development of optimal intervention strategies for prevention and control of disease. At the same time, constructing such computational models faces several challenges. High complexity is one of the major impediments for the practical applications of the models. Thus, reducing the size/complexity of a model becomes a critical issue in problems such as model selection, construction of tractable subnetwork models, and control of its dynamical behavior. We focus on the reduction problem in the context of two specific models of genomic regulation: Boolean networks with perturbation (BN_P) and probabilistic Boolean networks (PBN). We also compare and draw a parallel between the reduction problem and two other important problems of computational modeling of genomic networks: the problem of network inference and the problem of designing external control policies for intervention/altering the dynamics of the model.     

Steady State Detection of Chemical Reaction Networks Using a Simplified Analytical Method

Chemical reaction networks (CRNs) are susceptible to mathematical modelling. The dynamic behavior of CRNs can be investigated by solving the polynomial equations derived from its structure. However, simple CRN give rise to non-linear polynomials that are difficult to resolve. Here we propose a procedure to locate the steady states of CRNs from a formula derived through algebraic geometry methods. We have applied this procedure to define the steady states of a classic CRN that exhibits instability, and to a model of programmed cell death.     

Analysis of Discrete Bioregulatory Networks Using Symbolic Steady States

A discrete model of a biological regulatory network can be represented by a discrete function that contains all available information on interactions between network components and the rules governing the evolution of the network in a finite state space. Since the state space size grows exponentially with the number of network components, analysis of large networks is a complex problem. In this paper, we introduce the notion of symbolic steady state that allows us to identify subnetworks that govern the dynamics of the original network in some region of state space. We state rules to explicitly construct attractors of the system from subnetwork attractors. Using the results, we formulate sufficient conditions for the existence of multiple attractors resp. a cyclic attractor based on the existence of positive resp. negative feedback circuits in the graph representing the structure of the system. In addition, we discuss approaches to finding symbolic steady states. We focus both on dynamics derived via synchronous as well as asynchronous update rules. Lastly, we illustrate the results by analyzing a model of T helper cell differentiation.     

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.     

Identification of a Topological Characteristic Responsible for the Biological Robustness of Regulatory Networks

Attribution of biological robustness to the specific structural properties of a regulatory network is an important yet unsolved problem in systems biology. It is widely believed that the topological characteristics of a biological control network largely determine its dynamic behavior, yet the actual mechanism is still poorly understood. Here, we define a novel structural feature of biological networks, termed ‘regulation entropy’, to quantitatively assess the influence of network topology on the robustness of the systems. Using the cell-cycle control networks of the budding yeast (Saccharomyces cerevisiae) and the fission yeast (Schizosaccharomyces pombe) as examples, we first demonstrate the correlation of this quantity with the dynamic stability of biological control networks, and then we establish a significant association between this quantity and the structural stability of the networks. And we further substantiate the generality of this approach with a broad spectrum of biological and random networks. We conclude that the regulation entropy is an effective order parameter in evaluating the robustness of biological control networks. Our work suggests a novel connection between the topological feature and the dynamic property of biological regulatory networks.     

Evolving sensitivity balances Boolean Networks

We investigate the sensitivity of Boolean Networks (BNs) to mutations. We are interested in Boolean Networks as a model of Gene Regulatory Networks (GRNs). We adopt Ribeiro and Kauffman's Ergodic Set and use it to study the long term dynamics of a BN. We define the sensitivity of a BN to be the mean change in its Ergodic Set structure under all possible loss of interaction mutations. In silico experiments were used to selectively evolve BNs for sensitivity to losing interactions. We find that maximum sensitivity was often achievable and resulted in the BNs becoming topologically balanced, i.e. they evolve towards network structures in which they have a similar number of inhibitory and excitatory interactions. In terms of the dynamics, the dominant sensitivity strategy that evolved was to build BNs with Ergodic Sets dominated by a single long limit cycle which is easily destabilised by mutations. We discuss the relevance of our findings in the context of Stem Cell Differentiation and propose a relationship between pluripotent stem cells and our evolved sensitive networks.     

PATHLOGIC-S: A Scalable Boolean Framework for Modelling Cellular Signalling

Curated databases of signal transduction have grown to describe several thousand reactions, and efficient use of these data requires the development of modelling tools to elucidate and explore system properties. We present PATHLOGIC-S, a Boolean specification for a signalling model, with its associated GPL-licensed implementation using integer programming techniques. The PATHLOGIC-S specification has been designed to function on current desktop workstations, and is capable of providing analyses on some of the largest currently available datasets through use of Boolean modelling techniques to generate predictions of stable and semi-stable network states from data in community file formats. PATHLOGIC-S also addresses major problems associated with the presence and modelling of inhibition in Boolean systems, and reduces logical incoherence due to common inhibitory mechanisms in signalling systems. We apply this approach to signal transduction networks including Reactome and two pathways from the Panther Pathways database, and present the results of computations on each along with a discussion of execution time. A software implementation of the framework and model is freely available under a GPL license.     

On Circuit Functionality in Boolean Networks

It has been proved, for several classes of continuous and discrete dynamical systems, that the presence of a positive (resp. negative) circuit in the interaction graph of a system is a necessary condition for the presence of multiple stable states (resp. a cyclic attractor). A positive (resp. negative) circuit is said to be functional when it “generates” several stable states (resp. a cyclic attractor). However, there are no definite mathematical frameworks translating the underlying meaning of “generates.” Focusing on Boolean networks, we recall and propose some definitions concerning the notion of functionality along with associated mathematical results.     

Inference of Boolean Networks Using Sensitivity Regularization

The inference of genetic regulatory networks from global measurements of gene expressions is an important problem in computational biology. Recent studies suggest that such dynamical molecular systems are poised at a critical phase transition between an ordered and a disordered phase, affording the ability to balance stability and adaptability while coordinating complex macroscopic behavior. We investigate whether incorporating this dynamical system-wide property as an assumption in the inference process is beneficial in terms of reducing the inference error of the designed network. Using Boolean networks, for which there are well-defined notions of ordered, critical, and chaotic dynamical regimes as well as well-studied inference procedures, we analyze the expected inference error relative to deviations in the networks'' dynamical regimes from the assumption of criticality. We demonstrate that taking criticality into account via a penalty term in the inference procedure improves the accuracy of prediction both in terms of state transitions and network wiring, particularly for small sample sizes.