Limits...
Approximating Attractors of Boolean Networks by Iterative CTL Model Checking.

Klarner H, Siebert H - Front Bioeng Biotechnol (2015)

Bottom Line: Our main result is an alternative approach which is based on the iterative refinement of an initially poor approximation.The algorithm detects so-called autonomous sets in the interaction graph, variables that contain all their regulators, and considers their intersection and extension in order to perform model checking on the smallest possible state spaces.A benchmark, in which we apply the algorithm to 18 published Boolean networks, is given.

View Article: PubMed Central - PubMed

Affiliation: Fachbereich Mathematik und Informatik, Freie Universität Berlin , Berlin , Germany.

ABSTRACT
This paper introduces the notion of approximating asynchronous attractors of Boolean networks by minimal trap spaces. We define three criteria for determining the quality of an approximation: "faithfulness" which requires that the oscillating variables of all attractors in a trap space correspond to their dimensions, "univocality" which requires that there is a unique attractor in each trap space, and "completeness" which requires that there are no attractors outside of a given set of trap spaces. Each is a reachability property for which we give equivalent model checking queries. Whereas faithfulness and univocality can be decided by model checking the corresponding subnetworks, the naive query for completeness must be evaluated on the full state space. Our main result is an alternative approach which is based on the iterative refinement of an initially poor approximation. The algorithm detects so-called autonomous sets in the interaction graph, variables that contain all their regulators, and considers their intersection and extension in order to perform model checking on the smallest possible state spaces. A benchmark, in which we apply the algorithm to 18 published Boolean networks, is given. In each case, the minimal trap spaces are faithful, univocal, and complete, which suggests that they are in general good approximations for the asymptotics of Boolean networks.

No MeSH data available.


Related in: MedlinePlus

(A) The interaction graph of an example network where each fi is the disjunction of its inputs (e.g., f6 = v5 + v4) except for v1 which is inhibited by v2 ( ). (B) The condensation graph (Z, ▹) with the unique top layer node {v1v2}. (C) The corresponding minimal autonomous set W. The restriction (W, F/W) is trap-space-free. (D) To extend W, we compute the graph (Z′, ▹), which is obtained from (Z, ▹) by removing the node that intersects W. The new top layer node is Y  : = {v5, v6}. (E) The extended autonomous set W ′ is obtained by considering Above(Y) in the interaction graph. It has a minimal trap space p that is defined by fixing v5 and v6 to 1.
© Copyright Policy
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC4562258&req=5

Figure 2: (A) The interaction graph of an example network where each fi is the disjunction of its inputs (e.g., f6 = v5 + v4) except for v1 which is inhibited by v2 ( ). (B) The condensation graph (Z, ▹) with the unique top layer node {v1v2}. (C) The corresponding minimal autonomous set W. The restriction (W, F/W) is trap-space-free. (D) To extend W, we compute the graph (Z′, ▹), which is obtained from (Z, ▹) by removing the node that intersects W. The new top layer node is Y  : = {v5, v6}. (E) The extended autonomous set W ′ is obtained by considering Above(Y) in the interaction graph. It has a minimal trap space p that is defined by fixing v5 and v6 to 1.

Mentions: To illustrate how the condensation graph is used for extending autonomous sets, consider the network given in Figure 2. First, we compute its minimal autonomous sets, i.e., the top layer of (Z, ▹). In this example, there is a unique W  ∈ Z with Lay(W) = 1. The restriction (W, F/W) consists of an isolated negative feedback circuit and is trap-space-free. To determine the smallest extension that contains new feedback circuits, we first compute the graph (Z′, ▹), which is obtained from the condensation graph (Z, ▹) by removing all U ∈ Z that satisfy U ∩ W  ≠ ∅. For each Y  ∈ Z′ that satisfies Lay(Y) = 1, we get an extended autonomous set W ′ by considering the variables above Y in the interaction graph (V, →). In the example, there is again a unique Y and the restriction to W ′ : = Above(Y) contains a non-trivial trap space p. The failure criterion is not satisfied by p and so we have found an initial complete set, namely P : = {p}. Note that in general, there will be several minimal autonomous sets and several possible extensions. We are now ready to design an efficient algorithm for deciding completeness.


