亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        基于密度感知模式的生物序列分類(lèi)算法

        2018-04-12 07:15:39胡耀煒
        計(jì)算機(jī)應(yīng)用 2018年2期
        關(guān)鍵詞:間隔閾值長(zhǎng)度

        胡耀煒,段 磊,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.

        猜你喜歡
        間隔閾值長(zhǎng)度
        間隔問(wèn)題
        1米的長(zhǎng)度
        小波閾值去噪在深小孔鉆削聲發(fā)射信號(hào)處理中的應(yīng)用
        間隔之謎
        基于自適應(yīng)閾值和連通域的隧道裂縫提取
        愛(ài)的長(zhǎng)度
        怎樣比較簡(jiǎn)單的長(zhǎng)度
        比值遙感蝕變信息提取及閾值確定(插圖)
        河北遙感(2017年2期)2017-08-07 14:49:00
        室內(nèi)表面平均氡析出率閾值探討
        不同長(zhǎng)度
        淫欲一区二区中文字幕| 亚洲自拍偷拍色图综合| 在线精品国产亚洲av麻豆| 四虎影视久久久免费观看| 亚洲熟女乱色一区二区三区| 精品国产一区二区三区久久女人| 男女视频在线观看一区二区| 色爱情人网站| 97伦伦午夜电影理伦片| 国产高清在线精品一区αpp| 中文字幕一二区中文字幕| 婷婷久久av综合一区二区三区| 少妇中文字幕乱码亚洲影视| 国产人妻黑人一区二区三区 | 加勒比日本东京热1区| 男男做h嗯啊高潮涩涩| 国产成人精品无码一区二区三区| 一个人在线观看免费视频www| 26uuu欧美日本在线播放| 久久亚洲av午夜福利精品西区| 免费亚洲一区二区三区av| 精精国产xxxx视频在线播放 | 久久夜色国产精品噜噜亚洲av| 欧美video性欧美熟妇| 国产亚洲精品久久久久久| 亚洲国产日韩在线人成蜜芽| 美女一区二区三区在线视频| 成人免费看aa片| 婷婷丁香社区| 抖射在线免费观看视频网站| av在线免费观看网站免费| 欧美天天综合色影久久精品| 亚洲欧美日韩中文字幕网址 | 日本不卡视频一区二区| 久久久久亚洲av成人网人人网站 | 久久开心婷婷综合中文| 又湿又紧又大又爽a视频国产| 人人做人人妻人人精| 青青草视频国产在线观看| 国产白浆一区二区三区性色| 国产乱人伦在线播放|