袁 健，趙 樺，張 明，張勁松

1(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093) 2(海軍軍醫(yī)大學(xué) 教研保障中心，上海 200433) 3(中國(guó)科學(xué)院 上海生命科學(xué)研究院，上海 200031)

1 引 言

自然界存在多種多樣的病菌，如何有效地將人類(lèi)新發(fā)現(xiàn)的細(xì)菌快速加以鑒別、分類(lèi)，以便選擇有效藥物進(jìn)行治療，在生物醫(yī)學(xué)領(lǐng)域具有重要意義.革蘭氏染色法用于鑒別細(xì)菌[1]，可以把眾多的細(xì)菌分為兩大類(lèi)，革蘭氏陽(yáng)性菌和革蘭氏陰性菌[2].大多數(shù)化膿性球菌屬于革蘭氏陽(yáng)性菌，它們能產(chǎn)生外毒素使人致病，而大多數(shù)腸道菌屬于革蘭氏陰性菌，它們產(chǎn)生內(nèi)毒素，靠?jī)?nèi)毒素使人致病.在治療上，大多數(shù)革蘭氏陽(yáng)性菌都對(duì)青霉素敏感，而革蘭氏陰性菌則對(duì)青霉素不敏感，卻對(duì)鏈霉素、氯霉素等敏感.所以區(qū)分出病原菌是革蘭氏陽(yáng)性菌還是陰性菌，在選擇抗生素方面意義重大.

目前細(xì)菌分類(lèi)方法主要是革蘭氏染色法.然而，染色時(shí)會(huì)發(fā)現(xiàn)某些革蘭氏陽(yáng)性菌褪色，某些革蘭氏陰性菌會(huì)由于菌齡或培養(yǎng)基的不同而產(chǎn)生黑色的染色粒，同時(shí)染色程序較為復(fù)雜，由于細(xì)胞培養(yǎng)時(shí)間過(guò)長(zhǎng)可能導(dǎo)致部分細(xì)胞發(fā)生死亡或自溶，從而導(dǎo)致染色結(jié)果為假陰性.革蘭氏染色法借助細(xì)菌不同的細(xì)胞壁結(jié)構(gòu)引起的染色性差異來(lái)進(jìn)行分類(lèi)，但是涂片的厚薄和脫色時(shí)間的掌握制約著該方法的準(zhǔn)確性，這已成為未知細(xì)菌的準(zhǔn)確和快速分類(lèi)的瓶頸.隨著第3代測(cè)序技術(shù)和質(zhì)譜技術(shù)的成熟，大家已能夠很方便和快速地獲得細(xì)菌的蛋白質(zhì)序列.因此，本文開(kāi)創(chuàng)性地研究了利用計(jì)算機(jī)對(duì)細(xì)菌的蛋白質(zhì)序列進(jìn)行特征分析和提取來(lái)進(jìn)行細(xì)菌的革蘭氏陰陽(yáng)性判別的算法，經(jīng)實(shí)驗(yàn)證明效果良好.

本文主要完成以下3項(xiàng)工作：

1)提出利用細(xì)菌蛋白質(zhì)序列進(jìn)行細(xì)菌的革蘭氏陰陽(yáng)性判別算法GCBPS算法；

2)用實(shí)驗(yàn)驗(yàn)證選用閉合鄰接序列模式(FCloConSP)的GCBPS算法進(jìn)行細(xì)菌革蘭氏陰陽(yáng)性判別的準(zhǔn)確性以及可行性；

3)用FConSP替代GCBPS算法中的FCloConSP后生成GCBPS-X算法，比較GCBPS和GCBPS-X的準(zhǔn)確性，以及FCloConSP相比FConSP的精簡(jiǎn)性，驗(yàn)證GCBPS算法的優(yōu)化性.

2 相關(guān)工作

目前對(duì)細(xì)菌的分類(lèi)方法主要有以下幾種，其中由丹麥醫(yī)生革蘭于1884年發(fā)明的革蘭氏染色法為主要的鑒別染色法[1].革蘭氏染色法根據(jù)細(xì)菌體內(nèi)含有特殊的核蛋白質(zhì)鎂鹽與多糖的復(fù)合物與燃料的吸附性進(jìn)行分類(lèi)，但是，該方法結(jié)果容易受許多因素的影響，比如菌齡和乙醇脫色時(shí)間對(duì)染色結(jié)果的影響.針對(duì)革蘭氏染色法操作復(fù)雜以及容易脫色的缺點(diǎn)，有一些可克服上述缺點(diǎn)的輔助方法，如氨肽酶法、吖啶橙染色法.此外還有利用氫氧化鉀溶液對(duì)細(xì)菌進(jìn)行分類(lèi)[3]，此類(lèi)輔助方法相比革蘭氏染色法而言操作更加簡(jiǎn)便，時(shí)間較快.此外，基于聲光可調(diào)濾光片(AOTF)的高光譜顯微鏡成像(HMI)方法具有從細(xì)胞水平上快速鑒定微菌落中食源性致病細(xì)菌的潛力，文獻(xiàn)[4]利用高光譜顯微鏡成像方法對(duì)革蘭氏陽(yáng)性和革蘭氏陰性食源性致病菌進(jìn)行分類(lèi)以及文獻(xiàn)[5]利用利用拉曼光譜法對(duì)革蘭氏陰陽(yáng)性細(xì)胞結(jié)構(gòu)所接受的拉曼散射強(qiáng)度不同來(lái)進(jìn)行細(xì)菌對(duì)革蘭氏陰陽(yáng)性判別.鑒于序列特征研究的廣泛應(yīng)用[6]，為了更快速、方便地實(shí)現(xiàn)細(xì)菌的革蘭氏陰陽(yáng)性判別，本文研究對(duì)細(xì)菌的蛋白質(zhì)序列進(jìn)行智能分析來(lái)判別其革蘭氏陰陽(yáng)性的算法.

