集成改進(jìn)KNN算法預(yù)測蛋白質(zhì)亞細(xì)胞定位

薛衛(wèi)，王雄飛，趙南，楊榮麗，洪曉宇

?

集成改進(jìn)KNN算法預(yù)測蛋白質(zhì)亞細(xì)胞定位

薛衛(wèi)，王雄飛，趙南，楊榮麗，洪曉宇

南京農(nóng)業(yè)大學(xué)信息科學(xué)技術(shù)學(xué)院，江蘇南京 210095

基于Adaboost算法對多個相似性比對K最近鄰 (K-nearest neighbor，KNN) 分類器集成實(shí)現(xiàn)蛋白質(zhì)的亞細(xì)胞定位預(yù)測。相似性比對KNN算法分別以氨基酸組成、二肽、偽氨基酸組成為蛋白序列特征，在KNN的決策階段使用Blast比對決定蛋白質(zhì)的亞細(xì)胞定位。在Jackknife檢驗(yàn)下，Adaboost集成分類算法提取3種蛋白序列特征，3種特征在數(shù)據(jù)集CH317和Gram1253的最高預(yù)測成功率分別為92.4%和93.1%。結(jié)果表明Adaboost集成改進(jìn)KNN分類預(yù)測方法是一種有效的蛋白質(zhì)亞細(xì)胞定位預(yù)測方法。

亞細(xì)胞區(qū)間，蛋白序列特征，K-nearest neighbor，basic local alignment search tool，Adaboost

蛋白質(zhì)的功能與其所屬的亞細(xì)胞定位有著緊密的聯(lián)系，不同蛋白質(zhì)只有處于特定的亞細(xì)胞定位才能發(fā)揮其功能，保障生命活動的正常進(jìn)行，因此對蛋白序列的亞細(xì)胞定位預(yù)測研究有著重要意義[1]。

利用機(jī)器學(xué)習(xí)實(shí)現(xiàn)蛋白質(zhì)亞細(xì)胞定位預(yù)測是目前獲取定位信息的主要方法，并取得了一系列進(jìn)展[2-6]。Zhou等構(gòu)建凋亡蛋白數(shù)據(jù)集，在氨基酸組成特征下，利用協(xié)變判別函數(shù)實(shí)現(xiàn)區(qū)間預(yù)測[7]。Huang等用支持向量機(jī)對氨基酸組成特征實(shí)現(xiàn)了對凋亡蛋白的預(yù)測[8]。Bulashevska等用貝葉斯分類器同樣得到較好的分類預(yù)測效果[9]。Chen等在使用凋亡蛋白數(shù)據(jù)集的同時，構(gòu)建了數(shù)據(jù)集CH317，將多種特征融合后使用混合增量的方式實(shí)現(xiàn)預(yù)測[10]。Ding等在偽氨基酸特征下，將模糊K近鄰 (Fuzzy K-nearest neighbor,FKNN) 分類器與遺傳算法相結(jié)合，預(yù)測準(zhǔn)確率有一定提高[11]。Lin等采用偽氨基酸結(jié)合支持向量機(jī)方法對蛋白質(zhì)亞細(xì)胞定位進(jìn)行預(yù)測[12]。Zhang等運(yùn)用支持向量機(jī)融合距離頻率實(shí)現(xiàn)蛋白序列的定位預(yù)測[13]。Liao等將偽氨基酸、二肽等多種特征進(jìn)行融合后通過支持向量機(jī)在CH317上取得較好的預(yù)測效果[14]。Hu等提取序列之間的網(wǎng)狀信息，對位于19個區(qū)間的酵母菌數(shù)據(jù)集進(jìn)行預(yù)測，實(shí)現(xiàn)效果較好[15]。Yao等基于序列之間的進(jìn)化信息，通過位置特異性得分矩陣 (PSSM)，統(tǒng)計各氨基酸的突變率取得較好的預(yù)測效 果[16]。Liu等提取序列PSSM特征輸入SVM進(jìn)行預(yù)測，得到較好的預(yù)測效果[17]。Wang等提取序列GO注釋信息特征，在支持向量機(jī)中實(shí)現(xiàn)了革蘭氏陰性菌的多區(qū)間分類問題[18]。Chen等利用序列的物化屬性、PSSM和GO注釋3種特征，對多個細(xì)菌數(shù)據(jù)集進(jìn)行預(yù)測，得到較高的預(yù)測成功率[19]?？偠灾?，序列特征越來越豐富，提取過程更復(fù)雜，以上所述特征各有優(yōu)缺點(diǎn)，結(jié)合適當(dāng)?shù)念A(yù)測分類器可以取得一定的成功率，其中支持向量機(jī)、貝葉斯分類器、神經(jīng)網(wǎng)絡(luò)等訓(xùn)練較為復(fù)雜與耗時。故如何在一般低維或簡單特征和低復(fù)雜度的預(yù)測模型前提下提高識別率是本文重點(diǎn)解決的問題。

