A CoD-based reduction algorithm for designing stationary control policies on Boolean networks

Control of Large-Scale Boolean Networks via Network Aggregation

A major challenge to solve problems in control of Boolean networks is that the computational cost increases exponentially when the number of nodes in the network increases. We consider the problem of controllability and stabilizability of Boolean control networks, address the increasing cost problem by partitioning the network graph into several subnetworks, and analyze the subnetworks separately. Easily verifiable necessary conditions for controllability and stabilizability are proposed for a general aggregation structure. For acyclic aggregation, we develop a sufficient condition for stabilizability. It dramatically reduces the computational complexity if the number of nodes in each block of the acyclic aggregation is small enough compared with the number of nodes in the entire Boolean network.

Efficient experimental design for uncertainty reduction in gene regulatory networks

Background

An accurate understanding of interactions among genes plays a major role in developing therapeutic intervention methods. Gene regulatory networks often contain a significant amount of uncertainty. The process of prioritizing biological experiments to reduce the uncertainty of gene regulatory networks is called experimental design. Under such a strategy, the experiments with high priority are suggested to be conducted first.

Results

The authors have already proposed an optimal experimental design method based upon the objective for modeling gene regulatory networks, such as deriving therapeutic interventions. The experimental design method utilizes the concept of mean objective cost of uncertainty (MOCU). MOCU quantifies the expected increase of cost resulting from uncertainty. The optimal experiment to be conducted first is the one which leads to the minimum expected remaining MOCU subsequent to the experiment. In the process, one must find the optimal intervention for every gene regulatory network compatible with the prior knowledge, which can be prohibitively expensive when the size of the network is large. In this paper, we propose a computationally efficient experimental design method. This method incorporates a network reduction scheme by introducing a novel cost function that takes into account the disruption in the ranking of potential experiments. We then estimate the approximate expected remaining MOCU at a lower computational cost using the reduced networks.

Conclusions

Simulation results based on synthetic and real gene regulatory networks show that the proposed approximate method has close performance to that of the optimal method but at lower computational cost. The proposed approximate method also outperforms the random selection policy significantly. A MATLAB software implementing the proposed experimental design method is available at http://gsp.tamu.edu/Publications/supplementary/roozbeh15a/.

Learning restricted Boolean network model by time-series data

Restricted Boolean networks are simplified Boolean networks that are required for either negative or positive regulations between genes. Higa et al. (BMC Proc 5:S5, 2011) proposed a three-rule algorithm to infer a restricted Boolean network from time-series data. However, the algorithm suffers from a major drawback, namely, it is very sensitive to noise. In this paper, we systematically analyze the regulatory relationships between genes based on the state switch of the target gene and propose an algorithm with which restricted Boolean networks may be inferred from time-series data. We compare the proposed algorithm with the three-rule algorithm and the best-fit algorithm based on both synthetic networks and a well-studied budding yeast cell cycle network. The performance of the algorithms is evaluated by three distance metrics: the normalized-edge Hamming distance [Formula: see text], the normalized Hamming distance of state transition [Formula: see text], and the steady-state distribution distance μ (ssd). Results show that the proposed algorithm outperforms the others according to both [Formula: see text] and [Formula: see text], whereas its performance according to μ (ssd) is intermediate between best-fit and the three-rule algorithms. Thus, our new algorithm is more appropriate for inferring interactions between genes from time-series data.

Using the minimum description length principle to reduce the rate of false positives of best-fit algorithms

The inference of gene regulatory networks is a core problem in systems biology. Many inference algorithms have been proposed and all suffer from false positives. In this paper, we use the minimum description length (MDL) principle to reduce the rate of false positives for best-fit algorithms. The performance of these algorithms is evaluated via two metrics: the normalized-edge Hamming distance and the steady-state distribution distance. Results for synthetic networks and a well-studied budding-yeast cell cycle network show that MDL-based filtering is more effective than filtering based on conditional mutual information (CMI). In addition, MDL-based filtering provides better inference than the MDL algorithm itself.