近年來(lái)，利用序列來(lái)分類(lèi)在很多領(lǐng)域應(yīng)用頗多，尤其在基因組研究中引起了廣泛的關(guān)注[7，8]，比如，利用樸素貝葉斯對(duì)rRNA序列進(jìn)行分類(lèi)[9]歸到Bergey的《原核生物分類(lèi)大綱》.在一條生物序列中，每一項(xiàng)(核酸或氨基酸)都有著不同的關(guān)系，并不同以往的頻繁項(xiàng)集與關(guān)聯(lián)規(guī)則中的項(xiàng)出現(xiàn)的順序[10]，這種序列分析工作又被稱(chēng)為序列模式挖掘，主要研究如何有效地發(fā)現(xiàn)序列中能代表核心特征的一般序列模式(General Sequential Pattern)或精簡(jiǎn)序列模式(Compact Sequential Pattern)[11，12].由于，精簡(jiǎn)序列模式可以產(chǎn)生相對(duì)少量但分類(lèi)效果、信息承載能力與一般序列模式相當(dāng)?shù)男蛄心Ｊ絒13，14].所以本文采用精簡(jiǎn)序列模式來(lái)分析蛋白質(zhì)序列.

在精簡(jiǎn)序列模式分析下，本文提出了基于蛋白質(zhì)序列特征分析的細(xì)菌革蘭氏陰陽(yáng)性判別算法(Gram Classification algorithm for Bacteria based on Protein Sequences，GCBPS)，從而實(shí)現(xiàn)對(duì)蛋白質(zhì)序列進(jìn)行精簡(jiǎn)序列模式的挖掘和特征的提取以及對(duì)革蘭氏陰陽(yáng)性的判別.此算法僅需對(duì)細(xì)菌的蛋白質(zhì)序列進(jìn)行計(jì)算機(jī)軟件處理，無(wú)需再進(jìn)行生物實(shí)驗(yàn).該方法對(duì)硬件條件要求低，判別時(shí)間短，準(zhǔn)確性較高.

3 相關(guān)定義與問(wèn)題陳述

3.1 相關(guān)定義

定義1.(鄰接子序列)

若序列S1=，S2=，若序列當(dāng)存在整數(shù)z1，z2，…，zi，滿(mǎn)足1≤z1

定義2.(鄰接序列模式)

指定一個(gè)支持度閾值σ，若一個(gè)鄰接子序列s滿(mǎn)足SupD(s)≥σ，其中SupD(s)表示s支持度，則s為鄰接序列模式.

定義3.(閉合鄰接模式)

若一個(gè)鄰接序列模式s滿(mǎn)足不存在一個(gè)鄰接序列模式s1，同時(shí)使s?s1和SupD(s)=SupD(s1)成立，則s為閉合鄰接序列模式.

定義4.(前后子序列)

給定兩個(gè)序列s1=和s2=，如果s1是s2的前子序列，則需同時(shí)滿(mǎn)足：s1的長(zhǎng)度≥1，s2的長(zhǎng)度比s1的長(zhǎng)度大1，并且x1=y1，x2=y2，…，xi=yj-1.相應(yīng)地，如果s1是s2的后子序列，則需同時(shí)滿(mǎn)足s1的長(zhǎng)度≥1，并且s2的長(zhǎng)度比s1的長(zhǎng)度大1以及x1=y2，x2=y3，…，xi=yj.前子序列和后子序列統(tǒng)稱(chēng)為前后子序列.

3.2 問(wèn)題陳述

需解決的問(wèn)題如下：

采用第3代測(cè)序技術(shù)和質(zhì)譜技術(shù)可輕松得到細(xì)菌的蛋白質(zhì)序列，因此先把若干已知陰陽(yáng)性的細(xì)菌蛋白質(zhì)序列組成序列數(shù)據(jù)庫(kù)Seq-D，如表1中1條蛋白質(zhì)短序列組成的序列數(shù)據(jù)庫(kù)Seq-D所示(第1列為序列的ID，第2列為某細(xì)菌的蛋白質(zhì)序列.示例中的序列由A、B、C，3種不同項(xiàng)(核酸或氨基酸)組成，長(zhǎng)度為13.)然后挖掘Seq-D中的精簡(jiǎn)序列模式，找出細(xì)菌的革蘭氏陰陽(yáng)性判別的特征，并提出細(xì)菌的革蘭氏陰陽(yáng)性判別算法.

