張 斐

（陜西警官職業(yè)學(xué)院警察技術(shù)系 西安 710021）

1 引言

所謂Motifs（模體）指的是在一組相關(guān)的蛋白質(zhì)或者DNA序列中重復(fù)出現(xiàn)的具有生物意義的序列模式，它能夠代表一個蛋白質(zhì)家族，隨著計算機技術(shù)在生物領(lǐng)域的不斷成熟和推廣，關(guān)于生物序列中Motifs的自動預(yù)測技術(shù)已經(jīng)成為一門新興技術(shù)，如何設(shè)計出預(yù)測算法以更好地對生物信息進行研究就成為了生物信息領(lǐng)域一個重要的研究課題。

一個蛋白質(zhì)家族所有的或大多數(shù)的成員共同擁有的Motifs極可能是該家族執(zhí)行某些重要功能或組成結(jié)構(gòu)不可或缺的部分。預(yù)測出一個蛋白質(zhì)家族共同的Motifs就能刻畫該家族特征，從而可以利用這些特征來進行發(fā)掘蛋白家族新成員等有意義的新發(fā)現(xiàn)。但是對于通過各種生物信息學(xué)方法識別的Motifs，目前沒有很好的辦法辨別真假和優(yōu)劣［1］。

本文通過研究對不同Motifs預(yù)測算法在同一數(shù)據(jù)集上測試后的評價策略，針對傳統(tǒng)的算法預(yù)測問題，采用新的評價方案和評價標(biāo)準(zhǔn)對算法預(yù)測的結(jié)果進行分析。

2 算法的種類

Motifs預(yù)測是將生物序列中的氨基酸或堿基轉(zhuǎn)化成為相應(yīng)的字符串，在不同字符串序列中尋找最大公共子串，再通過生物學(xué)特征將這些字符串提取，與通過實驗方法獲得的生物信息數(shù)據(jù)庫進行匹配。尋找最大公共子串的算法設(shè)計思想和數(shù)學(xué)模型是Motifs預(yù)測的關(guān)鍵。Motifs預(yù)測方法分為兩類：統(tǒng)計學(xué)方法，如Gibbs采樣算法、MEME和HMMER 等 ；確 定 性 方 法 ，如 Pratt、TEIRESIAS、SPLASH以及SPAT等，這些算法均能發(fā)現(xiàn)隱藏在序列中的弱模體（weak Motifs），但統(tǒng)計學(xué)Motifs預(yù)測方法在實際應(yīng)用更為廣泛。

統(tǒng)計學(xué)Motifs預(yù)測算法遵循了不同的數(shù)學(xué)方法和原理，但都避免不了自身的不足，例如Gibbs采樣算法雖具有簡單、計算速度快的優(yōu)點，但卻是局部優(yōu)化算法，不能保證結(jié)果的全局最優(yōu)性。而EM算法較好解決了具有隱變量模型的估計，但對于較短模體，EM算法極易陷入局部極值，從而得不到最優(yōu)解［2］。

3 主要算法描述

3.1MEME算法

MEME算法是基于最大期望值（EM）算法來識別Motifs的一種迭代算法，它交替執(zhí)行兩個步驟：期望值步驟E和最大值步驟M［3］。在步驟E中，通過給出的觀察數(shù)據(jù)和W的現(xiàn)有估計值，計算出隱變量的分布。在步驟M中，通過步驟E給出的隱變量的假定分布，計算出參數(shù)的最優(yōu)值。

算法1

Begin：

Input（輸入序列 s={s1，…，sN}）：

初始化變量：

LengthM（待處理的Motifs的長度）

NumberM（識別不同的Motifs的數(shù)目）

Iterative（設(shè)定的迭代次數(shù)）

EM（I）（在數(shù)據(jù)集中所期望每個Motifs出現(xiàn)的算法Algo

rithm（））：

｛

For Motifs=1 to NumberM

｛

For（數(shù)據(jù)集中的每個子序列根據(jù)從子序列得到的起

