Optimal constrained stationary intervention in gene regulatory networks

Pinning Stabilizer Design for Probabilistic Boolean Control Networks via Condensation Digraph

This article investigates the design of pinning controllers for state feedback stabilization of probabilistic Boolean control networks (PBCNs), based on the condensation digraph method. First, two effective algorithms are presented to achieve state feedback stabilization of the considered system from the perspective of condensation digraph. One is to find the desired matrix, and the other is to search for the minimum number of pinned nodes and specific pinned nodes. Then, all the mode-independent pinning controllers can be designed based on the desired matrix and pinned nodes. Several examples are delineated to illustrate the validity of the main results.

Stabilizing Large-Scale Probabilistic Boolean Networks by Pinning Control

This article aims to stabilize probabilistic Boolean networks (PBNs) via a novel pinning control strategy. In a PBN, the state evolution of each gene switches among a collection of candidate Boolean functions with preassigned probability distributions, which govern the activation frequency of each Boolean function. Due to the existence of stochasticity, the mode-independent pinning controller might be disabled. Thus, both mode-independent and mode-dependent pinning controller are required here. Moreover, a criterion is derived to determine whether mode-independent controllers are applicable while the pinned nodes are given. It is worth pointing out that this pinning control is based on the n×n network structure rather than 2ⁿ ×2ⁿ state transition matrix. Therefore, compared with the existing results, this pinning control strategy is more practicable and has the ability to handle large-scale networks, especially sparsely connected networks. To demonstrate the effectiveness of the designed control scheme, a PBN that describes the mammalian cell-cycle encountering a mutated phenotype is discussed as a simulation.

Exact Identification of the Structure of a Probabilistic Boolean Network from Samples

We study the number of samples required to uniquely determine the structure of a probabilistic Boolean network (PBN), where PBNs are probabilistic extensions of Boolean networks. We show via theoretical analysis and computational analysis that the structure of a PBN can be exactly identified with high probability from a relatively small number of samples for interesting classes of PBNs of bounded indegree. On the other hand, we also show that there exist classes of PBNs for which it is impossible to uniquely determine the structure of a PBN from samples.

Controllability and observability of Boolean networks arising from biology

Boolean networks are currently receiving considerable attention as a computational scheme for system level analysis and modeling of biological systems. Studying control-related problems in Boolean networks may reveal new insights into the intrinsic control in complex biological systems and enable us to develop strategies for manipulating biological systems using exogenous inputs. This paper considers controllability and observability of Boolean biological networks. We propose a new approach, which draws from the rich theory of symbolic computation, to solve the problems. Consequently, simple necessary and sufficient conditions for reachability, controllability, and observability are obtained, and algorithmic tests for controllability and observability which are based on the Gröbner basis method are presented. As practical applications, we apply the proposed approach to several different biological systems, namely, the mammalian cell-cycle network, the T-cell activation network, the large granular lymphocyte survival signaling network, and the Drosophila segment polarity network, gaining novel insights into the control and/or monitoring of the specific biological systems.

A comparison study of optimal and suboptimal intervention policies for gene regulatory networks in the presence of uncertainty

Perfect knowledge of the underlying state transition probabilities is necessary for designing an optimal intervention strategy for a given Markovian genetic regulatory network. However, in many practical situations, the complex nature of the network and/or identification costs limit the availability of such perfect knowledge. To address this difficulty, we propose to take a Bayesian approach and represent the system of interest as an uncertainty class of several models, each assigned some probability, which reflects our prior knowledge about the system. We define the objective function to be the expected cost relative to the probability distribution over the uncertainty class and formulate an optimal Bayesian robust intervention policy minimizing this cost function. The resulting policy may not be optimal for a fixed element within the uncertainty class, but it is optimal when averaged across the uncertainly class. Furthermore, starting from a prior probability distribution over the uncertainty class and collecting samples from the process over time, one can update the prior distribution to a posterior and find the corresponding optimal Bayesian robust policy relative to the posterior distribution. Therefore, the optimal intervention policy is essentially nonstationary and adaptive.

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.

Optimal Perturbation Control of General Topology Molecular Networks