表1 含一個(gè)序列的數(shù)據(jù)庫(kù)Seq-D樣例Table 1 An example sequence database Seq-D

精簡(jiǎn)序列模式又分為頻繁模式(FSP)、鄰接序列模式(FConSP)、閉合鄰接模式(FCloConSP)3種.若設(shè)定支持度σ為2，分別用上述3種模式對(duì)表1中的序列進(jìn)行挖掘，結(jié)果如表2所示.其中第2列中，具體的模式項(xiàng)以及模式對(duì)應(yīng)的支持度以“：”分隔，各模式項(xiàng)間用“，”分隔，其FSP有17個(gè)模式項(xiàng)，F(xiàn)ConSP有7個(gè)模式項(xiàng)，而FCloConSP有5個(gè)，由以上結(jié)果可見(jiàn)，同一支持度下，F(xiàn)SP的模式項(xiàng)數(shù)目最多，F(xiàn)CloConSP的模式項(xiàng)數(shù)目最少.

由一般經(jīng)驗(yàn)可知，3種序列模式中，所包含的模式項(xiàng)數(shù)目越多其保留的特征也越多，故應(yīng)選擇FSP來(lái)分析.但是從表2可看出FSP的模式項(xiàng)數(shù)目遠(yuǎn)大于其它兩種模式，而表2所分析的序列只包含了3種氨基酸，長(zhǎng)度只有13，實(shí)際的蛋白質(zhì)序列的氨基酸可多達(dá)20種，一個(gè)序列長(zhǎng)度可能長(zhǎng)達(dá)上千.可想而知，選擇FSP分析序列，后續(xù)的計(jì)算量巨大，這不是一種好的選擇.因此，若能保證正確率的情況下，選擇更精簡(jiǎn)和有效的模式，即性?xún)r(jià)比更高的序列模式，其處理時(shí)間短，更具有實(shí)用價(jià)值.故考慮從FConSP或FCloConSP產(chǎn)生的模式項(xiàng)中尋找特征完成判別.FConSP的數(shù)據(jù)量大于FCloConSP，若FCloConSP數(shù)據(jù)無(wú)法支撐準(zhǔn)確性，則需考慮FConSP.若FConSP和FCloConSP均能保證準(zhǔn)確性，則選擇FCloConSP更優(yōu).本文經(jīng)過(guò)大量實(shí)驗(yàn)，最終設(shè)計(jì)了使用FCloConSP模式的數(shù)據(jù)分析的判別算法.

表2 3種序列模式對(duì)比Table 2 Comparison of three sequential patterns

4 GCBPS算法

GCBPS算法的流程圖如圖1所示.

該算法先對(duì)給定的已知陰陽(yáng)性的序列數(shù)據(jù)庫(kù)Seq-D進(jìn)行數(shù)據(jù)預(yù)處理，將Seq-D中的序列處理為特定的數(shù)據(jù)結(jié)構(gòu)(S.id，S)，然后針對(duì)蛋白質(zhì)序列分析的特點(diǎn)改進(jìn)了閉合鄰接模式的挖掘算法CCSpan，對(duì)訓(xùn)練集數(shù)據(jù)庫(kù)中每條序列通過(guò)候選集生成、剪枝操作、閉合性篩選來(lái)挖掘FCloConSP，可以分別累計(jì)得到陰性的訓(xùn)練集閉合鄰接模式特征集合和陽(yáng)性的訓(xùn)練集閉合鄰接模式特征集合.接著對(duì)陽(yáng)性訓(xùn)練集特征集合進(jìn)行標(biāo)準(zhǔn)化和向量化，得到陽(yáng)性特征向量.

對(duì)待測(cè)蛋白質(zhì)序列進(jìn)行挖掘FConSP，得到待測(cè)鄰接序列模式特征集合，再經(jīng)過(guò)向量化處理得到待測(cè)序列特征向量.先計(jì)算待測(cè)向量與陽(yáng)性特征向量的相似度，結(jié)果若在區(qū)間[0.8，1]，則待測(cè)序列為陽(yáng)性.若相似性結(jié)果不在此區(qū)間，則初步判定為陰性，其實(shí)這些序列并不一定全是陰性，還存在假陰性(陽(yáng)性).因此，需進(jìn)行去假陰性處理.經(jīng)實(shí)驗(yàn)發(fā)現(xiàn)直接把待測(cè)序列向量與前述方法得出的陰性特征向量比對(duì)，其正確率受限，因此經(jīng)過(guò)大量試驗(yàn)后修正了陰性特征庫(kù)，即把原求出的陰性特征集中長(zhǎng)度為2的模式項(xiàng)去掉作為修正的陰性特征集合，再進(jìn)行標(biāo)準(zhǔn)化和向量化，得到陰性特征向量.將非陽(yáng)性待測(cè)向量與陰性特征向量進(jìn)行相似度計(jì)算，若相似性結(jié)果在區(qū)間[0.8，1]，則為陰性序列，否則為陽(yáng)性序列.由此可得出最終的陰陽(yáng)性判定結(jié)果.

