Cascading decomposition of Boolean control networks: a graph-theoretical method

Yi-feng LI; Jian-dong ZHU

doi:10.1631/FITEE.1900422

Your Location：

Home >

Browse articles >

Cascading decomposition of Boolean control networks: a graph-theoretical method

Special Issue on Complex Systems and Networks with Their Applications | Updated：2022-05-19

- Cascading decomposition of Boolean control networks: a graph-theoretical method
- 布尔控制网络的级联分解：一种图论方法
- Frontiers of Information Technology & Electronic Engineering Vol. 21, Issue 2, Pages: 304-315(2020)
- Affiliations：
  
  Institute of Mathematics, School of Mathematical Sciences, Nanjing Normal University, Nanjing 210023, China
- Author bio：
  
  [ "LI Yi-feng,E-mail:liyifeng010@126.com" ]
  [ "ZHU Jian-dong,E-mail:zhujiandong@njnu.edu.cn" ]
- Funds：
- DOI：10.1631/FITEE.1900422
  CLC： O231
- Received：22 August 2019，
  
  Revised：2019-11-15，
  
  Published Online：27 December 2019，
  
  Published：2020-02
- Accepted：
Scan QR Code
Yi-feng LI, Jian-dong ZHU. Cascading decomposition of Boolean control networks: a graph-theoretical method[J]. Frontiers of Information Technology & Electronic Engineering, 2020, 21(2): 304-315.
DOI：

Yi-feng LI, Jian-dong ZHU. Cascading decomposition of Boolean control networks: a graph-theoretical method[J]. Frontiers of Information Technology & Electronic Engineering, 2020, 21(2): 304-315. DOI： 10.1631/FITEE.1900422.

摘要

采用图论方法研究布尔控制网络的两类级联分解问题。提出嵌套完美等点划分（NPEVP）的概念。基于NPEVP，得到级联分解问题可解的充要图条件。给定提出的图条件，可构造性地得到实现相应级联分解形式的逻辑坐标变换。最后，给出两个实例以验证结论。

Abstract

Two types of cascading decomposition problems of Boolean control networks are investigated using a graph-theoretical method. A new graphic concept called nested perfect equal vertex partition (NPEVP) is proposed. Based on NPEVP

the necessary and sufficient graphic conditions for solvability of the cascading decomposition problems are obtained. Given the proposed graphic conditions

the logical coordinate transformations are constructively obtained to realize the corresponding cascading decomposition forms. Finally

two illustrative examples are provided to validate the results.

关键词

Keywords

references

R Albert , , , HG Othmer . . The topology of the regulatory interactions predicts the expression pattern of the segment polarity genes in Drosophila melanogaster . . J Theor Biol , , 2003 . . 223 ( ( 1 ): ): 1 - - 18 . . DOI: 10.1016/S0022-5193(03)00035-3 http://doi.org/10.1016/S0022-5193(03)00035-3 . .

O Borůvka . . Foundations of the Theory of Groupoids and Groups . . VEB Deutscher Verlag der Wissenschaften, Berlin, Germany , , 1974 . . .

M Chaves , , , R Albert , , , ED Sontag . . Robustness and fragility of Boolean models for genetic regulatory networks . . J Theor Biol , , 2005 . . 235 ( ( 3 ): ): 431 - - 449 . . DOI: 10.1016/j.jtbi.2005.01.023 http://doi.org/10.1016/j.jtbi.2005.01.023 . .

DZ Cheng . . Disturbance decoupling of Boolean control networks . . IEEE Trans Autom Contr , , 2011 . . 56 ( ( 1 ): ): 2 - - 10 . . DOI: 10.1109/TAC.2010.2050161 http://doi.org/10.1109/TAC.2010.2050161 . .

DZ Cheng , , , HS Qi . . Controllability and observability of Boolean control networks . . Automatica , , 2009 . . 45 ( ( 7 ): ): 1659 - - 1667 . . DOI: 10.1016/j.automatica.2009.03.006 http://doi.org/10.1016/j.automatica.2009.03.006 . .

