Reducing Boolean networks with backward equivalence

BMC Bioinformatics

Research

Alberto Lluch Lafuente¹  Georgios A. Argyris¹  Andrea Vandin²  Max Tschaikowski³  Mirco Tribastone⁴ 

[1] Department of Applied Mathematics and Computer Science, Technical University of Denmark, Lyngby, Denmark;Department of Applied Mathematics and Computer Science, Technical University of Denmark, Lyngby, Denmark;Department of Excellence EMbeDS and Institute of Economics, Sant’Anna School for Advanced Studies, Pisa, Italy;Department of Computer Science, University of Aalborg, Aalborg, Denmark;SysMA Unit, IMT School for Advanced Studies, Lucca, Italy;

关键词: Boolean network;    Model reduction;    State-space generation;    Attractors analysis;    Partition refinement;   

DOI  :  10.1186/s12859-023-05326-9

 received in 2022-03-15, accepted in 2023-05-05,  发布年份 2023

来源: Springer

【 摘 要 】

BackgroundBoolean Networks (BNs) are a popular dynamical model in biology where the state of each component is represented by a variable taking binary values that express, for instance, activation/deactivation or high/low concentrations. Unfortunately, these models suffer from the state space explosion, i.e., there are exponentially many states in the number of BN variables, which hampers their analysis.ResultsWe present Boolean Backward Equivalence (BBE), a novel reduction technique for BNs which collapses system variables that, if initialized with same value, maintain matching values in all states. A large-scale validation on 86 models from two online model repositories reveals that BBE is effective, since it is able to reduce more than 90% of the models. Furthermore, on such models we also show that BBE brings notable analysis speed-ups, both in terms of state space generation and steady-state analysis. In several cases, BBE allowed the analysis of models that were originally intractable due to the complexity. On two selected case studies, we show how one can tune the reduction power of BBE using model-specific information to preserve all dynamics of interest, and selectively exclude behavior that does not have biological relevance.ConclusionsBBE complements existing reduction methods, preserving properties that other reduction methods fail to reproduce, and vice versa. BBE drops all and only the dynamics, including attractors, originating from states where BBE-equivalent variables have been initialized with different activation values The remaining part of the dynamics is preserved exactly, including the length of the preserved attractors, and their reachability from given initial conditions, without adding any spurious behaviours. Given that BBE is a model-to-model reduction technique, it can be combined with further reduction methods for BNs.

【 授权许可】

CC BY   
© The Author(s) 2023

【 图 表 】

41116_2023_36_Article_IEq500.gif

41116_2023_36_Article_IEq486.gif

41116_2023_36_Article_IEq482.gif

41116_2023_36_Article_IEq478.gif

41116_2023_36_Article_IEq475.gif

Fig. 3

41116_2023_36_Article_IEq473.gif

41116_2023_36_Article_IEq471.gif

41116_2023_36_Article_IEq470.gif

Fig. 1

41116_2023_36_Article_IEq469.gif

41116_2023_36_Article_IEq468.gif

41116_2023_36_Article_IEq467.gif

41116_2023_36_Article_IEq466.gif

Fig. 4

41116_2023_36_Article_IEq465.gif

41116_2023_36_Article_IEq464.gif

Fig. 2

Fig. 1

41116_2023_36_Article_IEq461.gif

Fig. 1

41116_2023_36_Article_IEq459.gif

41116_2023_36_Article_IEq458.gif

41116_2023_36_Article_IEq457.gif

41116_2023_36_Article_IEq456.gif

41116_2023_36_Article_IEq455.gif

41116_2023_36_Article_IEq454.gif

41116_2023_36_Article_IEq453.gif

41116_2023_36_Article_IEq452.gif

41116_2023_36_Article_IEq451.gif

41116_2023_36_Article_IEq450.gif

Fig. 2

41116_2023_36_Article_IEq449.gif

41116_2023_36_Article_IEq448.gif

41116_2023_36_Article_IEq447.gif

41116_2023_36_Article_IEq446.gif

40517_2023_255_Article_IEq1.gif

41116_2023_36_Article_IEq445.gif

41116_2023_36_Article_IEq444.gif

Fig. 3

41116_2023_36_Article_IEq443.gif

41116_2023_36_Article_IEq441.gif

Fig. 3

41116_2023_36_Article_IEq439.gif

41116_2023_36_Article_IEq438.gif

41116_2023_36_Article_IEq437.gif

41116_2023_36_Article_IEq436.gif

41116_2023_36_Article_IEq435.gif

41116_2023_36_Article_IEq434.gif

Fig. 3

Fig. 2

41116_2023_36_Article_IEq431.gif

41116_2023_36_Article_IEq430.gif

41116_2023_36_Article_IEq429.gif

Fig. 2

41116_2023_36_Article_IEq427.gif

41116_2023_36_Article_IEq426.gif

41116_2023_36_Article_IEq425.gif

Fig. 1

41116_2023_36_Article_IEq424.gif

41116_2023_36_Article_IEq423.gif

41116_2023_36_Article_IEq422.gif

41116_2023_36_Article_IEq421.gif

41116_2023_36_Article_IEq420.gif

41116_2023_36_Article_IEq419.gif

41116_2023_36_Article_IEq418.gif

41116_2023_36_Article_IEq417.gif

41116_2023_36_Article_IEq416.gif

Fig. 1

41116_2023_36_Article_IEq414.gif

41116_2023_36_Article_IEq413.gif

41116_2023_36_Article_IEq412.gif

41116_2023_36_Article_IEq410.gif

41116_2023_36_Article_IEq408.gif

41116_2023_36_Article_IEq407.gif

41116_2023_36_Article_IEq404.gif

Fig. 3

41116_2023_36_Article_IEq401.gif

41116_2023_36_Article_IEq399.gif

41116_2023_36_Article_IEq397.gif

41116_2023_36_Article_IEq391.gif

41116_2023_36_Article_IEq376.gif

41116_2023_36_Article_IEq369.gif

41116_2023_36_Article_IEq367.gif

41116_2023_36_Article_IEq364.gif

41116_2023_36_Article_IEq362.gif