胡耀煒，段　磊,2，李　嶺，韓　超

(1.四川大學(xué) 計(jì)算機(jī)學(xué)院，成都 610065；　2.四川大學(xué) 華西公共衛(wèi)生學(xué)院，成都 610041；3.四川大學(xué) 生命科學(xué)學(xué)院，成都 610041)(*通信作者電子郵箱leiduan@scu.edu.cn)

0　引言

理解細(xì)胞的分子生物機(jī)制的一個(gè)關(guān)鍵因素是通過(guò)對(duì)生物序列進(jìn)行分類(lèi)來(lái)了解不同生物序列的意義和功能[1-2]。隨著分子生物學(xué)技術(shù)的快速發(fā)展，產(chǎn)生了大量的生物序列數(shù)據(jù)，如DNA序列、蛋白質(zhì)序列等[3]。相比普通的符號(hào)序列數(shù)據(jù)，生物序列數(shù)據(jù)具有以下明顯特點(diǎn)：1)組成生物序列中的符號(hào)總數(shù)少。例如，一條DNA序列由4種堿基({a，c，g，t})組成，一條蛋白質(zhì)序列由20種氨基酸組成。在相同長(zhǎng)度下，生物序列包含更多的重復(fù)出現(xiàn)的符號(hào)。2)生物序列的長(zhǎng)度較長(zhǎng)，例如一條基因或蛋白序列的長(zhǎng)度通常在104的級(jí)別。3)不同類(lèi)別的生物序列樣本規(guī)模不平衡。受限于數(shù)據(jù)來(lái)源和數(shù)據(jù)采集成本，不同類(lèi)別的生物序列在樣本的長(zhǎng)度、數(shù)量等統(tǒng)計(jì)指標(biāo)上差別明顯。

目前生物序列分類(lèi)的方法大致可以分為三類(lèi)：1)利用序列對(duì)比工具如FASTA(FAST All)[4]、BLAST(Basic Local Alignment Search Tool)[5]進(jìn)行序列對(duì)比, 找出已知類(lèi)標(biāo)的數(shù)據(jù)庫(kù)中最為相似的序列；2)基于統(tǒng)計(jì)或機(jī)器學(xué)習(xí)的方法，通過(guò)一些統(tǒng)計(jì)方法抽取序列特征，然后利用機(jī)器學(xué)習(xí)的方法進(jìn)行序列分類(lèi)[6-9]；3)利用不同的模式挖掘來(lái)提取特征并進(jìn)行分類(lèi)[10-11]。利用序列對(duì)比工具進(jìn)行分類(lèi)在數(shù)據(jù)量較大時(shí)需要巨大的計(jì)算量；統(tǒng)計(jì)或機(jī)器學(xué)習(xí)方法所得到的結(jié)果盡管較好但解釋性較差；而基于模式的方法具有較強(qiáng)的解釋性，但存在分類(lèi)效果不夠理想、運(yùn)行時(shí)間較長(zhǎng)的問(wèn)題。

本文針對(duì)基于模式的分類(lèi)方法，設(shè)計(jì)了具有可解釋性的基于密度感知模式的生物序列分類(lèi)(Biological Sequence Classifier based on density-aware patterns, BSC)算法，其主要工作包括：1)引入了“密度感知”來(lái)評(píng)價(jià)模式在單條序列中出現(xiàn)的頻繁度，并提出了密度感知模型的概念；2)使用“間隔約束”來(lái)提高模式匹配的效率；3)在真實(shí)的蛋白質(zhì)序列和基因序列數(shù)據(jù)上進(jìn)行翔實(shí)的實(shí)驗(yàn)，驗(yàn)證了BSC算法有較高的生物序列分類(lèi)精度和執(zhí)行效率。

1　問(wèn)題定義

本文將允許在序列中出現(xiàn)的符號(hào)的集合稱(chēng)為符號(hào)集，記作Σ。例如，對(duì)于DNA序列，Σ={a，c，g，t}。序列由符號(hào)集中的元素按序組成，表示為S=e1e2…en(ei∈Σ，1≤i≤n)。用S[i]表示序列S中第i個(gè)元素，|S|表示序列S的長(zhǎng)度，即S中元素的總數(shù)。例如，給定基因序列S=acgcac，S[3]=g， |S|=6。

