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

DOI10.1016/J.DAM.2017.12.037MaRDI QIDQ1752437zbMATHOpenAlexFDO

Authors Adrien Richard

Publication date 24 May 2018

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

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

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)

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.

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

Cites work

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

Cited in

(23)

• Nilpotent dynamics on signed interaction graphs and weak converses of Thomas' rules
• Number of fixed points and disjoint cycles in monotone Boolean networks
• Characterisation of the elementary cellular automata in terms of their maximum sensitivity to all possible asynchronous updates
• Attractor separation and signed cycles in asynchronous Boolean networks
• On Fixable Families of Boolean Networks
• Topological fixed points in Boolean networks
• Counting periodic points in parallel graph dynamical systems
• Sequentialization and procedural complexity in automata networks
• From kernels in directed graphs to fixed points and negative cycles in Boolean networks
• Positive circuits and maximal number of fixed points in discrete dynamical systems
• Complexity of maximum fixed point problem in Boolean networks
• Positive and negative cycles in Boolean networks
• Fixed points of Boolean networks, guessing graphs, and coding theory
• Linear cuts in Boolean networks
• Existence and non existence of limit cycles in Boolean networks
• Local cycles and dynamical properties of Boolean networks
• Local negative circuits and fixed points in non-expansive Boolean networks
• Fixed point theorems for Boolean networks expressed in terms of forbidden subnetworks
• A general model of binary opinions updating
• A fixed point theorem for Boolean networks expressed in terms of forbidden subnetworks
• Graphic requirements for multistability and attractive cycles in a Boolean dynamical framework
• Negative local feedbacks in Boolean networks
• Complexity of fixed point counting problems 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)