圖1 GCBPS算法流程圖Fig.1 GCBPS algorithm flowchart

4.1 陰陽(yáng)序列特征庫(kù)生成

CCSpan算法[15]用于挖掘一個(gè)序列數(shù)據(jù)庫(kù)的指定支持度模式集合，GCBPS算法中的序列模式挖掘部分引入了CCSpan算法的主要思想，與原CCSpan算法不同的是，GCBPS算法只挖掘單條序列的FCloConSP，更有利于保持源序列庫(kù)中每條序列的特征.在取得Seq-D中每條序列的FCloConSP后，依次輸入該序列數(shù)據(jù)庫(kù)中的下一條序列繼續(xù)挖掘，直至該序列數(shù)據(jù)庫(kù)循環(huán)結(jié)束.此算法設(shè)計(jì)了以下幾種特殊的數(shù)據(jù)結(jié)構(gòu)，便于實(shí)驗(yàn)計(jì)算：

1.作為輸入的序列數(shù)據(jù)庫(kù)Seq-D由一個(gè)二元結(jié)構(gòu)(S.id，S)組成，其中S.id為此序列的ID編號(hào)，S則為序列本身.

2.閉合鄰接序列模式與非閉合鄰接序列模式以一個(gè)三元結(jié)構(gòu)組成(s，s.count，B)，其中f表示模式，s.count表示該模式在序列數(shù)據(jù)庫(kù)D上的頻數(shù)，即實(shí)際支持度，而B(niǎo)中有兩種值：“Y”代表模式閉合，“N”代表非閉合模式.

3.一條序列F可以分割成若干個(gè)不相交的子集合，即{{F1}，{F2}，…，{Fn}}，其中n是最大的模式長(zhǎng)度，F(xiàn)中每個(gè)子集僅僅包含單一長(zhǎng)度(n)的模式.

本文通過(guò)以下3步來(lái)實(shí)現(xiàn)FCloConSP的挖掘：

Step 1.取數(shù)據(jù)庫(kù)Seq-D的每一個(gè)序列S(S.id，S)按照設(shè)定的切分長(zhǎng)度切分成一系列的片段，這些片段中所有的項(xiàng)均保持原有的順序和鄰接屬性.初始切分長(zhǎng)度為2，當(dāng)一輪切分片段結(jié)束后，再把上一輪切分長(zhǎng)度+1進(jìn)行下一輪切分，一直到切分長(zhǎng)度等于原始序列長(zhǎng)度時(shí)，切分結(jié)束.得到的片段為候選片段.此時(shí)切分序列產(chǎn)生的集合為{{F1}，{F2}，…，{Fn}}，其中每個(gè)子片段為鄰接序列模式，其結(jié)構(gòu)為(s，s.count，B).

Step 2.采用CCSpan算法中的剪枝方法(前后子序列剪枝、支持度剪枝)對(duì)Step 1產(chǎn)生的候選片段進(jìn)行剪枝，刪除已經(jīng)出現(xiàn)過(guò)的片段和不滿(mǎn)足支持度要求(s.count<σ)的片段.經(jīng)剪枝后的候選片段仍為鄰接序列模式.

Step 3.對(duì)Step 2得到的鄰接序列模式進(jìn)行閉合性檢查[15]，則篩選出所有的非閉合鄰接序列模式并標(biāo)識(shí)即(s，s.count，B)中B標(biāo)識(shí)為“N”，從而以B=“Y”可篩選出該序列的閉合鄰接序列模式.

Step 4.取數(shù)據(jù)庫(kù)Seq-D中的下一條序列重復(fù)Step 1-Step 3得到該條序列的FCloConSP.將所有的上述序列的FCloConSP按照已知的陰陽(yáng)性放入陰性特征庫(kù)與陽(yáng)性特征庫(kù).若陽(yáng)性特征庫(kù)內(nèi)或陰性特征庫(kù)內(nèi)中有若干相同的模式項(xiàng)s時(shí)，則把s.count進(jìn)行累加后合并為一個(gè)模式項(xiàng).合并處理后每個(gè)模式項(xiàng)只出現(xiàn)1次.最終的結(jié)果就是陰性訓(xùn)練集特征庫(kù)和陽(yáng)性訓(xùn)練集特征庫(kù).記為：

LCloConSPs=[s1：s1.count，s2：s2.count，s3：s3.count，…，sn：sn.count].

為實(shí)現(xiàn)算法的軟件編程，此部分設(shè)計(jì)了以下幾個(gè)函數(shù)：

1)函數(shù)snip()：作用為獲得所有長(zhǎng)度為1的頻繁模式，該結(jié)果用于得到長(zhǎng)度為2的頻繁模式.在F1中每一個(gè)候選子序列實(shí)際支持度都不小于給定的閾值σ，其中每個(gè)模式都以三元組(s，s.count，Y)形式表示，標(biāo)記Y為默認(rèn)值.