KNN是目前理論成熟、應(yīng)用最為廣泛的分類預(yù)測算法之一[20]，算法簡單易優(yōu)化，這一點(diǎn)對于近年來蛋白序列數(shù)量的激劇增長是有利的，但現(xiàn)有研究直接利用KNN進(jìn)行定位預(yù)測效果并不理想，原因在于KNN受模式特征和決策機(jī)制影響較大。再考慮到Blast可用于推斷結(jié)構(gòu)和功能相似。本文嘗試將兩者結(jié)合起來，改進(jìn)KNN算法，利用KNN過濾出與預(yù)測序列特征相似度較高的序列，再對這些序列進(jìn)行更精細(xì)的Blast比對，作為最終預(yù)測依據(jù)。具體策略分別以序列的氨基酸組成、二肽和偽氨基酸作為KNN搜索階段的特征，KNN決策階段用Blast比對確定蛋白所屬定位，最后用Adaboost集成多個KNN子分類器進(jìn)行定位預(yù)測，算法在多個數(shù)據(jù)集上取得較好的實(shí)驗(yàn)效果。文中預(yù)測算法通過網(wǎng)站http://www.wsns.org/subloc/homepage_final.jsp實(shí)現(xiàn)。

1 材料與方法

1.1 數(shù)據(jù)集

