半張量積在布爾網(wǎng)絡(luò)同步中的應(yīng)用

張 靜，樊永艷

(滄州師范學(xué)院)

1 布爾網(wǎng)絡(luò)

近年來布爾型網(wǎng)絡(luò)以及同步分析被逐漸運(yùn)用于大型基因調(diào)節(jié)網(wǎng)絡(luò)全局行為的分析研究，其優(yōu)點(diǎn)是結(jié)構(gòu)簡單明了.另外，它在生命科學(xué)、金融科學(xué)以及其他一些典型復(fù)雜系統(tǒng)研究中都起到非常重要的作用.布爾網(wǎng)絡(luò)［1-2］G(V，F(xiàn))由結(jié)點(diǎn)狀態(tài)集V={X1，X2，…，Xn}和布爾函數(shù)集F={f1，f2，…，fn}組成.結(jié)點(diǎn)i在t+1時(shí)刻的狀態(tài)Xi∈{0，1}是由其他一些與它相連通的結(jié)點(diǎn)，，…在t時(shí)刻的狀態(tài)，，…，決定的，即

網(wǎng)絡(luò)在t時(shí)刻的狀態(tài)由所有結(jié)點(diǎn)的狀態(tài)向量→X(t)=X1(t)X2(t)…Xn(t)來描述.很明顯，對(duì)于一個(gè)有n個(gè)結(jié)點(diǎn)的網(wǎng)絡(luò)，它的狀態(tài)空間由00…0到11…1的2n種狀態(tài)組成的.

圖1 節(jié)點(diǎn)A和B組成的布爾網(wǎng)絡(luò)

圖1［3］是由兩個(gè)節(jié)點(diǎn)A和B組成的布爾網(wǎng)絡(luò)，它的動(dòng)態(tài)系統(tǒng)為

其 中 ∨ (∧)意 思 是 max(A(t)，B(t))(min(A(t)，B(t))).

2 半張量積

矩陣的半張量積是近期中科院系統(tǒng)所程代展教授在文獻(xiàn)［4］中提出的一種新的矩陣乘法，它是對(duì)普通矩陣乘法的推廣.對(duì)于普通矩陣，矩陣A、B只有矩陣A的列數(shù)與矩陣B的行數(shù)相等才可以相乘.而矩陣的半張量積可以解決非等維數(shù)的矩陣相乘，即矩陣A的列數(shù)與矩陣B的行數(shù)不相等的矩陣相乘.矩陣的半張量積的應(yīng)用領(lǐng)域很廣，它主要用來處理多維數(shù)組及處理非線性問題，在邏輯、幾何、代數(shù)、物理、控制系統(tǒng)及Morgan等等問題中均可找到它的應(yīng)用［4-6］.

定義1［4］設(shè) A ∈ Mm×n，B ∈ Mp×q.記 n 與 p的最小公倍數(shù)為t=lcm{n，p}.定義A與B的半張量積為

這里Mm×n表示所有m×n矩陣的集合，?表示kronecker積，?代表左半張量積.

定義2［4］換位矩陣 W［m，n］是一個(gè) mn × mn矩陣，定義如下:它的行和列都是由雙指標(biāo)(i，j)標(biāo)注，列是按照索引Id(i，j;m，n)排列，行是按照索引 Id(j，i;n，m)排列，并且位于［(I，J)，(i，j)］上的元素的值為

命題1［4］(1)換位矩陣的逆和轉(zhuǎn)置為

(2)當(dāng)m=n時(shí)，上式變?yōu)?/p>

m=n的情形特別重要，為了簡化符號(hào)，記

引理1［4］設(shè)A是一個(gè)邏輯變量，定義降冪矩陣為，那么對(duì)于任意的p×4q矩陣Ψ有ΨA2=ΨMrA.

定義3［4］(1)(經(jīng)典)邏輯論域Dt是指

(2)(經(jīng)典)邏輯變量P是指在Dt中取值的變量，即P∈Dt;

記T0≡T≡1和F0≡F≡0分別表示“真”和“假”.

定義4［4］(1)r元邏輯算子是指映射 σ:

為了使用矩陣表示，記

定義5［4］稱2×2r矩陣Mσ為r元邏輯算子σ的機(jī)構(gòu)矩陣，如果

考慮4個(gè)基本的二元邏輯算子;析取，P∨Q;合取，P∧Q;蘊(yùn)涵，P→Q;等值，P?Q.4個(gè)基本二元邏輯算子的結(jié)構(gòu)矩陣如下:

