進化論構(gòu)建網(wǎng)絡(luò)的方法和模型研究

1、進化論構(gòu)建網(wǎng)絡(luò)的方法和模型研究回顧小世界網(wǎng)絡(luò)模型BA無標度網(wǎng)絡(luò)模型及其構(gòu)造分子網(wǎng)絡(luò)特征1.小世界網(wǎng)絡(luò)模型WS小世界模型構(gòu)造算法如下：1.從規(guī)則圖開始：考慮一個含有N個點的最近鄰耦合網(wǎng)絡(luò)，它們圍成一個環(huán)，其中每個節(jié)點都與它左右的各K/2節(jié)點相連，K是偶數(shù)。：以概率P隨機地重新連接網(wǎng)絡(luò)中的每個邊，即將邊的一個端點保持不變，而另一個端點取為網(wǎng)絡(luò)中隨機選擇的一個節(jié)點。其中規(guī)定，任意兩個不同的節(jié)點之間至多只能有一條邊，并且每一個節(jié)點都不能有邊與自身相連。1.小世界網(wǎng)絡(luò)模型NW小世界模型構(gòu)造算法：考慮一個含有N個點的最近鄰耦合網(wǎng)絡(luò)，它們圍成一個環(huán)，其中每個節(jié)點都與它左右相鄰的各k/2個節(jié)點相連，k是偶數(shù)。

2、：以概率P在隨機選取的一對節(jié)點之間加上一條邊。其中，任意兩個不同的節(jié)點之間至多只能有一條邊，并且每一個節(jié)點都不能有邊與自身相連。BA無標度網(wǎng)絡(luò)的構(gòu)造： 基于網(wǎng)絡(luò)的增長和優(yōu)先連接特性，BA無標度網(wǎng)絡(luò)模型的構(gòu)造算法如下：1.增長：從一個具有m0個節(jié)點的網(wǎng)絡(luò)開始，每次引入一個新的節(jié)點，并且連到m個已存在的節(jié)點上，這里mm0；2.BA無標度網(wǎng)絡(luò)BA無標度網(wǎng)絡(luò)的構(gòu)造：2.優(yōu)先連接：一個新節(jié)點與一個已經(jīng)存在的節(jié)點i相連接的概率i與節(jié)點i的度為ki、節(jié)點j的度Kj之間滿足如下關(guān)系（所有節(jié)點的度之和之間滿足關(guān)系）：2.BA無標度網(wǎng)絡(luò)經(jīng)過t步后，該算法程序產(chǎn)生一具有N=t+m0個節(jié)點，mt條邊的網(wǎng)絡(luò)。例: m0

3、 = 3, m = 2t = 1t = 2t = 32.BA無標度網(wǎng)絡(luò)3.生物網(wǎng)絡(luò)特征生物分子網(wǎng)絡(luò)具有稀疏性生物分子網(wǎng)絡(luò)具scale-free性質(zhì)生物分子網(wǎng)絡(luò)具有超小世界性生物分子網(wǎng)絡(luò)具有層次結(jié)構(gòu)生物分子網(wǎng)絡(luò)具有度的負關(guān)聯(lián)性生物分子網(wǎng)絡(luò)具有一定的魯棒性和適應(yīng)性主要內(nèi)容10.1 隨機復(fù)制模型10.2 偏愛復(fù)制模型10.3 節(jié)點刪除變異模型10.4 刪邊變異模型引言眾所周知，從自然選擇和生物進化來看，復(fù)制和變異是生物分子網(wǎng)絡(luò)進化的內(nèi)在基本機制。近幾年來，不少研究者提出了各種不同的基于復(fù)制變異準則的生物網(wǎng)絡(luò)構(gòu)建模型，這里我們簡稱為DD模型。引言以生物進化論作為理論基礎(chǔ)，按照一些基本生物實驗和觀察的事

