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

?

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

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

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

基于Adaboost算法對多個(gè)相似性比對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ù)集的同時(shí)，構(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個(gè)區(qū)間的酵母菌數(shù)據(jù)集進(jìn)行預(yù)測，實(shí)現(xiàn)效果較好[15]。Yao等基于序列之間的進(jìn)化信息，通過位置特異性得分矩陣 (PSSM)，統(tǒng)計(jì)各氨基酸的突變率取得較好的預(yù)測效 果[16]。Liu等提取序列PSSM特征輸入SVM進(jìn)行預(yù)測，得到較好的預(yù)測效果[17]。Wang等提取序列GO注釋信息特征，在支持向量機(jī)中實(shí)現(xiàn)了革蘭氏陰性菌的多區(qū)間分類問題[18]。Chen等利用序列的物化屬性、PSSM和GO注釋3種特征，對多個(gè)細(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ù)雜與耗時(shí)。故如何在一般低維或簡單特征和低復(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集成多個(gè)KNN子分類器進(jìn)行定位預(yù)測，算法在多個(gè)數(shù)據(jù)集上取得較好的實(shí)驗(yàn)效果。文中預(yù)測算法通過網(wǎng)站http://www.wsns.org/subloc/homepage_final.jsp實(shí)現(xiàn)。

1 材料與方法

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

為了客觀評價(jià)預(yù)測算法的有效性，本文將Chen[10]等使用的CH317作為實(shí)驗(yàn)基準(zhǔn)數(shù)據(jù)集。CH317數(shù)據(jù)集中包含317條蛋白序列，分布在6個(gè)位置，其中細(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個(gè)位置，如表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)計(jì)構(gòu)成序列的20種氨基酸各自出現(xiàn)的頻率，那么序列的AAC特征可用公式1表示：

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

1.2.2 二肽(Dipeptide，Dipe)

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

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

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

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

1.3 預(yù)測算法

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

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

序列相似性常被用來推斷結(jié)構(gòu)和功能相似[26]，因此，序列比對技術(shù)出現(xiàn)在一些區(qū)間預(yù)測算法中，如將Blast比對作為集成分類器的一個(gè)子分類器[27]，從Needleman-Wunsch算法的得分矩陣提取特征用于預(yù)測[28]。本文采用Blast序列局部比對搜索算法計(jì)算蛋白序列之間氨基酸殘基的相似比率，從而確定蛋白序列所屬位置。通過Blast序列局部比對搜索算法計(jì)算得分后，得分最高的蛋白序列便是與檢索序列相似度最高的序列。基于改進(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集成分類算法對多個(gè)基于Blast改進(jìn)的KNN分類器進(jìn)行集成，得到一個(gè)較強(qiáng)的分類器[29]。在分類器訓(xùn)練過程中，由于每個(gè)分類器的權(quán)重都基于前一個(gè)分類器的分類效果，因此最后得到的集成分類器效果較好。

給定一個(gè)訓(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)值分布。每一個(gè)訓(xùn)練樣本最開始時(shí)都被賦予相同的權(quán)重：1/N。

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

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

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

(6)

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

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

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

(8)

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

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

步驟3：組合各個(gè)弱分類器

(11)

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

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

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

1.3.3 評價(jià)指標(biāo)

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

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

2 結(jié)果與分析

KNN分類器值的選取對于整個(gè)算法的準(zhǔn)確度有很大影響。值越大，包含的蛋白序列數(shù)量越多，算法的時(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)確率也較高?？傊c表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計(jì)算方法結(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)計(jì)準(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特征時(shí)Adaboost集成分類預(yù)測算法在4個(gè)區(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è)計(jì)上做了大量工作。在此基礎(chǔ)上，不失一般性，本文以常見的AAC、Dipe、PseAAC作為蛋白序列特征，基于相似度高的蛋白序列出現(xiàn)在同一個(gè)亞細(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)行時(shí)間。

基于通用性考慮，選用國際公認(rèn)有效的數(shù)據(jù)集CH317，并按通用標(biāo)準(zhǔn)構(gòu)建一個(gè)較大數(shù)據(jù)集用于測試。通過嚴(yán)格的Jackknife檢驗(yàn)，數(shù)據(jù)集CH317和Gram1253在3種特征下最高預(yù)測成功率分別為92.4%和93.1%。與一些報(bào)道的預(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種特征及多個(gè)數(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).

中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金(No. KYZ201668)，江蘇省自然科學(xué)基金(No. BK2012363)，國家科技支撐計(jì)劃(No. 2015BAK36B05) 資助。

October 18, 2016; Accepted: December 22, 2016

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

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

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