进化论构建网络的方法剖析

1、进化论构建网络的方法剖析n WS小世界模型构造算法如下：小世界模型构造算法如下：1.从规则图开始：考虑一个含有从规则图开始：考虑一个含有N个点的最近邻耦个点的最近邻耦合网络，它们围成一个环，其中每个节点都与它合网络，它们围成一个环，其中每个节点都与它左右的各左右的各K/2节点相连，节点相连，K是偶数。是偶数。2.随机化重连：以概率随机化重连：以概率P随机地重新连接网络中的随机地重新连接网络中的每个边，即将边的一个端点保持不变，而另一个每个边，即将边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点。其中规定，端点取为网络中随机选择的一个节点。其中规定，任意两个不同的节点之间至多只能有

2、一条边，并任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身且每一个节点都不能有边与自身1.小世界网络模型小世界网络模型nNW小世界模型构造算法：小世界模型构造算法：n1.从规则图开始：考虑一个含有从规则图开始：考虑一个含有N个点的最个点的最近邻耦合网络，它们围成一个环，其中每近邻耦合网络，它们围成一个环，其中每个节点都与它左右相邻的各个节点都与它左右相邻的各k/2个节点相连，个节点相连，k是偶数。是偶数。n2.随机化加边：以概率随机化加边：以概率P在随机选取的一对在随机选取的一对节点之间加上一条边。其中，任意两个不节点之间加上一条边。其中，任意两个不同的节点之间至多只能有

3、一条边，并且每同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。一个节点都不能有边与自身相连。jjiikk例例: m0 = 3, m = 2t = 1t = 2t = 33.生物网络特征生物网络特征n生物分子网络具有稀疏性生物分子网络具有稀疏性n生物分子网络具生物分子网络具scale-free性质性质n生物分子网络具有超小世界性生物分子网络具有超小世界性n生物分子网络具有层次结构生物分子网络具有层次结构n生物分子网络具有度的负关联性生物分子网络具有度的负关联性n生物分子网络具有一定的鲁棒性和适应性生物分子网络具有一定的鲁棒性和适应性n10.1 随机复制模型随机复制模型n10.2

4、 偏爱复制模型偏爱复制模型n10.3 节点删除变异模型节点删除变异模型n10.4 删边变异模型删边变异模型引言引言n众所周知，从自然选择和生物进化来看，众所周知，从自然选择和生物进化来看，复制和变异是生物分子网络进化的内在基复制和变异是生物分子网络进化的内在基本机制。本机制。n近几年来，不少研究者提出了各种不同的近几年来，不少研究者提出了各种不同的基于复制变异准则的生物网络构建模型，基于复制变异准则的生物网络构建模型，这里我们简称为这里我们简称为DD模型。模型。引言引言n以生物进化论作为理论基础，按照一些基以生物进化论作为理论基础，按照一些基本生物实验和观察的事实为依据，在复制本生物实验和观察

5、的事实为依据，在复制和变异过程中提出一些原则，从而设法构和变异过程中提出一些原则，从而设法构造出具有度负关联性的生物分子网络模型，造出具有度负关联性的生物分子网络模型，解决网络中度负相关性产生的生物学机制，解决网络中度负相关性产生的生物学机制，希望为生物分子网络构建的一般方法提供希望为生物分子网络构建的一般方法提供一些有用的启示。一些有用的启示。n首先考虑复制对度负关联性的影响。首先考虑复制对度负关联性的影响。n：给定单连接的具有：给定单连接的具有n0个节点的初始网络个节点的初始网络G0；n，随机选取一个节点进行复制，也就是说，随机选取一个节点进行复制，也就是说，新的复制节点将与原来的被复制节

6、点的邻新的复制节点将与原来的被复制节点的邻居相连。居相连。n这个过程一直进行下去，直到网络到达预这个过程一直进行下去，直到网络到达预期规模期规模N个节点。个节点。练习题练习题n如下图所示网络，依据随机复杂模型进行如下图所示网络，依据随机复杂模型进行时间步长为时间步长为T=8，即，即N=16，得到的新的网，得到的新的网络，给网络的度分布图。络，给网络的度分布图。DEGCFABH图图10.1随机复制模型的随机复制模型的rk关系图关系图（k是网络节点数，是网络节点数，r是是Pearson关联系数）关联系数）A：r0=-0.0068，N=3000B：r0=-0.0182，N=3000n如下图所示，给出

