楊夢(mèng)濤, 王翠青, 陳未如

(沈陽(yáng)化工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 遼寧 沈陽(yáng) 110142)

結(jié)構(gòu)關(guān)系模式(Structural Relation Patterns,SRPs)是一種后序列模式挖掘[1]的產(chǎn)物，描述了多個(gè)序列組成的復(fù)雜結(jié)構(gòu)關(guān)系.結(jié)構(gòu)關(guān)系模式挖掘首先研究的是序列模式之間的關(guān)系，然后再把這種關(guān)系進(jìn)一步分解、細(xì)化，整合成一種由并發(fā)、互斥、重復(fù)及串行關(guān)系組成的復(fù)合結(jié)構(gòu)模式[2].例如，結(jié)構(gòu)關(guān)系模式中的并發(fā)序列模式實(shí)現(xiàn)基于Web瀏覽中用來(lái)挖掘用戶(hù)瀏覽記錄里的并發(fā)關(guān)系，根據(jù)用戶(hù)每次瀏覽的喜好，分析客戶(hù)習(xí)慣，實(shí)現(xiàn)基于Web用戶(hù)行為分析、瀏覽興趣的網(wǎng)站設(shè)計(jì)[3].結(jié)構(gòu)關(guān)系模式在蛋白質(zhì)挖掘中也有重要應(yīng)用.傳統(tǒng)的序列模式挖掘只關(guān)注挖掘蛋白質(zhì)序列中頻繁出現(xiàn)的子序列，然而,在蛋白質(zhì)中一個(gè)特殊的功能點(diǎn)往往不是由一個(gè)子序列構(gòu)成，可能是多個(gè)基序共同作用，這種結(jié)構(gòu)關(guān)系隱藏在蛋白質(zhì)序列中.所以，可以在傳統(tǒng)序列模式的基礎(chǔ)上利用結(jié)構(gòu)關(guān)系模式挖掘這些子序列之間的結(jié)構(gòu)關(guān)系，以便高效地提取生物信息和分析蛋白質(zhì)功能組成規(guī)則.王翠青等人提出的ConSP算法是使用支持向量[4]數(shù)據(jù)結(jié)構(gòu)存放這些子序列在蛋白質(zhì)數(shù)據(jù)庫(kù)序列中的匹配情況，并進(jìn)行并發(fā)挖掘.實(shí)際蛋白質(zhì)數(shù)據(jù)集的實(shí)驗(yàn)突顯了ConSP方法在蛋白質(zhì)這種數(shù)據(jù)挖掘中的適用性[5].

生物信息學(xué)是由統(tǒng)計(jì)學(xué)、生物學(xué)、計(jì)算機(jī)學(xué)等多門(mén)學(xué)科構(gòu)成的一門(mén)交叉復(fù)雜學(xué)科，也是目前生物研究的熱點(diǎn)學(xué)科之一.生物信息學(xué)研究的熱點(diǎn)之一就是生物序列模式挖掘.它對(duì)識(shí)別基因和功能解釋、識(shí)別非編碼區(qū)功能元素以及蛋白質(zhì)序列組成信息的識(shí)別等具有重要的指導(dǎo)意義.在生物序列中挖掘頻繁模式或者挖掘特定模式是其中兩個(gè)重要研究領(lǐng)域.1995年，Agrawal和Srikant給出用于交易序列數(shù)據(jù)庫(kù)的序列頻繁模式挖掘[6]的定義，如Apriori、GSP、PrefixSpan、SPADE等算法.在這些算法基礎(chǔ)上，研究者們?cè)O(shè)計(jì)了多個(gè)針對(duì)生物序列的模式挖掘算法[7].