為了客觀評價預(yù)測算法的有效性，本文將Chen[10]等使用的CH317作為實(shí)驗(yàn)基準(zhǔn)數(shù)據(jù)集。CH317數(shù)據(jù)集中包含317條蛋白序列，分布在6個位置，其中細(xì)胞質(zhì)蛋白 (Cytoplasmic proteins，cy) 112條，膜蛋白 (Membrane proteins，me) 55條，細(xì)胞核蛋白 (Nuclear proteins，nu) 52條，線粒體蛋白 (Mitochondrial proteins，mi) 34條，內(nèi)質(zhì)網(wǎng)蛋白 (Endoplasmic reticulum proteins，en) 47條，分泌蛋白 (Secreted proteins，se) 17條。CH317中涉及到的所有蛋白序列均可在uniprot網(wǎng)站下載 (http://www.uniprot.org/)。

除了CH317，為了對預(yù)測算法進(jìn)行進(jìn)一步評估，本文參考Fan的數(shù)據(jù)集構(gòu)建方法[21]，具體參數(shù)本文不再復(fù)述。構(gòu)建了革蘭氏陰性菌數(shù)據(jù)集 (Gram1253)，Gram1253共包含符合規(guī)則蛋白序列1 253條，分布于5個位置，如表1 所示。

1.2 序列特征提取

對蛋白序列進(jìn)行不同特征的提取從而實(shí)現(xiàn)蛋白質(zhì)的亞細(xì)胞區(qū)間預(yù)測是目前研究所采用的主要方法。本文使用氨基酸組成、二肽和偽氨基酸特征。

表1 革蘭氏陰性菌數(shù)據(jù)集分布

1.2.1 氨基酸組成(Amino acid composition，AAC)

不同亞細(xì)胞定位中的蛋白質(zhì)在組成上有很大差別，基于這一特性提出了AAC特征提取方法[22]，Nakashima等首次在AAC特征基礎(chǔ)上實(shí)現(xiàn)了對亞細(xì)胞定位的預(yù)測[23]。AAC的基本思想：對于任意的蛋白序列，統(tǒng)計構(gòu)成序列的20種氨基酸各自出現(xiàn)的頻率，那么序列的AAC特征可用公式1表示：

上式中，f表示第種氨基酸在序列中出現(xiàn)的頻率。

1.2.2 二肽(Dipeptide，Dipe)

二肽特征是基于AAC特征的改進(jìn)，所謂二肽是指任意2個氨基酸構(gòu)成的氨基酸對，組成蛋白序列的氨基酸共有20種，因此二肽共有400種，通過統(tǒng)計二肽的頻率來描述一條蛋白序列的特征是二肽特征的基本思想[24]。對于任意的序列，其二肽特征可用公式2表示：

上式中，表示第種二肽在序列中出現(xiàn)的頻率。

1.2.3 偽氨基酸 (Pseudo amino acid composition，PseAAC)

偽氨基酸特征同樣是基于AAC特征的改進(jìn)，在統(tǒng)計氨基酸頻率的基礎(chǔ)上，利用維來表示氨基酸之間的位置信息[25]。同AAC特征相比，偽氨基酸特征對序列的刻畫更加全面。對于任意的序列，其偽氨基酸特征可用公式3表示：

1.3 預(yù)測算法

1.3.1 基于相似性改進(jìn)KNN分類算法

分類器的設(shè)計是對傳統(tǒng)KNN算法做改進(jìn)，修改KNN決策階段，利用Blast比對取代投票機(jī)制確定所屬區(qū)間位置。

序列相似性常被用來推斷結(jié)構(gòu)和功能相似[26]，因此，序列比對技術(shù)出現(xiàn)在一些區(qū)間預(yù)測算法中，如將Blast比對作為集成分類器的一個子分類器[27]，從Needleman-Wunsch算法的得分矩陣提取特征用于預(yù)測[28]。本文采用Blast序列局部比對搜索算法計算蛋白序列之間氨基酸殘基的相似比率，從而確定蛋白序列所屬位置。通過Blast序列局部比對搜索算法計算得分后，得分最高的蛋白序列便是與檢索序列相似度最高的序列?；诟倪M(jìn)KNN分類器算法流程見圖1。

圖1 基于Blast改進(jìn)的KNN分類算法

文中使用的Blast程序版本為2.2.30，在National Center for Biotechnology Information (NCBI) 官方網(wǎng)站下載 (ftp://ftp.ncbi.nlm.nih. gov/blast/executables/blast+/)。這里采用blastp子程序?qū)Φ鞍仔蛄械挠H緣性進(jìn)行比對，具體用到的命令及主要參數(shù)如下：

1) 數(shù)據(jù)庫格式化

makeblastdb.exe –in DB.fasta-parse_seqids- hash_index–dbtypeprot

其中makeblastdb.exe為格式化數(shù)據(jù)庫命令，–in指定數(shù)據(jù)庫文件，-parse_seqids-hash_index為子序列比對的參數(shù)，-dbtype指定比對類型，prot為蛋白序列。

2) 序列比對命令

blastp.exe-task blastp-query que-db DB–out out

使用blastp.exe命令實(shí)現(xiàn)蛋白序列比對，-query指定要比對的序列文件，-db為格式化后的數(shù)據(jù)庫文件，–out指定結(jié)果輸出文件。

1.3.2 Adaboost集成分類預(yù)測算法

Adaboost集成分類算法對多個基于Blast改進(jìn)的KNN分類器進(jìn)行集成，得到一個較強(qiáng)的分類器[29]。在分類器訓(xùn)練過程中，由于每個分類器的權(quán)重都基于前一個分類器的分類效果，因此最后得到的集成分類器效果較好。

給定一個訓(xùn)練數(shù)據(jù)集={(1,1), (2,2)… (x,y)}，其中實(shí)例，而實(shí)例空間，y屬于標(biāo)記集合{–1,+1}，Adaboost的算法流程如下：

步驟1：初始化訓(xùn)練數(shù)據(jù)的權(quán)值分布。每一個訓(xùn)練樣本最開始時都被賦予相同的權(quán)重：1/N。

步驟2：進(jìn)行多輪迭代，用=1,2, ...,表示迭代的第輪。

使用具有權(quán)值分布D的訓(xùn)練數(shù)據(jù)集學(xué)習(xí)，得到基本分類器：

計算G()在訓(xùn)練數(shù)據(jù)集上的分類誤差率

(6)

G()在訓(xùn)練數(shù)據(jù)集上的誤差率e即被G()誤分類樣本的權(quán)值之和。