Optimal Intervention in Markovian Gene Regulatory Networks With Random-Length Therapeutic Response to Antitumor Drug

The most effective cancer treatments are the ones that prolong patients' lives while offering a reasonable quality of life during and after treatment. The treatments must also carry out their actions rapidly and with high efficiency such that a very large percentage of tumor cells die or shift into a state where they stop proliferating. Due to biological and microenvironmental variabilities within tumor cells, the action period of an administered drug can vary among a population of patients. In this paper, based on a recently proposed model for tumor growth inhibition, we first probabilistically characterize the variability of the length of drug action. Then, we present a methodology to devise optimal intervention strategies for any Markovian genetic regulatory network governing the tumor when the antitumor drug has a random-length duration of action.

Recent development and biomedical applications of probabilistic Boolean networks

Probabilistic Boolean network (PBN) modelling is a semi-quantitative approach widely used for the study of the topology and dynamic aspects of biological systems. The combined use of rule-based representation and probability makes PBN appealing for large-scale modelling of biological networks where degrees of uncertainty need to be considered.A considerable expansion of our knowledge in the field of theoretical research on PBN can be observed over the past few years, with a focus on network inference, network intervention and control. With respect to areas of applications, PBN is mainly used for the study of gene regulatory networks though with an increasing emergence in signal transduction, metabolic, and also physiological networks. At the same time, a number of computational tools, facilitating the modelling and analysis of PBNs, are continuously developed.A concise yet comprehensive review of the state-of-the-art on PBN modelling is offered in this article, including a comparative discussion on PBN versus similar models with respect to concepts and biomedical applications. Due to their many advantages, we consider PBN to stand as a suitable modelling framework for the description and analysis of complex biological systems, ranging from molecular to physiological levels.

Intervention in gene regulatory networks with maximal phenotype alteration

MOTIVATION

A basic issue for translational genomics is to model gene interaction via gene regulatory networks (GRNs) and thereby provide an informatics environment to study the effects of intervention (say, via drugs) and to derive effective intervention strategies. Taking the view that the phenotype is characterized by the long-run behavior (steady-state distribution) of the network, we desire interventions to optimally move the probability mass from undesirable to desirable states Heretofore, two external control approaches have been taken to shift the steady-state mass of a GRN: (i) use a user-defined cost function for which desirable shift of the steady-state mass is a by-product and (ii) use heuristics to design a greedy algorithm. Neither approach provides an optimal control policy relative to long-run behavior.

RESULTS

We use a linear programming approach to optimally shift the steady-state mass from undesirable to desirable states, i.e. optimization is directly based on the amount of shift and therefore must outperform previously proposed methods. Moreover, the same basic linear programming structure is used for both unconstrained and constrained optimization, where in the latter case, constraints on the optimization limit the amount of mass that may be shifted to 'ambiguous' states, these being states that are not directly undesirable relative to the pathology of interest but which bear some perceived risk. We apply the method to probabilistic Boolean networks, but the theory applies to any Markovian GRN.

AVAILABILITY

Supplementary materials, including the simulation results, MATLAB source code and description of suboptimal methods are available at http://gsp.tamu.edu/Publications/supplementary/yousefi13b.

CONTACT

edward@ece.tamu.edu

SUPPLEMENTARY INFORMATION

Supplementary data are available at Bioinformatics online.

Newton, laplace, and the epistemology of systems biology

For science, theoretical or applied, to significantly advance, researchers must use the most appropriate mathematical methods. A century and a half elapsed between Newton's development of the calculus and Laplace's development of celestial mechanics. One cannot imagine the latter without the former. Today, more than three-quarters of a century has elapsed since the birth of stochastic systems theory. This article provides a perspective on the utilization of systems theory as the proper vehicle for the development of systems biology and its application to complex regulatory diseases such as cancer.

On optimal control policy for probabilistic Boolean network: a state reduction approach

Background

