Proceedings Article | 29 June 2005
Proc. SPIE. 5839, Bioengineered and Bioinspired Systems II
KEYWORDS: Proteins, Switches, Cancer, Molecules, Organisms, Control systems, Computer simulations, Statistical modeling, Systems modeling, Feedback signals
A random Boolean network is a synchronous Boolean automaton with n
vertices. The parameters of an RBN can be tuned so that its
statistical features match the characteristics of the gene regulatory
system. The number of vertices of the RBN represents the number of
genes in the cell. The number of cycles in the RBN's state space,
called attractors, corresponds the number of different cell
types. Attractor's length corresponds to the cell cycle time.
Sensitivity of the attractors to different kind of perturbations,
modeled by changing the state of a particular vertex, associated
Boolean function, or network edge, reflects the stability of the cell
to damage, mutations and virus attacks. In order to evaluate the
attractors, their number and length have to be re-computed
repeatedly. For large RBN's, searching for attractors in the O(2<sup>n</sup>) state space is an infeasible task. Fortunately, only a subset of vertices of an RBN, called relevant vertices, determines its dynamics. The remaining vertices are redundant. In this paper, we present an algorithm for identifying redundant vertices in RBNs which allows us to reduce the search space for computing attractors from O(2
<sup>n</sup>) to Θ2<sup>√n</sup>. We also show how RBNs can be used for studying evolution.