始位置）；

運行修改后的EM；

共迭代Iterative次；

EndFor

｝

EndFor

給定W和λ(0)選擇初始參數(shù)值θ(0)；執(zhí)行EM算法后建立新模型；釋放數(shù)據(jù)；

集中處理得到的Motifs

｝

在循環(huán)中，EM算法［4］選擇隨機的起始位點來迭代運行。其中，起始位點所輸入的數(shù)據(jù)集中的子序列得到的，而只有那些能使模型取得最大可能性值的起始位點被選中，EM算法從這個起始位點開始運行并最終迭代若干次后，得到一個相對穩(wěn)定值后結(jié)束。

3.2 基于貪心EM算法的改進預(yù)測算法（PKGE算法）

PKGE是基于Kd-樹的貪心EM預(yù)測算法，Kd-樹是通過定義一個遞歸的二進制的K維數(shù)據(jù)集，它的根節(jié)點包括全部數(shù)據(jù)，每一層通過檢測不同屬性（關(guān)鍵字）值以決定選擇分支的方向，從而加快查詢速度。所以算法的時間復(fù)雜度比較高，只適用于尋找短序列的 Motifs［5］。

算法執(zhí)行的步驟如下。

算法2

Begin：

設(shè)N條序列，長度從數(shù)據(jù)集中取值。

初始化字符串X={xi}(i=1，…，n)，滿足n

While（Kd-樹結(jié)構(gòu)→保守序列→K值最優(yōu)）

｛

For（依次掃描所有序列）

Kd-樹來處理數(shù)據(jù)集X，通過質(zhì)心C找到一致性序列

EndFor

｝

參數(shù)迭代：

設(shè)置模型劃分度

While（局部EM優(yōu)化→g劃分→似然度最優(yōu)）

｛

For（參數(shù)迭代掃描）

初始值執(zhí)行EM

g+1劃分的混合模型

EndFor

｝

求出Motifs的最大數(shù)量

算法描述了在Motifs預(yù)測中的一個混合Motifs模型。通過引入Kd-樹結(jié)構(gòu)，使數(shù)據(jù)集中，似然函數(shù)單調(diào)增加，徹底搜索候選序列部分的參數(shù)，從而使得其它Motifs大量存在的可能性大大降低。

4 評價策略

算法測試的硬件系統(tǒng)環(huán)境為IBMX365服務(wù)器、聯(lián)想PC。軟件系統(tǒng)環(huán)境為Win7（Matlab 7.1）、Linux red hat 9.0（MEME 3.4.5）。評價中采用的統(tǒng)計軟件有SigmaPlot9.0、SPSS22.0。

利用訓(xùn)練數(shù)據(jù)集和測試數(shù)據(jù)集驗證。在實驗中依據(jù)經(jīng)驗值將參數(shù)λ設(shè)置成0.8，并設(shè)置K=1來指定一個Motifs的相鄰矩陣，參數(shù)T的值為T=N/2（序列長度的一半）［5］。

對比使用MEME算法來進行驗證。其中在MEME中選擇的是anr模式即任意重復(fù)數(shù)量模式，評價策略見圖1。

圖1 評價策略圖

4.1 采用訓(xùn)練數(shù)據(jù)集的實驗

從PRINTS數(shù)據(jù)庫下載部分蛋白質(zhì)家族序列，隨機產(chǎn)生10條長度在200bp～250bp之間的蛋白質(zhì)序列，通過多次比對設(shè)定Kd-樹劃分值為6，葉子節(jié)點字符串的長度設(shè)定為 5，Motifs長度為 10［5］，由于選定序列源于生物數(shù)據(jù)庫，雖經(jīng)過人工拼接，但仍有部分片段保留，因而程序執(zhí)行后仍能找到8個Motifs。

4.2 采用測試數(shù)據(jù)集的實驗

4.2.1 Fingerprints法測試