2)函數(shù)ConSP-snip()：其作用為存儲(chǔ)當(dāng)下長(zhǎng)度的所有模式片段的Pn作為輸入，以挖掘長(zhǎng)度大于等于2的鄰接序列模式.經(jīng)過(guò)3步剪枝操作，Pn會(huì)不斷更新已檢測(cè)片段.

3)函數(shù)CloConSP-snip()：其作用為得到最后所需的閉合鄰接序列三元組.根據(jù)3.1定義中閉合鄰接序列的定義進(jìn)行閉合性檢測(cè)，可得包含閉合模式與非閉合模式的集合.

4)函數(shù)Count-Patterns()：最作用為統(tǒng)計(jì)由FCloConSP所產(chǎn)生的訓(xùn)練集合，其中LCloConSPs存儲(chǔ)陰陽(yáng)性訓(xùn)練集集合的FCloConSP.

4.2 陰陽(yáng)相似性判別

4.2.1 相似度計(jì)算

余弦相似度[16]用向量空間中兩個(gè)向量夾角的余弦值作為衡量?jī)蓚€(gè)個(gè)體間差異的大小.余弦值越接近1，表明夾角越接近0度，則兩個(gè)個(gè)體越相似.余弦距離更多的是從方向上區(qū)分差異，而對(duì)絕對(duì)的數(shù)值不敏感.所選用的公開(kāi)數(shù)據(jù)集中革蘭氏陰性菌的蛋白質(zhì)序列數(shù)量遠(yuǎn)大于陽(yáng)性菌的蛋白質(zhì)序列數(shù)量，在實(shí)際中亦是如此，本文在基礎(chǔ)的余弦相似度公式上增加了參數(shù)k，目的是在計(jì)算過(guò)程中，通過(guò)參數(shù)k對(duì)模式的頻數(shù)進(jìn)行篩選，過(guò)濾不必要的模式，降低了數(shù)據(jù)的計(jì)算時(shí)間復(fù)雜度，如公式(1)所示.經(jīng)過(guò)大量的實(shí)驗(yàn)計(jì)算得出，當(dāng)k為每組訓(xùn)練集中所有模式項(xiàng)的頻數(shù)的中位數(shù)時(shí)，刪掉頻數(shù)小于k的模式項(xiàng)后的精簡(jiǎn)訓(xùn)練集集合參加判別更準(zhǔn)確.在訓(xùn)練集中，與待測(cè)序列的鄰接序列模式取交集(若訓(xùn)練集中無(wú)此模式，則頻數(shù)置為0)，并以模式頻數(shù)構(gòu)建向量，利用公式(1)可計(jì)算待測(cè)序列向量與該組陰(陽(yáng))性訓(xùn)練集的余弦相似度.

(1)

其中x，y為待比較的兩個(gè)向量.

4.2.2 陰陽(yáng)性判別主要步驟

Step 1.統(tǒng)計(jì)得到陰陽(yáng)性訓(xùn)練集特征庫(kù)中的模式項(xiàng)頻數(shù)的中位數(shù)k，并過(guò)濾陰陽(yáng)性特征庫(kù)中模式項(xiàng)頻數(shù)小于k的模式項(xiàng)，即對(duì)LCloConSP中si.count≤k(1≤i≤n)的模式刪除，從而進(jìn)行標(biāo)準(zhǔn)化.

Step 2.將標(biāo)準(zhǔn)化后的陽(yáng)性訓(xùn)練集集合與待測(cè)序列取交集，若訓(xùn)練集中無(wú)此模式，則頻數(shù)置為0，并以訓(xùn)練集集合以及待測(cè)序列集合中模式頻數(shù)(si.count)分別向量化，即T=[s1.count，s2.count，s3.count；…，sn.count]，利用公式(1)求得待測(cè)序列與陽(yáng)性訓(xùn)練集向量的余弦相似度，結(jié)果若在[0.8，1]則判定為陽(yáng)性.

Step 3.得到第1步判別結(jié)果后，對(duì)于相似性結(jié)果在[0，0.8)的序列，會(huì)出現(xiàn)假陰性性狀.因此先將陰性特征訓(xùn)練集集合刪除模式長(zhǎng)度為2的模式，然后進(jìn)行Step 2中標(biāo)準(zhǔn)化以及向量化得到陰性訓(xùn)練集向量，最后利用公式(1)求得待測(cè)序列與陰性訓(xùn)練集向量的余弦相似度，結(jié)果若在[0.8，1]則判定為陰性，否則為陽(yáng)性.綜合兩步判別結(jié)果得到最終待測(cè)序列的陰陽(yáng)性.

此部分的主要函數(shù)為：

函數(shù)Cosin-S()：用于對(duì)向量化后的訓(xùn)練集以k值進(jìn)行標(biāo)準(zhǔn)化，并得到測(cè)試集與陰陽(yáng)性訓(xùn)練集的余弦相似度Cosine_sim.其中，TN、TP為陰陽(yáng)性訓(xùn)練集的向量，Ttest測(cè)試集中單條序列的向量.