4、實為依據(jù)，在復(fù)制和變異過程中提出一些原則，從而設(shè)法構(gòu)造出具有度負關(guān)聯(lián)性的生物分子網(wǎng)絡(luò)模型，解決網(wǎng)絡(luò)中度負相關(guān)性產(chǎn)生的生物學機制，希望為生物分子網(wǎng)絡(luò)構(gòu)建的一般方法提供一些有用的啟示。首先考慮復(fù)制對度負關(guān)聯(lián)性的影響。隨機復(fù)制模型：給定單連接的具有n0個節(jié)點的初始網(wǎng)絡(luò)G0；，隨機選取一個節(jié)點進行復(fù)制，也就是說，新的復(fù)制節(jié)點將與原來的被復(fù)制節(jié)點的鄰居相連。這個過程一直進行下去，直到網(wǎng)絡(luò)到達預(yù)期規(guī)模N個節(jié)點。練習題如下圖所示網(wǎng)絡(luò)，依據(jù)隨機復(fù)雜模型進行時間步長為T=8，即N=16，得到的新的網(wǎng)絡(luò)，給網(wǎng)絡(luò)的度分布圖。DEGCFABH隨機復(fù)制模型圖10.1隨機復(fù)制模型的rk關(guān)系圖（k是網(wǎng)絡(luò)節(jié)點數(shù)，r是Pear

5、son關(guān)聯(lián)系數(shù)）A：r0=-0.0068，N=3000B：r0=-0.0182，N=3000隨機復(fù)制模型如下圖所示，給出了網(wǎng)絡(luò)節(jié)點數(shù)k和pearson關(guān)聯(lián)系數(shù)r的關(guān)系。兩個初始網(wǎng)絡(luò)是中性的，節(jié)點數(shù)目都為n0=100，初始關(guān)聯(lián)系數(shù)分別為r00=-0.0182，最后的網(wǎng)絡(luò)規(guī)模為N=3000.由于網(wǎng)絡(luò)的生成是具有隨機性質(zhì)的，因此圖中每一點都是通過100個網(wǎng)絡(luò)取平均值得到。從結(jié)果明顯可以看出隨機復(fù)制能夠產(chǎn)生生物分子網(wǎng)絡(luò)的度負關(guān)聯(lián)性。隨機復(fù)制模型解釋：由于生物網(wǎng)絡(luò)是冪率分布，度大的節(jié)點遠遠小于度小的節(jié)點，因此，假設(shè)a是度大的節(jié)點那么bcd是a的鄰居，節(jié)點bcd中度小的占絕大多數(shù)，通過一次復(fù)制那么a要么它

6、的一個度小的鄰居（不失一般性，假定d）被復(fù)制，因此就會產(chǎn)生如圖（a）和（b）所示的兩種情況。注意到度大的節(jié)點占少數(shù)，a被復(fù)制的概率要比被它的一個度小的鄰居復(fù)制的概率小很多，因此一次復(fù)制以后(b)的情況更容易出現(xiàn)，它更具有度的負關(guān)聯(lián)性。因此，經(jīng)過一定時間步長以后，網(wǎng)絡(luò)更可能朝著負關(guān)聯(lián)網(wǎng)絡(luò)方向發(fā)展。偏愛復(fù)制模型基于增長和偏愛的準則（度大的節(jié)點更容易獲得新邊），1999年Barabasi與Albert提出了著名的BA模型。有研究者基于生物實際的考慮提出偏愛復(fù)制模型。事實上，在蛋白質(zhì)相互作用網(wǎng)絡(luò)中，度大的蛋白質(zhì)對應(yīng)的基因序列也更長。偏愛復(fù)制模型合理地認為相同長度的基因序列被復(fù)制的概率相等，度大的蛋白質(zhì)

7、更難被復(fù)制。因此有理由假定上述隨機復(fù)制模型中的復(fù)制具有某種偏愛性質(zhì)，于是得到偏愛復(fù)制模型。偏愛復(fù)制模型1.初始化：給定初始網(wǎng)絡(luò)G0（假設(shè)初始網(wǎng)絡(luò)是連通的）：對于t-1時刻的網(wǎng)絡(luò)Gt-1節(jié)點i以概率P(ki)進行復(fù)制，其中ki是節(jié)點i的度，記復(fù)制節(jié)點為i，即將i連接到i的所有鄰居上。以后每一時間單位都按照以上步驟進行更新，直到網(wǎng)絡(luò)的規(guī)模達到預(yù)期的規(guī)模。練習題依據(jù)偏愛復(fù)制模型，對下圖表示的網(wǎng)絡(luò)進行T=8次的復(fù)制后得到新的網(wǎng)絡(luò)，給網(wǎng)絡(luò)的度分布圖。圖DEGCFABH偏愛復(fù)制模型偏愛復(fù)制模型偏愛復(fù)制模型從圖10.4和10.5中，很容易怎出隨機網(wǎng)絡(luò)節(jié)點數(shù)目k增大而r減小。相比于隨機復(fù)制模型而言，偏愛復(fù)制模