DZ Cheng , , , HS Qi . . A linear representation of dynamics of Boolean networks . . IEEE Trans Autom Contr , , 2010a . . 55 ( ( 10 ): ): 2251 - - 2258 . . DOI: 10.1109/TAC.2010.2043294 http://doi.org/10.1109/TAC.2010.2043294 . .

DZ Cheng , , , HS Qi . . State-space analysis of Boolean networks . . IEEE Trans Neur Netw , , 2010b . . 21 ( ( 4 ): ): 584 - - 594 . . DOI: 10.1109/TNN.2009.2039802 http://doi.org/10.1109/TNN.2009.2039802 . .

DZ Cheng , , , XR Xu . . Bi-decomposition of multi-valued logical functions and its applications . . Automatica , , 2013 . . 49 ( ( 7 ): ): 1979 - - 1985 . . DOI: 10.1016/j.automatica.2013.03.013 http://doi.org/10.1016/j.automatica.2013.03.013 . .

DZ Cheng , , , ZQ Li , , , HS Qi . . Realization of Boolean control networks . . Automatica , , 2010 . . 46 ( ( 1 ): ): 62 - - 69 . . DOI: 10.1016/j.automatica.2009.10.036 http://doi.org/10.1016/j.automatica.2009.10.036 . .

DZ Cheng , , , HS Qi , , , ZQ Li . . Analysis and Control of Boolean Networks: a Semi-tensor Product Approach . . Springer, London, UK , , 2011 . . DOI: 10.1007/978-0-85729-097-7 http://doi.org/10.1007/978-0-85729-097-7 . .

WK Ching , , , SQ Zhang , , , MK Ng , , , 等 . . An approximation method for solving the steady-state probability distribution of probabilistic Boolean networks . . Bioinformatics , , 2007 . . 23 ( ( 12 ): ): 1511 - - 1518 . . DOI: 10.1093/bioinformatics/btm142 http://doi.org/10.1093/bioinformatics/btm142 . .

A Datta , , , A Choudhary , , , M Bittner . . External control in Markovian genetic regulatory networks: the imperfect information case . . Bioinformatics , , 2004 . . 20 ( ( 6 ): ): 924 - - 930 . . DOI: 10.1093/bioinformatics/bth008 http://doi.org/10.1093/bioinformatics/bth008 . .

C Farrow , , , J Heidel , , , J Maloney , , , 等 . . Scalar equations for synchronous Boolean networks with biological applications . . IEEE Trans Neur Netw , , 2004 . . 15 ( ( 2 ): ): 348 - - 354 . . DOI: 10.1109/TNN.2004.824262 http://doi.org/10.1109/TNN.2004.824262 . .

E Fornasini , , , ME Valcher . . Observability, reconstructibility and state observers of Boolean control networks . . IEEE Trans Autom Contr , , 2013 . . 58 ( ( 6 ): ): 1390 - - 1401 . . DOI: 10.1109/TAC.2012.2231592 http://doi.org/10.1109/TAC.2012.2231592 . .

S Huang . . Regulation of cellular states in mammalian cells from a genome wide view . . Proc Gene Regulations and Metabolism — Postgenomic Computational Approaches , , 2002 . . p.181 - - 220 . . . .

S Huang , , , DE Ingber . . Shape-dependent control of cell growth, differentiation, and apoptosis: switching between attractors in cell regulatory networks . . Exp Cell Res , , 2000 . . 261 91 - - 103 . . . .

SA Kauffman . . Metabolic stability and epigenesis in randomly constructed genetic nets . . J Theor Biol , , 1969 . . 22 ( ( 3 ): ): 437 - - 467 . . DOI: 10.1016/0022-5193(69)90015-0 http://doi.org/10.1016/0022-5193(69)90015-0 . .

S Klamt , , , J Saez-Rodriguez , , , JA Lindquist , , , 等 . . A methodology for the structural and functional analysis of signaling and regulatory networks . . BMC Bioinform , , 2006 . . 7 56 DOI: 10.1186/1471-2105-7-56 http://doi.org/10.1186/1471-2105-7-56 . .

