王麗美，鄭大軍，鄭程友

(1.臨滄師范高等?？茖W(xué)校數(shù)理系，云南臨滄677000；2.福建農(nóng)林大學(xué)計算機(jī)與信息學(xué)院，福建福州350002；3.桂林理工大學(xué)機(jī)械與控制工程學(xué)院，廣西桂林541000)

改進(jìn)的基于支持向量機(jī)模型剪接位點的預(yù)測

王麗美1，鄭大軍2，鄭程友3

(1.臨滄師范高等?？茖W(xué)校數(shù)理系，云南臨滄677000；2.福建農(nóng)林大學(xué)計算機(jī)與信息學(xué)院，福建福州350002；3.桂林理工大學(xué)機(jī)械與控制工程學(xué)院，廣西桂林541000)

在采用概率編碼的基礎(chǔ)上，利用支持向量機(jī)模型對人類剪接位點進(jìn)行預(yù)測，重點研究了基于核主成分分析方法對最終預(yù)測模型的影響.從實驗結(jié)果看，這種改進(jìn)的基于支持向量機(jī)模型剪接位點的預(yù)測在敏感性和特異性上優(yōu)于其他模型.

剪接；預(yù)測；特征提?。恢С窒蛄繖C(jī)；核主成分分析

Brunak[11]等人采用了神經(jīng)元網(wǎng)絡(luò)模型來識別剪接位點；Castelo[12]等人則在識別剪接位點的過程中采用了Bayesian網(wǎng)絡(luò)模型；Haussler[13]等人嘗試了隱馬爾科夫模型，并取得了不錯的識別效果.

Staden采用權(quán)重矩陣模型來對剪接位點進(jìn)行分析[14]，該模型假設(shè)各個位點的堿基是相互獨立的，其出現(xiàn)的概率是由位置決定的，與前后的堿基無關(guān)；Zhang和Marr采用權(quán)重陣列模型[3]，該方法可以看成是權(quán)重矩陣模型的擴(kuò)展，它放寬了堿基間獨立的限制，研究了堿基間的相互依賴關(guān)系，可以把它看作是一個一階馬爾科夫模型；Salzberg[15]利用條件概率模型對剪接位點以及起始轉(zhuǎn)錄點進(jìn)行識別；Burge[16]在對剪接位點的識別中提出了最大相關(guān)分解的思路，該模型能夠得到非相鄰位點堿基的相關(guān)性，取得了不錯的效果.

Wang[17-18]等利用改進(jìn)的神經(jīng)網(wǎng)絡(luò)來對剪接位點

剪接位點的識別主要包括傳統(tǒng)的生物學(xué)實驗方法和計算機(jī)算法的方法.傳統(tǒng)的生物學(xué)實驗的結(jié)果準(zhǔn)確，但是成本較高，會消耗大量的人力物力，因此限制了它的大規(guī)模使用；而基于計算機(jī)算法的研究方法代價則小得多，但是具體的識別精度要低于傳統(tǒng)的生物學(xué)實驗的方法.

剪接位點識別最初是利用生物學(xué)實驗的方法，這也是最基本可靠的方法.但近年來計算機(jī)技術(shù)和生物科學(xué)技術(shù)發(fā)展迅速，使生物學(xué)數(shù)據(jù)的爆炸性增長，給剪接位點的識別帶來了巨大的挑戰(zhàn).在這種背景下，傳統(tǒng)的生物學(xué)實驗的方法遠(yuǎn)遠(yuǎn)不能滿足人們的要求.所以，人們開始嘗試采用統(tǒng)計學(xué)、數(shù)學(xué)模型、模式識別等方法來建立預(yù)測模型，并將其在計算機(jī)上實現(xiàn)，以加快實驗的進(jìn)程.