序列S中元素S[i]和S[j](1≤i

給定序列S和序列P，若P=S[k1]S[k2]…S[km]，其中1≤k1

若存在實(shí)例〈k1,k2,…,km〉∈ins(P,S)滿足? 1≤i≤m，γ.min≤gap(S，ki，ki+1)≤γ.max，那么稱(chēng)實(shí)例〈k1,k2, …,km〉滿足間隔約束γ，且P是S的γ-子序列(或稱(chēng)Pγ-匹配S)，記作P?S。例如：給定序列S=acgcact，序列P=agc，間隔約束γ=[0, 1]，則P在S中的實(shí)例有〈1，3，4〉。由于gap(S， 1，3)=1∈γ且gap(S，3，4)=0∈γ，因此P?S。將ins(P，S)中滿足間隔約束γ的實(shí)例的集合記為γ-ins(P,S)。容易看出，γ-ins(P，S)?ins(P，S)。

給定序列S，間隔約束γ和模式長(zhǎng)度l，則序列的長(zhǎng)度為l且滿足間隔約束γ的實(shí)例的數(shù)量N為|{〈k1,k2, …,kl〉|? 1≤i≤l(1≤ki≤|S|)(? 1≤j

定義1密度。給定序列P和S，間隔約束γ，序列P在S的密度den(P，S)為：

den(P,S)=|γ-ins(P,S)|/N

(1)

若P?S，即γ-ins(P,S)≠?,那么，1/N≤den(P,S)≤1.0。

定義2支持度。給定序列集合D、間隔約束γ和密度閾值δ，序列P的支持度記作sup(P，δ，D)，為Pγ-匹配D中序列，且匹配密度不小于δ的序列的個(gè)數(shù)與D中序列樣本總數(shù)的比值，即:

sup(P,δ,D)=|{S∈D|den(P,S)≥δ}|/|D|

(2)

給定支持度閾值，若sup(P，δ，D)≥α，那么稱(chēng)P為密度感知模式。

給定類(lèi)標(biāo)簽集合C(|C|個(gè)類(lèi)別)，序列數(shù)據(jù)集(Sequential DataBase, SDB)為由一個(gè)序列數(shù)據(jù)對(duì)象及其對(duì)應(yīng)的唯一類(lèi)標(biāo)簽組成的二元組的集合，記作SDB={〈S,c〉}，其中S是一條序列，c∈C是S的類(lèi)標(biāo)簽。為便于描述，將所有類(lèi)別為c的序列組成的集合記為Dc，即Dc={S|〈S,c〉∈SDB}。那么，給定類(lèi)標(biāo)簽Ci，Cj∈C，Dci∩Dcj=?。

定義3置信度。給定序列數(shù)據(jù)集SDB，間隔約束γ，密度閾值δ。序列P關(guān)于類(lèi)別c的置信度(記作conf(P，c))為:

(3)

根據(jù)統(tǒng)計(jì)學(xué)習(xí)的思想，某個(gè)序列的重要性隨著它在該類(lèi)中出現(xiàn)的次數(shù)呈正比增加，同時(shí)隨著它在其他類(lèi)中出現(xiàn)的頻率呈反比下降。即序列P出現(xiàn)在類(lèi)別c中頻率很高，同時(shí)又出現(xiàn)在較少的類(lèi)中，則P和c類(lèi)有較大的相關(guān)性，可作為用于分類(lèi)的模式。根據(jù)該思想具有以下對(duì)比度定義：

定義4對(duì)比度。給定序列數(shù)據(jù)集SDB，間隔約束γ，密度閾值δ,序列P關(guān)于類(lèi)別c的對(duì)比度(記作cst(P，c))為:

cst(P,c)=sup(P,δ,Dc)×(1+lg(|C|/m))

(4)

其中，m=|{i∈C|sup(P，δ，Di)≥α}|。

表1列出了本文常用的符號(hào)及其定義。

表1　符號(hào)及定義Tab. 1　Notations and definitions

2　BSC算法設(shè)計(jì)

為了對(duì)生物序列數(shù)據(jù)集分類(lèi)，本文提出了一種基于密度感知模式的生物序列分類(lèi)算法BSC。BSC算法主要步驟包括：1)密度感知模式挖掘；2)生成分類(lèi)規(guī)則；3)構(gòu)建序列分類(lèi)器。

2.1　密度感知模式挖掘

集合枚舉樹(shù)(圖1)是廣泛采用的生成頻繁模式的算法，BSC算法采用遍歷集合枚舉樹(shù)的方式生成候選模式。