在序列模式挖掘中有時(shí)需要有時(shí)間限制約束條件，以保證序列事件或元素之間滿(mǎn)足一定的間隔限制.在蛋白質(zhì)中，通常一個(gè)功能點(diǎn)可能是由多個(gè)蛋白質(zhì)基序共同組成.為了有效地發(fā)現(xiàn)這些基序之間的關(guān)系，Chen-Ming Hsu等人提出WildSpan算法[8].此算法基于Prefixspan算法[9]，在此基礎(chǔ)上增加了蛋白質(zhì)氨基酸序列之間的間隙約束.首先挖掘出蛋白質(zhì)序列中帶有固定間隙約束的塊，然后通過(guò)這些塊之間的序列關(guān)系來(lái)挖掘出它們順序出現(xiàn)的W-模式.

本文首先提出間隙模式、剛隙模式等概念，試圖在通配符間隙約束條件挖掘[10]和One-Off[11]條件的基礎(chǔ)上，將間隙體現(xiàn)在模式挖掘結(jié)果當(dāng)中，并提出了基于間隙模式的并發(fā)序列模式思想和基于剛隙模式的并發(fā)序列模式算法PBcon.與已有的WildSpan算法的W-模式結(jié)果集比較，PBcon算法找到了WildSpan算法未發(fā)現(xiàn)的模式，且PBcon算法的挖掘效率也有優(yōu)勢(shì).

1 相關(guān)概念

1.1 并發(fā)關(guān)系、并發(fā)度及并發(fā)序列模式

并發(fā)關(guān)系、并發(fā)度及并發(fā)序列模式的定義在參考文獻(xiàn)[4]中已有詳細(xì)的描述.

1.2 間隙模式及剛隙模式

間隙模式：間隙模式是指序列模式中個(gè)別位置可以是數(shù)據(jù)庫(kù)元素集Σ的任意元素，該位置用通配符x表示，稱(chēng)作間隙.在客戶(hù)序列數(shù)據(jù)庫(kù)中，一個(gè)間隙模式被表示為:

GP=a1-x(s1,t1)-a2-x(s2,t2)-…-

x(sn-1,tn-1)-an

(1)

式中，ai是元素，x(si,ti)是元素間的間隙，si和ti是間隙個(gè)數(shù)下限和上限，即x(si,ti)表示該位置對(duì)應(yīng)si到ti個(gè)通配符，其中0≤si≤ti.若si

剛隙模式：剛隙模式是一種特殊的間隙模式，其中只允許存在剛性間隙，表示為

RGP=a1-x(s1)-a2-x(s2)-…-

x(sn-1)-an

(2)

子間隙模式：從間隙模式p首或尾部刪除若干個(gè)元素得到新的序列s，并保證s兩端不存在通配符區(qū)域，則s仍是一個(gè)間隙模式，稱(chēng)s為間隙模式p的子間隙模式，p為間隙模式s的超間隙模式.

確型間隙模式、泛型間隙模式：若間隙模式p的通配符區(qū)域x(si,ti)的某個(gè)通配符置換為元素集Σ的某個(gè)確定元素，則可得到一個(gè)新的間隙模式s，稱(chēng)s為p的確型間隙模式，p是s的泛型間隙模式.

性質(zhì)1 間隙模式與其子間隙模式之間存在支持關(guān)系，即對(duì)于間隙模式s和p，若p∠s有s→p.

性質(zhì)2 如果一個(gè)間隙模式是頻繁的，則該間隙模式的子間隙模式也必然是頻繁的，該間隙模式的泛型間隙也必然是頻繁的.

間隙模式支持量：對(duì)于給定的序列數(shù)據(jù)庫(kù)SDB，間隙模式a的支持量BSV(a)定義為一個(gè)長(zhǎng)度為n的二進(jìn)制向量.其中，n是SDB的序列總數(shù)|SDB|；bi=1|0為序列數(shù)據(jù)庫(kù)第i個(gè)序列對(duì)間隙模式a的支持分量BSVi(a)，即間隙模式a是否在第i個(gè)序列出現(xiàn).參照序列支持度[8]的概念，間隙模式a的支持度也表示為：

(3)