目前剪接位點預(yù)測中所采用的主要方法有MM模型(Markov Model)[1]、WMM模型(WeightMatrixModel)[2]、WAM模型(Weight Array Model)[3]、MEM模型(Maximum Entropy Model)[4]、MDD模型(Maximum Dependence Decomposition Model)[5]、IDQD(Incrementof進(jìn)行識別，他們把模式識別和組分模式結(jié)合起來；Xia[19]等引入競爭機(jī)制對可變剪接位點進(jìn)行識別，供體端的識別率為89.21%，受體端的識別率為87.98%；Zhang[6]等采用多樣性指標(biāo)的二次判別方法預(yù)測人類基因組中的組成性剪接位點.

Degroeve[9]等在對剪接位點的識別中考慮到了組成特征、位置特征以及密碼子偏好性等.

除了以上介紹的這些算法外，還有BRAIN (Batch Relevance-based Artificial Intelligence)學(xué)習(xí)算法、motif方法等.

本文主要是使用核主成分的方法來進(jìn)行剪切位點數(shù)據(jù)的特征提取，然后利用支持向量機(jī)的方法分別對供體剪接位點和受體剪接位點建立預(yù)測模型.

1 核主成分分析

假設(shè)x1,x2,...,xM為訓(xùn)練樣本，用{} xi表示輸入空間.KPCA方法的基本思想是通過某種隱式方式將輸入空間映射到某個高維空間(常稱為特征空間)，并且在特征空間中實現(xiàn)PCA.假設(shè)相應(yīng)的映射為Φ，其定義如下：

核函數(shù)通過映射Φ將隱式實現(xiàn)點x到F的映射，并且由此映射而得的特征空間中數(shù)據(jù)滿足中心化的條件，即

則特征空間中的協(xié)方差矩陣為：

現(xiàn)求C的特征值λ≥0和特征向量

即有

考慮到所有的特征向量可表示為Φ(x1),Φ(x2),...,Φ(xM)的線性張成，即

則有

其中v=1,2,…,M.定義M×M維矩陣K：

則式子(7)可以簡化為

顯然滿足

求解(10)就能得到特征值和特征向量，對于測試樣本在特征向量空間Vk的投影為

將內(nèi)積用核函數(shù)替換則有

當(dāng)(2)不成立時，需進(jìn)行調(diào)整，

則核矩陣可修正為

2 支持向量機(jī)

支持向量機(jī)[18]是機(jī)器學(xué)習(xí)的一種方法，能夠有效地處理模式識別和回歸等復(fù)雜的問題.另外，將其推廣之后，還可以在預(yù)測和評價等問題中得到應(yīng)用.支持向量機(jī)屬于一般化線性分類器，被稱為最大邊緣區(qū)域分類器.

假定有訓(xùn)練樣本集

其中，每個樣本都是d維向量，變量y是類別標(biāo)簽. w1類用+1表示，w2類用-1表示.而且，這些樣本所組成的數(shù)據(jù)集是線性可分的，也就是存在一個超平面

能夠把所有的N個樣本都沒有錯誤地分開.這里，w∈Rd是線性判別函數(shù)的權(quán)值，b是其中的常數(shù)項. (w?x)表示向量w與x的內(nèi)積，即w'x.

定義：一個超平面，如果它能夠?qū)⒂?xùn)練樣本沒有錯誤地分開，并且這兩類訓(xùn)練樣本中離超平面最近的樣本與超平面之間的距離是最大的，則把這個超平面稱作最優(yōu)分類超平面(optional seperating hyperplane)，簡稱最優(yōu)超平面(optionalhyperplane).兩類樣本中離分類面最近的樣本到分類面的距離稱作分類間隔(margin)，最優(yōu)超平面也稱作最大間隔超平面.

最優(yōu)超平面定義的分類決策函數(shù)為

其中，sgn()為符號函數(shù)，當(dāng)自變量為正值時函數(shù)取值為1，自變量為負(fù)值時函數(shù)取值為-1.

所有N個樣本都可以被超平面沒有錯誤地分開，就是要求所有樣本都滿足

既然尺度可以調(diào)整，把式(17)的條件變成