圖1　DNA集合枚舉樹(shù)Fig. 1　Enumeration tree of DNA set

為了獲得較高的執(zhí)行效率，可根據(jù)模式生成算法的性質(zhì)得到剪枝策略。

引理1給定序列集合D，間隔約束γ，密度閾值δ，支持度閾值α，序列P和P′(P′是P的連續(xù)子序列)，則sup(P′，δ，D)≥sup(P，δ，D)。

定理1給定序列集合D，間隔約束γ，支持度閾值α，序列P和P′(P′是P的連續(xù)子序列)，若sup(P′，0，D)<α,則sup(P，δ，D)<α。

證明因?yàn)閟up(P′，0，D)<α，sup(P′，0，D)≥sup(P，0，D),又因?yàn)閟up(P，0，D)≥sup(P，δ，D),所以sup(P，δ，D)<α。

證畢。

由定理1可以得到剪枝策略1。

剪枝策略1給定序列集合D，支持度閾值α和序列P，若sup(P，0，D)<α，則剪去集合枚舉樹(shù)中P和P的所有子節(jié)點(diǎn)。

本文采用基于廣度優(yōu)先遍歷集合枚舉樹(shù)生成候選模式的算法，基本思想為通過(guò)拼接兩個(gè)長(zhǎng)度為l的候選模式生成長(zhǎng)度為l+1的候選模式[13]。具體地，給定模式P和Q(|P|=|Q|=l)， 令pre(P)=P[1]P[2]…P[l-1]，suf(Q)=Q[2]Q[3]…Q[l]。 若pre(P)=suf(Q)，則可由模式P和Q生成長(zhǎng)度為l+1的候選模式P⊕Q=Q[1]P[1]P[2]…P[l]=Q[1]Q[2]…Q[l]P[l]。算法1中給出了BSC算法生成密度感知模式的偽代碼。

算法1GENPATTERNS(D，α，δ)。

輸入數(shù)據(jù)集D，支持度閾值α，密度閾值δ;

輸出密度感知模式集合F。

Yl←Σ；F←{長(zhǎng)度為1的密度感知模式}

whileYl≠? do

Yl+1←?

Yl←Yl{P∈Yl|sup(P，0，D)<α}

forP∈Yl，Q∈Yldo

ifpre(P)=suf(Q) then

Z=P⊕Q

Yl+1←Yl+1∪{Z}

ifsup(Z，δ，D)≥αthen

F←F∪{Z}

endif

endif

endfor

Yl←Yl+1

endwhile

returnF

2.2　生成規(guī)則

根據(jù)算法1可以從數(shù)據(jù)集SDB的每個(gè)類(lèi)中挖掘到密度感知模式。若在序列集合Dc中挖掘出頻繁模式P，則生成的候選分類(lèi)規(guī)則r形如：P?c。

數(shù)據(jù)集中每個(gè)類(lèi)通常會(huì)生成大量候選分類(lèi)規(guī)則，若直接應(yīng)用所有候選規(guī)則進(jìn)行分類(lèi)不僅會(huì)增加計(jì)算開(kāi)銷(xiāo)，還將引入低質(zhì)量的規(guī)則導(dǎo)致分類(lèi)效果不佳。因此，需要對(duì)候選分類(lèi)規(guī)則進(jìn)行評(píng)價(jià)以便挑選出分類(lèi)能力強(qiáng)的規(guī)則。

置信度反映的是分類(lèi)規(guī)則的確定性。給定分類(lèi)規(guī)則r：P?c，置信度閾值β，如果conf(P，c)≥β，則密度感知模式P對(duì)c類(lèi)具有較強(qiáng)分類(lèi)能力。

對(duì)比度反映的是分類(lèi)規(guī)則中密度感知模式P在c類(lèi)中的重要程度。即c中P出現(xiàn)的頻率較高且出現(xiàn)在很少的類(lèi)時(shí)，則P是一個(gè)能較好代表c的特征。

文獻(xiàn)[14]通過(guò)實(shí)驗(yàn)驗(yàn)證了當(dāng)其他條件相同時(shí)，模式長(zhǎng)度是評(píng)價(jià)模式分類(lèi)能力的重要指標(biāo)。

基于上述分析, 給出以下分類(lèi)能力評(píng)價(jià)規(guī)則：

