Finding the fixed points of a Boolean network from a positive feedback vertex set

Motivation: In the modeling of biological systems by Boolean networks, a key problem is finding the set of fixed points of a given network. Some constructed algorithms consider certain structural properties of the regulatory graph like those proposed by Akutsu et al. and Zhang et al., which consider a feedback vertex set of the graph. However, these methods do not take into account the type of action (activation and inhibition) between its components. Results: In this article, we propose a new algorithm for finding the set of fixed points of a Boolean network, based on a positive feedback vertex set P of its regulatory graph and which works, by applying a sequential update schedule, in time O(2(vertical bar P vertical bar) center dot n(2+k)), where n is the number of components and the regulatory functions of the network can be evaluated in time O(n(k)), k >= 0. The theoretical foundation of this algorithm is due a nice characterization, that we give, of the dynamical behavior of the Boolean networks without positive cycles and with a fixed point.