即要求第一類樣本中g(shù)(x)最小等于1，而第二類樣本中g(shù)(x)最大等于-1.把樣本的類別標(biāo)號y值乘到不等式(16)中，可以把兩個不等式合并成一個統(tǒng)一的形式：

用此條件約束分類超平面的權(quán)值尺度變化，這種超平面稱作規(guī)范化的分類超平面(the canonical form of the separating hyperplane).g(x)=1和g(x)=-1就是過兩類中各自離分類面最近的樣本且與分類面平行的兩個邊界超平面.

由于限制兩類離分類面最近的樣本g(x)分別等于1和-1，那么分類間隔就是.于是，求解最優(yōu)超平面的問題就成為

這是一個在不等式約束下的優(yōu)化問題，可以通過拉格朗日法求解.對每個樣本引入一個拉格朗日系數(shù)可以把式(20)和式(21)的優(yōu)化問題等價地轉(zhuǎn)化為下面的問題

式中的L(w,b,α)是拉格朗日泛函，式(20)、式(21)的解等價于式(23)對w和b求最小，而對α求最大，最優(yōu)解在L(w,b,α)的鞍點上取得.

在式(21)的鞍點處，目標(biāo)函數(shù)L(w,b,α)對w和b的偏導(dǎo)數(shù)為零，由此可以得到，對最優(yōu)解，有

且

將式(22)和式(23)帶入拉格朗日泛函中可以得到，式(20)、式(21)的最優(yōu)超平面問題的解等價于下面的優(yōu)化問題的解

且

這是一個對αi,i=1,2,…,N的二次優(yōu)化問題，稱作最優(yōu)超平面的對偶問題(the dualproblem)，而式(20)、式(21)的優(yōu)化問題稱作對偶超平面的原問題(the primary problem).通過對偶問題的解i=1,2,…,N，可以求出原問題的解

現(xiàn)在來看b*的求解問題.

根據(jù)最優(yōu)化理論中的庫恩-塔克(Kuhn-Tucker)條件，式(23)中的拉格朗日泛函的鞍點處滿足

再考慮到式(21)和式(22)，可以看到，對于滿足式(22)中大于號的樣本，必定有αi=0.而只有那些使式(21)中等號成立的樣本所對應(yīng)的αi才會大于0.這些樣本就是離分類面最近的那些樣本，是這些樣本決定了最終的最優(yōu)超平面的位置；在式(27)和式(28)的加權(quán)求和中，實際也只有這些αi＞0的樣本參與求和.這些樣本被稱作支持向量(supportvectors)，它們往往只是訓(xùn)練樣本中的很少一部分.

對于這些支持向量來說，有

因為已經(jīng)求出了w*，所以b*可以用任何一個支持向量根據(jù)式(29)的方程求得.在實際的數(shù)值計算中，通常采用所有αi非零的樣本用式(29)求解b*后再取平均.

上面提到的線性支持向量機(jī)，它求解的分類器為：

其中的αi,i=1,2,…,N是下列二次優(yōu)化問題的解

b通過使

成立的樣本(即支持向量)求得.

而相應(yīng)的優(yōu)化函數(shù)問題變成

定義支持向量的等式成為

仔細(xì)觀察這些公式會發(fā)現(xiàn)，在進(jìn)行變換后，無論變換的具體形式如何，變換對支持向量機(jī)的影響是把兩個樣本在原特征空間中的內(nèi)積(xi?xj)變成了在新空間中的內(nèi)積(φ(xi)?φ(xj)).新空間中的內(nèi)積也是原特征的函數(shù)，可以記作

把它稱作核函數(shù).這樣，變換空間里的支持向量機(jī)就可以寫成

其中，系數(shù)α是下列優(yōu)化問題的解

b通過滿足下式的樣本(支持向量)求得

泛函空間的有關(guān)理論表明這樣做是完全可行的，條件是需要找到能夠構(gòu)成某一變換空間的內(nèi)積核函數(shù).Mercer定理給出了這一條件：

