Inverse perturbation for optimal intervention in gene regulatory networks

Algorithm to identify the optimal perturbation based on the net basin-of-state of perturbed states in Boolean network

Boolean networks are widely used to model gene regulatory networks and to design therapeutic intervention strategies to affect the long-term behavior of systems. Here, the authors investigate the 1 bit perturbation, which falls under the category of structural intervention. The authors' idea is that, if and only if a perturbed state evolves from a desirable attractor to an undesirable attractor or from an undesirable attractor to a desirable attractor, then the size of basin of attractor of a desirable attractor may decrease or increase. In this case, if the authors obtain the net BOS of the perturbed states, they can quickly obtain the optimal 1 bit perturbation by finding the maximum value of perturbation gain. Results from both synthetic and real biological networks show that the proposed algorithm is not only simpler and but also performs better than the previous basin-of-states (BOS)-based algorithm by Hu et al..

An efficient algorithm to identify the optimal one-bit perturbation based on the basin-of-state size of Boolean networks

Boolean networks are widely used to model gene regulatory networks and to design therapeutic intervention strategies to affect the long-term behavior of systems. In this paper, we investigate the less-studied one-bit perturbation, which falls under the category of structural intervention. Previous works focused on finding the optimal one-bit perturbation to maximally alter the steady-state distribution (SSD) of undesirable states through matrix perturbation theory. However, the application of the SSD is limited to Boolean networks with about ten genes. In 2007, Xiao et al. proposed to search the optimal one-bit perturbation by altering the sizes of the basin of attractions (BOAs). However, their algorithm requires close observation of the state-transition diagram. In this paper, we propose an algorithm that efficiently determines the BOA size after a perturbation. Our idea is that, if we construct the basin of states for all states, then the size of the BOA of perturbed networks can be obtained just by updating the paths of the states whose transitions have been affected. Results from both synthetic and real biological networks show that the proposed algorithm performs better than the exhaustive SSD-based algorithm and can be applied to networks with about 25 genes.

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

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.

Robustness of inverse perturbation for discrete event control

We study the robustness of the inverse perturbation solution in discrete-time systems modeled by homogeneous Markov chains. We cast the optimal inverse perturbation control as a strictly convex optimization problem, which admits a unique global solution. We show that the optimal inverse perturbation control is robust to estimation errors in the original network. The derived results are applied to the Human melanoma gene regulatory network, where the aim is to force the network to converge to a desired steady-state distribution of gene regulation.