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|P|·n2+k), where n is the number of components and the regulatory functions of the network can be evaluated in time O(nk), 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. AVAILABILITY AND IMPLEMENTATION: An executable file of FixedPoint algorithm made in Java and some examples of input files are available at: www.inf.udec.cl/˜lilian/FPCollector/. SUPPLEMENTARY INFORMATION: Supplementary material is available at Bioinformatics online.

Given a digraph $G$, much attention has focused on the maximum number $\phi(G)$ of fixed points in a Boolean network $f:\{0,1\}^n\to\{0,1\}^n$ with $G$ as interaction graph. In particular, a central problem in network coding consists in studying the optimality of the feedback bound $\phi(G)\leq 2^{\tau}$, where $\tau$ is the minimum size of a feedback vertex set of $G$. In this paper, we study the maximum number $\phi_m(G)$ of fixed points in a monotone Boolean network with interaction graph $G$. We establish new upper and lower bounds on $\phi_m(G)$ that depend on the cycle structure of $G$. In addition to $\tau$, the involved parameters are the maximum number $\nu$ of vertex-disjoint cycles, and the maximum number $\nu^*$ of vertex-disjoint cycles verifying some additional technical conditions. We improve the feedback bound $2^\tau$ by proving that $\phi_m(G)$ is at most the largest sublattice of $\{0,1\}^\tau$ without chain of size $\nu+2$, and without another forbidden pattern described by two disjoint antichains of size $\nu^*+1$. Then, we prove two optimal lower bounds: $\phi_m(G)\geq \nu+1$ and $\phi_m(G)\geq 2^{\nu^*}$. As a consequence, we get the following characterization: $\phi_m(G)=2^\tau$ if and only if $\nu^*=\tau$. As another consequence, we get that if $c$ is the maximum length of a chordless cycle of $G$, then $2^{\nu/3^c}\leq\phi_m(G)\leq 2^{c\nu}$. Finally, with the techniques introduced, we establish an upper bound on the number of fixed points of any Boolean network according to its signed interaction graph.

MOTIVATION: Boolean networks (BNs) are commonly used to model genetic regulatory networks (GRNs). Due to the sensibility of the dynamical behavior to changes in the updating scheme (order in which the nodes of a network update their state values), it is increasingly common to use different updating rules in the modeling of GRNs to better capture an observed biological phenomenon and thus to obtain more realistic models.In Aracena et al. equivalence classes of deterministic update schedules in BNs, that yield exactly the same dynamical behavior of the network, were defined according to a certain label function on the arcs of the interaction digraph defined for each scheme. Thus, the interaction digraph so labeled (update digraphs) encode the non-equivalent schemes. RESULTS: We address the problem of enumerating all non-equivalent deterministic update schedules of a given BN. First, we show that it is an intractable problem in general. To solve it, we first construct an algorithm that determines the set of update digraphs of a BN. For that, we use divide and conquer methodology based on the structural characteristics of the interaction digraph. Next, for each update digraph we determine a scheme associated. This algorithm also works in the case where there is a partial knowledge about the relative order of the updating of the states of the nodes. We exhibit some examples of how the algorithm works on some GRNs published in the literature. AVAILABILITY AND IMPLEMENTATION: An executable file of the UpdateLabel algorithm made in Java and the files with the outputs of the algorithms used with the GRNs are available at: www.inf.udec.cl/ ∼lilian/UDE/ CONTACT: [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.