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.

We study the relationships between the positive and negative circuits of the connection graph and the fixed points of discrete neural networks (DNNs). As main results, we give necessary conditions and sufficient conditions for the existence of fixed points in a DNN. Moreover, we exhibit an upper bound for the number of fixed points in terms of the structure and number of positive circuits in the connection graph. This allows the determination of the maximum capacity for storing vectors in DNNs as fixed points, depending on the architecture of the network.

The human genome with its 23 pairs of chromosomes, is the result of evolution. This evolution has been ruled by the mutation process and also by the physiological and pathological reorganization of the genomic material inside or between the chromosomes, which are conditioning the genomic variability. This reorganization is starting at singular points on the short or long chromosomic arms, called crossing-over, or translocations, insertions, break points. In this paper, we will show that these points, also called weak points or hot spots of the genome are correlated, independently of their origin. In addition, we will give some properties of the genetic interaction matrices in terms of attractors of the genetic expression dynamics.

The human genome has evolved from a primitive genome to its present state dispatched along the 23 pairs of chromosomes. This evolution has been ruled by the mutation process and also by the physiological and pathological reorganization of the genomic material inside or between the chromosomes, which condition the genomic variability. This reorganization starts at singular points on the short or long chromosomic arms, called crossover, translocation, insertion or break-points. In this paper, we show that these points, also called "weak points" or "hot spots" of the genome, are correlated independently of their origin. In addition, we give some properties of the interaction matrices in terms of attractors (generalizing some earlier results to the discrete case).