7、了网络节点数如下图所示，给出了网络节点数k和和pearson关联系数关联系数r的关系。两个初始网络的关系。两个初始网络是中性的，节点数目都为是中性的，节点数目都为n0=100，初始关，初始关联系数分别为联系数分别为r00=-0.0182，最后的网络规，最后的网络规模为模为N=3000.n由于网络的生成是具有随机性质的，因此由于网络的生成是具有随机性质的，因此图中每一点都是通过图中每一点都是通过100个网络取平均值得个网络取平均值得到。从结果明显可以看出随机复制能够产到。从结果明显可以看出随机复制能够产生生物分子网络的度负关联性。生生物分子网络的度负关联性。n 解释：由于生物网络是幂率分布，度大

8、的节点远远解释：由于生物网络是幂率分布，度大的节点远远小于度小的节点，因此，假设小于度小的节点，因此，假设a是度大的节点那么是度大的节点那么bcd是是a的邻居，节点的邻居，节点bcd中度小的占绝大多数，通中度小的占绝大多数，通过一次复制那么过一次复制那么a要么它的一个度小的邻居（不失要么它的一个度小的邻居（不失一般性，假定一般性，假定d）被复制，因此就会产生如图（）被复制，因此就会产生如图（a）和（和（b）所示的两种情况。）所示的两种情况。n 注意到度大的节点占少数，注意到度大的节点占少数，a被复制的概率要比被被复制的概率要比被它的一个度小的邻居复制的概率小很多，因此一次它的一个度小的邻居复制

9、的概率小很多，因此一次复制以后复制以后(b)的情况更容易出现，它更具有度的负关的情况更容易出现，它更具有度的负关联性。联性。n 因此，经过一定时间步长以后，网络更可能朝着负因此，经过一定时间步长以后，网络更可能朝着负关联网络方向发展。关联网络方向发展。n基于增长和偏爱的准则（度大的节点更容基于增长和偏爱的准则（度大的节点更容易获得新边），易获得新边），202X年年Barabasi与与Albert提出了著名的提出了著名的BA模型。模型。n有研究者基于生物实际的考虑提出偏爱复有研究者基于生物实际的考虑提出偏爱复制模型。制模型。n事实上，在蛋白质相互作用网络中，度大事实上，在蛋白质相互作用网络中，度

10、大的蛋白质对应的基因序列也更长。的蛋白质对应的基因序列也更长。n合理地认为相同长度的基因序列被复制的合理地认为相同长度的基因序列被复制的概率相等，度大的蛋白质更难被复制。概率相等，度大的蛋白质更难被复制。n因此有理由假定上述随机复制模型中的复因此有理由假定上述随机复制模型中的复制具有某种偏爱性质，于是得到偏爱复制制具有某种偏爱性质，于是得到偏爱复制模型。模型。n1.初始化：给定初始网络初始化：给定初始网络G0（假设初始网（假设初始网络是连通的）络是连通的）n：对于：对于t-1时刻的网络时刻的网络Gt-1节点节点i以概率以概率P(ki)进行复制，其中进行复制，其中ki是节点是节点i的度，记复制节

