Trap spaces as labelled ideals of SCC posets: A structural–functional theory of reachability in asynchronous boolean networks.
Saved in:
| Title: | Trap spaces as labelled ideals of SCC posets: A structural–functional theory of reachability in asynchronous boolean networks. |
|---|---|
| Authors: | Yizengaw, Belayneh Yibeltal1 (AUTHOR) belayneh.yizengaw@up.ac.za |
| Source: | Journal of Bioinformatics & Computational Biology. Jun2026, Vol. 24 Issue 3, p1-19. 19p. |
| Subjects: | Boolean networks, Partially ordered sets, Biological networks, Cell differentiation, Dynamical systems |
| Abstract: | Boolean networks provide a qualitative framework for modelling regulatory systems when kinetic parameters are unavailable, with cellular phenotypes represented as attractors of the induced dynamics [J. D. Schwab et al., Concepts in Boolean network modeling, Comput. Struct. Biotechnol. J. 18:571–582, 2020]. A central challenge is phenotypic reachability: determining whether asynchronous dynamics can connect invariant regions of the state space, a problem that becomes computationally intractable in large networks [L. Cifuentes-Fontanals, M. Noual, and E. Remy, Revisiting trap spaces in Boolean networks, Theor. Comput. Sci. 915:1–20, 2022; K. Perrot and C. Paulevé, Complexity of asynchronous reachability in Boolean networks, Theor. Comput. Sci. 1000:114650, 2024.]. We develop a structural theory of reachability in which trap spaces are identified with labelled order ideals of SCC-posets. The SCC-poset determines the order of commitment events, while admissible evaluations encode branching within regulatory modules, so that multistability appears as an intrinsic feature of the theory. Within this framework, we establish necessary and sufficient conditions for reachability, introduce the commitment depth, and show that deciding non-trivial branching is computationally intractable. We further demonstrate that effective interaction structure is jointly determined by topology and Boolean logic. We validate the framework on a Boolean model of CD4 + T-cell differentiation, where refinement chains recover the observed ordering of cytokine response, lineage commitment, and phenotypic branching. In the absence of multistability the structure collapses to a distributive lattice, a non-generic limiting regime. [ABSTRACT FROM AUTHOR] |
| Copyright of Journal of Bioinformatics & Computational Biology is the property of World Scientific Publishing Company and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
| Abstract: | Boolean networks provide a qualitative framework for modelling regulatory systems when kinetic parameters are unavailable, with cellular phenotypes represented as attractors of the induced dynamics [J. D. Schwab et al., Concepts in Boolean network modeling, Comput. Struct. Biotechnol. J. 18:571–582, 2020]. A central challenge is phenotypic reachability: determining whether asynchronous dynamics can connect invariant regions of the state space, a problem that becomes computationally intractable in large networks [L. Cifuentes-Fontanals, M. Noual, and E. Remy, Revisiting trap spaces in Boolean networks, Theor. Comput. Sci. 915:1–20, 2022; K. Perrot and C. Paulevé, Complexity of asynchronous reachability in Boolean networks, Theor. Comput. Sci. 1000:114650, 2024.]. We develop a structural theory of reachability in which trap spaces are identified with labelled order ideals of SCC-posets. The SCC-poset determines the order of commitment events, while admissible evaluations encode branching within regulatory modules, so that multistability appears as an intrinsic feature of the theory. Within this framework, we establish necessary and sufficient conditions for reachability, introduce the commitment depth, and show that deciding non-trivial branching is computationally intractable. We further demonstrate that effective interaction structure is jointly determined by topology and Boolean logic. We validate the framework on a Boolean model of CD4 + T-cell differentiation, where refinement chains recover the observed ordering of cytokine response, lineage commitment, and phenotypic branching. In the absence of multistability the structure collapses to a distributive lattice, a non-generic limiting regime. [ABSTRACT FROM AUTHOR] |
|---|---|
| ISSN: | 02197200 |
| DOI: | 10.1142/S0219720026500071 |