3 半張量積在布爾網(wǎng)絡(luò)中的應(yīng)用

應(yīng)用半張量積，就可以將布爾網(wǎng)絡(luò)的邏輯方程轉(zhuǎn)化成為代數(shù)方程［7］，邏輯變量就表達(dá)成了向量形式，定義T=1 ～，F(xiàn)=0 ～，其中是單位陣In的第i列，則邏輯變量A(t)在D:={，}中取值.

對(duì)于每個(gè)邏輯算子ξ=ξ(A1，…，An)存在一個(gè) ξ的結(jié)構(gòu)矩陣，記為 Mξ∈ M2×2n，表示為

例如，對(duì)于∧和∨，分別為Mc和Md，Mc= σ2［1，2，2，2，2］，Md= σ2［1，1，1，2］.例如 A(t+1)=A(t)∨B(t)可以被表示為代數(shù)形式:

B(t+1)=A(t)∧B(t)可以被表示為代數(shù)形式:

基于以上，將一個(gè)邏輯動(dòng)態(tài)系統(tǒng)轉(zhuǎn)化為一離散時(shí)間動(dòng)態(tài)系統(tǒng)的方法，可以得到一個(gè)網(wǎng)絡(luò)過渡矩陣L.把邏輯動(dòng)態(tài)方程轉(zhuǎn)化為離散時(shí)間的動(dòng)態(tài)方程，一個(gè)有 n個(gè)節(jié)點(diǎn) Ai，i=1，2，…，n的布爾網(wǎng)絡(luò)被表示為

其中 ξi，i=1，2，…，n 是邏輯函數(shù)(算子).

應(yīng)用(12)，Ai(t+1)=WiA1(t)A2(t)…An(t)，i=1，2，…，n，定義 x(t)=A1(t)A2(t)…An(t).可以得出

應(yīng)用半張量積性質(zhì)以及降冪矩陣Mr=σ4［1，4］，(16)可以被表示為x(t+1)=Lx(t).其中L被叫做過渡矩陣.

由圖 1，計(jì)算其過渡矩陣，設(shè) x(t)=A(t)B(t)，那么

則 L=Md(I4? Mc)(I2? w［2］)Mr(I2? Mr)= δ4［1，2，2，4］

4 布爾網(wǎng)絡(luò)的同步分析

在生態(tài)環(huán)境中，存在著許多同步現(xiàn)象，如夏日青蛙，知了的齊鳴，螢火蟲一致發(fā)光，蟋蟀群的叫聲有節(jié)奏地唱和，鳥兒成群的飛;不僅是生態(tài)，從核子到宇宙、從物理到化學(xué)，乃至人類社會(huì)，都廣泛存在著同步現(xiàn)象，如心肌細(xì)胞和大腦神經(jīng)網(wǎng)絡(luò)的同步，鐘擺同步現(xiàn)象，劇場中觀眾自發(fā)鼓掌同步等.對(duì)于復(fù)雜系統(tǒng)內(nèi)部個(gè)體之間通過局部相互作用(耦合)，從一種狀態(tài)突然變成另一種狀態(tài)，逐漸的自組織形成了每個(gè)個(gè)體狀態(tài)一致的現(xiàn)象，稱作同步現(xiàn)象.

布爾網(wǎng)絡(luò)可以用邏輯函數(shù)來表示，如圖2.假設(shè)有一個(gè)簡單的布爾網(wǎng)絡(luò)，有四個(gè)結(jié)點(diǎn)，分別為A、B、C、D，并且兩兩相連，假設(shè)結(jié)點(diǎn) A受結(jié)點(diǎn) B和結(jié)點(diǎn)D的狀態(tài)控制，節(jié)點(diǎn)B則受結(jié)點(diǎn)A和結(jié)點(diǎn)C的狀態(tài)控制，結(jié)點(diǎn)C受結(jié)點(diǎn)B和結(jié)點(diǎn)D的狀態(tài)控制，結(jié)點(diǎn)D受結(jié)點(diǎn)C和結(jié)點(diǎn)A的狀態(tài)控制.如果給結(jié)點(diǎn)A、C“或”布爾作用，給結(jié)點(diǎn)B、D“與”布爾作用，分別用“0”和“1”表示結(jié)點(diǎn)處于“是”和“否”兩種狀態(tài).

