Negative circuits and sustained oscillations in asynchronous automata networks (Q962004)

The paper deals with some conjectures about dynamics of gene networks and their interaction graphs. Here a network is \((X,F)\), where the state space \(X\) is the cartesian product of the state spaces of \(n\) interacting automata, and the mapping \(F:X\to X,F(x)=\left(f_1(x),\dots,f_n(x)\right)\), provides the \textit{asynchronous dynamics}: given a point \(x^0\in X\) and a sequence \(\left\{\varphi_t\right\}_{t\in\mathbb{N}}\) in \(\{1,\dots,n\}\), \(x^{t+1}\) is the same as \(x^t\) except that coordinate \(\varphi_t\) is updated to \(f_{\varphi_t}\left(x^t\right)\). From \(F\), an edge-weighted graph \(G(F)\) (the \textit{interaction graph of \(F\)}) is constructed, having states \(\{1,\dots,n\}\) and \textit{signed} edges (that is, edges with weights in \(\{-1,1\}\)) according to certain criterion on the \(f_i\)'s. Each path in \(G(F)\) is then endowed with a sign by taking the product of the weights of the edges in the path. The main result in the paper solves, for asynchronous automata networks, a 20-years conjecture due to biologist R. Thomas: if \(F\) has sustained oscillations, then the interaction graph of \(F\) has a negative cycle. The proof is achieved by considering \(\Gamma(F)\), the \textit{asynchronous state transition graph of \(F\)}, which is constructed from \(X\) and \(F\), and allows to study some dynamical properties of \(F\); for instance, the stable states (resp. cyclic attractors) of \(\Gamma(F)\) correspond to fixed points (resp. sustained oscillations) of \(F\). A variant of \(G(F)\) and \(\Gamma(F)\) more suited to the modeling of gene regulatory networks is also discussed, allowing to obtain sufficient conditions (in combinatorial terms) for \(F\) to have fixed points.