| 第11行： |
第11行： |
| | | | |
| | ==经典模型== | | ==经典模型== |
| − | A Boolean network is a particular kind of [[sequential dynamical system]], where time and states are discrete, i.e. both the set of variables and the set of states in the time series each have a [[bijection]] onto an integer series. Such systems are like [[cellular automata]] on networks, except for the fact that when they are set up each node has a rule that is randomly chosen from all ''2{{sup|2{{sup|K}}}}'' possible ones with ''K'' inputs. With ''K=2'' class 2 behavior tends to dominate. But for ''K>2'', the behavior one sees quickly approaches what is typical for a random mapping in which the network representing the evolution of the ''2{{sup|N}}'' states of the ''N'' underlying nodes is itself connected essentially randomly.<ref>{{cite book|last1=Wolfram|first1=Stephen|title=A New Kind of Science|date=2002|publisher=Wolfram Media, Inc.|location=Champaign, Illinois|isbn=978-1579550080|page=[https://archive.org/details/newkindofscience00wolf/page/936 936]|url=https://archive.org/details/newkindofscience00wolf/page/936|accessdate=15 March 2018|url-access=registration}}</ref>
| |
| | | | |
| − | <nowiki>A Boolean network is a particular kind of sequential dynamical system, where time and states are discrete, i.e. both the set of variables and the set of states in the time series each have a bijection onto an integer series. Such systems are like cellular automata on networks, except for the fact that when they are set up each node has a rule that is randomly chosen from all 2}} possible ones with K inputs. With K=2 class 2 behavior tends to dominate. But for K>2, the behavior one sees quickly approaches what is typical for a random mapping in which the network representing the evolution of the 2 states of the N underlying nodes is itself connected essentially randomly.</nowiki>
| |
| | | | |
| − | 布尔网络是一种有着特殊的顺序动力学的系统，其中时间和状态都是离散的。也就是说，时间序列中的变量集和状态集都各自有一个偏射到一个整数序列上。这样的系统就像网络上的 | + | 布尔网络是一种有着特殊的顺序动力学的系统，其中时间和状态都是离散的。也就是说，时间序列中的变量集和状态集都各自有一个偏射到一个整数序列上。这样的系统就像网络上的'''<font color="#FF8000">元胞自动机 cellular automata（CA）</font>'''一样，只是当它们被建立起来的时候，每个节点都遵从着一个规则，这个规则是从所有 ''2<sup>k</sup>'' 个可能的规则中随机选择的，有 ''K'' 个输入。在 ''K=2'' 时，第二类行为往往占主导地位。但对于 ''K>2'' ，人们看到的行为很快就会接近随机映射的典型特征，其中代表 ''N'' 个底层节点的 ''2<sup>k</sup>'' 种状态演化的网络本身基本上是随机连接的<ref>{{cite book|last1=Wolfram|first1=Stephen|title=A New Kind of Science|date=2002|publisher=Wolfram Media, Inc.|location=Champaign, Illinois|isbn=978-1579550080|page=[https://archive.org/details/newkindofscience00wolf/page/936 936]|url=https://archive.org/details/newkindofscience00wolf/page/936|accessdate=15 March 2018|url-access=registration}}</ref>。 |
| − | '''<font color="#FF8000">元胞自动机 cellular automata（CA）</font>'''一样，只是当它们被建立起来的时候，每个节点都遵从着一个规则，这个规则是从所有 ''2<sup>k</sup>'' 个可能的规则中随机选择的，有 ''K'' 个输入。在 ''K=2'' 时，第二类行为往往占主导地位。但对于 ''K>2'' ，人们看到的行为很快就会接近随机映射的典型特征，其中代表 ''N'' 个底层节点的 ''2<sup>k</sup>'' 种状态演化的网络本身基本上是随机连接的。 | |
| | | | |
| − | 状态转移图的一个重要性质是图中的每个节点都有一条出边，因为布尔网络的下一个状态是由布尔网络的当前状态唯一确定的。从这个属性可以看出，状态转换图是树状结构的集合，每个树状结构由树和循环组成，其中树和/或循环可以由单个节点和一个自循环组成。在这些树状结构中，每条边都是从叶指向根的，循环对应于树的根。
| + | 为了结构化分析布尔网络，我们先介绍一下'''<font color="#FF8000">状态迁移图State Transition Diagram (STD)</font>'''的概念。状态迁移图也称为状态转移图，被用来描述系统或对象的状态，以及导致系统或对象的状态改变的事件，从而描述系统的行为。属于结构化分析方法使用工具。在状态迁移图中，由一个状态和一个事件所确定的下一状态可能会有多个。实际系统在下一步会迁移到哪一个状态，是由更详细的内部状态和更详细的事件信息来决定的，此时在状态迁移图中可能需要使用加进判断框和处理框的记法。状态迁移图在结构化分析中具有如下优点：第一，状态之间的关系能够直观地捕捉到，这样很直观地就能看到是否所有可能的状态迁移都已纳入图中，是否存在不必要的状态等。第二，由于状态迁移图的单纯性，能够简单机械地分析许多状态转移的情况，可以很容易地建立分析工具。 |
| | | | |
| − | A '''random Boolean network''' (RBN) is one that is randomly selected from the set of all possible boolean networks of a particular size, ''N''. One then can study statistically, how the expected properties of such networks depend on various statistical properties of the ensemble of all possible networks. For example, one may study how the RBN behavior changes as the average connectivity is changed.
| + | 那么对于布尔网络的结构分析，其状态迁移图的一个重要性质是图中的每个节点都有一条出边，因为布尔网络的下一个状态是由布尔网络的当前状态唯一确定的。从这个属性可以看出，状态迁移图是树状结构的集合，每个树状结构由树和循环组成，其中树和/或循环可以由单个节点和一个自循环组成。在这些树状结构中，每条边都是从叶指向根的，循环对应于树的根。 |
| | | | |
| − | A random Boolean network (RBN) is one that is randomly selected from the set of all possible boolean networks of a particular size, N. One then can study statistically, how the expected properties of such networks depend on various statistical properties of the ensemble of all possible networks. For example, one may study how the RBN behavior changes as the average connectivity is changed.
| + | 接下来我们了解布尔网络中的另一种随机型网络：'''<font color="#FF8000">随机布尔网络 Random Boolean Network（RBN） </font>'''是指从所有具有特定大小''N'' 的可能布尔网络集合中随机选取的网络。然后，人们可以从统计学上研究，这种网络的预期特性如何依赖于所有可能网络的集合的各种统计特性。 例如，人们可以研究随机布尔网络的行为如何随着网络集合属性中'''<font color="#FF8000"> 平均连通性 Average Connectivity </font>'''的改变而改变。 |
| | | | |
| − | '''<font color="#FF8000">随机布尔网络 Random Boolean Network（RBN） </font>'''是指从所有可能的特定大小的布尔网络 ''N'' 的集合中随机选取的网络。然后，人们可以从统计学上研究，这种网络的预期特性如何依赖于所有可能网络的集合的各种统计特性。 例如，人们可以研究RBN行为如何随着'''<font color="#FF8000"> Average Connectivity 平均连通性 </font>'''的改变而改变。
| + | 对于布尔网络经典模型的研究历史，最早可以追溯到1969年，Stuart A. Kauffman 就提出了第一个布尔网络，作为遗传调控网络的随机模型<ref name="KauffmanOriginal">{{cite journal|last1=Kauffman|first1=Stuart|title=Homeostasis and Differentiation in Random Genetic Control Networks|journal=Nature|date=11 October 1969|volume=224|issue=5215|pages=177–178|doi=10.1038/224177a0|pmid=5343519|bibcode = 1969Natur.224..177K }}<!--|accessdate=25 November 2014--></ref>，但直到2000年之后，人们对于布尔网络模型的数学理解才逐步开始<ref name="AldanaCoppersmithKadanoff">{{cite book|last1=Aldana|first1=Maximo|last2=Coppersmith|first2=Susan|author2-link= Susan Coppersmith |last3=Kadanoff|first3=Leo P.|title=Boolean Dynamics with Random Couplings|journal=Perspectives and Problems in Nonlinear Sciences|date=2003|pages=23–89|doi=10.1007/978-0-387-21789-5_2|arxiv=nlin/0204062|isbn=978-1-4684-9566-9}}</ref><ref>{{Cite journal|arxiv=nlin.AO/0408006|last1=Gershenson|first1=Carlos|title=Introduction to Random Boolean Networks|journal=In Bedau, M., P. Husbands, T. Hutton, S. Kumar, and H. Suzuki (eds.) Workshop and Tutorial Proceedings, Ninth International Conference on the Simulation and Synthesis of Living Systems (ALife IX). Pp|volume=2004|pages=160–173|year=2004|bibcode=2004nlin......8006G}}</ref>。 |
| | | | |
| | + | ==吸引子== |
| | + | <br> |
| | | | |
| − | The first Boolean networks were proposed by [[Stuart A. Kauffman]] in 1969, as [[random]] models of [[genetic regulatory network]]s<ref name="KauffmanOriginal">{{cite journal|last1=Kauffman|first1=Stuart|title=Homeostasis and Differentiation in Random Genetic Control Networks|journal=Nature|date=11 October 1969|volume=224|issue=5215|pages=177–178|doi=10.1038/224177a0|pmid=5343519|bibcode = 1969Natur.224..177K }}<!--|accessdate=25 November 2014--></ref> but their mathematical understanding only started in the 2000s.<ref name="AldanaCoppersmithKadanoff">{{cite book|last1=Aldana|first1=Maximo|last2=Coppersmith|first2=Susan|author2-link= Susan Coppersmith |last3=Kadanoff|first3=Leo P.|title=Boolean Dynamics with Random Couplings|journal=Perspectives and Problems in Nonlinear Sciences|date=2003|pages=23–89|doi=10.1007/978-0-387-21789-5_2|arxiv=nlin/0204062|isbn=978-1-4684-9566-9}}</ref><ref>{{Cite journal|arxiv=nlin.AO/0408006|last1=Gershenson|first1=Carlos|title=Introduction to Random Boolean Networks|journal=In Bedau, M., P. Husbands, T. Hutton, S. Kumar, and H. Suzuki (eds.) Workshop and Tutorial Proceedings, Ninth International Conference on the Simulation and Synthesis of Living Systems (ALife IX). Pp|volume=2004|pages=160–173|year=2004|bibcode=2004nlin......8006G}}</ref>
| + | 由于布尔网络只有 2<sup>N</sup> 种有限可能的状态，所以一个系统历经的状态轨迹迟早会到达以前访问过的状态。因此，由于动力学是确定性的，系统的状态轨迹将落入一个稳定的状态或状态周期中，这种稳定状态或者周期即被称为'''<font color="#FF8000">吸引子 Attractors </font>'''。这里说明一下，对于在更广泛的动力学系统领域的情况，一个稳定状态或者周期只有当对于系统的扰动导致系统状态回到这个稳定状态或者周期状态时才称其为吸引子。如果吸引子只有一个孤立的状态，则称为'''<font color="#FF8000">点吸引子point attractor'''，如果吸引子由一个以上的多个状态组成，则称为'''<font color="#FF8000">周期吸引子cycle attractor'''或者'''<font color="#FF8000">极限环limit cycle</font>'''。导致吸引子的状态集称为吸引子的'''<font color="#FF8000">吸引域basin of the attractor</font>'''。 |
| | | | |
| − | The first Boolean networks were proposed by Stuart A. Kauffman in 1969, as random models of genetic regulatory networks but their mathematical understanding only started in the 2000s.
| + | 只发生在系统状态轨迹开始时的状态（也就是没有其他轨迹通向它们）被称为'''<font color="#FF8000">伊甸园状态garden-of-Eden states<ref name="WuenscheBook">{{cite book|last1=Wuensche|first1=Andrew|title=Exploring discrete dynamics : [the DDLab manual : tools for researching cellular automata, random Boolean and multivalue neworks [sic] and beyond]|date=2011|publisher=Luniver Press|location=Frome, England|isbn=9781905986316|page=16|url=https://books.google.de/books?id=qsktzY_Vg8QC&pg=PA16|accessdate=12 January 2016}}</ref>'''，网络的动态从这些状态流向吸引子，而它们到达吸引子所需的时间也被称为'''<font color="#FF8000">瞬态时间transient time<ref name="DrosselRbn" />'''。 |
| | | | |
| − | 1969年，Stuart A. Kauffman提出了第一个布尔网络，作为遗传调控网络的随机模型，但其数学理解在2000年才开始。
| |
| − |
| |
| − | ==Attractors==
| |
| − | '''<font color="#FF8000">吸引子 Attractors </font>'''<br>
| |
| − |
| |
| − |
| |
| − |
| |
| − | Since a Boolean network has only 2<sup>''N''</sup> possible states, a trajectory will sooner or later reach a previously visited state, and thus, since the dynamics are deterministic, the trajectory will fall into a steady state or cycle called an [[attractor]] (though in the broader field of dynamical systems a cycle is only an attractor if perturbations from it lead back to it). If the attractor has only a single state it is called a ''point attractor'', and if the attractor consists of more than one state it is called a ''cycle attractor''. The set of states that lead to an attractor is called the ''basin'' of the attractor. States which occur only at the beginning of trajectories (no trajectories lead ''to'' them), are called ''garden-of-Eden'' states<ref name="WuenscheBook">{{cite book|last1=Wuensche|first1=Andrew|title=Exploring discrete dynamics : [the DDLab manual : tools for researching cellular automata, random Boolean and multivalue neworks [sic] and beyond]|date=2011|publisher=Luniver Press|location=Frome, England|isbn=9781905986316|page=16|url=https://books.google.de/books?id=qsktzY_Vg8QC&pg=PA16|accessdate=12 January 2016}}</ref> and the dynamics of the network flow from these states towards attractors. The time it takes to reach an attractor is called ''transient time''.<ref name="DrosselRbn" />
| |
| − |
| |
| − | Since a Boolean network has only 2<sup>N</sup> possible states, a trajectory will sooner or later reach a previously visited state, and thus, since the dynamics are deterministic, the trajectory will fall into a steady state or cycle called an attractor (though in the broader field of dynamical systems a cycle is only an attractor if perturbations from it lead back to it). If the attractor has only a single state it is called a point attractor, and if the attractor consists of more than one state it is called a cycle attractor. The set of states that lead to an attractor is called the basin of the attractor. States which occur only at the beginning of trajectories (no trajectories lead to them), are called garden-of-Eden states and the dynamics of the network flow from these states towards attractors. The time it takes to reach an attractor is called transient time.
| |
| − |
| |
| − | 由于布尔网络只有 2<sup>N</sup> 种可能的状态，一个轨迹迟早会到达以前访问过的状态，因此，由于动力学是确定性的，轨迹将落入一个稳定状态或周期，称为吸引子（不过在更广泛的动力学系统领域，一个周期只有当来自它的扰动导致回到它时才是吸引子）。如果吸引子只有一个状态，则称为点吸引子，如果吸引子由一个以上的状态组成，则称为周期吸引子。导致吸引子的状态集称为吸引子的盆地。只在轨迹开始时出现的状态（没有轨迹导致它们），称为'''<font color="#FF8000">伊甸园状态 '''
| |
| | garden-of-Eden states </font>'''网络的动态从这些状态流向吸引子。到达吸引子所需的时间称为'''<font color="#FF8000">瞬时 transient time </font>'''。''' | | garden-of-Eden states </font>'''网络的动态从这些状态流向吸引子。到达吸引子所需的时间称为'''<font color="#FF8000">瞬时 transient time </font>'''。''' |
| | | | |
| | | | |
| − | With growing computer power and increasing understanding of the seemingly simple model, different authors gave different estimates for the mean number and length of the attractors, here a brief summary of key publications.<ref name="GreilReview">{{cite journal|last1=Greil|first1=Florian|title=Boolean Networks as Modeling Framework|journal=Frontiers in Plant Science|date=2012|volume=3|pages=178|doi=10.3389/fpls.2012.00178|pmid=22912642|pmc=3419389}}<!--|accessdate=26 November 2014--></ref>
| + | 随着计算机能力的不断提高，人们对看似简单的模型的理解也越来越深刻，在网络研究中不同的作者对吸引子的平均数量和长度给出了不同的估计，这里简单地总结一下在主要出版物上发表的研究成果<ref name="GreilReview">{{cite journal|last1=Greil|first1=Florian|title=Boolean Networks as Modeling Framework|journal=Frontiers in Plant Science|date=2012|volume=3|pages=178|doi=10.3389/fpls.2012.00178|pmid=22912642|pmc=3419389}}<!--|accessdate=26 November 2014--></ref>。 |
| − | | |
| − | With growing computer power and increasing understanding of the seemingly simple model, different authors gave different estimates for the mean number and length of the attractors, here a brief summary of key publications.
| |
| − | | |
| − | 随着计算机能力的不断提高，对看似简单的模型的理解也越来越深刻，不同的作者对吸引子的平均数量和长度给出了不同的估计，这里简单总结一下主要的出版物。
| |
| | {| class="wikitable sortable" | | {| class="wikitable sortable" |
| | | | |
| 第174行： |
第157行： |
| | |Bilke/ Sjunnesson<ref>{{cite journal|last1=Bilke|first1=Sven|last2=Sjunnesson|first2=Fredrik|title=Stability of the Kauffman model|journal=Physical Review E|date=December 2001|volume=65|issue=1|pages=016129|doi=10.1103/PhysRevE.65.016129|pmid=11800758|arxiv = cond-mat/0107035 |bibcode = 2002PhRvE..65a6129B }}<!--|accessdate=26 November 2014--></ref> | | |Bilke/ Sjunnesson<ref>{{cite journal|last1=Bilke|first1=Sven|last2=Sjunnesson|first2=Fredrik|title=Stability of the Kauffman model|journal=Physical Review E|date=December 2001|volume=65|issue=1|pages=016129|doi=10.1103/PhysRevE.65.016129|pmid=11800758|arxiv = cond-mat/0107035 |bibcode = 2002PhRvE..65a6129B }}<!--|accessdate=26 November 2014--></ref> |
| | | | |
| − | |Bilke/ Sjunnesson | + | | Bilke/ Sjunnesson |
| | | | |
| | |Bilke/Sjunnesson | | |Bilke/Sjunnesson |
| 第208行： |
第191行： |
| | |- | | |- |
| | | | |
| − | |Socolar/Kauffman<ref>{{cite journal|last1=Socolar|first1=J.|last2=Kauffman|first2=S.|title=Scaling in Ordered and Critical Random Boolean Networks|journal=Physical Review Letters|date=February 2003|volume=90|issue=6|pages=068702|doi=10.1103/PhysRevLett.90.068702|pmid=12633339|bibcode=2003PhRvL..90f8702S|arxiv = cond-mat/0212306 }}</ref> | + | | Socolar/Kauffman<ref>{{cite journal|last1=Socolar|first1=J.|last2=Kauffman|first2=S.|title=Scaling in Ordered and Critical Random Boolean Networks|journal=Physical Review Letters|date=February 2003|volume=90|issue=6|pages=068702|doi=10.1103/PhysRevLett.90.068702|pmid=12633339|bibcode=2003PhRvL..90f8702S|arxiv = cond-mat/0212306 }}</ref> |
| | | | |
| | |Socolar/Kauffman | | |Socolar/Kauffman |