給定兩個(gè)分類(lèi)規(guī)則r1：P?c，r2：P′ ?c。

1)如果conf(P，c)≥conf(P′，c)，那么r1?r2(r1優(yōu)于r2)。

2)如果conf(P，c)=conf(P′，c)且cst(P，c)≥cst(P′，c), 那么r1?r2。

3)如果conf(P，c)=conf(P′，c)，cst(P，c)=cst(P′，c)且|P|≥|P′|，那么r1?r2。

4)如果conf(P，c)=conf(P′，c)，cst(P，c)=cst(P′，c)，|P|=|P′|且P先于P′生成，那么r1?r2。

通過(guò)評(píng)價(jià)規(guī)則可以對(duì)候選分類(lèi)規(guī)則進(jìn)行排序。按分類(lèi)能力的高低順序排好序的分類(lèi)規(guī)則更加利于剪枝并挑選出分類(lèi)能力較強(qiáng)的規(guī)則來(lái)構(gòu)建分類(lèi)器。

本文候選分類(lèi)規(guī)則剪枝采用數(shù)據(jù)集覆蓋方法[15]，即從排好序的候選分類(lèi)規(guī)則集合中依次取規(guī)則r對(duì)數(shù)據(jù)集D中的序列進(jìn)行匹配，若數(shù)據(jù)集D中至少存在一條序列S滿足den(P，S)≥δ，則把此規(guī)則加入分類(lèi)規(guī)則集合R中，并把序列S從數(shù)據(jù)集D中去除。該過(guò)程直到數(shù)據(jù)集D為空或沒(méi)有滿足匹配條件的序列為止。

當(dāng)數(shù)據(jù)集SDB的每個(gè)類(lèi)按上述方法進(jìn)行匹配后，剩余序列最多的類(lèi)的類(lèi)標(biāo)即為默認(rèn)類(lèi)標(biāo)，默認(rèn)類(lèi)標(biāo)在2.3節(jié)中用到。

算法2給出了生成分類(lèi)規(guī)則的偽代碼。

算法2GENRULES(D，F(xiàn)，δ)。

輸入數(shù)據(jù)集D，密度感知模式集合F，密度閾值δ;

輸出分類(lèi)規(guī)則集合R。

R←{P?c|P∈F}

/*構(gòu)造分類(lèi)規(guī)則,c為數(shù)據(jù)集D的類(lèi)標(biāo)*/

R←?

/*初始化分類(lèi)規(guī)則集合R*/

sortR

/*按照分類(lèi)能力評(píng)價(jià)規(guī)則進(jìn)行排序*/

forr∈Rdo

forS∈Ddo

ifden(P，S)≥δthen

D←DS;

endif

endfor

R←R∪{r}

endfor

returnR

2.3　構(gòu)建序列分類(lèi)器

本節(jié)將根據(jù)算法2得到的分類(lèi)規(guī)則集合來(lái)構(gòu)建序列分類(lèi)器，對(duì)未知序列進(jìn)行分類(lèi)。

在已經(jīng)取得分類(lèi)規(guī)則集合的情況下,若用分類(lèi)規(guī)則去匹配待分類(lèi)序列S，則會(huì)出現(xiàn)多個(gè)分類(lèi)規(guī)則同時(shí)匹配S且這些規(guī)則屬于不同類(lèi)別的情況，因此需要一種合適的判定方法來(lái)判定S屬于的類(lèi)別。

容易想到用投票的方式來(lái)進(jìn)行分類(lèi)，匹配的規(guī)則中某個(gè)類(lèi)的數(shù)量最多則預(yù)測(cè)待分類(lèi)序列S屬于該類(lèi)。然而，這種方式?jīng)]有考慮不同分類(lèi)規(guī)則具有不同的可信度，因此分類(lèi)效果不佳。本文則采用如下方式進(jìn)行判定：

給定待分類(lèi)序列S，分類(lèi)規(guī)則集合Rs，則類(lèi)別c在待分類(lèi)序列S上的得分為：

(5)

若某條分類(lèi)規(guī)則能夠匹配到待分類(lèi)序列，則該規(guī)則的置信度作為它的得分累加到該規(guī)則預(yù)測(cè)的類(lèi)別上。最終，得分最高的類(lèi)為待分類(lèi)序列所屬的類(lèi)。算法3給出了構(gòu)建序列分類(lèi)器的偽代碼。

算法3CLASSIFIER(Rs，S，γ，k)。