我們選擇的PRINTS數(shù)據(jù)庫［6］包含了大量蛋白質(zhì)家族，每個家族成員中都有Motifs出現(xiàn)，F(xiàn)ingerprints法已成為數(shù)據(jù)庫中標(biāo)準(zhǔn)的序列分析工具［7］，有網(wǎng)絡(luò)版可使用。當(dāng)前最新的PRINTS含有1600家族的9800個Motifs［8］。

在這個實驗中評估預(yù)測Motifs的準(zhǔn)確率采用了信息量 IC（Information Content）［9］。

其中表示字符αl在背景序列中出現(xiàn)的頻率，IC值越高說明序列越保守，因而可以比較Motifs在不同序列中的數(shù)量，實際計算中可通過統(tǒng)計位置權(quán)重矩陣得到［10］。

我們選用表1中所列的4個PRINTS蛋白質(zhì)家族作為測試集，考慮到時間復(fù)雜度，選定每個家族的各序列長度在150bp～300bp之間，用Fingerprints法找出在每個成員出現(xiàn)一次的Motifs（即單拷貝序列），再將這些Motifs從數(shù)據(jù)集中刪除。我們設(shè)定Motifs的長度為W，采用MEME和PKGE算法發(fā)現(xiàn)蛋白質(zhì)家族中最多有20個Motifs。

表1 PRINTS的蛋白質(zhì)家族

圖2柱狀圖表示在每條序列中Motifs出現(xiàn)的數(shù)量。其中黑色柱狀圖表示MEME在4個蛋白質(zhì)家族的預(yù)測數(shù)量，灰色柱代表PKGE算法預(yù)測的Motifs數(shù)量，由于所有Motifs在序列中有相同的發(fā)生率，因此可以用IC值來比較預(yù)測效率［11］。其中MEME的IC值可通過運行軟件，統(tǒng)計輸出的IC值后求平均值得到，而PKGE算法計算IC值，可通過對PWM矩陣中的序列字符的對應(yīng)值求平均后得到。設(shè)定相同長度為W的Motifs的IC的平均值標(biāo)記在圖2柱狀圖的上方，試驗統(tǒng)計數(shù)據(jù)表明通過PKGE算法測定的IC值較MEME的要高。

4.2.2 MEME-MAST算法測試［12］

實驗?zāi)康氖峭ㄟ^比較MEME和PKGE算法對蛋白質(zhì)家族的Motifs預(yù)測，得到對目標(biāo)序列的精確性分析，由于以上的實驗結(jié)果通過IC值證實我們的算法在發(fā)現(xiàn)大量更保守的Motifs時有一定的作用，因此下一步中使用MEME-MAST來預(yù)測Motifs。

MEME算法的基本思想是把序列集分成Motifs模式和背景模式，利用EM算法計算出每個字母在短序列中每個位置出現(xiàn)的概率，然后算出該短序列分別出現(xiàn)在Motifs模式和背景模式下的概率，最后通過統(tǒng)計方法確定該短序列是不是一個Motifs；MAST算法是計算數(shù)據(jù)庫中每個序列和給定一組Motifs中每個Motifs的匹配值。對于每個序列，匹配值就是各種不同類型的P值，它們被用來決定序列和Motifs集的匹配度和Motifs大概的順序以及各個Motifs出現(xiàn)在序列中的間隔［13］。

選取表2所示4個PROSITE蛋白質(zhì)家族的數(shù)據(jù)集［14］，在每個家族被隨機的挑選部分序列（10條）作為Motifs預(yù)測的數(shù)據(jù)集。設(shè)定W=10，通過算法去除冗余，表3所示為預(yù)測的PROSITE蛋白質(zhì)家族的Motifs的數(shù)量，可以看出PKGE算法識別了大量的Motifs。

圖2 PKGE算法與MEME算法預(yù)測Motifs比較

表2 PRINTS的蛋白質(zhì)家族

表3 預(yù)測的PROSITE蛋白質(zhì)家族Motifs數(shù)量對比