序列的并發(fā)間隙模式和并發(fā)間隙模式集：若序列數(shù)據(jù)庫(kù)的序列s對(duì)于間隙模式GPa和GPb的支持分量BSVs(GPa)=BSVs(GPb)=1，則GPa和GPb在該序列中滿(mǎn)足并發(fā)關(guān)系.一般地，所有被序列s所支持的間隙模式c1,c2,…,cm在該序列中滿(mǎn)足并發(fā)關(guān)系，稱(chēng)它們?yōu)樵谛蛄衧上的并發(fā)間隙模式，表示為[c1+c2+…+cm]s，構(gòu)成序列s上的并發(fā)間隙模式集{c1,c2,…,cm}.

2 PBcon算法分析

參考了文獻(xiàn)[4]中并發(fā)全集和最大并發(fā)集的概念,本算法應(yīng)用了間隙模式集、間隙模式最大集、并發(fā)間隙模式最大集等概念，這里不再詳細(xì)闡述.

輸入：序列數(shù)據(jù)源SDB，最小并發(fā)度mincon.

輸出：并發(fā)間隙模式最大集MCGP.

算法：

(1) 在SDB上以mincon為最小支持度挖掘間隙模式，得到間隙模式最大集SetOfGP，并計(jì)算其中每個(gè)間隙模式的支持量BSV;

(2) 令CGP=null,CGPK=SetOfGP=null,k=0;

(3) do

NewSet=null;

k++;

for each c of CGPK

for each s of CGPK

if(c和s有k-1條相同的分支

且concurrence()≥mincon

且不構(gòu)成平凡并發(fā)關(guān)系)

構(gòu)成新的k+1分支并發(fā)間隙模式ncgp;

令NewSet=NewSetU{ncgp} 并標(biāo)識(shí)c和s為子模式;

CGPK=NewSet;

CGP=CGPUCGPK;

While(NewSet is not null);

(4) CGP即為并發(fā)間隙模式全集，刪除其中的所有被標(biāo)識(shí)為子模式的元素，得到最大集MCGP.

(5) 在生成并發(fā)間隙模式的過(guò)程中，生成的并發(fā)間隙模式的數(shù)量會(huì)隨著制定的mincon的遞增而遞減.

3 蛋白質(zhì)序列并發(fā)間隙模式挖掘?qū)嶒?yàn)

為驗(yàn)證PBcon算法的有效性和可行性，嘗試在蛋白質(zhì)序列上挖掘并發(fā)間隙模式.WildSpan算法首先挖掘出帶有固定間隙的塊集，塊集的性質(zhì)正好滿(mǎn)足剛隙模式集的定義.因此，先用WildSpan挖掘出帶有固定間隙約束的由蛋白質(zhì)組成氨基酸為元素的塊集(剛隙模式集)SetOfGP，進(jìn)行基于蛋白質(zhì)剛隙模式的并發(fā)序列模式挖掘，實(shí)現(xiàn)PBcon算法.需要指出的是，這里僅是使用WildSpan算法的中間結(jié)果作為進(jìn)一步挖掘基礎(chǔ)的剛隙模式集，而剛隙模式集的挖掘方法并不只限于使用WildSpan算法.

3.1 數(shù)據(jù)準(zhǔn)備

實(shí)驗(yàn)數(shù)據(jù)是從蛋白質(zhì)功能位點(diǎn)數(shù)據(jù)庫(kù)下載的蛋白質(zhì)序列的文件.一條蛋白質(zhì)序列是由A、

C、D、E、F、G、H、I、K、L、M、N、P、Q、R、S、T、V、W、Y 20個(gè)字符的字母表元素組成的線性序列，其中蛋白質(zhì)序列是用PORSITE語(yǔ)言描述的fasta格式，一個(gè)文件包含多個(gè)fasta格式的蛋白質(zhì)序列.

3.2 實(shí)驗(yàn)過(guò)程與分析

在CODEBLOCK軟件上用C++實(shí)現(xiàn)了PBCon算法，并在內(nèi)存為2G、CPU為2.40 GHz的Windows2007操作系統(tǒng)的環(huán)境上進(jìn)行了蛋白質(zhì)序列分析測(cè)試.