輸入分類(lèi)規(guī)則集合Rs，待分類(lèi)序列S，間隔約束γ，k個(gè)分類(lèi)規(guī)則;

輸出待分類(lèi)序列S的類(lèi)標(biāo)。

對(duì)每個(gè)類(lèi)c初始化score(c)為0

count←0

forr∈Rsandcount

ifγ-ins(P，S)≠? then

score(c)←score(c)+conf(P，c)

count←count+1

endif

endfor

ifcount=0 then

return 默認(rèn)類(lèi)標(biāo)

returnscore(c)最大的類(lèi)標(biāo)

3　實(shí)驗(yàn)與分析

3.1　實(shí)驗(yàn)數(shù)據(jù)及環(huán)境

為驗(yàn)證算法的有效性、執(zhí)行效率和不同參數(shù)對(duì)算法的影響，在4組真實(shí)的蛋白質(zhì)序列數(shù)據(jù)集和基因序列數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，包括：Thermophilic數(shù)據(jù)集[16]、Apoliporotein數(shù)據(jù)集[17]，以及來(lái)自于Pfam數(shù)據(jù)庫(kù)(http://pfam.xfam.org/)的Protein數(shù)據(jù)集和Gene數(shù)據(jù)集。這4組數(shù)據(jù)特征如表2所示。

為驗(yàn)證BSC算法分類(lèi)效果，與四種基于模式的可解釋性分類(lèi)算法進(jìn)行比較。其中：SCIS_HAR、SCIS_MA序列分類(lèi)算法的代碼來(lái)自文獻(xiàn)[10]；另兩種算法則采用不同長(zhǎng)度的頻繁模式作為特征，然后使用解釋性較強(qiáng)的決策樹(shù)和樸素貝葉斯作為分類(lèi)算法進(jìn)行分類(lèi)，且算法由懷卡托智能分析環(huán)境(Waikato Environment for Knowledge Analysis, Weka)[18]實(shí)現(xiàn)，為便于敘述稱(chēng)這兩種算法為DTree和NBayes。

五種算法均采用Java語(yǔ)言編寫(xiě)，代碼公開(kāi)在https://github.com/huyaowei1992/BSC。所有實(shí)驗(yàn)都進(jìn)行了10折交叉驗(yàn)證，即把數(shù)據(jù)集分成10等份，每次取其中1份作為測(cè)試集，其他部分作為訓(xùn)練集，依次進(jìn)行10次實(shí)驗(yàn)，求平均值作為最后結(jié)果。實(shí)驗(yàn)在配置為Intel Core i7- 4760 3.60 GHz CPU，16 GB內(nèi)存，Windows 7(64位)操作系統(tǒng)的個(gè)人計(jì)算機(jī)上完成。

表2　實(shí)驗(yàn)數(shù)據(jù)集特征Tab. 2　Characteristics of experimental datasets

3.2　有效性實(shí)驗(yàn)

為保證實(shí)驗(yàn)的一致性，設(shè)定所有算法中相同的參數(shù)為：支持度閾值α=0.05，置信度閾值β=0.5，使用的分類(lèi)規(guī)則數(shù)k=10。因?qū)Ρ鹊乃惴ㄐ枰脩粼O(shè)定生成模式的最大長(zhǎng)度L，為了實(shí)驗(yàn)的公平，BSC算法也添加該參數(shù)進(jìn)行比較。

表3列出了五種算法在4組數(shù)據(jù)集中隨著模式最大長(zhǎng)度L變化的分類(lèi)精度情況，其中N/A表示算法因?yàn)閮?nèi)存溢出而無(wú)法完成實(shí)驗(yàn)。由表3可以看出, BSC算法在4組數(shù)據(jù)集上都達(dá)到了最好的分類(lèi)精度，同時(shí)L較小時(shí)BSC算法已經(jīng)穩(wěn)定。SCIS_MA算法和SCIS_HAR算法分類(lèi)精度隨L的增大而提高，但是這兩種算法對(duì)不同數(shù)據(jù)集分類(lèi)效果差別較大。需要注意的是，對(duì)比算法在Gene數(shù)據(jù)的分類(lèi)精度普遍不高的原因是：Gene數(shù)據(jù)的字符集比蛋白質(zhì)更小，只有4個(gè)，因此模式的長(zhǎng)度較小時(shí)，很容易在各類(lèi)序列中得到匹配，因此需要枚舉出比蛋白質(zhì)更長(zhǎng)的模式，分類(lèi)效果才會(huì)有所提升。但是增大模式長(zhǎng)度時(shí)，需要枚舉的模式數(shù)量會(huì)指數(shù)增大，內(nèi)存需求則會(huì)更多，所以根據(jù)實(shí)驗(yàn)情況，本文列舉的模式的最大長(zhǎng)度為7。

