An open Why are motif-avoidant attractors so rare in asynchronous Boolean networks?

Authors: Samuel Pastva, Kyu Hyong Park, Ondřej Huvar, Jordan C. Rozum, Réka Albert

Abstract

Asynchronous Boolean networks are a type of discrete dynamical system in which each variable can take one of two states, and a single variable state is updated in each time step according to pre-selected rules. Boolean networks are popular in systems biology due to their ability to model long-term biological phenotypes within a qualitative, predictive framework. Boolean networks model phenotypes as attractors, which are closely linked to minimal trap spaces (inescapable hypercubes in the system’s state space). In biological applications, attractors and minimal trap spaces are typically in one-to-one correspondence. However, this correspondence is not motif-avoidant attractors (MAAs) that lie outside minimal trap spaces are possible. MAAs are rare and poorly understood, despite recent efforts. In this contribution to the BMB & JMB Special Collection “Problems, Progress and Perspectives in Mathematical and Computational Biology”, we summarize the current state of knowledge regarding MAAs and present several novel observations regarding their response to node deletion reductions and linear extensions of edges. We conduct large-scale computational studies on an ensemble of 14 000 models derived from published Boolean models of biological systems, and more than 100 million Random Boolean Networks. Our findings quantify the rarity of MAAs; in particular, we only observed MAAs in biological models after applying standard simplification methods, highlighting the role of network reduction in introducing MAAs into the dynamics. We also show that MAAs are fragile to linear in sparse networks, even a single linear node can disrupt virtually all MAAs. Motivated by this observation, we improve the upper bound on the number of delays needed to disrupt a motif-avoidant attractor.

Supplementary Information

The online version contains supplementary material available at 10.1007/s00285-025-02235-8.

Introduction

Boolean networks are discrete dynamical systems that have been widely and successfully applied to model complex processes, especially in systems biology (Schwab et al. 2020; Rozum et al. 2024; Abou-Jaoudé et al. 2016). They describe the causal logic of regulatory dynamics using nodes to represent biomolecular entities (such as genes, proteins, or metabolites) that are connected by directed edges representing regulatory influences. Each node (also referred to as variable) can take on one of two states at any given time step—ON (1) or OFF (0)—that is updated according to an update function of the node’s incoming regulators’ states.

The nodes and edges that underpin the dynamics of a Boolean network form its interaction graph. Signs are often assigned to the individual edges, indicating an activating (+1), inhibiting (-1), or ambiguous (0) influence.1 The interaction graph is the primary and best-constrained parameter of the Boolean numerous properties can be inferred solely from its structure (Paulevé and Richard 2012). However, many Boolean systems can share the same interaction graph, thus many problems cannot be conclusively solved based on the interaction graph alone.

The dynamics of a Boolean network are affected by how nodes (variables) are selected for update in each time step (Park et al. 2023). Various choices are possible, including updating all variables (synchronous update), randomly selecting a single variable to update (asynchronous update), or other more complicated schemes involving hidden states, such as the most-permissive scheme of (Paulevé et al. 2020). In this work, we focus primarily (but not exclusively) on the asynchronous update scheme.

Typically, the long-term dynamics of a Boolean network (i.e., its attractors) are intended to correspond to the biological phenotypes of the system under study. In the context of Boolean networks, attractors are defined as minimal trap sets i.e., the smallest sets of states that are invariant under the network’s dynamics (Schwab et al. 2020; Rozum et al. 2024). There are various efficient methods to identify attractors, despite the NP-hardness of the problem (Mori and Akutsu 2022; Rozum et al. 2021; Beneš et al. 2021; Van Giang and Hiraishi 2021; Trinh et al. 2024).

Attractors alone may be insufficient to answer many practical questions about Boolean networks. For example, one may wish to understand which interventions can or cannot drive the system toward a target behavior (Paul et al. 2019; Cifuentes-Fontanals et al. 2022; Brim et al. 2023), which components of the system contribute to certain phenotypes (Beneš et al. 2022), or which initial conditions lead to which outcomes (Albert et al. 2008). One fruitful approach toward answering these questions is to study how node states reinforce each other to lock a subnetwork of the system into a particular configuration (called a stable motif, see Zañudo and Albert 2013). Once reached, these stable configurations confine the dynamics to a subspace in which the constrained nodes are fixed, i.e., to a trap space (Klarner et al. 2015). Stable motifs determine the system’s commitment to one phenotype versus another. When a system has multiple stable motifs, the trap spaces nest within one another.

The most deeply nested minimal trap spaces must each contain one or more attractors. However, there can be additional attractors that do not lie within any minimal trap space. In this case, the set of minimal trap spaces is called incomplete (Klarner and Siebert 2015), and an attractor outside all minimal trap spaces is called motif-avoidant (Rozum et al. 2021), as states belonging to the attractor avoid the self-reinforcing network configurations (stable motifs) that result in constraining the dynamics to a minimal trap space. Despite recent efforts (Richard and Tonello 2023; Naldi et al. 2023), motif-avoidant attractors (MAAs) are still poorly understood, especially under asynchronous update. Empirical evidence suggests that motif-avoidant attractors are exceedingly rare in real-world biological networks (Tonello and Paulevé 2023; Trinh et al. 2024), but to the best of our knowledge, this observation has not been quantified before. Despite their apparent rarity, MAAs introduce complications into otherwise straightforward and efficient algorithms for attractor enumeration (Klarner and Siebert 2015; Rozum et al. 2021; Tonello and Paulevé 2023). Therefore, a better understanding of MAAs may lead to significant improvements in Boolean network algorithms.

In this work, we seek to lay out the current state of knowledge about MAAs and discuss some key open problems concerning their presence or absence. Inspired by Tonello and Paulevé (2023) and Naldi et al. (2023), we explore how motif avoidance relates to node deletion reduction and to adding a delay to a regulation (linear extension). To gain further insight into these phenomena, we conducted multiple large-scale computational studies involving approximately 14 000 networks derived from published biological models and one hundred million Random Boolean Networks (RBNs) (Kauffman 1969). We use these insights to guide the development of some analytical results regarding MAA fragility.

In Sects. 2 and 3, we introduce the necessary formal concepts and recall published results about motif-avoidant attractors. Sect. 4 presents examples of MAAs that challenge our expectations of when motif avoidance should or should not be possible. Sect. 5 explores the rarity of motif We find no asynchronous MAAs in published Boolean models of biological systems, even when accounting for a wide array of model inputs and contexts. In RBNs, we show that the likelihood of encountering motif avoidance is non-trivial for dense networks (near \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ N=K