4.3 算法過(guò)程

GCBPS算法主要由兩部分組成:1)為陰陽(yáng)性訓(xùn)練集與測(cè)試集模式集合挖掘；2)為測(cè)試序列與陰陽(yáng)性訓(xùn)練集的相似性計(jì)算.

以下為GCBPS算法偽代碼，其中：原始的序列數(shù)據(jù)庫(kù)為Seq-D，最小支持度為σ.F存儲(chǔ)所有的鄰接序列模式，F(xiàn)n存儲(chǔ)長(zhǎng)度為n的序列模式.F1存儲(chǔ)模式長(zhǎng)度為1的頻繁模式.模式集合F= {s，s.count，B}|f.count≥σ}為所挖掘頻繁模式的訓(xùn)練集集合.集合LCloConSPs={(s，s.count，B)|f.count≥σ}存儲(chǔ)序列數(shù)據(jù)庫(kù)中全部序列挖掘的FCloConSP.LTest={(s，s.count，B)|f.count≥σ}存儲(chǔ)一條待測(cè)序列的FConSP集合.陰性訓(xùn)練集向量為T(mén)N，陽(yáng)性訓(xùn)練集向量為T(mén)P，測(cè)試集向量為T(mén)Test.

算法GCBPS：

輸入：由待測(cè)序列組成的序列數(shù)據(jù)庫(kù)Seq-D，以及支持度 σ

輸出：Seq-D中各序列的S.id與該序列革蘭氏陰陽(yáng)性判別結(jié)果

Begin：

F←φ；//以F存儲(chǔ)CloConSPs

Fn←φ；//以Fn存儲(chǔ)長(zhǎng)度為n的ConSPs

F1←snip//(Seq-D，σ)//獲得1-sequences

1.for(n=2；Fn-1≠φ；n++)do

2.Pn←φ//以Pn存儲(chǔ)當(dāng)前切分長(zhǎng)度片段

3.foreach sequence S ∈Seq-Dand l(S)≥ ndo

4.foreach con subsequence s ∈ S and l(s)= ndo

5. ConSP-snip(Seq-D，s，F(xiàn)n-1，Pn，S.id，σ)；//獲得ConSPs

6.endfor

7.endfor

8.Fn-1←CloConSP-snip(Fn-1，F(xiàn)n)；//獲得CloConSPs

9.F←∪n-1Fn-1；

10.endfor

11.LCloConSPs，LTest←Count-Patterns(F)//獲得模式集合

12.TP←LCloConSPs//訓(xùn)練集集合向量化

13.TTest←LTest//測(cè)試序列模式集合向量化

14.Cosine_sim←Cosin-S(TP，Ttest)//相似度計(jì)算

15.ifCosine_sim ∈ [0.8，1]：

16. 待測(cè)序列為陽(yáng)性

17.else：TN←刪除LCloConSPs中長(zhǎng)度為2的模式

18. Cosine_sim←Cosin-S(TN，Ttest)

19.ifCosine_sim∈[0.8，1]：

20. 待測(cè)序列為陰性

21.else：待測(cè)序列為陽(yáng)性

End

5 實(shí) 驗(yàn)

為了驗(yàn)證GCBPS算法的準(zhǔn)確性、可行性及優(yōu)化性，設(shè)計(jì)和完成了以下兩個(gè)實(shí)驗(yàn).

5.1 實(shí)驗(yàn)設(shè)置

論文選取蛋白質(zhì)序列公開(kāi)數(shù)據(jù)集PSORTb v3.0(1)https：//www.psort.org/dataset/datasetv2.html.該數(shù)據(jù)集中包含1591條革蘭氏陰性菌蛋白質(zhì)序列和576條革蘭氏陽(yáng)性菌蛋白質(zhì)序列.本文實(shí)驗(yàn)選取10折交叉驗(yàn)證，即1將數(shù)據(jù)集分成10組，輪流將其中9組做訓(xùn)練1組做驗(yàn)證，10次所得結(jié)果均值為算法精度的估計(jì).本實(shí)驗(yàn)中，采用精準(zhǔn)率P、召回率R、值F1-score作為實(shí)驗(yàn)的主要評(píng)價(jià)指標(biāo)[17]，計(jì)算方法如公式(2)-公式(4)所示.其中：TP：表示測(cè)試集中正確的把陰(陽(yáng))性菌預(yù)測(cè)為陰(陽(yáng))性的序列個(gè)數(shù)；FN：表示測(cè)試集中錯(cuò)誤的把陰性菌預(yù)測(cè)為陽(yáng)性的序列個(gè)數(shù)；FP：表示測(cè)試集中錯(cuò)誤的把陽(yáng)性菌預(yù)測(cè)為陰性的序列個(gè)數(shù).F1值為綜合度量準(zhǔn)確率和召回率的指標(biāo).

(2)

(3)

(4)

5.2 實(shí)驗(yàn)及結(jié)果分析