D Laschov , , , M Margaliot . . A maximum principle for single-input Boolean control networks . . IEEE Trans Autom Contr , , 2011 . . 56 ( ( 4 ): ): 913 - - 917 . . DOI: 10.1109/TAC.2010.2101430 http://doi.org/10.1109/TAC.2010.2101430 . .

FF Li , , , JT Sun . . Controllability and optimal control of a temporal Boolean network . . Neur Netw , , 2012 . . 34 10 - - 17 . . DOI: 10.1016/j.neunet.2012.06.002 http://doi.org/10.1016/j.neunet.2012.06.002 . .

HT Li , , , YZ Wang . . Further results on feedback stabilization control design of Boolean control networks . . Automatica , , 2017 . . 83 303 - - 308 . . DOI: 10.1016/j.automatica.2017.06.043 http://doi.org/10.1016/j.automatica.2017.06.043 . .

HT Li , , , LH Xie , , , YZ Wang . . Output regulation of Boolean control networks . . IEEE Trans Autom Contr , , 2017 . . 62 ( ( 6 ): ): 2993 - - 2998 . . DOI: 10.1109/TAC.2016.2606600 http://doi.org/10.1109/TAC.2016.2606600 . .

R Li , , , M Yang , , , TG Chu . . State feedback stabilization for Boolean control networks . . IEEE Trans Autom Contr , , 2013 . . 58 ( ( 7 ): ): 1853 - - 1857 . . DOI: 10.1109/TAC.2013.2238092 http://doi.org/10.1109/TAC.2013.2238092 . .

YF Li , , , JD Zhu . . On disturbance decoupling problem of Boolean control network . . Asian J Contr, in press , , 2019 . . DOI: 10.1002/asjc.2115 http://doi.org/10.1002/asjc.2115 . .

Y Liu , , , HW Chen , , , JQ Lu , , , 等 . . Controllability of probabilistic Boolean control networks based on transition probability matrices . . Automatica , , 2015 . . 52 340 - - 345 . . DOI: 10.1016/j.automatica.2014.12.018 http://doi.org/10.1016/j.automatica.2014.12.018 . .

Y Liu , , , BW Li , , , HW Chen , , , 等 . . Function perturbations on singular Boolean networks . . Automatica , , 2017a . . 84 36 - - 42 . . DOI: 10.1016/j.automatica.2017.06.035 http://doi.org/10.1016/j.automatica.2017.06.035 . .

Y Liu , , , BW Li , , , JQ Lu , , , 等 . . Pinning control for the disturbance decoupling problem of Boolean networks . . IEEE Trans Autom Contr , , 2017b . . 62 ( ( 12 ): ): 6595 - - 6601 . . DOI: 10.1109/TAC.2017.2715181 http://doi.org/10.1109/TAC.2017.2715181 . .

JQ Lu , , , J Zhong , , , C Huang , , , 等 . . On pinning controllability of Boolean control networks . . IEEE Trans Autom Contr , , 2016 . . 61 ( ( 6 ): ): 1658 - - 1663 . . DOI: 10.1109/TAC.2015.2478123 http://doi.org/10.1109/TAC.2015.2478123 . .

JQ Lu , , , LJ Sun , , , Y Liu , , , 等 . . Stabilization of Boolean control networks under aperiodic sampled-data control . . SIAM J Contr Optim , , 2018 . . 56 ( ( 6 ): ): 4385 - - 4404 . . DOI: 10.1137/18M1169308 http://doi.org/10.1137/18M1169308 . .

M Meng , , , J Lam , , , JE Feng , , , 等 . . l 1 -gain analysis and model reduction problem for Boolean control networks . . Inform Sci , , 2016 . . 348 68 - - 83 . . DOI: 10.1016/j.ins.2016.02.010 http://doi.org/10.1016/j.ins.2016.02.010 . .

R Potůček . . Construction of the smallest common coarser of two and three set partitions . . Anal Univ Ovid Const Ser Matem , , 2014 . . 22 ( ( 1 ): ): 237 - - 246 . . DOI: 10.2478/auom-2014-0019 http://doi.org/10.2478/auom-2014-0019 . .