定理(Mercer條件)對于任意的對稱函數(shù)K(x,x')，它是某個特征空間中的內(nèi)積運(yùn)算的充分必要條件是，對于任意的φ≠0且∫φ2(x) d x＜∞，有

因此，選擇一個滿足Mercer條件的核函數(shù)，就可以構(gòu)建非線性的支持向量機(jī).進(jìn)一步可以證明，這個條件還可以放松為滿足如下條件的正定核(posi-是定義在空間X上的對稱函數(shù)，且對任意的訓(xùn)練數(shù)據(jù)x1,…,xm∈X和任意的實系數(shù)a1,…,am∈R，都有

對于滿足正定條件的核函數(shù)，肯定存在一個從X空間到內(nèi)積空間H的變換φ(x)，使得

這樣構(gòu)成的空間是在泛函中定義的所謂可再生核希爾伯特空間RKHS(reproducing kernel Hilbert space).

采用不同的核函數(shù)就得到不同形式的非線性支持向量機(jī).

支持向量機(jī)的基本思想可以概括為：首先通過非線性變換將輸入空間變換到一個高維空間，然后在這個新空間中求最優(yōu)分類面即最大間隔分類面，而這種非線性變換是通過定義適當(dāng)?shù)膬?nèi)積核函數(shù)實現(xiàn)的.

支持向量機(jī)求得的分類函數(shù)，形式上類似于一個神經(jīng)網(wǎng)絡(luò)，其輸出是若干中間層節(jié)點的線性組合，而每一個中間層節(jié)點對應(yīng)于輸入樣本與一個支持向量機(jī)的內(nèi)積，因此早期也被叫做支持向量網(wǎng)絡(luò).

3 基于支持向量機(jī)模型剪接位點的預(yù)測

3.1 編碼方式

為了能夠充分利用原始的堿基位點的數(shù)據(jù)的信息[20]，不采用直接編碼的方式，而是分別統(tǒng)計真實的供體位點、虛假的供體位點、真實的受體位點、虛假的受體位點這些堿基序列在各位點上A、T、C、G四種堿基出現(xiàn)的相對頻率.

然后，具體的在供體位點的編碼方式上，取真實的供體位點序列各位點上四種堿基出現(xiàn)的相對頻率和虛假的供體位點序列各位點上四種堿基出現(xiàn)的相對頻率的差值，就可以得到一個相對頻率差的矩陣，將這個矩陣作為供體位點序列的編碼依據(jù)；同樣地，將真實的受體位點序列各位點上四種堿基出現(xiàn)的相對頻率和虛假的受體位點序列各位點上四種堿基出現(xiàn)的相對頻率的差值矩陣作為受體位點序列的編碼依據(jù)[10]，如表1、表2所示.

表1 供體位點編碼矩陣部分示意圖

表2 受體位點編碼矩陣部分示意圖

3.2 基因剪接位點預(yù)測評價體系

為了確定預(yù)測模型的好壞，需要一些標(biāo)準(zhǔn)來對其進(jìn)行衡量，本文采用最廣泛通用的評價體系，即：敏感性Sn、特異性Sp、準(zhǔn)確度ACC和相關(guān)性系數(shù)MCC值.下面，定義一些變量，以便計算所需要的評價指標(biāo)：

TP：True Positive，即真陽性的數(shù)目；

TN：True Negative，即真陰性的數(shù)目；

FP：False Positive，即假陽性的數(shù)目；

FN：False Negative，即假陰性的數(shù)目.

那么，Sn、Sp、ACC及MCC可以表示為：

根據(jù)上述公式，可以得出：Sn是真實的剪接位點被識別正確的比率；Sp是虛假的剪接位點被識別正確的比率；ACC是剪接位點識別正確的比率；MCC是真實剪接位點和虛假剪接位點的相性.

