布尔控制网络的级联分解：一种图论方法

李一峰; 朱建栋

doi:10.1631/FITEE.1900422

Your Location：

Home >

Browse articles >

布尔控制网络的级联分解：一种图论方法

复杂系统和网络及其应用专辑 | Updated：2022-05-19

- 布尔控制网络的级联分解：一种图论方法
- Cascading decomposition of Boolean control networks: a graph-theoretical method
- 信息与电子工程前沿（英文） 2020年21卷第2期页码：304-315
- 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：
  
  Project supported by the National Natural Science Foundation of China (No. 61673012)
- DOI：10.1631/FITEE.1900422
  中图分类号： O231
- 收稿：2019-08-22，
  
  修回：2019-11-15，
  
  网络出版：2019-12-27，
  
  纸质出版：2020-02
- Accepted：
Scan QR Code
李一峰, 朱建栋. 布尔控制网络的级联分解：一种图论方法[J]. 信息与电子工程前沿（英文）, 2020,21(2):304-315.

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.
李一峰, 朱建栋. 布尔控制网络的级联分解：一种图论方法[J]. 信息与电子工程前沿（英文）, 2020,21(2):304-315. DOI： 10.1631/FITEE.1900422.

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 . .

浏览量

Downloads

CSCD

文章被引用时，请邮件提醒。

Submit

工具集

关联资源

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