Probabilistic Boolean Network (PBN) is a popular model for studying genetic regulatory networks. An important and practical problem is to find the optimal control policy for a PBN so as to avoid the network from entering into undesirable states. A number of research works have been done by using dynamic programming-based (DP) method. However, due to the high computational complexity of PBNs, DP method is computationally inefficient for a large size network. Therefore it is natural to seek for approximation methods.

Results

Inspired by the state reduction strategies, we consider using dynamic programming in conjunction with state reduction approach to reduce the computational cost of the DP method. Numerical examples are given to demonstrate both the effectiveness and the efficiency of our proposed method.

Conclusions

Finding the optimal control policy for PBNs is meaningful. The proposed problem has been shown to be ∑2p - hard. By taking state reduction approach into consideration, the proposed method can speed up the computational time in applying dynamic programming-based algorithm. In particular, the proposed method is effective for larger size networks.

Gene interaction enrichment and network analysis to identify dysregulated pathways and their interactions in complex diseases

BACKGROUND

The molecular behavior of biological systems can be described in terms of three fundamental components: (i) the physical entities, (ii) the interactions among these entities, and (iii) the dynamics of these entities and interactions. The mechanisms that drive complex disease can be productively viewed in the context of the perturbations of these components. One challenge in this regard is to identify the pathways altered in specific diseases. To address this challenge, Gene Set Enrichment Analysis (GSEA) and others have been developed, which focus on alterations of individual properties of the entities (such as gene expression). However, the dynamics of the interactions with respect to disease have been less well studied (i.e., properties of components ii and iii).

RESULTS

Here, we present a novel method called Gene Interaction Enrichment and Network Analysis (GIENA) to identify dysregulated gene interactions, i.e., pairs of genes whose relationships differ between disease and control. Four functions are defined to model the biologically relevant gene interactions of cooperation (sum of mRNA expression), competition (difference between mRNA expression), redundancy (maximum of expression), or dependency (minimum of expression) among the expression levels. The proposed framework identifies dysregulated interactions and pathways enriched in dysregulated interactions; points out interactions that are perturbed across pathways; and moreover, based on the biological annotation of each type of dysregulated interaction gives clues about the regulatory logic governing the systems level perturbation. We demonstrated the potential of GIENA using published datasets related to cancer.

CONCLUSIONS

We showed that GIENA identifies dysregulated pathways that are missed by traditional enrichment methods based on the individual gene properties and that use of traditional methods combined with GIENA provides coverage of the largest number of relevant pathways. In addition, using the interactions detected by GIENA, specific gene networks both within and across pathways associated with the relevant phenotypes are constructed and analyzed.

PATHWAY REGULATORY ANALYSIS IN THE CONTEXT OF BAYESIAN NETWORKS USING THE COEFFICIENT OF DETERMINATION

To effectively intervene when cells are trapped in pathological modes of operation it is necessary to build models that capture relevant network structure and include characterization of dynamical changes within the system. The model must be of sufficient detail that it facilitates the selection of intervention points where pathological cell behavior arising from improper regulation can be stopped. What is known about this type of cellular decision-making is consistent with the general expectations associated with any kind of decision-making operation. If the result of a decision at one node is serially transmitted to other nodes, resetting their states, then the process may suffer from mechanistic inefficiencies of transmission or from blockage or activation of transmission through the action of other nodes acting on the same node. A standard signal-processing network model, Bayesian networks, can model these properties. This paper employs a Bayesian tree model to characterize conditional pathway logic and quantify the effects of different branching patterns, signal transmission efficiencies and levels of alternate or redundant inputs. In particular, it characterizes master genes and canalizing genes within the quantitative framework. The model is also used to examine what inferences about the network structure can be made when perturbations are applied to various points in the network.

A CoD-based stationary control policy for intervening in large gene regulatory networks

BACKGROUND

One of the most important goals of the mathematical modeling of gene regulatory networks is to alter their behavior toward desirable phenotypes. Therapeutic techniques are derived for intervention in terms of stationary control policies. In large networks, it becomes computationally burdensome to derive an optimal control policy. To overcome this problem, greedy intervention approaches based on the concept of the Mean First Passage Time or the steady-state probability mass of the network states were previously proposed. Another possible approach is to use reduction mappings to compress the network and develop control policies on its reduced version. However, such mappings lead to loss of information and require an induction step when designing the control policy for the original network.

