Fixed points and connections between positive and negative cycles in Boolean networks

DOI10.1016/J.DAM.2017.12.037zbMATH Open1387.05244arXiv1509.07702OpenAlexW2962714361MaRDI QIDQ1752437FDOQ1752437

Adrien Richard

Publication date: 24 May 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: We are interested in the relationships between the number fixed points in a Boolean network $f:{0,1}^{n}o{0,1}^n$ and its interaction graph, which is the arc-signed digraph $G$ on $1,dots,n$ that describes the positive and negative influences between the components of the network. A fundamental theorem of Aracena says that if $G$ has no positive (resp. negative) cycle, then $f$ has at most (resp. at least) one fixed point; the sign of a cycle being the product of the signs of its arcs. In this note, we generalize this result by taking into account the influence of connections between positive and negative cycles. In particular, we prove that if every positive (resp. negative) cycle of $G$ has an arc $a$ such that $Gsetminusa$ has a non-trivial initial strongly connected component containing the terminal vertex of $a$ and only negative (resp. positive) cycles, then $f$ has at most (resp. at least) one fixed point. This is, up to our knowledge, the first generalization of Aracena's theorem where the conditions are expressed with $G$ only.

Full work available at URL: https://arxiv.org/abs/1509.07702

Recommendations

• Positive and negative cycles in Boolean networks
• Topological fixed points in Boolean networks
• On the computation of fixed points in Boolean networks
• From kernels in directed graphs to fixed points and negative cycles in Boolean networks
• Local negative circuits and fixed points in non-expansive Boolean networks
• Fixed points of Boolean networks with small number of elementary circuits
• Number of fixed points and disjoint cycles in monotone Boolean networks
• Existence and non existence of limit cycles in Boolean networks
• On Fixable Families of Boolean Networks
• Fixed point theorems for Boolean networks expressed in terms of forbidden subnetworks

zbMATH Keywords

fixed pointBoolean networkinteraction graphnegative cyclepositive cycle

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Deterministic network models in operations research (90B10) Small world graphs, complex networks (graph-theoretic aspects) (05C82)

Cites Work

• Neural networks and physical systems with emergent collective computational abilities.
• A combinatorial analogue of the Jacobian problem in automata networks
• Solutions of irreflexive relations
• Multistationarity, the basis of cell differentiation and memory. II: Logical analysis of regulatory networks in terms of feedback circuits
• Fixed Points of Boolean Networks, Guessing Graphs, and Coding Theory
• Title not available (Why is that?)
• Title not available (Why is that?)
• Combinatorics of Boolean automata circuits dynamics
• Network information flow
• A logical calculus of the ideas immanent in nervous activity
• Maximum number of fixed points in regulatory Boolean networks
• Graphic requirements for multistability and attractive cycles in a Boolean dynamical framework
• On kernels and semikernels of digraphs
• Boolean modeling of genetic regulatory networks
• Necessary conditions for multistationarity in discrete dynamical systems
• Negative circuits and sustained oscillations in asynchronous automata networks
• Title not available (Why is that?)
• A new necessary condition on interaction graphs for multistationarity
• Positive circuits and maximal number of fixed points in discrete dynamical systems
• From kernels in directed graphs to fixed points and negative cycles in Boolean networks
• Fixed point theorems for Boolean networks expressed in terms of forbidden subnetworks
• Relations between gene regulatory networks and cell dynamics in Boolean models
• Asynchronous Dynamics of Boolean Automata Double-Cycles
• Reduction and Fixed Points of Boolean Networks and Linear Network Coding Solvability
• \(H\)-kernels and \(H\)-obstructions in \(H\)-colored digraphs

Cited In (12)

• Counting periodic points in parallel graph dynamical systems
• Sequentialization and procedural complexity in automata networks
• On Fixable Families of Boolean Networks
• Nilpotent dynamics on signed interaction graphs and weak converses of Thomas' rules
• Positive circuits and maximal number of fixed points in discrete dynamical systems
• A general model of binary opinions updating
• Characterisation of the elementary cellular automata in terms of their maximum sensitivity to all possible asynchronous updates
• Existence and non existence of limit cycles in Boolean networks
• Complexity of fixed point counting problems in Boolean networks
• Positive and negative cycles in Boolean networks
• Attractor separation and signed cycles in asynchronous Boolean networks
• Linear cuts in Boolean networks

This page was built for publication: Fixed points and connections between positive and negative cycles in Boolean networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1752437)