圖2 邏輯函數(shù)布爾網(wǎng)絡(luò)

則邏輯函數(shù)為:

通過給定的布爾作用，如果四個(gè)結(jié)點(diǎn)在某一時(shí)刻T的狀態(tài)確定，則各結(jié)點(diǎn)在下一時(shí)刻T+1的狀態(tài)也可以相應(yīng)地確定，表1給出了四個(gè)結(jié)點(diǎn)在不同時(shí)刻可能的16種狀態(tài)的真值.若在某一時(shí)刻T0，四個(gè)結(jié)點(diǎn)的狀態(tài)均為0或1，則這個(gè)布爾網(wǎng)絡(luò)同步.通過計(jì)算，得出，A、B、C、D初始狀態(tài)為1011、1110、1111時(shí)可以達(dá)到同步狀態(tài)為1，初始狀態(tài)為0000時(shí)可以達(dá)到同步狀態(tài)為0.其余的初始狀態(tài)最終進(jìn)入循環(huán)狀態(tài)，達(dá)不到同步.

表1 邏輯函數(shù)布爾網(wǎng)絡(luò)真值表

利用邏輯算子研究布爾網(wǎng)絡(luò)的同步.

一個(gè)邏輯變量是指一個(gè)命題，如果這個(gè)命題是真的，就說這個(gè)邏輯變量取值為“真”或“1”，如果這個(gè)命題是假的，就說這個(gè)邏輯變量取值為“假”或“0”.

對(duì)于上面的四個(gè)節(jié)點(diǎn)有布爾作用的網(wǎng)絡(luò)同步問題，可以把每個(gè)節(jié)點(diǎn)的狀態(tài)看成一個(gè)邏輯變量，狀態(tài)為1代表這個(gè)命題是真的，狀態(tài)為0代表這個(gè)命題是假的.

可以將以上問題轉(zhuǎn)化為以下邏輯方程:

若在T+k時(shí)刻網(wǎng)絡(luò)同步，則A、B、C、D四個(gè)邏輯變量在T+k時(shí)刻同時(shí)取值為“真(即1)”或“假(0)”.那么，應(yīng)用邏輯算子，給出(19)式和(20)式:

對(duì)(19)式在T+1時(shí)刻的邏輯值，有如下計(jì)算:

根據(jù)(21)式可以得出ac(b+d-bd)=1，則共有三個(gè)解:

這就意味著，對(duì)于在T時(shí)刻為上面解中的三種狀態(tài)時(shí)，在下一時(shí)刻該網(wǎng)絡(luò)可以達(dá)到同步狀態(tài)為1.同樣地，可以用式(20)解出，對(duì)于在T時(shí)刻四個(gè)結(jié)點(diǎn)狀態(tài)只有為0000時(shí)，在下一時(shí)刻該網(wǎng)絡(luò)可以達(dá)到同步狀態(tài)為0，與真值表分析法結(jié)果相同.

在第3部分中，介紹了一個(gè)邏輯函數(shù)，可以找到一個(gè)過渡矩陣L，使下一狀態(tài)x(t+1)=Lx(t).對(duì)于一個(gè)已知的初始狀態(tài)，在何時(shí)可以達(dá)到同步狀態(tài)為1的問題，可以歸納為解x(t)=的問題.同樣的，當(dāng) x(t)=時(shí)，可以達(dá)到同步狀態(tài)為0.

［1］ Liang S，F(xiàn)uhrman S，Somogyi R.A general reverse engineering algorithm for inference of genetic network architectures［J］.In Paciac Symposium on Biocomputing，1998，3:18-29.

［2］ Pal R.Generating Boolean Networks with a Prescribed Attractor Structure［J］.Bioinformatics，2002，18:261-274.

［3］ Cheng D.Controllability and Observability of Boolean control networks.IEEE Trans，2009，45:1659-1667.

［4］ 程代展，齊洪勝.矩陣的半張量積［M］.北京:科學(xué)出版社，2007.

［5］ Cheng Daizhan.Semi-tensor product of matrices and its app lication to morgen’s problem［J］.Science in China(Series F)，2001，44(3):195-212.

［6］ Cheng Daizhan.Some application s of Semi-tensor product of m atrices in algebra［J］.Computers and Mathematics with Applications，2006，52:1045.

［7］ Zhou J，Chen T.Synchronization in general complex delayed dynamical Networks IEEE Trans on Circuit System，2006，53(3):7332-44.