Computing the long term behavior of regulatory and signaling networks
is critical in understanding how biological functions take place in
organisms. Steady states of these networks determine the activity
levels of individual entities in the long run. Identifying all the
steady states of these networks is difficult as it suffers from the
state space explosion problem. In this paper, we propose a method for
identifying all the steady states of Boolean regulatory and signaling
networks accurately and efficiently. We build a mathematical model
that allows pruning a large portion of the state space quickly without
causing any false dismissals. For the remaining state space, which is
typically very small compared to the whole state space, we develop a
randomized traversal method that extracts the steady states. We
estimate the number of steady states, and the expected behavior of
individual genes and gene pairs in steady states in an online
fashion. Also, we formulate a stopping criterion that terminates the
traversal as soon as user supplied percentage of the results are
returned with high confidence. We show that our algorithm can identify
all the steady states accurately. Furthermore, our method is scalable
to virtually any large scale Boolean biological regulatory network.