實(shí)驗(yàn)將數(shù)據(jù)集中的1591條革蘭氏陰性菌蛋白質(zhì)序列和576條革蘭氏陽(yáng)性菌蛋白質(zhì)序列放入1個(gè)數(shù)據(jù)庫(kù)中，再將數(shù)據(jù)集均勻分為10組，每組包含革蘭氏陽(yáng)性菌約57條，革蘭氏陰性菌約159條，其中1組作為測(cè)試集，余下9組作為訓(xùn)練集，依次進(jìn)行10組實(shí)驗(yàn).

實(shí)驗(yàn)1.驗(yàn)證GCBPS算法的準(zhǔn)確性與可行性

實(shí)驗(yàn)的步驟為：

Step 1.取1組序列作為測(cè)試組，從中取1條未測(cè)序列作為待測(cè)序列，剩下9組數(shù)據(jù)序列，放入GCBPS的序列數(shù)據(jù)庫(kù)Seq-D；

Step 2.按GCBPS的方法判別出序列的陰陽(yáng)性，即把數(shù)據(jù)帶入事先編寫(xiě)好的算法程序運(yùn)行得出結(jié)果；

Step 3.記錄算法得出的序列陰陽(yáng)性結(jié)果與實(shí)際的陰陽(yáng)性結(jié)果；

Step 4.若測(cè)試組的序列未測(cè)試完，則重復(fù)Step 1-Step 3.若測(cè)試完，則計(jì)算該組評(píng)估指標(biāo)(P、R、F1-score)，并進(jìn)入Step 5；

Step 5.依次更換其余9組輪流作為測(cè)試組，重復(fù)Step 1-Step 4，得到10組的評(píng)估指標(biāo)，并計(jì)算平均值，如表3所示.

用GCBPS算法對(duì)細(xì)菌進(jìn)行革蘭氏陰陽(yáng)性判別結(jié)果的實(shí)驗(yàn)評(píng)價(jià)指標(biāo)如表3所示.本實(shí)驗(yàn)在支持度σ=2 的條件下，分別從10組實(shí)驗(yàn)的精確率、召回率以及F1值來(lái)判斷該算法的準(zhǔn)確性及可行性.

表3 GCBPS算法10組實(shí)驗(yàn)評(píng)價(jià)指標(biāo)Table 3 GCBPS algorithm 10 groups of experimental evaluation indicators

F1是綜合度量準(zhǔn)確率和召回率的指標(biāo)，由表3可看出第3組實(shí)驗(yàn)F1值最高為99.05%，10組的平均F1值為95.40%，所以GCBPS算法判別細(xì)菌的革蘭氏陰陽(yáng)性的結(jié)果較準(zhǔn)確.因此可以得出：不進(jìn)行生物實(shí)驗(yàn)，直接采用實(shí)現(xiàn)GCBPS算法的計(jì)算機(jī)軟件進(jìn)行細(xì)菌的革蘭氏陰陽(yáng)性判別方法是準(zhǔn)確的和可行的.

實(shí)驗(yàn)2.驗(yàn)證GCBPS中選擇FCloConSP的精簡(jiǎn)性與優(yōu)化性

本組實(shí)驗(yàn)選取支持度σ=2，用FConSP替代GCBPS算法中對(duì)訓(xùn)練集進(jìn)行特征提取的步驟，其余步驟相同，為以示區(qū)別，后稱(chēng)為GCBPS-X算法.

其實(shí)驗(yàn)步驟為：

Step 1.按實(shí)驗(yàn)1的方法步驟并跳過(guò)5.1中的Step 3后運(yùn)行；

Step 2.記錄GCBPS-X算法的評(píng)估結(jié)果；

Step 3.統(tǒng)計(jì)GCBPS算法中產(chǎn)生的FCloConSP訓(xùn)練集特征庫(kù)模式項(xiàng)的種類(lèi)及個(gè)數(shù).

Step 4.統(tǒng)計(jì)GCBPS-X算法中產(chǎn)生的FConSP訓(xùn)練集特征庫(kù)模式項(xiàng)的種類(lèi)及個(gè)數(shù).

由實(shí)驗(yàn)可得FConSP下的10組實(shí)驗(yàn)的評(píng)價(jià)指標(biāo)由表4可見(jiàn)，圖2-圖4分別為GCBPS算法與GCBPS-X算法兩種模式準(zhǔn)確率、召回率、F1值對(duì)比.

由表3可知，GCBPS判別實(shí)驗(yàn)F1值均值為95.40%；由表4可知，GCBPS-X判別實(shí)驗(yàn)F1值均值為94.26%.因此，GCBPS算法比GCBPS-X算法綜合準(zhǔn)確率高.由圖2可知有6組實(shí)驗(yàn)的準(zhǔn)確率是GCBPS高于GCBPS-X；由圖3可知有8組實(shí)驗(yàn)的召回率是GCBPS高于GCBPS-X；由圖4可知有6組實(shí)驗(yàn)的F1值是GCBPS高于GCBPS-X，由此可見(jiàn)GCBPS比GCBPS-X的判別準(zhǔn)確率更高.

