進(jìn)化論構(gòu)建網(wǎng)絡(luò)的方法

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

基于網(wǎng)絡(luò)的增長和優(yōu)先連接特性，BA無標(biāo)度網(wǎng)絡(luò)模型的構(gòu)造算法如下：1.增長：從一個具有m0個節(jié)點(diǎn)的網(wǎng)絡(luò)開始，每次引入一個新的節(jié)點(diǎn)，并且連到m個已存在的節(jié)點(diǎn)上，這里m≤m0；2.BA無標(biāo)度網(wǎng)絡(luò)第五頁，共五十二頁，編輯于2023年，星期二BA無標(biāo)度網(wǎng)絡(luò)的構(gòu)造：2.優(yōu)先連接：一個新節(jié)點(diǎn)與一個已經(jīng)存在的節(jié)點(diǎn)i相連接的概率Πi與節(jié)點(diǎn)i的度為ki、節(jié)點(diǎn)j的度Kj之間滿足如下關(guān)系（所有節(jié)點(diǎn)的度之和之間滿足關(guān)系）：2.BA無標(biāo)度網(wǎng)絡(luò)第六頁，共五十二頁，編輯于2023年，星期二經(jīng)過t步后，該算法程序產(chǎn)生一具有N=t+m0個節(jié)點(diǎn)，mt條邊的網(wǎng)絡(luò)。例:m0=3,m=2t=1t=2t=32.BA無標(biāo)度網(wǎng)絡(luò)第七頁，共五十二頁，編輯于2023年，星期二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ò)具有度的負(fù)關(guān)聯(lián)性生物分子網(wǎng)絡(luò)具有一定的魯棒性和適應(yīng)性第八頁，共五十二頁，編輯于2023年，星期二主要內(nèi)容10.1隨機(jī)復(fù)制模型10.2偏愛復(fù)制模型10.3節(jié)點(diǎn)刪除變異模型10.4刪邊變異模型第九頁，共五十二頁，編輯于2023年，星期二引言眾所周知，從自然選擇和生物進(jìn)化來看，復(fù)制和變異是生物分子網(wǎng)絡(luò)進(jìn)化的內(nèi)在基本機(jī)制。近幾年來，不少研究者提出了各種不同的基于復(fù)制變異準(zhǔn)則的生物網(wǎng)絡(luò)構(gòu)建模型，這里我們簡稱為DD模型。第十頁，共五十二頁，編輯于2023年，星期二引言以生物進(jìn)化論作為理論基礎(chǔ)，按照一些基本生物實(shí)驗(yàn)和觀察的事實(shí)為依據(jù)，在復(fù)制和變異過程中提出一些原則，從而設(shè)法構(gòu)造出具有度負(fù)關(guān)聯(lián)性的生物分子網(wǎng)絡(luò)模型，解決網(wǎng)絡(luò)中度負(fù)相關(guān)性產(chǎn)生的生物學(xué)機(jī)制，希望為生物分子網(wǎng)絡(luò)構(gòu)建的一般方法提供一些有用的啟示。首先考慮復(fù)制對度負(fù)關(guān)聯(lián)性的影響。第十一頁，共五十二頁，編輯于2023年，星期二10.1隨機(jī)復(fù)制模型1.初始化：給定單連接的具有n0個節(jié)點(diǎn)的初始網(wǎng)絡(luò)G0；2.每一個時間步長，隨機(jī)選取一個節(jié)點(diǎn)進(jìn)行復(fù)制，也就是說，新的復(fù)制節(jié)點(diǎn)將與原來的被復(fù)制節(jié)點(diǎn)的鄰居相連。這個過程一直進(jìn)行下去，直到網(wǎng)絡(luò)到達(dá)預(yù)期規(guī)模N個節(jié)點(diǎn)。第十二頁，共五十二頁，編輯于2023年，星期二練習(xí)題如下圖所示網(wǎng)絡(luò)，依據(jù)隨機(jī)復(fù)雜模型進(jìn)行時間步長為T=8，即N=16，得到的新的網(wǎng)絡(luò)，給網(wǎng)絡(luò)的度分布圖。DEGCFABH第十三頁，共五十二頁，編輯于2023年，星期二10.1隨機(jī)復(fù)制模型圖10.1隨機(jī)復(fù)制模型的r~k關(guān)系圖（k是網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)，r是Pearson關(guān)聯(lián)系數(shù)）A：r0=-0.0068，N=3000B：r0=-0.0182，N=3000第十四頁，共五十二頁，編輯于2023年，星期二10.1隨機(jī)復(fù)制模型如下圖所示，給出了網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)k和pearson關(guān)聯(lián)系數(shù)r的關(guān)系。兩個初始網(wǎng)絡(luò)是中性的，節(jié)點(diǎn)數(shù)目都為n0=100，初始關(guān)聯(lián)系數(shù)分別為r0=-0.0068和r0=-0.0182，最后的網(wǎng)絡(luò)規(guī)模為N=3000.由于網(wǎng)絡(luò)的生成是具有隨機(jī)性質(zhì)的，因此圖中每一點(diǎn)都是通過100個網(wǎng)絡(luò)取平均值得到。從結(jié)果明顯可以看出隨機(jī)復(fù)制能夠產(chǎn)生生物分子網(wǎng)絡(luò)的度負(fù)關(guān)聯(lián)性。第十五頁，共五十二頁，編輯于2023年，星期二10.1隨機(jī)復(fù)制模型解釋：由于生物網(wǎng)絡(luò)是冪率分布，度大的節(jié)點(diǎn)遠(yuǎn)遠(yuǎn)小于度小的節(jié)點(diǎn)，因此，假設(shè)a是度大的節(jié)點(diǎn)那么bcd是a的鄰居，節(jié)點(diǎn)bcd中度小的占絕大多數(shù)，通過一次復(fù)制那么a要么它的一個度小的鄰居（不失一般性，假定d）被復(fù)制，因此就會產(chǎn)生如圖（a）和（b）所示的兩種情況。注意到度大的節(jié)點(diǎn)占少數(shù)，a被復(fù)制的概率要比被它的一個度小的鄰居復(fù)制的概率小很多，因此一次復(fù)制以后(b)的情況更容易出現(xiàn)，它更具有度的負(fù)關(guān)聯(lián)性。因此，經(jīng)過一定時間步長以后，網(wǎng)絡(luò)更可能朝著負(fù)關(guān)聯(lián)網(wǎng)絡(luò)方向發(fā)展。第十六頁，共五十二頁，編輯于2023年，星期二10.2偏愛復(fù)制模型基于增長和偏愛的準(zhǔn)則（度大的節(jié)點(diǎn)更容易獲得新邊），1999年Barabasi與Albert提出了著名的BA模型。有研究者基于生物實(shí)際的考慮提出偏愛復(fù)制模型。事實(shí)上，在蛋白質(zhì)相互作用網(wǎng)絡(luò)中，度大的蛋白質(zhì)對應(yīng)的基因序列也更長。第十七頁，共五十二頁，編輯于2023年，星期二10.2偏愛復(fù)制模型合理地認(rèn)為相同長度的基因序列被復(fù)制的概率相等，度大的蛋白質(zhì)更難被復(fù)制。因此有理由假定上述隨機(jī)復(fù)制模型中的復(fù)制具有某種偏愛性質(zhì)，于是得到偏愛復(fù)制模型。第十八頁，共五十二頁，編輯于2023年，星期二10.2偏愛復(fù)制模型1.初始化：給定初始網(wǎng)絡(luò)G0（假設(shè)初始網(wǎng)絡(luò)是連通的）2.網(wǎng)絡(luò)在每一時間步長按如下步驟更新：對于t-1時刻的網(wǎng)絡(luò)Gt-1節(jié)點(diǎn)i以概率P(ki)進(jìn)行復(fù)制，其中ki是節(jié)點(diǎn)i的度，記復(fù)制節(jié)點(diǎn)為i'，即將i'連接到i的所有鄰居上。以后每一時間單位都按照以上步驟進(jìn)行更新，直到網(wǎng)絡(luò)的規(guī)模達(dá)到預(yù)期的規(guī)模。第十九頁，共五十二頁，編輯于2023年，星期二練習(xí)題依據(jù)偏愛復(fù)制模型，對下圖表示的網(wǎng)絡(luò)進(jìn)行T=8次的復(fù)制后得到新的網(wǎng)絡(luò)，給網(wǎng)絡(luò)的度分布圖。圖DEGCFABH第二十頁，共五十二頁，編輯于2023年，星期二10.2偏愛復(fù)制模型第二十一頁，共五十二頁，編輯于2023年，星期二10.2偏愛復(fù)制模型第二十二頁，共五十二頁，編輯于2023年，星期二10.2偏愛復(fù)制模型從圖10.4和10.5中，很容易怎出隨機(jī)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目k增大而r減小。相比于隨機(jī)復(fù)制模型而言，偏愛復(fù)制模型的r減小得更快一些。也就是說，兩種復(fù)制機(jī)制都能導(dǎo)致網(wǎng)絡(luò)度負(fù)關(guān)聯(lián)性質(zhì)，偏愛復(fù)制模型比隨機(jī)復(fù)制模型能夠進(jìn)一步加強(qiáng)這種負(fù)關(guān)聯(lián)性，網(wǎng)絡(luò)更容易朝著負(fù)關(guān)聯(lián)網(wǎng)絡(luò)演化。第二十三頁，共五十二頁，編輯于2023年，星期二復(fù)制模型從上述討論中，很容易看到：復(fù)制能夠使得網(wǎng)絡(luò)朝著負(fù)關(guān)聯(lián)網(wǎng)絡(luò)發(fā)展，偏愛模型會加強(qiáng)這種變化趨勢。因此，從生物進(jìn)化的角度來看，復(fù)制是生物網(wǎng)絡(luò)產(chǎn)生度負(fù)關(guān)聯(lián)性的一種機(jī)制。第二十四頁，共五十二頁，編輯于2023年，星期二復(fù)制模型在上面的復(fù)制模型中，只考慮復(fù)制而忽略變異是為了更好地弄清楚復(fù)制對生物分子網(wǎng)絡(luò)度負(fù)關(guān)聯(lián)性的內(nèi)在本質(zhì)。事實(shí)上，生物分子網(wǎng)絡(luò)是復(fù)制和變異這兩個進(jìn)化機(jī)制共同作用的結(jié)果，因此，應(yīng)當(dāng)進(jìn)一步研究變異對度負(fù)關(guān)聯(lián)性的影響。第二十五頁，共五十二頁，編輯于2023年，星期二變異模型在真實(shí)網(wǎng)絡(luò)的進(jìn)化過程中，存在著以下兩個基本的生物變異過程。1.刪除節(jié)點(diǎn)：當(dāng)一個基因發(fā)生功能缺失變異時，會發(fā)生節(jié)點(diǎn)刪除；2.邊的變化：新的邊會產(chǎn)生，已經(jīng)存在的邊會刪除或者重組，這些變化都是由于生物分子編碼序列的變異造成的。第二十六頁，共五十二頁，編輯于2023年，星期二10.3節(jié)點(diǎn)刪除變異模型從生物層面上來講，有害的變異會導(dǎo)致基因的毀滅。一旦基因變成非功能性基因，它所調(diào)控的蛋白也就與之不相關(guān)了。在蛋白質(zhì)網(wǎng)絡(luò)的進(jìn)化過程中，通過復(fù)制產(chǎn)生的大多數(shù)蛋白被當(dāng)作冗余被丟棄，這在生物網(wǎng)絡(luò)上反映為節(jié)點(diǎn)刪除。第二十七頁，共五十二頁，編輯于2023年，星期二10.3節(jié)點(diǎn)刪除變異模型為了模擬這個變異過程，考慮兩種節(jié)點(diǎn)刪除變異的方式：隨機(jī)移除蛋白（和它的相互連接）偏愛移除蛋白（和它的相互連接）第二十八頁，共五十二頁，編輯于2023年，星期二10.3節(jié)點(diǎn)刪除變異模型隨機(jī)節(jié)點(diǎn)刪除變異模型1.初始化：給定單連通的具有N個節(jié)點(diǎn)的初始網(wǎng)絡(luò)G0，G0是由BA模型生成的中性網(wǎng)絡(luò)，即初始關(guān)聯(lián)系數(shù)r接近于零。這樣，G0是無標(biāo)度的，網(wǎng)絡(luò)中度小的節(jié)點(diǎn)占大多數(shù)；第二十九頁，共五十二頁，編輯于2023年，星期二10.3節(jié)點(diǎn)刪除變異模型隨機(jī)節(jié)點(diǎn)刪除變異模型2.網(wǎng)絡(luò)在每一時間步長，隨機(jī)選取一個節(jié)點(diǎn)，刪除它及其他所有連接。若產(chǎn)生孤立節(jié)點(diǎn)，刪除它，相當(dāng)于本次操作失敗，這對生物網(wǎng)絡(luò)中不起作用的蛋白質(zhì)降解。這個過程一直進(jìn)行下去直到網(wǎng)絡(luò)經(jīng)過T個時間長。第三十頁，共五十二頁，編輯于2023年，星期二練習(xí)題下列網(wǎng)絡(luò)依據(jù)隨機(jī)節(jié)點(diǎn)刪除模式經(jīng)過時間步長為T=4，得到新網(wǎng)絡(luò)，并給出網(wǎng)絡(luò)的度分布圖。ACBHFGDKEJI第三十一頁，共五十二頁，編輯于2023年，星期二10.3節(jié)點(diǎn)刪除變異模型事實(shí)上，研究表明，擁有越多連接的蛋白進(jìn)化速度越慢。在蛋白相互作用的網(wǎng)絡(luò)中，具有最多連接的蛋白在存活時間上是具有較少的連接蛋白的三倍，這些蛋白是更多效的、進(jìn)化更慢的，更不容易在進(jìn)化時被移除。另外，度小的節(jié)點(diǎn)在網(wǎng)絡(luò)中確實(shí)更容易被刪除。特別地，保守性好的蛋白的度與它的進(jìn)化速度是成反比的。第三十二頁，共五十二頁，編輯于2023年，星期二10.3節(jié)點(diǎn)刪除變異模型因此，可以認(rèn)為節(jié)點(diǎn)刪除變異的過程確實(shí)包含偏愛性，從而可以給出如下偏愛節(jié)點(diǎn)刪除變異模型：1.初始化（同隨機(jī)節(jié)點(diǎn)刪除變異模型）；2.網(wǎng)絡(luò)在每一個時間步長，度為ki的節(jié)點(diǎn)i以概率pi被選擇刪除及其連的邊，若產(chǎn)生孤立節(jié)點(diǎn)，刪除它；這個過程一直進(jìn)行下去，直到網(wǎng)絡(luò)經(jīng)過T個時間步長。第三十三頁，共五十二頁，編輯于2023年，星期二練習(xí)題下列網(wǎng)絡(luò)依據(jù)偏愛節(jié)點(diǎn)刪除變異模型經(jīng)過時間步長為T=4，請給出新網(wǎng)絡(luò)及網(wǎng)絡(luò)的度分布圖。ACBHFGDKEJI第三十四頁，共五十二頁，編輯于2023年，星期二10.3節(jié)點(diǎn)刪除變異模型第三十五頁，共五十二頁，編輯于2023年，星期二10.3節(jié)點(diǎn)刪除變異模型第三十六頁，共五十二頁，編輯于2023年，星期二10.3節(jié)點(diǎn)刪除變異模型在兩個圖中關(guān)聯(lián)系數(shù)r都隨著時間步長的增大而稍微下降，或者說，在一定的時間步長內(nèi)，隨機(jī)刪除節(jié)點(diǎn)和偏愛刪除節(jié)點(diǎn)對網(wǎng)絡(luò)的度負(fù)關(guān)聯(lián)性是沒有太大影響的。事實(shí)上，由于初始網(wǎng)絡(luò)為無標(biāo)度網(wǎng)絡(luò)，即初始網(wǎng)絡(luò)中度小的節(jié)點(diǎn)占大多數(shù)，所以在選擇節(jié)點(diǎn)的時候，無論是隨機(jī)還是偏愛，都是容易選擇度小的節(jié)點(diǎn)。第三十七頁，共五十二頁，編輯于2023年，星期二10.3節(jié)點(diǎn)刪除變異模型再者，由于初始網(wǎng)絡(luò)為中性網(wǎng)絡(luò)，即無關(guān)聯(lián)網(wǎng)絡(luò)，對于一個度小的節(jié)點(diǎn)來說，它的鄰居中度大的節(jié)點(diǎn)與度小的節(jié)點(diǎn)的比例是幾乎相同的，所以大節(jié)點(diǎn)的邊（簡稱小-大）的概率是大致相同的，這樣在一定的時間步長內(nèi)，隨機(jī)刪除節(jié)點(diǎn)和偏愛刪除節(jié)點(diǎn)會使得關(guān)聯(lián)系數(shù)r有略微的減小，但并不會強(qiáng)烈影響網(wǎng)絡(luò)的度負(fù)關(guān)聯(lián)性。第三十八頁，共五十二頁，編輯于2023年，星期二10.4刪邊變異模型引起邊的變異的生物機(jī)制在本質(zhì)上非對稱的，即當(dāng)一條邊發(fā)生編譯時，其中只有一個節(jié)點(diǎn)發(fā)生變異，另一個節(jié)點(diǎn)保持不變。這種非對稱性意味著邊變異的速率會同時決定于發(fā)生變異的節(jié)點(diǎn)和未發(fā)生變異的節(jié)點(diǎn)的度。第三十九頁，共五十二頁，編輯于2023年，星期二10.4刪邊變異模型隨機(jī)刪邊變異模型：1.初始化（同隨機(jī)節(jié)點(diǎn)刪除變異模型）；2.網(wǎng)絡(luò)在每一個時間步長，隨機(jī)選擇一個節(jié)點(diǎn)i作為變異節(jié)點(diǎn)，再從i的鄰居中隨機(jī)選擇節(jié)點(diǎn)j（節(jié)點(diǎn)j不發(fā)生變異），刪去連接i和j的邊Lij，若產(chǎn)生孤立節(jié)點(diǎn)，刪除它。這個過程一直進(jìn)行下去，直到網(wǎng)絡(luò)經(jīng)過T個時間步長。第四十頁，共五十二頁，編輯于2023年，星期二練習(xí)題下列網(wǎng)絡(luò)依據(jù)隨機(jī)刪邊變異模型，經(jīng)過時間步長為T=4，給出新網(wǎng)絡(luò)及網(wǎng)絡(luò)的度分布圖。ACBHFGDKEJI第四十一頁，共五十二頁，編輯于2023年，星期二10.4刪邊變異模型根據(jù)生物大分子的保守性和邊變異的非對稱性，選擇度小的節(jié)點(diǎn)作為變異節(jié)點(diǎn)，然而，現(xiàn)在還存在這樣一個問題：即怎樣去選擇剩下的那個未發(fā)生變異的節(jié)點(diǎn)呢？Berg等考慮了一個最簡單的例子去反映邊的失去，并且給出了失去邊的速度為dk,k'∝(1/k+1/k')，即度小的節(jié)點(diǎn)之間更容易發(fā)生邊的失去。第四十二頁，共五十二頁，編輯于2023年，星期二10.4刪邊變異模型這種特殊的機(jī)制也同樣運(yùn)用于其他研究中。例如，Shi等提出了一個反偏愛的刪除機(jī)制，在每一個時間步長，T0條已存在的連接將按照下列方式刪除：第i個節(jié)點(diǎn)首先以偏愛概率П（ki）被選擇.第四十三頁，共五十二頁，編輯于2023年，星期二10.4刪邊變異模型然后從i的鄰居中（定義為O（i））以概率P(kj)選擇節(jié)點(diǎn)j。兩個節(jié)點(diǎn)i和j之間的連接將被刪除，重復(fù)這個過程T0次。第四十四頁，共五十二頁，編輯于2023年，星期二練習(xí)題下列網(wǎng)絡(luò)依據(jù)反偏愛刪邊變異機(jī)制，經(jīng)過時間步長為T=4，給出新網(wǎng)絡(luò)及網(wǎng)絡(luò)的度分布圖。ACBHFGDKEJI第四十五頁，共五十二頁，編輯于2023年，星期二10.4刪邊變異模型這里可以注意到概率P（kj）是全局的，而事實(shí)上邊的變異是局部的過程，所以對此進(jìn)行修正，并給出了偏愛刪邊變異模型。第四十六頁，共五十二頁，編