基于間隙模式的并發(fā)序列模式挖掘算法

楊夢濤, 王翠青, 陳未如

(沈陽化工大學 計算機科學與技術(shù)學院, 遼寧 沈陽 110142)

結(jié)構(gòu)關(guān)系模式(Structural Relation Patterns,SRPs)是一種后序列模式挖掘[1]的產(chǎn)物，描述了多個序列組成的復雜結(jié)構(gòu)關(guān)系.結(jié)構(gòu)關(guān)系模式挖掘首先研究的是序列模式之間的關(guān)系，然后再把這種關(guān)系進一步分解、細化，整合成一種由并發(fā)、互斥、重復及串行關(guān)系組成的復合結(jié)構(gòu)模式[2].例如，結(jié)構(gòu)關(guān)系模式中的并發(fā)序列模式實現(xiàn)基于Web瀏覽中用來挖掘用戶瀏覽記錄里的并發(fā)關(guān)系，根據(jù)用戶每次瀏覽的喜好，分析客戶習慣，實現(xiàn)基于Web用戶行為分析、瀏覽興趣的網(wǎng)站設(shè)計[3].結(jié)構(gòu)關(guān)系模式在蛋白質(zhì)挖掘中也有重要應用.傳統(tǒng)的序列模式挖掘只關(guān)注挖掘蛋白質(zhì)序列中頻繁出現(xiàn)的子序列，然而,在蛋白質(zhì)中一個特殊的功能點往往不是由一個子序列構(gòu)成，可能是多個基序共同作用，這種結(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ù)庫序列中的匹配情況，并進行并發(fā)挖掘.實際蛋白質(zhì)數(shù)據(jù)集的實驗突顯了ConSP方法在蛋白質(zhì)這種數(shù)據(jù)挖掘中的適用性[5].

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

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

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

1 相關(guān)概念

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

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

1.2 間隙模式及剛隙模式

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

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

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

(1)

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

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

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

x(sn-1)-an

(2)

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

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

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

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

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

(3)

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

2 PBcon算法分析

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

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

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

算法：

(1) 在SDB上以mincon為最小支持度挖掘間隙模式，得到間隙模式最大集SetOfGP，并計算其中每個間隙模式的支持量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} 并標識c和s為子模式;

CGPK=NewSet;

CGP=CGPUCGPK;

While(NewSet is not null);

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

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

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

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

3.1 數(shù)據(jù)準備

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

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

3.2 實驗過程與分析

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

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

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

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

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

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

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

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

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

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

在對PS00627.fasta的挖掘結(jié)果中，WildSpan僅在minsup=51.14 %時挖掘出1個W-模式P-x(3)-G-L-x(1,3)-S-S-A-x(146,267)-G-A-G;在PBcon算法挖掘中，當mincon=55.00 %時，挖掘出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 %時挖掘出1個2-分枝的并發(fā)間隙模式和一個3-分枝的并發(fā)間隙模式，說明它們之間的并發(fā)度很高，值得生物學家分析其中的可能信息.PBcon算法在mincon=80.00 %～50.00 %時均能挖掘出更多的多分枝并發(fā)間隙模式.

4 結(jié) 語

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