計算G()的系數(shù)，表示G()在最終分類器中的比重

更新訓(xùn)練數(shù)據(jù)集的權(quán)值分布，用于下一輪迭代。

(8)

更新權(quán)重使得被基本分類器G()誤分類樣本的權(quán)值增大，而被正確分類樣本的權(quán)值減小。通過這樣的方式，Adaboost方法能“聚焦于”那些較難分的樣本上。

其中，Z是規(guī)范化因子，使得D+1成為一個概率分布：

步驟3：組合各個弱分類器

(11)

從而得到最終分類器，如下：

Adaboost分類通過對多個相似性比對改進(jìn)KNN分類器進(jìn)行集成，實(shí)現(xiàn)亞細(xì)胞定位預(yù)測。一個Adaboost分類器只能完成二分類，所以需要訓(xùn)練多個分類器達(dá)到多區(qū)間預(yù)測，分類器構(gòu)建過程如下：

1) 對于位于個區(qū)間位置的數(shù)據(jù)集，隨機(jī)取其中一個區(qū)間作為類別1，其余位置作為類別2，轉(zhuǎn)化成一個二分類問題；2)初始化數(shù)據(jù)集中蛋白序列的權(quán)重；3)隨機(jī)生成值，得到對應(yīng)的相似性比對改進(jìn)KNN分類器；4)使用該分類器對數(shù)據(jù)集進(jìn)行預(yù)測，由預(yù)測誤差確定分類器系數(shù)；5)重復(fù)步驟3?4次，得到一個Adaboost分類器；6)根據(jù)預(yù)測效果更新數(shù)據(jù)集中樣本的權(quán)重，用于下一個分類器的訓(xùn)練；7)對于類別2，重復(fù)步驟1–6，獲取對應(yīng)的分類器，直到區(qū)間無法再細(xì)分為止；8)對于個區(qū)間的樣本，進(jìn)行–1次訓(xùn)練，得到–1個Adaboost分類器；9)對–1個Adaboost分類器進(jìn)行集成，得到最終的集成分類器。

1.3.3 評價指標(biāo)

Jackknife檢驗(yàn)是蛋白質(zhì)亞細(xì)胞定位預(yù)測中較為常用的檢驗(yàn)方法，基本原理為：從數(shù)據(jù)集中取出一條蛋白序列作為測試序列，剩余序列作為訓(xùn)練集，測試完畢后將該序列放入數(shù)據(jù)集并取出下一條序列作為測試序列，以此類推直至所有序列預(yù)測完畢。本文中的預(yù)測算法在Jackknife檢驗(yàn)下完成。

參考Chen使用的評價指標(biāo)，引入敏感性 (S)、特異性 (S)、相關(guān)系數(shù) (MMC) 以及總體準(zhǔn)確率 ()[10]。

2 結(jié)果與分析

KNN分類器值的選取對于整個算法的準(zhǔn)確度有很大影響。值越大，包含的蛋白序列數(shù)量越多，算法的時間復(fù)雜度越高。值越小，則越有可能丟棄掉一些真正有意義的蛋白序列，影響算法的準(zhǔn)確度。故文中算法在各數(shù)據(jù)集的序列預(yù)測過程值均取20。

2.1 本文算法在多數(shù)據(jù)集及多特征下預(yù)測結(jié)果與分析

基于相似性比對改進(jìn)KNN的Adaboost集成分類預(yù)測算法，對數(shù)據(jù)集CH317和Gram1253提取3種特征進(jìn)行預(yù)測，CH317的實(shí)驗(yàn)結(jié)果如表2所示。

由表2可知，除了位置cy和en外，數(shù)據(jù)集CH317的AAC、PseAAC特征準(zhǔn)確率都高于Dipe特征并且總的預(yù)測準(zhǔn)確率也較高，說明在KNN搜索階段Dipe特征會誤排除一些同模式序列。

基于相似性比對改進(jìn)KNN的Adaboost集成分類預(yù)測算法在數(shù)據(jù)集Gram1253的實(shí)驗(yàn)結(jié)果如表3所示。