MEME-MAST算法計算Motifs的目標(biāo)序列后統(tǒng)計E值，實驗方法如下：利用MAST和PKGE算法處理一段序列，在MAST輸入一段已知的Motifs并計算每條序列的E值，并將開始目標(biāo)序列的E值作為陽性分類的依據(jù)。

考慮到算法的敏感度和特異性，真陽性的減小降低了敏感度，而假陽性的減小對提高特異度有利。為了提高正確率，需要獲得較大的敏感度和較大的特異度，因此選擇合適的Motifs長度非常重要，文中選擇了如表2所示長度為100bp～360bp的序列。

圖3是利用SPSS繪制的算法在四個蛋白質(zhì)家族數(shù)據(jù)中執(zhí)行的ROC曲線，ROC（Receiver Operating Characteristic，接收者工作特征曲線）是利用真陽性和假陽性繪制的曲線［15］。曲線的位置用來判斷其所代表算法的優(yōu)劣，曲線越靠近左上角，或者曲線下方的面積越大，代表算法的分類的精確度越高。從曲線可以清晰看出PKGE算法預(yù)測精確度較高。

圖3 兩種算法預(yù)測Motifs的ROC曲線

5 結(jié)語

本文采用統(tǒng)計學(xué)方法來比較和篩選Motifs預(yù)測軟件的預(yù)測結(jié)果，將數(shù)據(jù)集中已知Motifs作為參考，將Motifs預(yù)測算法對數(shù)據(jù)集的搜索結(jié)果作為對數(shù)據(jù)集中序列的分類。通過測試集來測試Motifs預(yù)測算法的精確性。分類效果越好，Motifs模型越能真實反映蛋白質(zhì)家族的情況。反之，模型就越可能是隨機產(chǎn)生的而不具有生物意義。

評價中應(yīng)用PKGE算法對訓(xùn)練數(shù)據(jù)集和測試數(shù)據(jù)集進行了實驗，結(jié)合同樣基于EM算法的MEME算法工具進行了對比實驗，應(yīng)用我們的評測方案在實驗中搜集了大量實驗參數(shù)，無論是在相同長度的Motifs還是在時間復(fù)雜度上都較MEME有所優(yōu)化。通過運用信息量IC等指標(biāo)對兩種算法工具進行了定量檢測，最后結(jié)合醫(yī)學(xué)檢測中常用的ROC曲線進行了特異度和敏感度的比較，進一步驗證PKGE算法的改進性。

結(jié)合生物實驗中總結(jié)的經(jīng)驗方法對照通過算法獲取的Motifs能夠有效地提高預(yù)測算法的精確性，篩選后的數(shù)據(jù)集還需要生物實驗來驗證才能最終被確定。

本文的評價策略還存在一定的不足，例如本身在一個蛋白質(zhì)家族的成員序列之間就存在一定的差異，因而通過隨機選取的訓(xùn)練集和測試集序列就會有一定的偏差。此外受到實驗中軟硬件環(huán)境的制約，評價策略的效果也會受到一定的影響。因而在后面的研究中還需要對訓(xùn)練集和測試集序列建立更好的數(shù)據(jù)模型，以提高通過本文評價策略篩選Motifs的精確性。

［1］杜春鵑，朱云平，賀福初，等.蛋白質(zhì)家族模體（motif）的評價策略［J］.北京生物醫(yī)學(xué)工程，2005，24（2）：97-102.DU Chunjuan，ZHU Yunping，HE Fuchu，et al.A New Strategy to Evaluate Protein Motifs［J］.Beijing Biomedical Engineering，2005，24（2）：97-102.

［2］張斐，譚軍，謝競博.基于不同算法的motif預(yù)測比較分析與優(yōu)化［J］.計算機工程，2009，35（22）：94-96.ZHANG Fei，TAN Jun，XIE Jingbo.Comparison，Analysis and Optimization of Motif Finding Based on Different Algorithms［J］.Computer Engineering，2009，35（22）：94-96.

