Minimally perturbing a gene regulatory network to avoid a disease phenotype: the glioma network as a test case

Abstract

Background: Mathematical modeling of biological networks is an essential part of Systems Biology. Developing and using such models in order to understand gene regulatory networks is a major challenge.

Results: We present an algorithm that determines the smallest perturbations required for manipulating the dynamics of a network formulated as a Petri net, in order to cause or avoid a specified phenotype. By modifying McMillan's unfolding algorithm, we handle partial knowledge and reduce computation cost. The methodology is demonstrated on a glioma network. Out of the single gene perturbations, activation of glutathione S-transferase P (GSTP1) gene was by far the most effective in blocking the cancer phenotype. Among pairs of perturbations, NFkB and TGF-beta had the largest joint effect, in accordance with their role in the EMT process.

Conclusion: Our method allows perturbation analysis of regulatory networks and can overcome incomplete information. It can help in identifying drug targets and in prioritizing perturbation experiments.

Figure 1

A simple GRN and its state graph. A: A simple GRN. The network contains three entities, A, B and C. Entities A and C regulate entity B, B regulates C, and C regulates A. Each table shows the level of the regulated gene when its regulation function acts, depending on the regulators' levels. B: The state graph of the GRN. Nodes correspond to global states (with coordinates A, B, C from left to right), and edges to transitions between these states. The labels on the edges show the regulation functions that cause this transition. C: The restricted state graph starting from the initial state 000. Only states that are reachable by transitions from 000 are shown. For simplicity, self loops are not shown. Sequences of state traversals that follow from the initial state can be cyclic (return to the same state) or can lead to the endpoint state 111.

Figure 2

A Petri net and its unfolding. A: A Petri net and its unfolding. The net contains 'places' (light blue circles), the model's entities, and 'transitions' (rectangles), which constitute the regulation functions and define the model's dynamics. Arcs connect input places to transitions, and transitions to their output places. Places that receive discrete values are called tokens (blue dots). A transition that is activated, or 'fired', reduces the tokens in its input places and increases the number of tokens in each of its output places. At any time step, every transition that has enough tokens in its input places may be fired. In the example, every transition consumes one token from every input place, and produces one token at every output place. Labels next to thick arrows indicate which transition fired. Transitions t1 and t3 can be fired in alternation indefinitely, whereas no other transition can be fired after t2 has fired. B: Unfolding of the Petri net. Transitions are represented by rectangles, places by circles. The two places p₁ and p₂ that have tokens in the initial marking in state I are the input-less places of the unfolding. The local configuration of t₂ at layer 2 corresponds to the marking 010, i.e. the marking in which only p₂ contains a token, corresponding to II in Figure 2A. The local configuration of t₃ corresponds to the firing of t₁ followed by t₃, and to the marking 110, i.e. the initial marking. The instances of t₁ and of t₂ at layer 6 are cutoff points, since their local configurations' markings are already represented by other local configurations. The graph constitutes a branching process.

Figure 3

Petri net representation of a Boolean entity. In this example gene 2 inactivates gene 1. Each of them is represented by two places in the Petri net. The upper (lower) part of the figure shows the Petri net before (after) the transition fires. When gene 2 is active, it inactivates gene 1. Therefore, the transition consumes a token from the active place of gene 1, and produces a token to its inactive place. The transition also consumes a token from the active place of gene 2, and produces a token to the same place. The latter consumption and production express the fact that gene 2 needs to be active in order to inactivate gene 1, but the inactivation itself does not change the level of gene 2.

Figure 4

The glioma network. Genes (ovals) and their alternative regulation functions (rectangles) are bordered by frames of the same color. Ovals contain the name of the relevant human gene, following the nomenclature in [48]. Rectangles contain the name of the regulation function [49]. Regulation functions are connected by directed edges to the gene they regulate. Regulators are connected by directed edges to the regulation functions in which they are involved. The figure was generated using Cytoscape [59]. The bold arrows indicate the two entities that constitute the prohibited phenotype (see text).

Figure 5

Frequency of perturbation size needed. The histogram plots the fraction of solutions of each size. "Size 0" indicates states from which the avoided phenotype is not reachable.

Figure 6

Frequency of minimal perturbations of sizes 1, 2 and 3. Each bar shows the proportion of the occurrences of a different perturbation. Act: activation; rep: repression