由表3結(jié)果可知，基于相似性比對改進(jìn)KNN的Adaboost集成分類預(yù)測算法在數(shù)據(jù)集Gram1253上，AAC、PseAAC特征各位置的準(zhǔn)確率都高于Dipe特征并且總的預(yù)測準(zhǔn)確率也較高。總之，與表2的結(jié)果一致的是，AAC、PseAAC特征預(yù)測準(zhǔn)確率都較高，而維數(shù)更高的Dipe效果均要差些，帶有相鄰位置信息的氨基酸對頻率不能較準(zhǔn)確地代表序列特征。

表2 通過Jackknife檢驗(yàn)在數(shù)據(jù)集CH317上的預(yù)測結(jié)果

表3 通過Jackknife檢驗(yàn)在數(shù)據(jù)集Gram1253上的預(yù)測結(jié)果

2.2 本文算法與其他算法預(yù)測結(jié)果比較

在數(shù)據(jù)集CH317上，將基于相似性比對改進(jìn)KNN的Adaboost集成分類預(yù)測算法的預(yù)測結(jié)果同其他方法進(jìn)行比較，并將結(jié)果列于表4中，由于一些其他預(yù)測方法不涉及特異性和相關(guān)系數(shù)，所以這里只對敏感性(S)進(jìn)行比較。

ID算法使用混合增量 (Increment of diversity, ID) 作為特征進(jìn)行預(yù)測；FKNN使用PseAAC作為特征，結(jié)合模糊近鄰算法預(yù)測；PseAAC_SVM使用PseAAC特征結(jié)合支持向量機(jī)預(yù)測；DF_SVM使用距離頻率 (Distance frequency, DF) 結(jié)合支持向量機(jī)預(yù)測；Mix_SVM提出新的PseAAC計算方法結(jié)合支持向量機(jī)預(yù)測；PSSM_SVM使用位置特異性得分矩陣 (PSSM) 結(jié)合支持向量機(jī)預(yù)測。

由表4可以看出，與其他預(yù)測算法相比，基于相似性比對改進(jìn)KNN的Adaboost集成分類預(yù)測算法的最高準(zhǔn)確率高于其他算法，尤其超過其他以PseAAC為特征的預(yù)測算法；在各位置上的預(yù)測準(zhǔn)確率也較高，特別是CH317的me、se、en位置獲得最高準(zhǔn)確率，且總體準(zhǔn)確率也有一定提高。

為了便于對Gram1253的預(yù)測結(jié)果進(jìn)行比較，采用支持向量機(jī)作為分類器，分別在3種特征下統(tǒng)計準(zhǔn)確率，并與KNN分類器預(yù)測結(jié)果進(jìn)行比較，結(jié)果列于表5中。

表4 通過Jackknife檢驗(yàn)在數(shù)據(jù)集CH317上不同方法的預(yù)測結(jié)果

表5 通過Jackknife檢驗(yàn)在數(shù)據(jù)集Gram1253上不同方法的預(yù)測結(jié)果

由表5可以看出，與支持向量機(jī)以及KNN算法相比，當(dāng)使用AAC特征時Adaboost集成分類預(yù)測算法在4個區(qū)間cy、me、pe、nu位置的預(yù)測效果較好，總體預(yù)測準(zhǔn)確率有了一定提高。表4、5中，與文中算法預(yù)測率接近的是基于支持向量機(jī)的預(yù)測技術(shù)，與它相比，本文算法更適合大數(shù)據(jù)的處理，算法簡單易實(shí)現(xiàn)，而支持向量機(jī)處理大數(shù)據(jù)效率低。

3 討論

蛋白質(zhì)亞細(xì)胞定位預(yù)測是生物信息學(xué)領(lǐng)域較復(fù)雜的研究內(nèi)容，研究者在序列特征提取與預(yù)測算法設(shè)計上做了大量工作。在此基礎(chǔ)上，不失一般性，本文以常見的AAC、Dipe、PseAAC作為蛋白序列特征，基于相似度高的蛋白序列出現(xiàn)在同一個亞細(xì)胞位置中可能性較高的思想構(gòu)建改進(jìn)KNN分類器，進(jìn)而集成改進(jìn)KNN分類器，實(shí)現(xiàn)蛋白質(zhì)亞細(xì)胞定位預(yù)測。算法架構(gòu)可滿足大數(shù)據(jù)處理的要求，對于大數(shù)據(jù)集，改進(jìn)KNN分類器便于實(shí)現(xiàn)Hadoop等分布式處理架構(gòu)，縮短算法運(yùn)行時間。