［3］TIMOTHY L B，CHARLES E.The value of prior knowledge in discovering Motifs with MEME.Proceeding of the Third International Conference on intelligent Systems for Molecular Biology，Menlo Park，California，1995［C］.AAAI Press，1995，3：21-29.

［4］王維彬，鐘潤添.一種基于貪心EM算法學(xué)習(xí)GMM的聚類算法［J］.計算機仿真，2007，24（2）：65-68.WANG Weibin，ZHONG Runtian.A C lustering A lgorithm Based on G reedy EM A lgorithm Learning GMM［J］.Computer Simulation，2007，24（2）：65-68.

［5］張懿璞.轉(zhuǎn)錄因子結(jié)合位點識別問題的算法研究［D］.西安：西安電子科技大學(xué)，2014：120-121.ZHANG Yipu.Algorithm research on the problem of transcription factor binging sites dentification［D］.Xi'an：Xidian University，2014：120-121.

［6］ T K Attwood，M D R Croning，D R Flower，et al.PRINT-S：the database formerly known as PRINTS［J］.Nucleic Acids Res，2000，28：225-227.

［7］杜耀華，倪青山，王正志.利用序列保守模體和局部構(gòu)象信息預(yù)測轉(zhuǎn)錄因子結(jié)合位點［J］.生命科學(xué)研究，2006，10（3）：215-223.DU Yaohua，NI Qingshan，WANG Zhengzhi.Computerational Prediction of Transcription Factor Binding Sites Based on Conserved Motif and Local Conformational Knowledge in Genomic Sequences［J］.Life Science Research，2006，10（3）：215-223.

［8］G Pavesi，P Mereghetti，F(xiàn) Zambelli，et al.MoD Tools：regulatory Motif discovery in nucleotide sequences from co-regulated or homologous genes［J］.Nucleic Acids Res，2006，34（Web Sever issue）：566-570.

［9］ T K Attwood，M D R Croning，D R Flower，et al.PRINT-S：the database formerly known as PRINTS［J］.Nucleic Acids Res，2000，28：225-227.

［10］王欣.模體的并行聚類算法及在短柄草核心啟動子預(yù)測的應(yīng)用研究［D］.青島：青島大學(xué)，2016.WANG Xin.A parallel clustering algorithm for the model body and its application in the prediction of the core Promoter of the short stalks［D］.Qingdao：Qingdao University，2016.

［11］劉維，陳漢武，陳崚.一種識別基因調(diào)控元件的新型優(yōu)化算法［J］.計算機應(yīng)用與軟件，2013，30（1）：21-28.LIU Wei，CHEN Hanwu，CHEN Ling.A Novel Optimisation Algorithm for Gene Regulatorary Elements Recognition［J］.Computer Applications and Software，2013，30（1）：21-28.

［12］Grundy William N，Bailey TL，Elkan CP，et al.Meta2MEME：Motif2based hidden markov models of biological sequences［J］.Computer Applications in the Biosciences，1997，13（4）：397-406.

［13］霍紅衛(wèi)，郭丹丹，于強，等.（l，d）-模體識別問題的遺傳優(yōu)化算法［J］.計算機學(xué)報，2012，35（7）：1429-1439.HUO Hongwei，GUO Dandan，YU Qiang，et al.Genetic Optimization for（l，d）-Motif Discovery［J］.Chinese Journal of Computers，2012，35（7）：1429-1439.

［14］T L Bailey，C Elkan.Unsupervised learning of multiple Motifs in biopolymers using expectation maximization［J］.Machine Learning，1995，21：51-83.

［15］R Durbin，S Eddy，A Igogh，et al.生物序列分析，第三章：蛋白質(zhì)和核酸的概率論模型［M］.北京：清華大學(xué)出版社，2010.R Durbin，S Eddy，A Igogh，et al.Biological sequence analysis，third chapter：the probability theory model of protein and nucleic acid［M］.Beijing：Tsinghua University Press，2010.