Formally, the long-term behaviors correspond to the minimal trap sets of the state transition graph which are also called its attractors. An important type of prediction that can be obtained from such models concerns the long-term behavior of the represented processes. Different transition relations have been suggested, among them the synchronous update of Kauffman ( 1993) and the asynchronous update of Thomas ( 1991). The dynamics of such models is captured by the state transition graph, a directed graph that relates states to potential successor states.
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.īoolean and multi-valued networks are frequently used to model the dynamics of biological processes that involve gene regulation and signal transduction.
A benchmark, in which we apply the algorithm to 18 published Boolean networks, is given. 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. Our main result is an alternative approach which is based on the iterative refinement of an initially poor approximation. 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. Each is a reachability property for which we give equivalent model checking queries. 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. This paper introduces the notion of approximating asynchronous attractors of Boolean networks by minimal trap spaces.
0 kommentar(er)