Approximating Attractors of Boolean Networks by Iterative CTL Model Checking.

Klarner H, Siebert H - Front Bioeng Biotechnol (2015)

(A) The interaction graph of an example network where each fi is the disjunction of its inputs (e.g., f6 = v5 + v4) except for v1 which is inhibited by v2 ( ). (B) The condensation graph (Z, ▹) with the unique top layer node {v1v2}. (C) The corresponding minimal autonomous set W. The restriction (W, F/W) is trap-space-free. (D) To extend W, we compute the graph (Z′, ▹), which is obtained from (Z, ▹) by removing the node that intersects W. The new top layer node is Y  : = {v5, v6}. (E) The extended autonomous set W ′ is obtained by considering Above(Y) in the interaction graph. It has a minimal trap space p that is defined by fixing v5 and v6 to 1.
© Copyright Policy
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC4562258&req=5

Figure 2: (A) The interaction graph of an example network where each fi is the disjunction of its inputs (e.g., f6 = v5 + v4) except for v1 which is inhibited by v2 ( ). (B) The condensation graph (Z, ▹) with the unique top layer node {v1v2}. (C) The corresponding minimal autonomous set W. The restriction (W, F/W) is trap-space-free. (D) To extend W, we compute the graph (Z′, ▹), which is obtained from (Z, ▹) by removing the node that intersects W. The new top layer node is Y  : = {v5, v6}. (E) The extended autonomous set W ′ is obtained by considering Above(Y) in the interaction graph. It has a minimal trap space p that is defined by fixing v5 and v6 to 1.
Mentions: To illustrate how the condensation graph is used for extending autonomous sets, consider the network given in Figure 2. First, we compute its minimal autonomous sets, i.e., the top layer of (Z, ▹). In this example, there is a unique W  ∈ Z with Lay(W) = 1. The restriction (W, F/W) consists of an isolated negative feedback circuit and is trap-space-free. To determine the smallest extension that contains new feedback circuits, we first compute the graph (Z′, ▹), which is obtained from the condensation graph (Z, ▹) by removing all U ∈ Z that satisfy U ∩ W  ≠ ∅. For each Y  ∈ Z′ that satisfies Lay(Y) = 1, we get an extended autonomous set W ′ by considering the variables above Y in the interaction graph (V, →). In the example, there is again a unique Y and the restriction to W ′ : = Above(Y) contains a non-trivial trap space p. The failure criterion is not satisfied by p and so we have found an initial complete set, namely P : = {p}. Note that in general, there will be several minimal autonomous sets and several possible extensions. We are now ready to design an efficient algorithm for deciding completeness.

Bottom Line: Our main result is an alternative approach which is based on the iterative refinement of an initially poor approximation.The algorithm detects so-called autonomous sets in the interaction graph, variables that contain all their regulators, and considers their intersection and extension in order to perform model checking on the smallest possible state spaces.A benchmark, in which we apply the algorithm to 18 published Boolean networks, is given.

View Article: PubMed Central - PubMed

Affiliation: Fachbereich Mathematik und Informatik, Freie Universität Berlin , Berlin , Germany.

ABSTRACT
This paper introduces the notion of approximating asynchronous attractors of Boolean networks by minimal trap spaces. We define three criteria for determining the quality of an approximation: "faithfulness" which requires that the oscillating variables of all attractors in a trap space correspond to their dimensions, "univocality" which requires that there is a unique attractor in each trap space, and "completeness" which requires that there are no attractors outside of a given set of trap spaces. Each is a reachability property for which we give equivalent model checking queries. Whereas faithfulness and univocality can be decided by model checking the corresponding subnetworks, the naive query for completeness must be evaluated on the full state space. Our main result is an alternative approach which is based on the iterative refinement of an initially poor approximation. The algorithm detects so-called autonomous sets in the interaction graph, variables that contain all their regulators, and considers their intersection and extension in order to perform model checking on the smallest possible state spaces. A benchmark, in which we apply the algorithm to 18 published Boolean networks, is given. In each case, the minimal trap spaces are faithful, univocal, and complete, which suggests that they are in general good approximations for the asymptotics of Boolean networks.

No MeSH data available.


Related in: MedlinePlus