In this paper, we develop a comprehensive framework for optimal perturbation control of dynamic networks. The aim of the perturbation is to drive the network away from an undesirable steady-state distribution and to force it to converge towards a desired steady-state distribution. The proposed framework does not make any assumptions about the topology of the initial network, and is thus applicable to general-topology networks. We define the optimal perturbation control as the minimum-energy perturbation measured in terms of the Frobenius-norm between the initial and perturbed probability transition matrices of the dynamic network. We subsequently demonstrate that there exists at most one optimal perturbation that forces the network into the desirable steady-state distribution. In the event where the optimal perturbation does not exist, we construct a family of suboptimal perturbations, and show that the suboptimal perturbation can be used to approximate the optimal limiting distribution arbitrarily closely. Moreover, we investigate the robustness of the optimal perturbation control to errors in the probability transition matrix, and demonstrate that the proposed optimal perturbation control is robust to data and inference errors in the probability transition matrix of the initial network. Finally, we apply the proposed optimal perturbation control method to the Human melanoma gene regulatory network in order to force the network from an initial steady-state distribution associated with melanoma and into a desirable steady-state distribution corresponding to a benign cell.

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.

Intervention in gene regulatory networks via phenotypically constrained control policies based on long-run behavior

A salient purpose for studying gene regulatory networks is to derive intervention strategies to identify potential drug targets and design gene-based therapeutic intervention. Optimal and approximate intervention strategies based on the transition probability matrix of the underlying Markov chain have been studied extensively for probabilistic Boolean networks. While the key goal of control is to reduce the steady-state probability mass of undesirable network states, in practice it is important to limit collateral damage and this constraint should be taken into account when designing intervention strategies with network models. In this paper, we propose two new phenotypically constrained stationary control policies by directly investigating the effects on the network long-run behavior. They are derived to reduce the risk of visiting undesirable states in conjunction with constraints on the shift of undesirable steady-state mass so that only limited collateral damage can be introduced. We have studied the performance of the new constrained control policies together with the previous greedy control policies to randomly generated probabilistic Boolean networks. A preliminary example for intervening in a metastatic melanoma network is also given to show their potential application in designing genetic therapeutics to reduce the risk of entering both aberrant phenotypes and other ambiguous states corresponding to complications or collateral damage. Experiments on both random network ensembles and the melanoma network demonstrate that, in general, the new proposed control policies exhibit the desired performance. As shown by intervening in the melanoma network, these control policies can potentially serve as future practical gene therapeutic intervention strategies.

Recent advances in intervention in markovian regulatory networks

Markovian regulatory networks constitute a class of discrete state-space models used to study gene regulatory dynamics and discover methods that beneficially alter those dynamics. Thereby, this class of models provides a framework to discover effective drug targets and design potent therapeutic strategies. The salient translational goal is to design therapeutic strategies that desirably modify network dynamics via external signals that vary the expressions of a control gene. The objective of an intervention strategy is to reduce the likelihood of the pathological cellular function related to a disease. The task of finding an effective intervention strategy can be formulated as a sequential decision making problem for a pre-defined cost of intervention and a cost-per-stage function that discriminates the gene-activity profiles. An effective intervention strategy prescribes the actions associated with an external signal that result in the minimum expected cost. This strategy in turn can be used as a treatment that reduces the long-run likelihood of gene expressions favorable to the disease. In this tutorial, we briefly summarize the first method proposed to design such therapeutic interventions, and then move on to some of the recent refinements that have been proposed. Each of these recent intervention methods is motivated by practical or analytical considerations. The presentation of the key ideas is facilitated with the help of two case studies.

From biological pathways to regulatory networks

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

Inverse perturbation for optimal intervention in gene regulatory networks

MOTIVATION

Analysis and intervention in the dynamics of gene regulatory networks is at the heart of emerging efforts in the development of modern treatment of numerous ailments including cancer. The ultimate goal is to develop methods to intervene in the function of living organisms in order to drive cells away from a malignant state into a benign form. A serious limitation of much of the previous work in cancer network analysis is the use of external control, which requires intervention at each time step, for an indefinite time interval. This is in sharp contrast to the proposed approach, which relies on the solution of an inverse perturbation problem to introduce a one-time intervention in the structure of regulatory networks. This isolated intervention transforms the steady-state distribution of the dynamic system to the desired steady-state distribution.

RESULTS