8、型的r減小得更快一些。也就是說，兩種復(fù)制機制都能導致網(wǎng)絡(luò)度負關(guān)聯(lián)性質(zhì)，偏愛復(fù)制模型比隨機復(fù)制模型能夠進一步加強這種負關(guān)聯(lián)性，網(wǎng)絡(luò)更容易朝著負關(guān)聯(lián)網(wǎng)絡(luò)演化。復(fù)制模型從上述討論中，很容易看到：復(fù)制能夠使得網(wǎng)絡(luò)朝著負關(guān)聯(lián)網(wǎng)絡(luò)發(fā)展，偏愛模型會加強這種變化趨勢。因此，從生物進化的角度來看，復(fù)制是生物網(wǎng)絡(luò)產(chǎn)生度負關(guān)聯(lián)性的一種機制。復(fù)制模型在上面的復(fù)制模型中，只考慮復(fù)制而忽略變異是為了更好地弄清楚復(fù)制對生物分子網(wǎng)絡(luò)度負關(guān)聯(lián)性的內(nèi)在本質(zhì)。事實上，生物分子網(wǎng)絡(luò)是復(fù)制和變異這兩個進化機制共同作用的結(jié)果，因此，應(yīng)當進一步研究變異對度負關(guān)聯(lián)性的影響。變異模型在真實網(wǎng)絡(luò)的進化過程中，存在著以下兩個基本的生物變異過程。：

9、當一個基因發(fā)生功能缺失變異時，會發(fā)生節(jié)點刪除；：新的邊會產(chǎn)生，已經(jīng)存在的邊會刪除或者重組，這些變化都是由于生物分子編碼序列的變異造成的。節(jié)點刪除變異模型從生物層面上來講，有害的變異會導致基因的毀滅。一旦基因變成非功能性基因，它所調(diào)控的蛋白也就與之不相關(guān)了。在蛋白質(zhì)網(wǎng)絡(luò)的進化過程中，通過復(fù)制產(chǎn)生的大多數(shù)蛋白被當作冗余被丟棄，這在生物網(wǎng)絡(luò)上反映為節(jié)點刪除。節(jié)點刪除變異模型為了模擬這個變異過程，考慮兩種節(jié)點刪除變異的方式：隨機移除蛋白（和它的相互連接）偏愛移除蛋白（和它的相互連接）節(jié)點刪除變異模型隨機節(jié)點刪除變異模型1.初始化：給定單連通的具有N個節(jié)點的初始網(wǎng)絡(luò)G0，G0是由BA模型生成的中性網(wǎng)絡(luò)，

10、即初始關(guān)聯(lián)系數(shù)r接近于零。這樣，G0是無標度的，網(wǎng)絡(luò)中度小的節(jié)點占大多數(shù)；節(jié)點刪除變異模型隨機節(jié)點刪除變異模型2.網(wǎng)絡(luò)在每一時間步長，隨機選取一個節(jié)點，刪除它及其他所有連接。若產(chǎn)生孤立節(jié)點，刪除它，相當于本次操作失敗，這對生物網(wǎng)絡(luò)中不起作用的蛋白質(zhì)降解。這個過程一直進行下去直到網(wǎng)絡(luò)經(jīng)過T個時間長。練習題下列網(wǎng)絡(luò)依據(jù)隨機節(jié)點刪除模式經(jīng)過時間步長為T=4，得到新網(wǎng)絡(luò)，并給出網(wǎng)絡(luò)的度分布圖。ACBHFGDKEJI節(jié)點刪除變異模型事實上，研究表明，擁有越多連接的蛋白進化速度越慢。在蛋白相互作用的網(wǎng)絡(luò)中，具有最多連接的蛋白在存活時間上是具有較少的連接蛋白的三倍，這些蛋白是更多效的、進化更慢的，更不容易在

11、進化時被移除。另外，度小的節(jié)點在網(wǎng)絡(luò)中確實更容易被刪除。特別地，保守性好的蛋白的度與它的進化速度是成反比的。節(jié)點刪除變異模型因此，可以認為節(jié)點刪除變異的過程確實包含偏愛性，從而可以給出如下偏愛節(jié)點刪除變異模型：1.初始化（同隨機節(jié)點刪除變異模型）；2.網(wǎng)絡(luò)在每一個時間步長，度為ki的節(jié)點i以概率pi被選擇刪除及其連的邊，若產(chǎn)生孤立節(jié)點，刪除它；這個過程一直進行下去，直到網(wǎng)絡(luò)經(jīng)過T個時間步長。練習題下列網(wǎng)絡(luò)依據(jù)偏愛節(jié)點刪除變異模型經(jīng)過時間步長為T=4，請給出新網(wǎng)絡(luò)及網(wǎng)絡(luò)的度分布圖。ACBHFGDKEJI節(jié)點刪除變異模型節(jié)點刪除變異模型節(jié)點刪除變異模型在兩個圖中關(guān)聯(lián)系數(shù)r都隨著時間步長的增大而稍微

