×

Bisimulations of probabilistic Boolean networks. (English) Zbl 1498.93332

Summary: A probabilistic Boolean network (PBN) is a collection of Boolean networks endowed with a probability structure describing the likelihood with which a constituent network is active at each time step. This paper proposes a definition of bisimulation for PBNs. The notion is inspired by the analogous notions for probabilistic chains and for stochastic linear systems. Necessary and sufficient conditions to check the proposed notion are derived, model reduction of PBNs via bisimulation is addressed, and a discussion on the use of probabilistic bisimulation for optimal control design is given. The present results extend the theory of bisimulation known for deterministic Boolean networks to a stochastic setting.

MSC:

93C29 Boolean control/observation systems
93E03 Stochastic systems in control theory (general)
93B70 Networked control
93E20 Optimal stochastic control
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] R. Albert and J. Thakar, Boolean modeling: A logic-based dynamic approach for understanding signaling and regulatory networks and for making useful predictions, Wiley Interdiscip. Rev. Syst. Biol. Med., 6 (2014), pp. 353-369.
[2] C. Baier and J.-P. Katoen, Principles of Model Checking, MIT Press, Cambridge, MA, 2008. · Zbl 1179.68076
[3] D. P. Bertsekas, Dynamic Programming and Stochastic Control, Academic Press, New York, 1976. · Zbl 0549.93064
[4] D. P. Bertsekas, Dynamic Programming and Optimal Control, 3rd ed., vol. II, Athena Scientific, Belmont, MA, 2007. · Zbl 1209.90343
[5] B. Bloom, Structural operational semantics for weak bisimulations, Theoret. Comput. Sci., 146 (1995), pp. 25-68. · Zbl 0873.68130
[6] H. Chen, J. Liang, J. Lu, and J. Qiu, Synchronization for the realization-dependent probabilistic Boolean networks, IEEE Trans. Neural Netw. Learn. Syst., 29 (2018), pp. 819-831.
[7] X. Chen, Z. Gao, and T. Başar, Asymptotic behavior of conjunctive Boolean networks over weakly connected digraphs, IEEE Trans. Automat. Control, 65 (2020), pp. 2536-2549. · Zbl 07256367
[8] D. Cheng, C. Li, and F. He, Observability of Boolean networks via set controllability approach, Systems Control Lett., 115 (2018), pp. 22-25. · Zbl 1390.93144
[9] D. Cheng and H. Qi, Controllability and observability of Boolean control networks, Automatica, 45 (2009), pp. 1659-1667. · Zbl 1184.93014
[10] D. Cheng and H. Qi, A linear representation of dynamics of Boolean networks, IEEE Trans. Automat. Control, 55 (2010), pp. 2251-2258. · Zbl 1368.37025
[11] D. Cheng, H. Qi, and Z. Li, Analysis and Control of Boolean Networks: A Semi-Tensor Product Approach, Springer, London, 2011. · Zbl 1209.93001
[12] W.-K. Ching, X. Chen, and N.-K. Tsing, Generating probabilistic Boolean networks from a prescribed transition probability matrix, IET Syst. Biol., 3 (2009), pp. 453-464.
[13] E. P. de Vink and J. J. M. M. Rutten, Bisimulation for probabilistic transition systems: A coalgebraic approach, Theoret. Comput. Sci., 221 (1999), pp. 271-293. · Zbl 0930.68092
[14] J. Eloranta, M. Tienari, and A. Valmari, Essential transitions to bisimulation equivalences, Theoret. Comput. Sci., 179 (1997), pp. 397-419. · Zbl 0901.68140
[15] M. Flöttmann, T. Scharp, and E. Klipp, A stochastic model of epigenetic dynamics in somatic cell reprogramming, Front. Physiol., 3 (2012), 216.
[16] E. Fornasini and M. E. Valcher, Optimal control of Boolean control networks, IEEE Trans. Automat. Control, 59 (2014), pp. 1258-1270. · Zbl 1360.93387
[17] E. Fornasini and M. E. Valcher, Observability and reconstructibility of probabilistic Boolean networks, IEEE Control Syst. Lett., 4 (2020), pp. 319-324.
[18] K. A. Grasse, Simulation and bisimulation of nonlinear control systems with admissible classes of inputs and disturbances, SIAM J. Control Optim., 46 (2007), pp. 562-584. · Zbl 1141.93009
[19] Y. Guo, R. Zhou, Y. Wu, W. Gui, and C. Yang, Stability and set stability in distribution of probabilistic Boolean networks, IEEE Trans. Automat. Control, 64 (2019), pp. 736-742. · Zbl 1482.60037
[20] R. F. Hashimoto, H. Stagni, and C. H. A. Higa, Budding yeast cell cycle modeled by context-sensitive probabilistic Boolean network, in Proceedings of the IEEE International Workshop on Genomic Signal Processing and Statistics, Minneapolis, MN, 2009, pp. 1-4.
[21] C. Huang, D. W. C. Ho, J. Lu, W. Xiong, and J. Cao, Synchronization of an array of coupled probabilistic Boolean networks, IEEE Trans. Syst. Man Cybernet. Syst., 52 (2022), pp. 3834-3846.
[22] K. Kobayashi and K. Hiraishi, Design of probabilistic Boolean networks based on network structure and steady-state probabilities, IEEE Trans. Neural Netw. Learn. Syst., 28 (2017), pp. 1966-1971.
[23] K. G. Larsen and A. Skou, Bisimulation through probabilistic testing, Inform. and Comput., 94 (1991), pp. 1-28. · Zbl 0756.68035
[24] D. Laschov, M. Margaliot, and G. Even, Observability of Boolean networks: A graph-theoretic approach, Automatica, 49 (2013), pp. 2351-2362. · Zbl 1364.93095
[25] H. Li and Y. Wang, Lyapunov-based stability and construction of Lyapunov functions for Boolean networks, SIAM J. Control Optim., 55 (2017), pp. 3437-3457. · Zbl 1373.93249
[26] H. Li, X. Yang, and S. Wang, Robustness for stability and stabilization of Boolean networks with stochastic function perturbations, IEEE Trans. Automat. Control, 66 (2021), pp. 1231-1237. · Zbl 07352071
[27] R. Li, T. Chu, and X. Wang, Bisimulations of Boolean control networks, SIAM J. Control Optim., 56 (2018), pp. 388-416. · Zbl 1380.93137
[28] R. Li, Q. Zhang, and T. Chu, Reduction and analysis of Boolean control networks by bisimulation, SIAM J. Control Optim., 59 (2021), pp. 1033-1056. · Zbl 1490.93061
[29] R. Li, Q. Zhang, and T. Chu, Quotients of probabilistic Boolean networks, IEEE Trans. Automat. Control, 2022, https://doi.org/10.1109/TAC.2022.3144273. · Zbl 07741810
[30] Y. Li, J. Zhu, B. Li, Y. Liu, and J. Lu, A necessary and sufficient graphic condition for the original disturbance decoupling of Boolean networks, IEEE Trans. Automat. Control, 66 (2021), pp. 3765-3772. · Zbl 1472.93081
[31] J. Liang, H. Chen, and J. Lam, An improved criterion for controllability of Boolean control networks, IEEE Trans. Automat. Control, 62 (2017), pp. 6012-6018. · Zbl 1390.93150
[32] Y. Liu, L. Wang, J. Lu, and J. Cao, Sampled-data stabilization of probabilistic Boolean control networks, Systems Control Lett., 124 (2019), pp. 106-111. · Zbl 1408.93099
[33] J. Lu, J. Zhong, C. Huang, and J. Cao, On pinning controllability of Boolean control networks, IEEE Trans. Automat. Control, 61 (2016), pp. 1658-1663. · Zbl 1359.93057
[34] J. Lu, J. Zhong, L. Li, D. W. C. Ho, and J. Cao, Synchronization analysis of master-slave probabilistic Boolean networks, Sci. Rep., 5 (2015), 13437.
[35] Z. Ma, Z. J. Wang, and M. J. McKeown, Probabilistic Boolean network analysis of brain connectivity in Parkinson’s disease, IEEE J. Sel. Topics Signal Process., 2 (2008), pp. 975-985.
[36] N. Y. Megawati and A. van der Schaft, Bisimulation equivalence of differential-algebraic systems, Internat. J. Control, 91 (2018), pp. 45-56. · Zbl 1390.93223
[37] M. Meng, G. Xiao, C. Zhai, and G. Li, Controllability of Markovian jump Boolean control networks, Automatica, 106 (2019), pp. 70-76. · Zbl 1429.93040
[38] R. Milner, Communication and Concurrency, Prentice-Hall, Upper Saddle River, NJ, 1989. · Zbl 0683.68008
[39] S. Mirzazad-Barijough and J.-W. Lee, Stability and transient performance of discrete-time piecewise affine systems, IEEE Trans. Automat. Control, 57 (2012), pp. 936-949. · Zbl 1369.93536
[40] R. Pal, A. Datta, and E. R. Dougherty, Optimal infinite-horizon control for probabilistic Boolean networks, IEEE Trans. Signal Process., 54 (2006), pp. 2375-2387. · Zbl 1374.94952
[41] G. J. Pappas, Bisimilar linear systems, Automatica, 39 (2003), pp. 2035-2047. · Zbl 1045.93033
[42] D. Park, Concurrency and automata on infinite sequences, in Proceedings of the 5th GI Conference on Theoretical Computer Science, Springer, 1981, pp. 167-183. · Zbl 0457.68049
[43] G. Pola, C. Manes, A. J. van der Schaft, and M. D. D. Benedetto, Bisimulation equivalence of discrete-time stochastic linear control systems, IEEE Trans. Automat. Control, 63 (2018), pp. 1897-1912. · Zbl 1423.93367
[44] G. Pola, A. J. van der Schaft, and M. D. D. Benedetto, Equivalence of switching linear systems by bisimulation, Internat. J. Control, 79 (2006), pp. 74-92. · Zbl 1122.93319
[45] P. Prabhakar, G. Dullerud, and M. Viswanathan, Stability preserving simulations and bisimulations for hybrid systems, IEEE Trans. Automat. Control, 60 (2015), pp. 3210-3225.
[46] I. Shmulevich, E. R. Dougherty, S. Kim, and W. Zhang, Probabilistic Boolean networks: A rule-based uncertainty model for gene regulatory networks, Bioinformatics, 18 (2002), pp. 261-274.
[47] P. Tabuada and G. J. Pappas, Bisimilar control affine systems, Systems Control Lett., 52 (2004), pp. 49-58. · Zbl 1157.93300
[48] J. C. Tay and P. Tan, Finding intervention points in the pathogenesis of dengue viral infection, in Proceedings of the International Conference of the IEEE Engineering in Medicine and Biology Society, New York, 2006, pp. 5315-5321.
[49] M. Toyoda and Y. Wu, Mayer-type optimal control of probabilistic Boolean control network with uncertain selection probabilities, IEEE Trans. Cybernet., 51 (2021), pp. 3079-3092.
[50] A. J. van der Schaft, Equivalence of dynamical systems by bisimulation, IEEE Trans. Automat. Control, 49 (2004), pp. 2160-2172. · Zbl 1365.93212
[51] A. Veliz-Cuba and B. Stigler, Boolean models can explain bistability in the lac operon, J. Comput. Biol., 18 (2011), pp. 783-794.
[52] H. Vinjamoor and A. J. van der Schaft, The achievable dynamics via control by interconnection, IEEE Trans. Automat. Control, 56 (2011), pp. 1110-1117. · Zbl 1368.93117
[53] B. Wang and J. Feng, On detectability of probabilistic Boolean networks, Inform. Sci., 483 (2019), pp. 383-395.
[54] R.-S. Wang, A. Saadatpour, and R. Albert, Boolean modeling in systems biology: An overview of methodology and applications, Phys. Biol., 9 (2012), 055001.
[55] E. Weiss and M. Margaliot, A polynomial-time algorithm for solving the minimal observability problem in conjunctive Boolean networks, IEEE Trans. Automat. Control, 64 (2019), pp. 2727-2736. · Zbl 1482.93085
[56] Y. Wu, Y. Guo, and M. Toyoda, Policy iteration approach to the infinite horizon average optimal control of probabilistic Boolean networks, IEEE Trans. Neural Netw. Learn. Syst., 32 (2021), pp. 2910-2924.
[57] A. Yerudkar, C. D. Vecchio, and L. Glielmo, Feedback stabilization control design for switched Boolean control networks, Automatica, 116 (2020), 108934. · Zbl 1440.93205
[58] L. Yu, S. Marshall, T. Forster, and P. Ghazal, Modelling of macrophage gene expression in the interferon pathway, in Proceeding of the IEEE International Workshop on Genomic Signal Processing and Statistics, College Station, TX, 2006, pp. 45-46.
[59] Y. Yu, J. Feng, J. Pan, and D. Cheng, Block decoupling of Boolean control networks, IEEE Trans. Automat. Control, 64 (2019), pp. 3129-3140. · Zbl 1482.93027
[60] K. Zhang and K. H. Johansson, Efficient verification of observability and reconstructibility for large Boolean control networks with special structures, IEEE Trans. Automat. Control, 65 (2020), pp. 5144-5158. · Zbl 07320090
[61] K. Zhang, L. Zhang, and R. Su, A weighted pair graph representation for reconstructibility of Boolean control networks, SIAM J. Control Optim., 54 (2016), pp. 3040-3060. · Zbl 1350.93048
[62] Q. Zhang, J. Feng, and B. Wang, Stability analysis of probabilistic Boolean networks with switching topology, Nonlinear Anal. Hybrid Syst., 42 (2021), 101076. · Zbl 1478.93728
[63] Q. Zhang, J. Feng, B. Wang, and M. Meng, Bisimulations of Boolean control networks with impulsive effects and its application in controllability, Asian J. Control, 21 (2019), pp. 2559-2568. · Zbl 1451.93038
[64] X. Zhang, Y. Wang, and D. Cheng, Output tracking of Boolean control networks, IEEE Trans. Automat. Control, 65 (2020), pp. 2730-2735. · Zbl 07256388
[65] Z. Zhang, T. Leifeld, and P. Zhang, Reduced-order observer design for Boolean control networks, IEEE Trans. Automat. Control, 65 (2020), pp. 434-441. · Zbl 1483.93422
[66] Y. Zhao and D. Cheng, On controllability and stabilizability of probabilistic Boolean control networks, Sci. China Inf. Sci., 57 (2014), 012202. · Zbl 1331.93027
[67] J. Zhong, D. W. C. Ho, and J. Lu, A new approach to pinning control of Boolean networks, IEEE Trans. Control Netw. Syst., 9 (2022), pp. 415-426.
[68] J. Zhong, Z. Yu, Y. Li, and J. Lu, State estimation for probabilistic Boolean networks via outputs observation, IEEE Trans. Neural Netw. Learn. Syst., 2021, https://doi.org/10.1109/TNNLS.2021.3059795.
[69] R. Zhou, Y. Guo, and W. Gui, Set reachability and observability of probabilistic Boolean networks, Automatica, 106 (2019), pp. 230-241. · Zbl 1429.93034
[70] R. Zhou, Y. Guo, Y. Wu, and W. Gui, Asymptotical feedback set stabilization of probabilistic Boolean control networks, IEEE Trans. Neural Netw. Learn. Syst., 31 (2020), pp. 4524-4537.
[71] Q. Zhu, Y. Liu, J. Lu, and J. Cao, On the optimal control of Boolean control networks, SIAM J. Control Optim., 56 (2018), pp. 1321-1341. · Zbl 1403.49039
[72] S. Zhu, J. Lu, L. Lin, and Y. Liu, Minimum-time and minimum-triggering observability of stochastic Boolean networks, IEEE Trans. Automat. Control, 67 (2022), pp. 1558-1565. · Zbl 07560667
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.