表3　算法分類(lèi)準(zhǔn)確率比較　%Tab. 3　Comparison of classification accuracy　%

BSC算法采用基于密度的頻繁模式，在長(zhǎng)度不同的序列中，密度公式的分子分母都會(huì)根據(jù)長(zhǎng)度的增大而增大，因此會(huì)削弱因?yàn)樾蛄虚L(zhǎng)度的差別對(duì)分類(lèi)效果產(chǎn)生的影響；且支持度的公式同樣采用分?jǐn)?shù)形式，對(duì)不同的數(shù)據(jù)規(guī)模有一定的歸一化的效果。

實(shí)驗(yàn)結(jié)果表明，與其他基于模式的分類(lèi)算法相比，BSC算法對(duì)蛋白質(zhì)數(shù)據(jù)和基因數(shù)據(jù)有較高的分類(lèi)精度，而且在模式長(zhǎng)度較小時(shí)就可以達(dá)到較高精度，算法的有效性因此得到驗(yàn)證。

3.3　執(zhí)行效率驗(yàn)證

為驗(yàn)證BSC算法的執(zhí)行效率，圖2記錄了有效性實(shí)驗(yàn)中算法在4組數(shù)據(jù)集上隨L變化的運(yùn)行時(shí)間。因?yàn)镾CIS_HAR和SCIS_MA這兩個(gè)算法挖掘的模式和分類(lèi)規(guī)則都完全一樣，只在構(gòu)造分類(lèi)器的過(guò)程中有所不同，所以運(yùn)行時(shí)間幾乎相同。因此，圖2中使用SCIS統(tǒng)一表示。由圖2可以看出，算法的運(yùn)行時(shí)間隨著L增大而變長(zhǎng)，但BSC算法運(yùn)行時(shí)間的增長(zhǎng)幅度明顯小于其他算法。這是因?yàn)锽SC算法在間隔約束的控制下生成的密度感知模式很少，因此算法的計(jì)算開(kāi)銷(xiāo)較小。需要注意的是，BSC算法在L較小時(shí)，大部分模式被剪枝策略剪枝，不會(huì)再枚舉出更長(zhǎng)模式，所以運(yùn)行時(shí)間趨于穩(wěn)定。在圖中還可以觀察到，其他算法在L較大(L>2)時(shí)，運(yùn)行時(shí)間會(huì)陡增，這是因?yàn)楹蜻x模式的規(guī)模隨L增大呈指數(shù)增長(zhǎng)。實(shí)驗(yàn)結(jié)果表明，對(duì)生物序列進(jìn)行分類(lèi)，BSC算法相對(duì)于其他分類(lèi)算法具有更高的執(zhí)行效率。

圖2　不同模式長(zhǎng)度的運(yùn)行時(shí)間Fig.2　Runtime results for different pattern lengths

3.4　不同參數(shù)對(duì)算法的影響

為了探究不同的參數(shù)設(shè)置對(duì)BSC算法分類(lèi)精度的影響，本文在4組數(shù)據(jù)集上進(jìn)行了關(guān)于間隔約束γ和密度閾值δ不同取值時(shí)對(duì)分類(lèi)精度影響的實(shí)驗(yàn)。設(shè)定在蛋白質(zhì)數(shù)據(jù)集中L=3，Gene數(shù)據(jù)集中L=7，其他參數(shù)同有效性實(shí)驗(yàn)。當(dāng)某一參數(shù)變化時(shí)，其他參數(shù)保持不變。