12、下降，或者說，在一定的時間步長內(nèi)，隨機刪除節(jié)點和偏愛刪除節(jié)點對網(wǎng)絡(luò)的度負關(guān)聯(lián)性是沒有太大影響的。事實上，由于初始網(wǎng)絡(luò)為無標度網(wǎng)絡(luò)，即初始網(wǎng)絡(luò)中度小的節(jié)點占大多數(shù)，所以在選擇節(jié)點的時候，無論是隨機還是偏愛，都是容易選擇度小的節(jié)點。節(jié)點刪除變異模型再者，由于初始網(wǎng)絡(luò)為中性網(wǎng)絡(luò)，即無關(guān)聯(lián)網(wǎng)絡(luò)，對于一個度小的節(jié)點來說，它的鄰居中度大的節(jié)點與度小的節(jié)點的比例是幾乎相同的，所以大節(jié)點的邊（簡稱小-大）的概率是大致相同的，這樣在一定的時間步長內(nèi)，隨機刪除節(jié)點和偏愛刪除節(jié)點會使得關(guān)聯(lián)系數(shù)r有略微的減小，但并不會強烈影響網(wǎng)絡(luò)的度負關(guān)聯(lián)性。刪邊變異模型引起邊的變異的生物機制在本質(zhì)上非對稱的，即當一條邊發(fā)生編譯時，

13、其中只有一個節(jié)點發(fā)生變異，另一個節(jié)點保持不變。這種非對稱性意味著邊變異的速率會同時決定于發(fā)生變異的節(jié)點和未發(fā)生變異的節(jié)點的度。刪邊變異模型隨機刪邊變異模型：1.初始化（同隨機節(jié)點刪除變異模型）；，隨機選擇一個節(jié)點i作為變異節(jié)點，再從i的鄰居中隨機選擇節(jié)點j（節(jié)點j不發(fā)生變異），刪去連接i和j的邊Lij，若產(chǎn)生孤立節(jié)點，刪除它。這個過程一直進行下去，直到網(wǎng)絡(luò)經(jīng)過T個時間步長。練習題下列網(wǎng)絡(luò)依據(jù)隨機刪邊變異模型，經(jīng)過時間步長為T=4，給出新網(wǎng)絡(luò)及網(wǎng)絡(luò)的度分布圖。ACBHFGDKEJI刪邊變異模型根據(jù)生物大分子的保守性和邊變異的非對稱性，選擇度小的節(jié)點作為變異節(jié)點，然而，現(xiàn)在還存在這樣一個問題：即怎

14、樣去選擇剩下的那個未發(fā)生變異的節(jié)點呢？Berg等考慮了一個最簡單的例子去反映邊的失去，并且給出了失去邊的速度為dk,k(1/k+1/k)，即度小的節(jié)點之間更容易發(fā)生邊的失去。刪邊變異模型這種特殊的機制也同樣運用于其他研究中。例如，Shi等提出了一個反偏愛的刪除機制，在每一個時間步長，T0條已存在的連接將按照下列方式刪除：第i個節(jié)點首先以偏愛概率（ki）被選擇.刪邊變異模型然后從i的鄰居中（定義為O（i）以概率P(kj)選擇節(jié)點j。兩個節(jié)點i和j之間的連接將被刪除，重復(fù)這個過程T0次。練習題下列網(wǎng)絡(luò)依據(jù)反偏愛刪邊變異機制，經(jīng)過時間步長為T=4，給出新網(wǎng)絡(luò)及網(wǎng)絡(luò)的度分布圖。ACBHFGDKEJI刪邊變異模型這里可以注意到概率P（kj）是全局的，而事實上邊的變異是局部的過程，所以對此進行修正，并給出了偏愛刪邊變異模型。刪邊變異模型偏愛刪邊變異模型。1.初始化（同隨機節(jié)點刪除變異模型）2.網(wǎng)絡(luò)在每一個時間步長，度為ki的節(jié)點i以偏愛概率（ki）選擇成為變異節(jié)點，隨后再從i的鄰居中以偏愛概率P*（kj）選擇節(jié)點j(節(jié)點j不發(fā)生變異