进化论构建网络的方法.pptx

分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 1回顾n小世界网络模型nBA无标度网络模型及其构造n生物分子网络特征分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 21.小世界网络模型nWS小世界模型构造算法如下：1.从规则图开始：考虑一个含有N个点的最近邻耦合网络，它们围成一个环，其中每个节点都与它左右的各K/2节点相连，K是偶数。2.随机化重连：以概率P随机地重新连接网络中的每个边，即将边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点。其中规定，任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 31.小世界网络模型nNW小世界模型构造算法：n1.从规则图开始：考虑一个含有N个点的最近邻耦合网络，它们围成一个环，其中每个节点都与它左右相邻的各k/2个节点相连，k是偶数。n2.随机化加边：以概率P在随机选取的一对节点之间加上一条边。其中，任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 4nBA无标度网络的构造：基于网络的增长和优先连接特性，BA无标度网络模型的构造算法如下：1.增长：从一个具有m0个节点的网络开始，每次引入一个新的节点，并且连到m个已存在的节点上，这里mm0；2.BA无标度网络分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 5nBA无标度网络的构造：2.优先连接：一个新节点与一个已经存在的节点i相连接的概率i与节点i的度为ki、节点j的度Kj之间满足如下关系（所有节点的度之和之间满足关系）：2.BA无标度网络分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 6n经过t步后，该算法程序产生一具有N=t+m0个节点，mt条边的网络。例例:m0=3,m=2t=1t=2t=32.BA无标度网络分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 73.生物网络特征n生物分子网络具有稀疏性n生物分子网络具scale-free性质n生物分子网络具有超小世界性n生物分子网络具有层次结构n生物分子网络具有度的负关联性n生物分子网络具有一定的鲁棒性和适应性分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 8主要内容n10.1 随机复制模型n10.2 偏爱复制模型n10.3 节点删除变异模型n10.4 删边变异模型分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 9引言n众所周知，从自然选择和生物进化来看，复制和变异是生物分子网络进化的内在基本机制。n近几年来，不少研究者提出了各种不同的基于复制变异准则的生物网络构建模型，这里我们简称为DD模型。分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 10引言n以生物进化论作为理论基础，按照一些基本生物实验和观察的事实为依据，在复制和变异过程中提出一些原则，从而设法构造出具有度负关联性的生物分子网络模型，解决网络中度负相关性产生的生物学机制，希望为生物分子网络构建的一般方法提供一些有用的启示。n首先考虑复制对度负关联性的影响。分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 1110.1随机复制模型n1.初始化：给定单连接的具有n0个节点的初始网络G0；n2.每一个时间步长，随机选取一个节点进行复制，也就是说，新的复制节点将与原来的被复制节点的邻居相连。n这个过程一直进行下去，直到网络到达预期规模N个节点。分子生物网络分析分子生物网络分析Molecular Biology Network Analysis)Page 12练习题n如下图所示网络，依据随机复杂模型进行时间步长为T=8，即N=16，得到的新的网络，给网络的度分布图。DEGCFABH分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 1310.1随机复制模型图图10.1随机复制模型的随机复制模型的rk关系图关系图（k是网络节点数，是网络节点数，r是是Pearson关联系数）关联系数）A：r0=-0.0068，N=3000B：r0=-0.0182，N=3000分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 1410.1随机复制模型n如下图所示，给出了网络节点数k和pearson关联系数r的关系。两个初始网络是中性的，节点数目都为n0=100，初始关联系数分别为r0=-0.0068和r0=-0.0182，最后的网络规模为N=3000.n由于网络的生成是具有随机性质的，因此图中每一点都是通过100个网络取平均值得到。从结果明显可以看出随机复制能够产生生物分子网络的度负关联性。分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 1510.1随机复制模型n解释：由于生物网络是幂率分布，度大的节点远远小于度小的节点，因此，假设a是度大的节点那么bcd是a的邻居，节点bcd中度小的占绝大多数，通过一次复制那么a要么它的一个度小的邻居（不失一般性，假定d）被复制，因此就会产生如图（a）和（b）所示的两种情况。n注意到度大的节点占少数，a被复制的概率要比被它的一个度小的邻居复制的概率小很多，因此一次复制以后(b)的情况更容易出现，它更具有度的负关联性。n因此，经过一定时间步长以后，网络更可能朝着负关联网络方向发展。分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 1610.2偏爱复制模型n基于增长和偏爱的准则（度大的节点更容易获得新边），1999年Barabasi与Albert提出了著名的BA模型。n有研究者基于生物实际的考虑提出偏爱复制模型。n事实上，在蛋白质相互作用网络中，度大的蛋白质对应的基因序列也更长。分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 1710.2偏爱复制模型n合理地认为相同长度的基因序列被复制的概率相等，度大的蛋白质更难被复制。n因此有理由假定上述随机复制模型中的复制具有某种偏爱性质，于是得到偏爱复制模型。分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 1810.2偏爱复制模型n1.初始化：给定初始网络G0（假设初始网络是连通的）n2.网络在每一时间步长按如下步骤更新：对于t-1时刻的网络Gt-1节点i以概率P(ki)进行复制，其中ki是节点i的度，记复制节点为i，即将i连接到i的所有邻居上。n以后每一时间单位都按照以上步骤进行更新，直到网络的规模达到预期的规模。分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 19练习题n依据偏爱复制模型，对下图表示的网络进行T=8次的复制后得到新的网络，给网络的度分布图。图图DEGCFABH分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 2010.2偏爱复制模型分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 2110.2偏爱复制模型分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 2210.2偏爱复制模型n从图10.4和10.5中，很容易怎出随机网络节点数目k增大而r减小。n相比于随机复制模型而言，偏爱复制模型的r减小得更快一些。n也就是说，两种复制机制都能导致网络度负关联性质，偏爱复制模型比随机复制模型能够进一步加强这种负关联性网络更容易朝着负关联网络演化。分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 23复制模型n从上述讨论中，很容易看到：n复制能够使得网络朝着负关联网络发展，偏爱模型会加强这种变化趋势。n因此，从生物进化的角度来看，复制是生物网络产生度负关联性的一种机制。分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 24复制模型n在上面的复制模型中，只考虑复制而忽略变异是为了更好地弄清楚复制对生物分子网络度负关联性的内在本质。n事实上，生物分子网络是复制和变异这两个进化机制共同作用的结果，因此，应当进一步研究变异对度负关联性的影响。分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 25变异模型n在真实网络的进化过程中，存在着以下两个基本的生物变异过程。n1.删除节点：当一个基因发生功能缺失变异时，会发生节点删除；n2.边的变化：新的边会产生，已经存在的边会删除或者重组，这些变化都是由于生物分子编码序列的变异造成的。分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 2610.3节点删除变异模型n从生物层面上来讲，有害的变异会导致基因的毁灭。一旦基因变成非功能性基因，它所调控的蛋白也就与之不相关了。n在蛋白质网络的进化过程中，通过复制产生的大多数蛋白被当作冗余被丢弃，这在生物网络上反映为节点删除。分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 2710.3节点删除变异模型n为了模拟这个变异过程，考虑两种节点删除变异的方式：n随机移除蛋白（和它的相互连接）n偏爱移除蛋白（和它的相互连接）分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 2810.3节点删除变异模型n随机节点删除变异模型n1.初始化：给定单连通的具有N个节点的初始网络G0，G0是由BA模型生成的中性网络，即初始关联系数r接近于零。这样，G0是无标度的，网络中度小的节点占大多数；分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 2910.3节点删除变异模型n随机节点删除变异模型n2.网络在每一时间步长，随机选取一个节点，删除它及其他所有连接。若产生孤立节点，删除它，相当于本次操作失败，这对生物网络中不起作用的蛋白质降解。n这个过程一直进行下去直到网络经过T个时间长。分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 30练习题n下列网络依据随机节点删除模式经过时间步长为T=4，得到新网络，并给出网络的度分布图。ACBHFGDKEJI分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 3110.3节点删除变异模型n事实上，研究表明，拥有越多连接的蛋白进化速度越慢。n在蛋白相互作用的网络中，具有最多连接的蛋白在存活时间上是具有较少的连接蛋白的三倍，这些蛋白是更多效的、进化更慢的，更不容易在进化时被移除。n另外，度小的节点在网络中确实更容易被删除。特别地，保守性好的蛋白的度与它的进化速度是成反比的。分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 3210.3节点删除变异模型n因此，可以认为节点删除变异的过程确实包含偏爱性，从而可以给出如下偏爱节点删除变异模型：n1.初始化（同随机节点删除变异模型）；n2.网络在每一个时间步长，度为ki的节点i以概率pi被选择删除及其连的边，若产生孤立节点，删除它；n这个过程一直进行下去，直到网络经过T个时间步长。分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 33练习题n下列网络依据偏爱节点删除变异模型经过时间步长为T=4，请给出新网络及网络的度分布图。ACBHFGDKEJI分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 3410.3节点删除变异模型分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 3510.3节点删除变异模型分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 3610.3节点删除变异模型n在两个图中关联系数r都随着时间步长的增大而稍微下降，或者说，在一定的时间步长内，随机删除节点和偏爱删除节点对网络的度负关联性是没有太大影响的。n事实上，由于初始网络为无标度网络，即初始网络中度小的节点占大多数，所以在选择节点的时候，无论是随机还是偏爱，都是容易选择度小的节点。分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 3710.3节点删除变异模型n再者，由于初始网络为中性网络，即无关联网络，对于一个度小的节点来说，它的邻居中度大的节点与度小的节点的比例是几乎相同的，所以大节点的边（简称小-大）的概率是大致相同的，这样在一定的时间步长内，随机删除节点和偏爱删除节点会使得关联系数r有略微的减小，但并不会强烈影响网络的度负关联性。分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 3810.4删边变异模型n引起边的变异的生物机制在本质上非对称的，即当一条边发生编译时，其中只有一个节点发生变异，另一个节点保持不变。这种非对称性意味着边变异的速率会同时决定于发生变异的节点和未发生变异的节点的度。分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 3910.4删边变异模型n随机删边变异模型：n1.初始化（同随机节点删除变异模型）；n2.网络在每一个时间步长，随机选择一个节点i作为变异节点，再从i的邻居中随机选择节点j（节点j不发生变异），删去连接i和j的边Lij，若产生孤立节点，删除它。n这个过程一直进行下去，直到网络经过T个时间步长。分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 40练习题n下列网络依据随机删边变异模型，经过时间步长为T=4，给出新网络及网络的度分布图。ACBHFGDKEJI分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 4110.4删边变异模型n根据生物大分子的保守性和边变异的非对称性，选择度小的节点作为变异节点，然而，现在还存在这样一个问题：即怎样去选择剩下的那个未发生变异的节点呢？nBerg等考虑了一个最简单的例子去反映边的失去，并且给出了失去边的速度为dk,k(1/k+1/k)，即度小的节点之间更容易发生边的失去。分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 4210.4删边变异模型n这种特殊的机制也同样运用于其他研究中。n例如，Shi等提出了一个反偏爱的删除机制，在每一个时间步长，T0条已存在的连接将按照下列方式删除：第i个节点首先以偏爱概率（ki）被选择.分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 4310.4删边变异模型n然后从i的邻居中（定义为O（i）以概率P(kj)选择节点j。n两个节点i和j之间的连接将被删除，重复这个过程T0次。分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 44练习题n下列网络依据反偏爱删边变异机制，经过时间步长为T=4，给出新网络及网络的度分布图。ACBHFGDKEJI分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 4510.4删边变异模型n这里可以注意到概率P（kj）是全局的，而事实上边的变异是局部的过程，所以对此进行修正，并给出了偏爱删边变异模型。分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 4610.4删边变异模型n偏爱删边变异模型。n1.初始化（同随机节点删除变异模型）n2.网络在每一个时间步长，度为ki的节点i以偏爱概率（ki）选择成为变异节点，随后再从i的邻居中以偏爱概率P*（kj）选择节点j(节点j不发生变异)，删去连接i到j的边Lij，若产生孤立节点，删除它。n这个过程一直进行下去直到网络经过T时间步长。分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 47练习题n下列网络依据偏爱删边变异模型，经过时间步长为T=4，给出新网络及网络的度分布图。ACBHFGDKEJI分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 4810.4删边变异模型分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 4910.4删边变异模型分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 5010.4删边变异模型n很容易看到在两种情况下关联系数r都随着时间步长t的增大而减小，相对于随机删除边变异模型而言，偏爱删边变异模型中的关联系数r减少得更快。n这两种删除机制都能产生负关联性，而偏爱删边机制比随机删边机制更能加强这种负关联性。分子生物网络分析分子生物网络分析(Molecular Biology Network Analysis)Page 5110.4删边变异模型n事实上，这很容易解释，对于随机删边机制，由于初始网络是中性的，两次随机选择的节点就容易是度小的节点，这样大-小在网络中所占的比例会变大。n所以，经过一定的时间步长后，网络会逐渐演化成一个负关联的网络。