首先用WildSpan算法在數(shù)據(jù)源PS00627.fasta上生成包含99個(gè)剛隙模式的候選1-剛隙模式集，生成剛隙模式時(shí)minsup=48.86 %；然后用PBcon算法對(duì)其分別進(jìn)行挖掘?qū)嶒?yàn).

圖1表示數(shù)據(jù)源PS00627.fasta用PBcon算法在不同并發(fā)度下并發(fā)間隙模式全集中的2、3、4、5分支并發(fā)的間隙模式個(gè)數(shù).由圖1可知：并發(fā)間隙模式集數(shù)隨最小并發(fā)度mincon的增加而減少，表明并發(fā)度越大，所能挖掘的并發(fā)間隙模式的模式數(shù)量越少，基本呈遞減趨勢(shì)，與理論分析相符.

圖1 數(shù)據(jù)源PS00627.fasta并發(fā)間隙模式變化曲線

圖2是數(shù)據(jù)源PS00627.fasta用WildSpan算法挖掘W-模式的變化曲線.由圖2可知：W-模式的挖掘結(jié)果隨minsup的變化而變化，但是只在minsup=51.14 %時(shí)挖掘出一個(gè)W-模式.

圖2 數(shù)據(jù)源PS00627.fasta W-模式變化曲線

圖3是數(shù)據(jù)源PS00627.fasta用PBcon算法挖掘并發(fā)間隙模式集所需要的運(yùn)行時(shí)間曲線.該曲線表明：隨著并發(fā)度的增加，挖掘所需要的時(shí)間減少.這與隨并發(fā)度的增加而產(chǎn)生的并發(fā)間隙模式集數(shù)減少有關(guān).

圖3 數(shù)據(jù)源PS00627.fasta運(yùn)行時(shí)間變化曲線

表1是數(shù)據(jù)源PS00627.fasta用WildSpan算法和PBcon算法生成的W-模式和并發(fā)間隙模式集的對(duì)比.

表1 PBcon算法和WildSpan結(jié)果對(duì)比

在對(duì)PS00627.fasta的挖掘結(jié)果中，WildSpan僅在minsup=51.14 %時(shí)挖掘出1個(gè)W-模式P-x(3)-G-L-x(1,3)-S-S-A-x(146,267)-G-A-G;在PBcon算法挖掘中，當(dāng)mincon=55.00 %時(shí)，挖掘出P-x(3)-G-L(137,142)S-S-A(144,146)G-x(2)-S-S(218,222)G-L-x-S(325,328)G-A-G(332,334)，上述W-模式被包含其中.除此以外，PBcon算法在mincon=90.00 %時(shí)挖掘出1個(gè)2-分枝的并發(fā)間隙模式和一個(gè)3-分枝的并發(fā)間隙模式，說(shuō)明它們之間的并發(fā)度很高，值得生物學(xué)家分析其中的可能信息.PBcon算法在mincon=80.00 %～50.00 %時(shí)均能挖掘出更多的多分枝并發(fā)間隙模式.

4 結(jié) 語(yǔ)

并發(fā)性是研究序列結(jié)構(gòu)關(guān)系的重要特性.本研究將并發(fā)序列模式挖掘和間隙模式應(yīng)用于蛋白質(zhì)基序的結(jié)構(gòu)關(guān)系挖掘.相比較WildSpan算法，PBcon算法可以找到更多的有意義的并發(fā)間隙模式.這有助于在蛋白質(zhì)序列的組成中找到更多隱藏在結(jié)構(gòu)之間的關(guān)系，可將其應(yīng)用在預(yù)測(cè)蛋白質(zhì)功能點(diǎn)的組合分析中.同時(shí)，PBcon算法與現(xiàn)有算法相比效率更高.今后將致力于找到更加優(yōu)化的算法，提高效率，把并發(fā)序列模式應(yīng)用到更多的類(lèi)似蛋白質(zhì)序列的序列分析數(shù)據(jù)中.