RESULTS

In this paper, we propose a novel solution, CoD-CP, for designing intervention policies for large Boolean networks. The new method utilizes the Coefficient of Determination (CoD) and the Steady-State Distribution (SSD) of the model. The main advantage of CoD-CP in comparison with the previously proposed methods is that it does not require any compression of the original model, and thus can be directly designed on large networks. The simulation studies on small synthetic networks shows that CoD-CP performs comparable to previously proposed greedy policies that were induced from the compressed versions of the networks. Furthermore, on a large 17-gene gastrointestinal cancer network, CoD-CP outperforms other two available greedy techniques, which is precisely the kind of case for which CoD-CP has been developed. Finally, our experiments show that CoD-CP is robust with respect to the attractor structure of the model.

CONCLUSIONS

The newly proposed CoD-CP provides an attractive alternative for intervening large networks where other available greedy methods require size reduction on the network and an extra induction step before designing a control policy.

Probabilistic reconstruction of the tumor progression process in gene regulatory networks in the presence of uncertainty

Background

Accumulation of gene mutations in cells is known to be responsible for tumor progression, driving it from benign states to malignant states. However, previous studies have shown that the detailed sequence of gene mutations, or the steps in tumor progression, may vary from tumor to tumor, making it difficult to infer the exact path that a given type of tumor may have taken.

Results

In this paper, we propose an effective probabilistic algorithm for reconstructing the tumor progression process based on partial knowledge of the underlying gene regulatory network and the steady state distribution of the gene expression values in a given tumor. We take the BNp (Boolean networks with pertubation) framework to model the gene regulatory networks. We assume that the true network is not exactly known but we are given an uncertainty class of networks that contains the true network. This network uncertainty class arises from our partial knowledge of the true network, typically represented as a set of local pathways that are embedded in the global network. Given the SSD of the cancerous network, we aim to simultaneously identify the true normal (healthy) network and the set of gene mutations that drove the network into the cancerous state. This is achieved by analyzing the effect of gene mutation on the SSD of a gene regulatory network. At each step, the proposed algorithm reduces the uncertainty class by keeping only those networks whose SSDs get close enough to the cancerous SSD as a result of additional gene mutation. These steps are repeated until we can find the best candidate for the true network and the most probable path of tumor progression.

Conclusions

Simulation results based on both synthetic networks and networks constructed from actual pathway knowledge show that the proposed algorithm can identify the normal network and the actual path of tumor progression with high probability. The algorithm is also robust to model mismatch and allows us to control the trade-off between efficiency and accuracy.

State reduction for network intervention in probabilistic Boolean networks

MOTIVATION

A key goal of studying biological systems is to design therapeutic intervention strategies. Probabilistic Boolean networks (PBNs) constitute a mathematical model which enables modeling, predicting and intervening in their long-run behavior using Markov chain theory. The long-run dynamics of a PBN, as represented by its steady-state distribution (SSD), can guide the design of effective intervention strategies for the modeled systems. A major obstacle for its application is the large state space of the underlying Markov chain, which poses a serious computational challenge. Hence, it is critical to reduce the model complexity of PBNs for practical applications.

RESULTS

We propose a strategy to reduce the state space of the underlying Markov chain of a PBN based on a criterion that the reduction least distorts the proportional change of stationary masses for critical states, for instance, the network attractors. In comparison to previous reduction methods, we reduce the state space directly, without deleting genes. We then derive stationary control policies on the reduced network that can be naturally induced back to the original network. Computational experiments study the effects of the reduction on model complexity and the performance of designed control policies which is measured by the shift of stationary mass away from undesirable states, those associated with undesirable phenotypes. We consider randomly generated networks as well as a 17-gene gastrointestinal cancer network, which, if not reduced, has a 2(17) × 2(17) transition probability matrix. Such a dimension is too large for direct application of many previously proposed PBN intervention strategies.