基于通用性考慮，選用國際公認(rèn)有效的數(shù)據(jù)集CH317，并按通用標(biāo)準(zhǔn)構(gòu)建一個較大數(shù)據(jù)集用于測試。通過嚴(yán)格的Jackknife檢驗(yàn)，數(shù)據(jù)集CH317和Gram1253在3種特征下最高預(yù)測成功率分別為92.4%和93.1%。與一些報道的預(yù)測算法相比，集成改進(jìn)KNN預(yù)測算法在3種特征下都取得較好的實(shí)驗(yàn)效果，且總體成功率有一定提高，優(yōu)于直接使用Blast比對預(yù)測，說明同源性比對不適合直接用于蛋白質(zhì)亞細(xì)胞定位預(yù)測。其中，AAC、PseAAC特征的準(zhǔn)確率最為穩(wěn)定，AAC總體更優(yōu)，表明在KNN的搜索階段無需考慮復(fù)雜的理化特性?？傊?，通過在3種特征及多個數(shù)據(jù)集下的驗(yàn)證測試，集成改進(jìn)KNN預(yù)測算法均取得較好的效果，該算法是一種較為有效的蛋白質(zhì)亞細(xì)胞定位預(yù)測算法。

REFERENCES

[1] Cai YD, Liu XJ, Xu XB, et al. Support vector machines for prediction of protein subcellular location. Mol Cell Biol Res Commun, 2000, 4(4): 230–233.

[2] Chou KC, Cai YD. A new hybrid approach to predict subcellular localization of proteins by incorporating gene ontology. Biochem Biophys Res Commun, 2003, 311(3): 743–747.

[3] Chou KC, Elrod DW. Prediction of membrane protein types and subcellular locations. Prot: Struct, Funct, Bioinform, 1999, 34(1): 137–153.

[4] Chou KC, Elrod DW. Protein subcellular location prediction. Protein Eng, Des Select, 1999, 12(2): 107–118.

[5] Reed JC, Paternostro G. Postmitochondrial regulation of apoptosis during heart failure. Proc Natl Acad Sci USA, 1999, 96(14): 7614–7616.

[6] Suzuki M, Youle RJ, Tjandra N. Structure of bax: coregulation of dimer formation and intracellular localization. Cell, 2000, 103(4): 645–654.

[7] Zhou GP, Doctor K. Subcellular location prediction of apoptosis proteins. Proteins: Struct, Funct, Bioinform, 2003, 50(1): 44–48.

[8] Huang J, Shi F. Support vector machines for predicting apoptosis proteins types. Acta Biotheor, 2005, 53(1): 39–47.

[9] Bulashevska A, Eils R. Predicting protein subcellular locations using hierarchical ensemble of Bayesian classifiers based on Markov chains. BMC Bioinformatics, 2006, 7(1): 298.

[10] Chen YL, Li QZ. Prediction of the subcellular location of apoptosis proteins. J Theoret Biol, 2007, 245(4): 775–783.

[11] Ding YS, Zhang TL. Using Chou’s pseudo amino acid composition to predict subcellular localization of apoptosis proteins: an approach with immune genetic algorithm-based ensemble classifier. Pattern Recognit Lett, 2008, 29(13): 1887–1892.

[12] Lin H, Wang H, Ding H, et al. Prediction of subcellular localization of apoptosis protein using Chou’s pseudo amino acid composition. Acta Biotheor, 2009, 57(3): 321–330.

[13] Zhang L, Liao B, Li DC,et al. A novel representation for apoptosis protein subcellular localization prediction using support vector machine. J Theoret Biol, 2009, 259(2): 361–365.

[14] Liao B, Jiang JB, Zeng QG, et al. Predicting apoptosis protein subcellular location with PseAAC by incorporating tripeptide composition. Protein Pept Lett, 2011, 18(11): 1086–1092.

[15] Hu LL, Feng KY, Cai YD, et al. Using protein-protein interaction network information to predict the subcellular locations of proteins in budding yeast. Protein Pept Lett, 2012, 19(6): 644–651.

[16] Yao YH, Shi ZX, Dai Q. Apoptosis protein subcellular location prediction based on position- specific scoring matrix. J Computat Theoret Nanosci, 2014, 11(10): 2073–2078.