在實際情況中，當(dāng)Sn、Sp達(dá)到一定的值后，往往會具有負(fù)相關(guān)的關(guān)系.也就是說，當(dāng)?shù)竭_(dá)一定程度之后，Sn繼續(xù)增加，同時假陰性也隨之增加；當(dāng)?shù)竭_(dá)一定程度之后，Sp繼續(xù)增加，同時假陽性也隨之增加.

3.3 特征描述和預(yù)測模型的建立

核主成分分析實際上是在主成分分析的基礎(chǔ)上進(jìn)行的拓展的方法.它是在特征空間進(jìn)行的主成分分析.具體的實驗數(shù)據(jù)，真實的的供體位點和虛假的供體位點的個數(shù)都隨機(jī)取2 000個，采用十倍交叉驗證的方法；同樣地，隨機(jī)取真實的受體位點和虛假的受體位點各2 000個.另外，主成分分析的貢獻(xiàn)率的閾值設(shè)置為90%，經(jīng)過試驗驗證，在供體位點的實驗中，選取3階多項式核主成分分析的方法，可以得到選取的特征為82個；在受體位點的實驗中，選取線性核主成分分析的方法，可以得到選取的特征為83個.

3.4 實驗結(jié)果與分析

通過實驗分別得出多項式核主成分和支持向量機(jī)模型對供體位點的識別結(jié)果、線性核主成分和支持向量機(jī)模型對受體位點的識別結(jié)果，如表3、表4所示.

由表3、表4得到的結(jié)果可以看出，在交叉驗證實驗中，無論是供體位點還是受體位點均在敏感性Sn、特異性Sp上保持了穩(wěn)定性，波動始終在一個合理的范圍，說明這個改進(jìn)的模型是穩(wěn)定和有效的.并且，可以得到供體位點預(yù)測結(jié)果平均為Sn=0.951，Sp=0.93；受體位點的預(yù)測結(jié)果平均值為Sn= 0.9305,Sp=0.913.在供體位點預(yù)測模型方面，基于多項式核主成分分析的特征提取方式相比較其他的模型都取得了更加出色的預(yù)測效果；在受體位點預(yù)測模型方面，基于線性核主成分分析的特征方式相比較其他的模型都取得了更加出色的預(yù)測效果.

表3 多項式核主成分和支持向量機(jī)模型對供體位點的識別結(jié)果

表4 線性核主成分和支持向量機(jī)模型對受體位點的識別結(jié)果

4 總結(jié)

本文在采用概率編碼的基礎(chǔ)上，利用支持向量機(jī)模型對人類剪接位點進(jìn)行預(yù)測，重點研究了基于核主成分分析方法對最終的預(yù)測模型的影響.從實驗結(jié)果看，這種改進(jìn)的基于支持向量機(jī)模型剪接位點的預(yù)測從敏感性和特異性都優(yōu)于其他模型.在特征描述的過程中是需要大量的運(yùn)算時間，比普通的預(yù)測模型的時間復(fù)雜度要高.下一步的工作要能夠在保證算法精度的情況下，盡可能的提高算法效率.

[1]Liu L,Ho Y K,Yau S.Prediction of primate splice site using inhomogeneous Markov chain and neural network[J].DNA and Cell Biology,2007,26(7):477-483.

[2]Staden R.The current status and portability of our sequence handling software[J].Nucleic AcidsResearch,1986,14(1):217-231.

[3]Zhang M,Marr TG.A weightarraymethod for splicing signal analysis[J].Computer Applications in the Biosciences:CABIOS,1993,9 (5):499-509.

[4]Yeo G,Burge C B.Maximum entropy modeling of short sequence motifswith applications to RNA splicing signals[J].Journal of Computational Biology,2004,11(2-3):377-394.

[5]Pertea M,Lin X,Salzberg S L.GeneSplicer:a new computational method for splice site prediction[J].Nucleic Acids Research,2001, 29(5):1185-1190.