WM Wonham . . Linear Multivariable Control: a Geometric Approach . . Springer-Verlag, Berlin, Germany , , 1974 . . DOI: 10.1007/978-3-662-22673-5 http://doi.org/10.1007/978-3-662-22673-5 . .

YH Wu , , , TL Shen . . An algebraic expression of finite horizon optimal control algorithm for stochastic logical dynamical systems . . Syst Contr Lett , , 2015 . . 82 108 - - 114 . . DOI: 10.1016/j.sysconle.2015.04.007 http://doi.org/10.1016/j.sysconle.2015.04.007 . .

YY Yu , , , JE Feng , , , JF Pan , , , 等 . . Block decoupling of Boolean control networks . . IEEE Trans Autom Contr , , 2019 . . 64 ( ( 8 ): ): 3129 - - 3140 . . DOI: 10.1109/TAC.2018.2880411 http://doi.org/10.1109/TAC.2018.2880411 . .

Y Zhao , , , ZQ Li , , , DZ Cheng . . Optimal control of logical control networks . . IEEE Trans Autom Contr , , 2011 . . 56 ( ( 8 ): ): 1766 - - 1776 . . DOI: 10.1109/TAC.2010.2092290 http://doi.org/10.1109/TAC.2010.2092290 . .

Y Zhao , , , J Kim , , , M Filippone . . Aggregation algorithm towards large-scale Boolean network analysis . . IEEE Trans Autom Contr , , 2013 . . 58 ( ( 8 ): ): 1976 - - 1985 . . DOI: 10.1109/TAC.2013.2251819 http://doi.org/10.1109/TAC.2013.2251819 . .

YL Zou , , , JD Zhu . . System decomposition with respect to inputs for Boolean control networks . . Automatica , , 2014 . . 50 ( ( 4 ): ): 1304 - - 1309 . . DOI: 10.1016/j.automatica.2014.02.039 http://doi.org/10.1016/j.automatica.2014.02.039 . .

YL Zou , , , JD Zhu . . Kalman decomposition for Boolean control networks . . Automatica , , 2015 . . 54 65 - - 71 . . DOI: 10.1016/j.automatica.2015.01.023 http://doi.org/10.1016/j.automatica.2015.01.023 . .

YL Zou , , , JD Zhu . . Graph theory methods for decomposition w.r.t. outputs of Boolean control networks . . J Syst Sci Compl , , 2017 . . 30 ( ( 3 ): ): 519 - - 534 . . DOI: 10.1007/s11424-016-5131-3 http://doi.org/10.1007/s11424-016-5131-3 . .

YL Zou , , , JD Zhu , , , YR Liu . . Cascading state-space decomposition of Boolean control networks . . Proc 37 th Chinese Control Conf , , 2018 . . p.6326 - - 6331 . . . .

YL Zou , , , JD Zhu , , , YR Liu . . Cascading state-space decomposition of Boolean control networks by nested method . . J Franklin Inst , , 2019 . . 356 ( ( 16 ): ): 10015 - - 10030 . . DOI: 10.1016/j.jfranklin.2018.10.042 http://doi.org/10.1016/j.jfranklin.2018.10.042 . .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

Analysis of the Pareto equilibrium in multi-objective games using semi-tensor product

Controllability of Boolean control networks with multiple time delays in both states and controls

A joint image compression and encryption scheme based on a novel coupled map lattice system and DNA operations

On observability of Galois nonlinear feedback shift registers over finite fields

Output tracking of delayed logical control networks with multi-constraint

Related Author

Jun'e FENG

Fanyueyang ZHANG

Lan WANG

Yifeng LI

Jungang LOU

Jianquan LU

Xiaoqing YOU

Yuanyuan LI

Related Institution

School of Mathematics, Shandong University

National Center for Applied Mathematics in Chongqing, Chongqing Normal University

Institute of Mathematics, School of Mathematical Sciences, Nanjing Normal University

Department of Applied Mathematics, College of Science, Nanjing Forestry University

School of Cyber Science and Engineering, Southeast University

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