[17] Liu TG, Tao PY, Li XW, et al. Prediction of subcellular location of apoptosis proteins combining tri-gram encoding based on PSSM and recursive feature elimination. J Theoret Biol, 2015, 366: 8–12.

[18] Wang X, Zhang J, Li GZ. Multi-location gram- positive and gram-negative bacterial protein subcellular localization using gene ontology and multi-label classifier ensemble. BMC Bioinformatics, 2015, 16(S12): S1.

[19] Chen J, Xu H, He PA, et al. A multiple information fusion method for predicting subcellular locations of two different types of bacterial protein simultaneously. Biosystems, 2016, 139: 37–45.

[20] Jiang Y, Zhou ZH. Editing training data for kNN classifiers with neural network ensemble[M]//Yin FL, Wang J, GuoCG, Eds. Advances in Neural Networks–ISNN 2004. Berlin Heidelberg: Springer, 2004: 356–361.

[21] Fan GL, Li QZ. Predict mycobacterial proteins subcellular locations by incorporating pseudo- average chemical shift into the general form of Chou’s pseudo amino acid composition. J Theoret Biol, 2012, 304: 88–95.

[22] Nakashima H, Nishikawa K, Tatsuo O. The folding type of a protein is relevant to the amino acid composition. J Biochem, 1986, 99(1): 153–162.

[23] Nakashima H, Nishikawa K. Discrimination of intracellular and extracellular proteins using amino acid composition and residue-pair frequencies. J Mol Biol, 1994, 238(1): 54–61.

[24] Wu C, Whitson G, Mclarty J, et al. Protein classification artificial neural system. Protein Sci, 1992, 1(5): 667–677.

[25] Chou KC, Shen HB. Cell-PLoc: a package of web servers for predicting subcellular localization of proteins in various organisms. Nat Protoc, 2008, 3(2): 153–162.

[26] Nair R, Rost B. Sequence conserved for subcellular localization. Protein Sci, 2002, 11(12): 2836–2847.

[27] Cherian BS, Nair AS. Protein location prediction using atomic composition and global features of the amino acid sequence. Biochem Biophys Res Commun, 2010, 391(4): 1670–1674.

[28] Kim JK, Bang SY, Choi S. Sequence-driven features for prediction of subcellular localization of proteins. Pattern Recognit, 2006, 39(12): 2301–2311.

[29] Lin J, Wang Y. Using a novel Adaboost algorithm and Chou’s pseudo amino acid composition for predicting protein subcellular localization. Protein Pept Lett, 2011, 18(12): 1219–1225.

(本文責(zé)編 陳宏宇)

Prediction of protein subcellular locations by ensemble of improved K-nearest neighbor

Wei Xue,Xiongfei Wang,Nan Zhao,Rongli Yang, and Xiaoyu Hong

School of Information Science and Technology, Nanjing Agricultural University, Nanjing 210095, Jiangsu, China

Adaboost algorithm with improved K-nearest neighbor classifiers is proposed to predict protein subcellular locations. Improved K-nearest neighbor classifier uses three sequence feature vectors including amino acid composition, dipeptide and pseudo amino acid composition of protein sequence. K-nearest neighbor uses Blast in classification stage. The overall success rates by the jackknife test on two data sets of CH317 and Gram1253 are 92.4% and 93.1%. Adaboost algorithm with the novel K-nearest neighbor improved by Blast is an effective method for predicting subcellular locations of proteins.

subcellular locations, protein sequence characteristics, K-nearest neighbor, basic local alignment search tool (Blast), Adaboost

Supported by: Fundamental Research Funds for the Central Universities (No. KYZ201668), Natural Science Foundation of Jiangsu Province (No. BK2012363), National Science and Technology Support Program Project (No. 2015BAK36B05).

中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金(No. KYZ201668)，江蘇省自然科學(xué)基金(No. BK2012363)，國家科技支撐計劃(No. 2015BAK36B05) 資助。

October 18, 2016; Accepted: December 22, 2016

Wei Xue. Tel: +86-21-84396350; E-mail: xwsky@njau.edu.cn

網(wǎng)絡(luò)出版時間：2017-01-09

http://www.cnki.net/kcms/detail/11.1998.Q.20170109.1240.002.html