Graphical Reduction of Probabilistic Boolean Networks
详细信息 查看官网全文
- 英文论文题名：Graphical Reduction of Probabilistic Boolean Networks
- 论文作者：Bo Li
- 英文论文作者：Bo Li ; Key Laboratory of Mathematics Mechanization ; Academy of Mathematics and Systems Science ; Chinese Academy of Sciences
- 年：2017
- 作者机构：Key Laboratory of Mathematics Mechanization,Academy of Mathematics and Systems Science,Chinese Academy of Sciences;
- 英文论文关键词：Boolean networks ; Gossiping process ; Markov chains ; Communication classes
- 会议召开时间：2017-07-26
- 会议录名称：第36届中国控制会议论文集（A）
- 英文会议录名称：Proceedings of the 36th Chinese Control Conference（A）
- 语种：英文
- 分类号：O157.5
- 学会代码：KZLL
- 会议名称：第36届中国控制会议
- 会议地点：中国辽宁大连
- 主办单位：中国自动化学会控制理论专业委员会
- 学会名称：中国自动化学会控制理论专业委员会
- 页数：5
- 文件大小：414k
- 原文格式：D
- 会议级别：全国
摘要
We propose a Boolean gossiping model as a simplified yet intriguing probabilistic Boolean network from a graphical reduction perspective. For the case that only positive node interactions are allowed, by standard theories of Markov chains,we prove that the node states almost surely asymptotically converge to an agreement. Using mean-field approximation we characterize the convergent distribution for large-scale networks. The number of states is exponential to the number of nodes in the network. Thus, the calculation of numbers of communication classes seems to be time consuming. Here, we give the exact number of communication classes of any positive Boolean networks. We show that minor variation in local structures can drastically change the number of network communication classes. For general Boolean interaction rules, we provide some examples to indicate the possible conditions under which the Boolean gossiping process are absorbing Markov chains. These results show the possibilities of using graphical methods to fundamentally reduce the computational complexity in deciding behaviors of Boolean networks.
We propose a Boolean gossiping model as a simplified yet intriguing probabilistic Boolean network from a graphical reduction perspective. For the case that only positive node interactions are allowed, by standard theories of Markov chains,we prove that the node states almost surely asymptotically converge to an agreement. Using mean-field approximation we characterize the convergent distribution for large-scale networks. The number of states is exponential to the number of nodes in the network. Thus, the calculation of numbers of communication classes seems to be time consuming. Here, we give the exact number of communication classes of any positive Boolean networks. We show that minor variation in local structures can drastically change the number of network communication classes. For general Boolean interaction rules, we provide some examples to indicate the possible conditions under which the Boolean gossiping process are absorbing Markov chains. These results show the possibilities of using graphical methods to fundamentally reduce the computational complexity in deciding behaviors of Boolean networks.
We propose a Boolean gossiping model as a simplified yet intriguing probabilistic Boolean network from a graphical reduction perspective. For the case that only positive node interactions are allowed, by standard theories of Markov chains,we prove that the node states almost surely asymptotically converge to an agreement. Using mean-field approximation we characterize the convergent distribution for large-scale networks. The number of states is exponential to the number of nodes in the network. Thus, the calculation of numbers of communication classes seems to be time consuming. Here, we give the exact number of communication classes of any positive Boolean networks. We show that minor variation in local structures can drastically change the number of network communication classes. For general Boolean interaction rules, we provide some examples to indicate the possible conditions under which the Boolean gossiping process are absorbing Markov chains. These results show the possibilities of using graphical methods to fundamentally reduce the computational complexity in deciding behaviors of Boolean networks.
引文
[1]H.Kitano.Foundations of Systems Biology.Cambrige:MIT Press,2001.
[2]S.A.Kauffman,“Metabolic stability and epigenesis in randomly constructed genetic nets,”Journal of Theoretical Biology,22:437-467,1969.
[3]S.A.Kauffman.The origins of order:Self-organization and selection in evolution.New York:Oxford University Press.1993.
[4]I.Shmulevich,E.R.Dougherty,S.Kim et al.,“Probabilistic Boolean networks:a rule-based uncertainty model for gene regulatory networksk,”Bioinformatics,2:261-274,2002.
[5]J.J.Hopfield,“Neural networks and physical systems with emergent collective computational abilities,”Proceedings of the National Academy of Sciences,vol.79,no.8,pp.2554-2558,April 1982.
[6]R.Karp,C.Schindelhauer,S.Shenker,and B.Vcking,“Randomized rumor spreading,”Proc.Symp.Foundations of Computer Science,564-574,2000.
[7]P.van Mieghem,J.Omic,and R.Kooij,“Virus spread in networks,”IEEE/ACM Transactions on Networking,vol.17,no.1,pp 1-14,2009.
[8]D.Cheng and H.Qi,“Controllability and observability of Boolean control networks,”Automatica,45:1659-1667,2009.
[9]I.Shmulevich,R.F.Hashimoto,E.R.Dougherty,et al.,“Steaty-state analysis of genetic regulatory networks modeled by probabilistic Boolean networks,”Comp Funct Genomics,4:601-608,2003.
[10]M.Brun,E.R.Dougherty,and I.Shmulevich,“Steady-state probabilities for attractors in probabilistic Boolean networks,”Signal Process,85:1993-2013,2005.
[11]R.Pal,“Context-sensitive probabilistic Boolean networks:steady-state properties,reduction,and steady-state approximation,”IEEE Transactions on Signal Processing,58(2):879-890,2010.
[12]R.Pal and S.Bhattacharya,“Characterizing the effect of coarse-scale PBN modeling on dynamics and intervention performance of genetic regulatory networks represented by stochastic master equation models,”IEEE Transactions on Signal Processing,58(6):3341-3351,2010.
[13]T.Akutsu,S.Kuhara,O.Maruyama,et al.“A system for identifying genetic networks from gene expression patterns produced by gene disruptions and overexpressions,”Genome Inf.,vol.9,pp.151C160,1998.
[14]S.Boyd,A.Ghosh,B.Prabhakar and D.Shah,“Randomized gossip algorithms,”IEEE Trans.Information Theory,vol.52,no.6,pp.2508-2530,2006.
[15]D.Acemoglu,A.Ozdaglar and A.Parandeh Gheibi,“Spread of(Mis)information in social networks,”Games and Economic Behavior,vol.70,no.2,pp.194-227,2010
[16]B.Doerr,M.Fouz,and T.Friedrich,“Why rumors spread so quickly in social networks?”Communications of ACM,55(6):2012.
[17]D.Shah,“Gossip Algorithms,”Foundations and Trends in Networking,vol.3,no.1,pp.1-125,2008.
[18]C.M.Grinstead and J.L.Snell.Introduction to Probability:Second Revised Edition.American Mathematical Society,2012.
[2]S.A.Kauffman,“Metabolic stability and epigenesis in randomly constructed genetic nets,”Journal of Theoretical Biology,22:437-467,1969.
[3]S.A.Kauffman.The origins of order:Self-organization and selection in evolution.New York:Oxford University Press.1993.
[4]I.Shmulevich,E.R.Dougherty,S.Kim et al.,“Probabilistic Boolean networks:a rule-based uncertainty model for gene regulatory networksk,”Bioinformatics,2:261-274,2002.
[5]J.J.Hopfield,“Neural networks and physical systems with emergent collective computational abilities,”Proceedings of the National Academy of Sciences,vol.79,no.8,pp.2554-2558,April 1982.
[6]R.Karp,C.Schindelhauer,S.Shenker,and B.Vcking,“Randomized rumor spreading,”Proc.Symp.Foundations of Computer Science,564-574,2000.
[7]P.van Mieghem,J.Omic,and R.Kooij,“Virus spread in networks,”IEEE/ACM Transactions on Networking,vol.17,no.1,pp 1-14,2009.
[8]D.Cheng and H.Qi,“Controllability and observability of Boolean control networks,”Automatica,45:1659-1667,2009.
[9]I.Shmulevich,R.F.Hashimoto,E.R.Dougherty,et al.,“Steaty-state analysis of genetic regulatory networks modeled by probabilistic Boolean networks,”Comp Funct Genomics,4:601-608,2003.
[10]M.Brun,E.R.Dougherty,and I.Shmulevich,“Steady-state probabilities for attractors in probabilistic Boolean networks,”Signal Process,85:1993-2013,2005.
[11]R.Pal,“Context-sensitive probabilistic Boolean networks:steady-state properties,reduction,and steady-state approximation,”IEEE Transactions on Signal Processing,58(2):879-890,2010.
[12]R.Pal and S.Bhattacharya,“Characterizing the effect of coarse-scale PBN modeling on dynamics and intervention performance of genetic regulatory networks represented by stochastic master equation models,”IEEE Transactions on Signal Processing,58(6):3341-3351,2010.
[13]T.Akutsu,S.Kuhara,O.Maruyama,et al.“A system for identifying genetic networks from gene expression patterns produced by gene disruptions and overexpressions,”Genome Inf.,vol.9,pp.151C160,1998.
[14]S.Boyd,A.Ghosh,B.Prabhakar and D.Shah,“Randomized gossip algorithms,”IEEE Trans.Information Theory,vol.52,no.6,pp.2508-2530,2006.
[15]D.Acemoglu,A.Ozdaglar and A.Parandeh Gheibi,“Spread of(Mis)information in social networks,”Games and Economic Behavior,vol.70,no.2,pp.194-227,2010
[16]B.Doerr,M.Fouz,and T.Friedrich,“Why rumors spread so quickly in social networks?”Communications of ACM,55(6):2012.
[17]D.Shah,“Gossip Algorithms,”Foundations and Trends in Networking,vol.3,no.1,pp.1-125,2008.
[18]C.M.Grinstead and J.L.Snell.Introduction to Probability:Second Revised Edition.American Mathematical Society,2012.