表4 GCBPS-X算法10組實(shí)驗(yàn)評(píng)價(jià)指標(biāo)Table 4 GCBPS-X algorithm 10 groups ofexperimental evaluation indicators

接下來(lái)進(jìn)行兩種算法中模式項(xiàng)的精簡(jiǎn)性對(duì)比.圖5為革蘭氏陰性菌GCBPS與GCBPS-X兩種算法中模式項(xiàng)數(shù)目的對(duì)比圖，其中橫坐標(biāo)為模式項(xiàng)的長(zhǎng)度，縱坐標(biāo)為模式項(xiàng)的數(shù)目.在陰性菌序列數(shù)據(jù)庫(kù)中，F(xiàn)ConSP共有130978個(gè)模式項(xiàng)，F(xiàn)CloConSP有11064個(gè)模式項(xiàng)，由此可見(jiàn)，F(xiàn)CloConSP的數(shù)目遠(yuǎn)遠(yuǎn)小于FConSP.由圖5可以看出兩條曲線(xiàn)在同一支持度下(σ = 2)呈下降趨勢(shì)，F(xiàn)CloConSP的模式項(xiàng)主要集中在長(zhǎng)度為3和4之間，分別占比46.74%與39.34%，而在FConSP中，長(zhǎng)度為3與長(zhǎng)度為4的模式僅占4.09%與4.88%.隨著模式長(zhǎng)度增長(zhǎng)的同時(shí)，F(xiàn)CloConSP中模式長(zhǎng)度較長(zhǎng)的模式為0.相比而言，GCBPS中的FCloConSP更為精簡(jiǎn).

圖6為革蘭氏陽(yáng)性菌GCBPS與GCBPS-X兩種算法中模式項(xiàng)數(shù)目的對(duì)比圖，其中橫坐標(biāo)為模式項(xiàng)的長(zhǎng)度，縱坐標(biāo)為模式項(xiàng)的數(shù)目.在陽(yáng)性菌576條序列數(shù)據(jù)庫(kù)中，F(xiàn)ConSP數(shù)目為203494條，而FCloConSP僅為3323條，由此可見(jiàn)，F(xiàn)CloConSP的數(shù)目遠(yuǎn)遠(yuǎn)小于FConSP.在FCloConSP中，長(zhǎng)度為3和4的模式數(shù)目分別為1869與360，分別占比為56.24%與10.83%，而在FConSP中，模式長(zhǎng)度為3和4的數(shù)目為2376與1841，分別占比為1.17%和0.90%.由此可見(jiàn)，在同一支持度下，F(xiàn)CloConSP的模式長(zhǎng)度小于普通FConSP；FCloConSP集合大小遠(yuǎn)遠(yuǎn)小于FConSP集合.

實(shí)驗(yàn)結(jié)果表明，GCBPS算法選擇FCloConSP進(jìn)行序列特征分析，所處理的模式項(xiàng)數(shù)目更少，軟件運(yùn)行時(shí)間更短，準(zhǔn)確性更高，其具有精簡(jiǎn)性和優(yōu)化性的特點(diǎn).

圖2 算法準(zhǔn)確率比較Fig.2 Comparison of algorithm precision

圖3 算法召回率比較Fig.3 Comparison of algorithm recall

圖4 算法F1值比較Fig.4 Comparison of algorithm F1 value

圖5 革蘭氏陰性菌特征集兩種模式項(xiàng)數(shù)目對(duì)比Fig.5 Comparison of the number of two model items in the Gram-negative bacterial feature sct

圖6 革蘭氏陽(yáng)性菌特征集兩種模式項(xiàng)數(shù)目對(duì)比Fig.6 Comparison of the number of two model items in the Gram-positive bacterial feature set

6 總 結(jié)

本文首次提出的用計(jì)算機(jī)軟件實(shí)現(xiàn)的GCBPS算法是細(xì)菌革蘭氏陰陽(yáng)性判別領(lǐng)域的創(chuàng)新方法.算法通過(guò)對(duì)已知陰陽(yáng)性序列的挖掘和分析，提取出陰性和陽(yáng)性序列的特征向量，再將待測(cè)未知陰陽(yáng)性序列進(jìn)行相似性判別，可得出陰陽(yáng)性結(jié)果.該方法中的陰陽(yáng)性特征向量可以通過(guò)不斷增加數(shù)據(jù)庫(kù)中已知陰陽(yáng)性序列的數(shù)量來(lái)進(jìn)行動(dòng)態(tài)更新，從而可持續(xù)提高判別準(zhǔn)確性.為了縮短判別時(shí)間，也可事先運(yùn)行軟件的訓(xùn)練集訓(xùn)練部分，判別時(shí)直接運(yùn)行待測(cè)序列與前述的訓(xùn)練結(jié)果比對(duì)判別的部分即可.

在未來(lái)的工作中，將進(jìn)一步優(yōu)化序列特征提取時(shí)所選用的模式，盡可能減少丟失的特征，提高判別準(zhǔn)確性和縮短計(jì)算時(shí)間.以后還將嘗試把GCBPS算法用于亞細(xì)胞的定位.