[6]Zhang L,Luo L.Splice site prediction with quadratic discriminant analysis using diversitymeasure[J].Nucleic Acids Research,2003, 31(21):6214-6220.

[7]Chen TM,Lu C C,LiW H.Prediction of splice sites with dependency graphsand theirexpanded bayesian networks[J].Bioinformatics,2005,21(4):471-482.

[8]Brunak S,Engelbrecht J,Knudsen S.Neuralnetwork detects errors in the assignment of mRNA splice sites[J].Nucleic Acids Research,1990,18(16):4797-4801.

[9]Degroeve S,Saeys Y,De Baets B,etal.Splice Machine:predicting splice sites from high-dimensional local context representations[J]. Bioinformatics,2005,21(8):1332-1338.

[10]王勇獻(xiàn),王正華.生物信息學(xué)導(dǎo)論[M].清華大學(xué)出版社,2011.

[11]Brunak S,Engelbrecht J,Knudsen S.Prediction of human mRNA donor and acceptor sites from the DNA sequence[J].Journal of Molecular Biology,1991,220(1):49-65.

[12]Castelo R,GuigóR.Splice site identification by idlBNs[J].Bioinformatics,2004,20(suppl1):i69-i76.

[13]Haussler D K D,Eeckman M GR FH.A generalized hidden Markovmodel for the recognition of human genes in DNA[C]//Proc Int Conf on Intelligent Systems for Molecular Biology,St Louis,1996: 134-142.

[14]Staden R,McLachian A.Codon preference and its use in identifying protein coding regions in long DNA sequences[J].Nucleic AcidsResearch,1982,10(1):141-156.

[15]Salzberg SL.Amethod for identifying splice sites and translational startsites in eukaryoticmRNA[J].Computer applications in the biosciences:CABIOS,1997,13(4):365-376.

[16]Burge C B.Identification of Genes in Human Genomic DNA[D]. Stanford:Stanford University,1997.

[17]Wang M,Marín A.Characterization and prediction of alternative splice sites[J].Gene,2006,366(2):219-227.

[18]余萍.基于支持向量機(jī)發(fā)展的研究[J].新課程:教育學(xué)術(shù),2011 (5):65-65.

[19]Xia H,Bi J,Li Y.Identification of alternative 5′/3′splice sites based on themechanism of splice site competition[J].Nucleic AcidsResearch,2006,34(21):6305-6313.

[20]黃金艷,李通化,陳開.基于知識編碼的剪切位點預(yù)測[J].同濟(jì)大學(xué)學(xué)報:自然科學(xué)版,2008,35(11):1548-1551.

【編校：許潔】

Prediction on Slice Site Based on Improved SVM Model

WANG Limei1,ZHENGDajun2,ZHENGChengyou3
(1.DepartmentofMathematicsand Physics,Lincang Teachers'College,Lincang,Yunnan 677000,China;2.CollegeofComputer and Information Technology,Fujian Agriculture and Forestry University,Fuzhou,Fujian 350002,China;3.College ofMechanicaland Control Engineering,Guilin University ofTechnology,Guilin,Guangxi541000,China)

By adopting probability encoding,the support vectormachine(SVM)modelwas used tomake a prediction on human's slice site and the impact of KPCAmethod on the final predictionmodelwas discussed.The experiment shows that this improved SVMmodel issuperior to othermodels in sensitivity and specificity on the prediction ofslice site.

slice;prediction;featureextraction;SVM;KPC Diversity with Quadratic Discriminant analysis)[6]、BN模型(Bayesian Network)[7]、NN模型(Neural Network，NN)[8]、SVM模型(SupportVectorMachine)[9-10]，等等.

TP301.6

A

1671-5365(2014)12-0093-06

2014-06-17修回：2014-08-21

王麗美(1987-)，助教，碩士，研究方向為數(shù)據(jù)挖據(jù)、生物信息

時間：2014-08-22 15:23

http://www.cnki.net/kcms/detail/51.1630.Z.20140822.1523.007.htm l