11、的度，记复制节点为点为i，即将，即将i连接到连接到i的所有邻居上。的所有邻居上。n以后每一时间单位都按照以上步骤进行更以后每一时间单位都按照以上步骤进行更新，直到网络的规模达到预期的规模。新，直到网络的规模达到预期的规模。jjkikikp11)(练习题练习题n依据偏爱复制模型，对下图表示的网络进依据偏爱复制模型，对下图表示的网络进行行T=8次的复制后得到新的网络，给网络的次的复制后得到新的网络，给网络的度分布图。度分布图。图图DEGCFABHn从图从图10.4和和10.5中，很容易怎出随机网络中，很容易怎出随机网络节点数目节点数目k增大而增大而r减小。减小。n相比于随机复制模型而言，偏爱复制模

12、型相比于随机复制模型而言，偏爱复制模型的的r减小得更快一些。减小得更快一些。n也就是说，两种复制机制都能导致网络度也就是说，两种复制机制都能导致网络度负关联性质，偏爱复制模型比随机复制模负关联性质，偏爱复制模型比随机复制模型能够进一步加强这种负关联性，网络更型能够进一步加强这种负关联性，网络更容易朝着负关联网络演化。容易朝着负关联网络演化。复制模型复制模型n从上述讨论中，很容易看到：从上述讨论中，很容易看到：n复制能够使得网络朝着负关联网络发展，复制能够使得网络朝着负关联网络发展，偏爱模型会加强这种变化趋势。偏爱模型会加强这种变化趋势。n因此，从生物进化的角度来看，复制是生因此，从生物进化的角

13、度来看，复制是生物网络产生度负关联性的一种机制。物网络产生度负关联性的一种机制。复制模型复制模型n在上面的复制模型中，只考虑复制而忽略在上面的复制模型中，只考虑复制而忽略变异是为了更好地弄清楚复制对生物分子变异是为了更好地弄清楚复制对生物分子网络度负关联性的内在本质。网络度负关联性的内在本质。n事实上，生物分子网络是复制和变异这两事实上，生物分子网络是复制和变异这两个进化机制共同作用的结果，因此，应当个进化机制共同作用的结果，因此，应当进一步研究变异对度负关联性的影响。进一步研究变异对度负关联性的影响。变异模型变异模型n在真实网络的进化过程中，存在着以下两在真实网络的进化过程中，存在着以下两个

14、基本的生物变异过程。个基本的生物变异过程。n：当一个基因发生功能缺失变异时，会发：当一个基因发生功能缺失变异时，会发生节点删除；生节点删除；n：新的边会产生，已经存在的边会删除或：新的边会产生，已经存在的边会删除或者重组，这些变化都是由于生物分子编码者重组，这些变化都是由于生物分子编码序列的变异造成的。序列的变异造成的。n从生物层面上来讲，有害的变异会导致基从生物层面上来讲，有害的变异会导致基因的毁灭。一旦基因变成非功能性基因，因的毁灭。一旦基因变成非功能性基因，它所调控的蛋白也就与之不相关了。它所调控的蛋白也就与之不相关了。n在蛋白质网络的进化过程中，通过复制产在蛋白质网络的进化过程中，通过

15、复制产生的大多数蛋白被当作冗余被丢弃，这在生的大多数蛋白被当作冗余被丢弃，这在生物网络上反映为节点删除。生物网络上反映为节点删除。n为了模拟这个变异过程，考虑两种节点删为了模拟这个变异过程，考虑两种节点删除变异的方式：除变异的方式：n随机移除蛋白（和它的相互连接）随机移除蛋白（和它的相互连接）n偏爱移除蛋白（和它的相互连接）偏爱移除蛋白（和它的相互连接）n随机节点删除变异模型随机节点删除变异模型n1.初始化：给定单连通的具有初始化：给定单连通的具有N个节点的初个节点的初始网络始网络G0，G0是由是由BA模型生成的中性网络，模型生成的中性网络，即初始关联系数即初始关联系数r接近于零。这样，接近于

16、零。这样，G0是无是无标度的，网络中度小的节点占大多数；标度的，网络中度小的节点占大多数；n随机节点删除变异模型随机节点删除变异模型n2.网络在每一时间步长，随机选取一个节网络在每一时间步长，随机选取一个节点，删除它及其他所有连接。若产生孤立点，删除它及其他所有连接。若产生孤立节点，删除它，相当于本次操作失败，这节点，删除它，相当于本次操作失败，这对生物网络中不起作用的蛋白质降解。对生物网络中不起作用的蛋白质降解。n这个过程一直进行下去直到网络经过这个过程一直进行下去直到网络经过T个时个时间长。间长。练习题练习题n下列网络依据随机节点删除模式经过时间下列网络依据随机节点删除模式经过时间步长为步

17、长为T=4，得到新网络，并给出网络的度，得到新网络，并给出网络的度分布图。分布图。ACBHFGDKEJIn事实上，研究表明，拥有越多连接的蛋白事实上，研究表明，拥有越多连接的蛋白进化速度越慢。进化速度越慢。n在蛋白相互作用的网络中，具有最多连接在蛋白相互作用的网络中，具有最多连接的蛋白在存活时间上是具有较少的连接蛋的蛋白在存活时间上是具有较少的连接蛋白的三倍，这些蛋白是更多效的、进化更白的三倍，这些蛋白是更多效的、进化更慢的，更不容易在进化时被移除。慢的，更不容易在进化时被移除。n另外，度小的节点在网络中确实更容易被另外，度小的节点在网络中确实更容易被删除。特别地，保守性好的蛋白的度与它删除。

18、特别地，保守性好的蛋白的度与它的进化速度是成反比的。的进化速度是成反比的。n因此，可以认为节点删除变异的过程确实因此，可以认为节点删除变异的过程确实包含偏爱性，从而可以给出如下偏爱节点包含偏爱性，从而可以给出如下偏爱节点删除变异模型：删除变异模型：n1.初始化（同随机节点删除变异模型）；初始化（同随机节点删除变异模型）；n2.网络在每一个时间步长，度为网络在每一个时间步长，度为ki的节点的节点i以概率以概率pi被选择删除及其连的边，若产生孤被选择删除及其连的边，若产生孤立节点，删除它；立节点，删除它；n这个过程一直进行下去，直到网络经过这个过程一直进行下去，直到网络经过T个个时间步长。时间步长

19、。),.,2 , 1( 11Npppkikip练习题练习题n下列网络依据偏爱节点删除变异模型经过下列网络依据偏爱节点删除变异模型经过时间步长为时间步长为T=4，请给出新网络及网络的度，请给出新网络及网络的度分布图。分布图。ACBHFGDKEJIn在两个图中关联系数在两个图中关联系数r都随着时间步长的增都随着时间步长的增大而稍微下降，或者说，在一定的时间步大而稍微下降，或者说，在一定的时间步长内，随机删除节点和偏爱删除节点对网长内，随机删除节点和偏爱删除节点对网络的度负关联性是没有太大影响的。络的度负关联性是没有太大影响的。n事实上，由于初始网络为无标度网络，即事实上，由于初始网络为无标度网络，

20、即初始网络中度小的节点占大多数，所以在初始网络中度小的节点占大多数，所以在选择节点的时候，无论是随机还是偏爱，选择节点的时候，无论是随机还是偏爱，都是容易选择度小的节点。都是容易选择度小的节点。n再者，由于初始网络为中性网络，即无关再者，由于初始网络为中性网络，即无关联网络，对于一个度小的节点来说，它的联网络，对于一个度小的节点来说，它的邻居中度大的节点与度小的节点的比例是邻居中度大的节点与度小的节点的比例是几乎相同的，所以大节点的边（简称小几乎相同的，所以大节点的边（简称小-大）大）的概率是大致相同的，这样在一定的时间的概率是大致相同的，这样在一定的时间步长内，随机删除节点和偏爱删除节点会步

21、长内，随机删除节点和偏爱删除节点会使得关联系数使得关联系数r有略微的减小，但并不会强有略微的减小，但并不会强烈影响网络的度负关联性。烈影响网络的度负关联性。n引起边的变异的生物机制在本质上非对称引起边的变异的生物机制在本质上非对称的，即当一条边发生编译时，其中只有一的，即当一条边发生编译时，其中只有一个节点发生变异，另一个节点保持不变。个节点发生变异，另一个节点保持不变。这种非对称性意味着边变异的速率会同时这种非对称性意味着边变异的速率会同时决定于发生变异的节点和未发生变异的节决定于发生变异的节点和未发生变异的节点的度。点的度。n随机删边变异模型：随机删边变异模型：n1.初始化（同随机节点删除

22、变异模型）；初始化（同随机节点删除变异模型）；n，随机选择一个节点，随机选择一个节点i作为变异节点，再从作为变异节点，再从i的邻居中随机选择节点的邻居中随机选择节点j（节点（节点j不发生变不发生变异），删去连接异），删去连接i和和j的边的边Lij，若产生孤立节，若产生孤立节点，删除它。点，删除它。n这个过程一直进行下去，直到网络经过这个过程一直进行下去，直到网络经过T个个时间步长。时间步长。练习题练习题n下列网络依据随机删边变异模型，经过时下列网络依据随机删边变异模型，经过时间步长为间步长为T=4，给出新网络及网络的度分布，给出新网络及网络的度分布图。图。ACBHFGDKEJIn根据生物大分子

23、的保守性和边变异的非对根据生物大分子的保守性和边变异的非对称性，选择度小的节点作为变异节点，然称性，选择度小的节点作为变异节点，然而，现在还存在这样一个问题：即怎样去而，现在还存在这样一个问题：即怎样去选择剩下的那个未发生变异的节点呢？选择剩下的那个未发生变异的节点呢？nBerg等考虑了一个最简单的例子去反映边等考虑了一个最简单的例子去反映边的失去，并且给出了失去边的速度为的失去，并且给出了失去边的速度为dk,k(1/k+1/k)，即度小的节点之间更容，即度小的节点之间更容易发生边的失去。易发生边的失去。n这种特殊的机制也同样运用于其他研究中。这种特殊的机制也同样运用于其他研究中。n例如，例如，Shi等提出了一个反偏爱的删除机制，等提出了一个反偏爱的删除机制，在每一个时间步长，在每一个时间步长，T0条已存在的连接将条已存在的连接将按照下列方式删除：第按照下列方式删除：第i个节点首先以偏爱个节点首先以偏爱概率概率（ki）被选择）被选择.ppkikik11)(n然后从然后从i的邻居中（定义为的邻居中（定义为O（i）以概率）以概率P(kj)选择节点选择节点j。)()()()(iOqqkjkjkPn两个节点两个节点i和和j之间的连接将被删除，重复这之间的连接将被删除，重复这个过程个过程T0次。次。练习题练习题n下列网络依据