圖3展示了BSC算法中間隔約束γ變化對(duì)分類(lèi)精度的影響。從3(a)看出，當(dāng)γ的起始位置變化而間隔大小不變時(shí)，對(duì)分類(lèi)精度的影響較小，但整體呈下降的趨勢(shì)。容易理解，相鄰的元素越接近，其間的聯(lián)系可能越強(qiáng)。如3(b)所示，在γ起始位置不變，間隔變大時(shí)，分類(lèi)精度在蛋白質(zhì)數(shù)據(jù)上變化較小，而在Gene數(shù)據(jù)上變化較大。這是因?yàn)樵贕ene數(shù)據(jù)集中找到的分類(lèi)規(guī)則比在蛋白質(zhì)數(shù)據(jù)集中挖掘的分類(lèi)規(guī)則少。當(dāng)γ變大時(shí)，更多的分類(lèi)規(guī)則將由于不滿足密度閾值而被剪枝，最終將大幅影響分類(lèi)的精度。

圖3　不同間隔約束的準(zhǔn)確率Fig. 3　Accuracy results for different gap constraints

圖4展示了BSC算法中密度閾值δ變化對(duì)分類(lèi)精度的影響。從圖4中可見(jiàn), 當(dāng)密度閾值設(shè)置過(guò)大時(shí)，兩組數(shù)據(jù)準(zhǔn)確率急劇下降，因?yàn)槊芏乳撝颠^(guò)大會(huì)有大量候選模式被剪枝，最后生成的分類(lèi)規(guī)則過(guò)少導(dǎo)致分類(lèi)精度下降。

3.5　參數(shù)設(shè)置討論

通過(guò)之前的實(shí)驗(yàn)可以看出不同參數(shù)對(duì)實(shí)驗(yàn)結(jié)果的影響，本節(jié)主要討論如何對(duì)參數(shù)進(jìn)行設(shè)置。

對(duì)于支持度閾值α和置信度閾值β，本文推薦通常情況下設(shè)置α=0.05，這個(gè)值相對(duì)比較小，能夠選出足夠的模式；β=0.5是一個(gè)比較好的選擇，可以選擇出全部有分類(lèi)能力的規(guī)則作為后面的備選。

從實(shí)驗(yàn)可見(jiàn)，間隔約束γ的初始位置和間隔的設(shè)置在數(shù)值較小時(shí)會(huì)有微小的上下波動(dòng)，但是隨著兩者數(shù)值的增大會(huì)呈現(xiàn)下降的趨勢(shì)；而隨著間隔區(qū)間的增大，算法的復(fù)雜度會(huì)不斷提升，因此本文推薦間隔約束γ的設(shè)置可以在數(shù)值較小的范圍內(nèi)使用網(wǎng)格搜索，找到對(duì)于不同數(shù)據(jù)集的最優(yōu)參數(shù)設(shè)置。

密度閾值δ的設(shè)置同樣重要，δ的值太大或者太小都對(duì)結(jié)果有較大影響。本文推薦可以從δ=0.1開(kāi)始，每次縮小到原來(lái)的1/10進(jìn)行實(shí)驗(yàn)，選擇最好的設(shè)置。

圖4　不同密度閾值的準(zhǔn)確率Fig. 4　Accuracy results for different density thresholds

4　結(jié)語(yǔ)

生物序列分類(lèi)是生命科學(xué)領(lǐng)域中的一項(xiàng)重要基礎(chǔ)問(wèn)題?，F(xiàn)有的易于解釋的基于模式的分類(lèi)算法對(duì)生物序列分類(lèi)存在分類(lèi)精度不理想、模型訓(xùn)練時(shí)間長(zhǎng)的問(wèn)題。針對(duì)這些問(wèn)題，本文考慮了蛋白質(zhì)序列和基因序列為代表的生物序列字符集規(guī)模小、序列長(zhǎng)度較長(zhǎng)的特點(diǎn)，設(shè)計(jì)了基于密度感知模式的生物序列分類(lèi)算法。在算法中引入了密度的概念，用來(lái)挖掘密度較高的頻繁模式即密度感知模式，同時(shí)采用間隔約束的方式來(lái)減少訓(xùn)練分類(lèi)模型的時(shí)間。在4組真實(shí)的生物數(shù)據(jù)集上，將BSC算法與四種序列分類(lèi)算法進(jìn)行比較，結(jié)果顯示BSC算法在分類(lèi)精度和運(yùn)行效率上具有更好的表現(xiàn)，同時(shí)展示了不同的參數(shù)設(shè)置對(duì)于算法分類(lèi)準(zhǔn)確率的影響并簡(jiǎn)要分析了原因。