We formulate the optimal intervention problem in gene regulatory networks as a minimal perturbation of the network in order to force it to converge to a desired steady-state distribution of gene regulation. We cast optimal intervention in gene regulation as a convex optimization problem, thus providing a globally optimal solution which can be efficiently computed using standard toolboxes for convex optimization. The criteria adopted for optimality is chosen to minimize potential adverse effects as a consequence of the intervention strategy. We consider a perturbation that minimizes (i) the overall energy of change between the original and controlled networks and (ii) the time needed to reach the desired steady-state distribution of gene regulation. Furthermore, we show that there is an inherent trade-off between minimizing the energy of the perturbation and the convergence rate to the desired distribution. We apply the proposed control to the human melanoma gene regulatory network.

AVAILABILITY

The MATLAB code for optimal intervention in gene regulatory networks can be found online: http://syen.ualr.edu/nxbouaynaya/Bioinformatics2010.html.

Computational inference and analysis of genetic regulatory networks via a supervised combinatorial-optimization pattern

Background

Post-genome era brings about diverse categories of omics data. Inference and analysis of genetic regulatory networks act prominently in extracting inherent mechanisms, discovering and interpreting the related biological nature and living principles beneath mazy phenomena, and eventually promoting the well-beings of humankind.

Results

A supervised combinatorial-optimization pattern based on information and signal-processing theories is introduced into the inference and analysis of genetic regulatory networks. An associativity measure is proposed to define the regulatory strength/connectivity, and a phase-shift metric determines regulatory directions among components of the reconstructed networks. Thus, it solves the undirected regulatory problems arising from most of current linear/nonlinear relevance methods. In case of computational and topological redundancy, we constrain the classified group size of pair candidates within a multiobjective combinatorial optimization (MOCO) pattern.

Conclusions

We testify the proposed approach on two real-world microarray datasets of different statistical characteristics. Thus, we reveal the inherent design mechanisms for genetic networks by quantitative means, facilitating further theoretic analysis and experimental design with diverse research purposes. Qualitative comparisons with other methods and certain related focuses needing further work are illustrated within the discussion section.

Optimal in silico target gene deletion through nonlinear programming for genetic engineering

Background

Optimal selection of multiple regulatory genes, known as targets, for deletion to enhance or suppress the activities of downstream genes or metabolites is an important problem in genetic engineering. Such problems become more feasible to address in silico due to the availability of more realistic dynamical system models of gene regulatory and metabolic networks. The goal of the computational problem is to search for a subset of genes to knock out so that the activity of a downstream gene or a metabolite is optimized.

Methodology/Principal Findings

Based on discrete dynamical system modeling of gene regulatory networks, an integer programming problem is formulated for the optimal in silico target gene deletion problem. In the first result, the integer programming problem is proved to be NP-hard and equivalent to a nonlinear programming problem. In the second result, a heuristic algorithm, called GKONP, is designed to approximate the optimal solution, involving an approach to prune insignificant terms in the objective function, and the parallel differential evolution algorithm. In the third result, the effectiveness of the GKONP algorithm is demonstrated by applying it to a discrete dynamical system model of the yeast pheromone pathways. The empirical accuracy and time efficiency are assessed in comparison to an optimal, but exhaustive search strategy.

Significance

Although the in silico target gene deletion problem has enormous potential applications in genetic engineering, one must overcome the computational challenge due to its NP-hardness. The presented solution, which has been demonstrated to approximate the optimal solution in a practical amount of time, is among the few that address the computational challenge. In the experiment on the yeast pheromone pathways, the identified best subset of genes for deletion showed advantage over genes that were selected empirically. Once validated in vivo, the optimal target genes are expected to achieve higher genetic engineering effectiveness than a trial-and-error procedure.

Automated large-scale control of gene regulatory networks

Controlling gene regulatory networks (GRNs) is an important and hard problem. As it is the case in all control problems, the curse of dimensionality is the main issue in real applications. It is possible that hundreds of genes may regulate one biological activity in an organism; this implies a huge state space, even in the case of Boolean models. This is also evident in the literature that shows that only models of small portions of the genome could be used in control applications. In this paper, we empower our framework for controlling GRNs by eliminating the need for expert knowledge to specify some crucial threshold that is necessary for producing effective results. Our framework is characterized by applying the factored Markov decision problem (FMDP) method to the control problem of GRNs. The FMDP is a suitable framework for large state spaces as it represents the probability distribution of state transitions using compact models so that more space and time efficient algorithms could be devised for solving control problems. We successfully mapped the GRN control problem to an FMDP and propose a model reduction algorithm that helps find approximate solutions for large networks by using existing FMDP solvers. The test results reported in this paper demonstrate the efficiency and effectiveness of the proposed approach.

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.