在未來(lái)的工作中，將繼續(xù)改進(jìn)BSC算法，針對(duì)目前的算法需要設(shè)置較多參數(shù)的問(wèn)題作出改進(jìn)。同時(shí)，將來(lái)可以借鑒目前統(tǒng)計(jì)方法，結(jié)合模式的易于解釋性進(jìn)行更好改進(jìn)。除此之外, 將現(xiàn)有算法設(shè)計(jì)成分布式版本，利用Hadoop、Spark進(jìn)行大規(guī)模數(shù)據(jù)的序列分類(lèi)，并將其應(yīng)用于生物信息領(lǐng)域的數(shù)據(jù)分析。

致謝感謝周承博士提供的SCIS_HAR和SCIS_MA算法執(zhí)行程序。

參考文獻(xiàn):

[1]LI Y, LU Y, ZHANG F, et al. Protein classification using family profiles [C]// FSKD 2010: Proceeding of the 7th International Conference on Fuzzy Systems and Knowledge Discovery. New York: ACM, 2010: 2212-2216.

[2]楊旸.基于機(jī)器學(xué)習(xí)方法的生物序列分類(lèi)研究[D].上海:上海交通大學(xué),2009:1-2. (YANG Y. Research on biological sequence classification based on machine learning methods [D]. Shanghai: Shanghai Jiao Tong University, 2009: 1-2.)

[4]PEARSON W R, LIPMAN D J. Improved tools for biological sequence comparison [J]. Proceedings of the National Academy of Sciences of the United States of America, 1988, 85(8): 2444-2448.

[5]ALTSCHUL S F, GISH W, MILLER W, et al. Basic local alignment search tool [J]. Journal of Molecular Biology, 1990, 215(3): 403-410.

[6]DAO F-Y, YANG H, SU Z-D, et al. Recent advances in conotoxin classification by using machine learning methods [J]. Molecules, 2017, 22(7): 1057.

[7]WEI L, XING P, SHI G, et al. Fast prediction of protein methylation sites using a sequence-based feature selection technique [J]. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2017, PP(99): 1.

[8]LIU B, XU J, FAN S, et al. PseDNA-Pro:DNA-binding protein identification by combining Chou’s PseAAC and physicochemical distance transformation [J]. Molecular Informatics, 2015, 34(1): 8-17.

[9]熊贇,陳越,朱揚(yáng)勇.ProFaM:一個(gè)蛋白質(zhì)序列家族挖掘算法[J].計(jì)算研究與發(fā)展,2007,44(7):1160-1168. (XIONG Y, CHEN Y, ZHU Y Y. ProFaM: an efficient algorithm for protein sequence family mining [J]. Journal of Computer Research and Development, 2007, 44(7): 1160-1168.)

[10]ZHOU C, CULE B, GOETHALS B. Pattern based sequence classification [J]. IEEE Transactions on Knowledge and Data Engineer, 2016, 28(5): 1285-1298.

[11]MULDER N J, KERSEY P, PRUESS M, et al. In silico characterization of proteins: UniProt, InterPro and Integr8 [J]. Molecular Biotechnology, 2008, 38(2): 165-177.

[12]ZHANG M, KAO B, CHEUNG D W, et al. Mining periodic: patterns with gap requirement from sequences [C]// SIGMOD ’05: Proceeding of the 2005 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2005: 623-633.

[13]WANG X, DUANG L, DDONG G, et al. Efficient mining of density-aware distinguishing sequential patterns with gap constraints [C]// DASFAA 2014: Proceeding of the 2014 International Conference on Database Systems for Advanced Applications, LNCS 8421. Cham: Springer, 2014: 372-387.

[14]TSENG V S, LEE C-H. Effective temporal data classification by integrating sequential pattern mining and probabilistic induction [J]. Expert Systems with Applications, 2009, 36(5): 9524-9532.

[15]LIU B, HSU W, MA Y. Integrating classification and association rule mining [C]// KDD’98： Proceeding of the 4th International Conference on Knowledge Discovery and Data Mining. Menlo Park, CA: AAAI Press, 1998: 80-86.

[16]LIN H, CHEN W. Prediction of thermophilic proteins using feature selection technique [J]. Journal of Microbiological Methods, 2010, 84(1): 67-70.

[17]TANG H, ZOU P, ZHANG C M, et al. Identification of using feature selection technique [J]. Scientific Reports 6, 2016: 30441.

[18]HALL M, FRANK E, HOLMES G, et al. The WEKA data mining software: an update [J]. ACM SIGKDD Explorations, 2009, 11(1): 10-18.