基于隱馬爾可夫模型的蛋白質(zhì)序列篩選算法

張毅，梅挺

（成都醫(yī)學(xué)院 人文信息管理學(xué)院，四川 成都 610083）

近年來，隨著人們對(duì)蛋白質(zhì)測(cè)序工作的快速發(fā)展，蛋白質(zhì)數(shù)據(jù)庫(kù)中的序列數(shù)量呈現(xiàn)指數(shù)級(jí)的增長(zhǎng)速度，在這存儲(chǔ)有海量的蛋白質(zhì)數(shù)據(jù)庫(kù)中，存在著大量的冗余蛋白質(zhì)序列。雖然目前對(duì)冗余蛋白質(zhì)序列尚未有很明確和統(tǒng)一的定義，但是普遍認(rèn)為，在蛋白質(zhì)數(shù)據(jù)庫(kù)中，如果兩條蛋白質(zhì)序列的具有非常高的相似度，尤其是在整個(gè)序列中控制蛋白質(zhì)功能的特征序列具有很強(qiáng)的相似性時(shí)，則認(rèn)為這兩條蛋白質(zhì)序列是互為冗余的序列。造成這種現(xiàn)象的原因很多，一個(gè)典型的原因即針對(duì)某一同源的蛋白質(zhì)序列進(jìn)行的測(cè)序，并將測(cè)量的結(jié)果存入數(shù)據(jù)庫(kù)中。

由于蛋白質(zhì)數(shù)據(jù)庫(kù)在醫(yī)學(xué)研究、物種研究等方面發(fā)揮著非常重要的作用，利用蛋白質(zhì)數(shù)據(jù)庫(kù)中的信息，有助于人們發(fā)現(xiàn)新物種，尋找物種之間的生物關(guān)系，研究針對(duì)某些特殊病毒的抗生藥物等。然而，如果在蛋白質(zhì)數(shù)據(jù)庫(kù)中存在大量的冗余序列，則可能導(dǎo)致對(duì)這些蛋白質(zhì)數(shù)據(jù)分析的誤差加大。比如在某一蛋白質(zhì)序列簇中，如果冗余序列過多，可能會(huì)夸大這一序列簇的某些功能特征，從而對(duì)蛋白質(zhì)序列間相互關(guān)系的研究產(chǎn)生誤導(dǎo)[1]。

目前，針對(duì)蛋白質(zhì)數(shù)據(jù)庫(kù)冗余的問題，國(guó)內(nèi)外有不少相關(guān)學(xué)者開展了研究，比較有代表性的有Hoblhm和Sander提出的CD-HIT去冗余算法，該算法的設(shè)計(jì)思想是在每個(gè)蛋白質(zhì)序列簇中選取一個(gè)序列作為特征序列，然后再將該簇中的其余序列進(jìn)行冗余檢測(cè)，如果某條序列與該序列的匹配程度超過某一閾值，則該序列被視為冗余序列。該算法是一種非常經(jīng)典的蛋白質(zhì)去冗余算法，目前也有很多算法是基于這一思想進(jìn)行變形實(shí)現(xiàn)。此外還有在2000年由Yona和Linial共同提出了蛋白質(zhì)序列聚類Protomap算法，Enright和Ouzounis提出了蛋白質(zhì)序列分級(jí)聚類Generage算法，2004年由Kawaji和Takenaka提出了基于圖論的蛋白質(zhì)序列分類算法?？傮w而言，這些蛋白質(zhì)分類算法在分類的精確性和分類準(zhǔn)確性兩方面還有待提高。

1 模型的建立與參數(shù)估計(jì)

1.1 模型的建立

從蛋白質(zhì)序列數(shù)據(jù)庫(kù)中選擇一個(gè)蛋白質(zhì)序列作為研究對(duì)象，記為D=D1D2…Dn，該研究對(duì)象也被稱為觀測(cè)對(duì)象。一個(gè)數(shù)據(jù)庫(kù)中的蛋白質(zhì)序列也被視為隱馬爾可夫鏈的初始狀態(tài)的序列分布π，每一條蛋白質(zhì)序列作為一個(gè)狀態(tài)的遷移中的中間狀態(tài)，觀測(cè)結(jié)果是初始狀態(tài)經(jīng)過一定的遷移變化，且和一些隨機(jī)過程共同作用的狀態(tài)結(jié)果。狀態(tài)的遷移概率P1和觀測(cè)得到某一特定狀態(tài)結(jié)果的概率P2在分析之前需要進(jìn)行確立，確立之后為隱馬爾可夫[2]可表示為 φ=（π，P1，P2）。

為了能夠?qū)Φ鞍踪|(zhì)數(shù)據(jù)庫(kù)中所有的序列進(jìn)行匹配篩選，因此需要將蛋白質(zhì)數(shù)據(jù)庫(kù)中的序列出現(xiàn)的概率進(jìn)行抽象和描述。然后才能在此基礎(chǔ)上設(shè)定篩選的規(guī)則，并按照篩選規(guī)則確定的權(quán)值，篩選出最具有代表性的蛋白質(zhì)序列。

假設(shè)在給定的隱馬爾可夫模型中，已經(jīng)有觀測(cè)到某一序列的部分值為：{D1D2…Dk}，且在時(shí)刻k，序列的狀態(tài)為 w1的概率[3]為：

由于該概率的初始值可根據(jù)蛋白質(zhì)數(shù)據(jù)庫(kù)中的常量計(jì)算得到，因此，該計(jì)算式可以采用遞歸的方式計(jì)算得到[4]：

該式經(jīng)過遞歸化簡(jiǎn)后可得：

1.2 模型參數(shù)的估計(jì)

模型參數(shù)建立起來之后，將考慮如何選取合適的參數(shù)，使得對(duì)于一個(gè)給定的隱馬爾可夫模型φ=（π，P1，P2），如何得到其特定子序列的概率最大值，即P（D|φ）為最大。

假定對(duì)一個(gè)給定的隱馬爾可夫模型 φ=（π，P1，P2）和得到的觀測(cè)序列 D={D1，D2，…，Dn}，在時(shí)刻 k 的狀態(tài)為 wi，時(shí)刻 k+1 的狀態(tài)為 wj，滿足這種特征的概率[5]記為 P（i，j），則有：

所以，通過上面的概率計(jì)算式，可以得到在模型確定的條件下，對(duì)于一個(gè)給定的觀測(cè)序列（即某一條蛋白質(zhì)序列）下，k時(shí)刻的狀態(tài)為wi的概率[6]：

其中 N≥i≥1， N≥d≥1。

2 同源蛋白質(zhì)序列篩選過程

蛋白質(zhì)序列篩選過程中最為關(guān)鍵的是找出每個(gè)蛋白質(zhì)序列的關(guān)鍵信息，這些信息直接決定了該蛋白質(zhì)序列的主要功能和特征。因此定位和篩選出每條蛋白質(zhì)序列中的關(guān)鍵信息是進(jìn)行同源蛋白質(zhì)序列篩選的重要前提。

蛋白質(zhì)數(shù)據(jù)庫(kù)中每條序列記為D=D1D2-Dm-1Dm，隱馬爾可夫鏈階梯步長(zhǎng)記為spl，在一條完整的序列中定義一個(gè)子片斷記為d=d1d2-dr-1dr。則子片斷d出現(xiàn)的概率[8]為：

由此，可定義若存在子片斷d條件下，各個(gè)序列值的概率[9]：

按照這種條件概率計(jì)算式，可以進(jìn)一步得到子片斷d的詳細(xì)計(jì)算式[10]：

再定義整個(gè)蛋白質(zhì)序列中，每一種可能的子片斷xd出現(xiàn)的概率[11]：

根據(jù)如上定義，可以得到任意一個(gè)子片斷的重要度描述參數(shù)Weight[12]。

確定了任意一個(gè)子片斷的權(quán)值后，再按照序列的模式匹配，定位序列之間的匹配位置和匹配程度。若兩個(gè)對(duì)比的蛋白質(zhì)序列長(zhǎng)度不等，記 D1中有 d[1：x]特征序列，記 D2中有 d[1：y]特征序列。通過調(diào)整特征序列的長(zhǎng)度，記錄兩個(gè)蛋白質(zhì)序列中的最大匹配權(quán)值，該權(quán)值即為兩個(gè)蛋白質(zhì)序列的匹配程度描述參數(shù)。對(duì)于兩個(gè)特征序列d[1：x]和d[1：y]的最大匹配權(quán)值計(jì)算式為[7]：

如此遞歸計(jì)算，最后得到最終結(jié)果。

3 測(cè)試結(jié)果

采用文中設(shè)計(jì)的基于隱馬爾可夫模型的蛋白質(zhì)序列篩選算法SWISS-PROT對(duì)蛋白質(zhì)數(shù)據(jù)庫(kù)中的數(shù)據(jù)進(jìn)行了分類篩選測(cè)試，通過本文設(shè)計(jì)的算法，對(duì)蛋白質(zhì)數(shù)據(jù)庫(kù)中的蛋白質(zhì)序列特征進(jìn)行提取和匹配，當(dāng)匹配到兩條蛋白質(zhì)序列的關(guān)鍵信息是一致的，則將這兩條蛋白質(zhì)序列標(biāo)記為同源蛋白質(zhì)序列，同時(shí)將得到的篩選結(jié)果與目前公認(rèn)的同源序列結(jié)果進(jìn)行對(duì)比，得出篩選的正確率。測(cè)試結(jié)果如表1所示。

表1 基于隱馬爾可夫模型的蛋白質(zhì)序列篩選算法測(cè)試結(jié)果Tab.1 Hidden Markov Model-based protein sequence selection algorithm results

測(cè)試結(jié)果表明，文中所設(shè)計(jì)的蛋白質(zhì)篩選算法對(duì)蛋白質(zhì)數(shù)據(jù)庫(kù)中篩選出了大量的同源蛋白質(zhì)序列，根據(jù)與目前公認(rèn)的同源蛋白質(zhì)序列進(jìn)行結(jié)果對(duì)比表明，在篩選過程中篩選出了蛋白質(zhì)數(shù)據(jù)庫(kù)中的絕大多數(shù)的同源蛋白質(zhì)序列，且篩選結(jié)果的正確率達(dá)到了95%以上，從篩選的精度而言，本設(shè)計(jì)的算法具有較高的篩選正確率。

4 結(jié)束語

從蛋白質(zhì)數(shù)據(jù)庫(kù)中對(duì)蛋白質(zhì)序列進(jìn)行分類和篩選有著非常現(xiàn)實(shí)的意義，尤其是面對(duì)指數(shù)級(jí)增長(zhǎng)的蛋白質(zhì)數(shù)據(jù)庫(kù)，只有通過對(duì)蛋白質(zhì)數(shù)據(jù)庫(kù)進(jìn)行去冗余的處理，篩選出真正代表每個(gè)蛋白質(zhì)簇的特征序列，才能建立更有實(shí)用價(jià)值的蛋白質(zhì)數(shù)據(jù)庫(kù)。目前這一問題也是全球蛋白質(zhì)序列研究的一個(gè)熱點(diǎn)問題，本文通過引入隱馬爾可夫模型對(duì)蛋白質(zhì)序列進(jìn)行分析篩選，探索了蛋白質(zhì)數(shù)據(jù)庫(kù)特征序列篩選的新方法，已進(jìn)行的測(cè)試結(jié)果也表明該方面在篩選的精度上可以達(dá)到95%以上。

[1]張成崗，歐陽(yáng)曙光，張紹文，等.基于PC/Linux的核酸序列分析系統(tǒng)的構(gòu)建及其應(yīng)用 [J].生物化學(xué)與生物物理進(jìn)展，2001（2）：263-266.

ZHANG Cheng-gang， OU YANG Shu-guang， ZHANG Shaowen， et al.Based PC/Linux system， Construction and application of the nucleic acid sequence analysis system based on PC/Linux[J].Biochemistry and Biophysics，2001（2）：263-266.

[2]陳英，彭心昭，樸英杰.自噬基因APG5基因結(jié)構(gòu)的生物信息學(xué)分析[J].遺傳學(xué)報(bào)，2001，28（11）：1077-1084.

CHEN Ying， PEN Xin-zhao， PU Ying-jie.Bioinformatics analysis of autophagy gene APG5 gene structure[J].Genetics，2001,28(11)：1077-1084.

[3]齊建勛，肖奕.基于小波方法的蛋白質(zhì)非規(guī)則二級(jí)結(jié)構(gòu)預(yù)測(cè)[J].科學(xué)通報(bào)，2002（6）：425-430.

QI Jian-xun，XIAO Yi.Non-wavelet-based method of protein secondary structure prediction rules[J].Chinese Science Bulletin，2002（6）：425-430.

[4]任力鋒，張波，劉輝.蛋白質(zhì)序列信息的提取與蛋白質(zhì)結(jié)構(gòu)預(yù)測(cè)[J].北京生物醫(yī)學(xué)工程，2005（3）：237-238.

REN Li-feng， ZHANG Bo， LIU Hui.Protein sequence information extraction and protein structure prediction[J].Beijing Biomedical Engineering，2005（3）：237-238.

[5]霍紅衛(wèi)，肖智偉.基于最大權(quán)值路徑算法的DNA多序列比對(duì)方法[J].軟件學(xué)報(bào)，2007，18（2）：185-195.

HUO Hong-wei，XIAO Zhi-wei.A multiplealignment approachforDNA sequencesbasedonthemaximum weighted path algorithms[J].Journal of Software，2007，18（2）：185-195.

[6]鄒權(quán)，郭茂祖，王曉凱，等.基于關(guān)鍵字樹的DNA多序列星比對(duì)算法[J].電子學(xué)報(bào)，2009，37（8）：1764-1850.

ZOU Quan， GUO Mao-zu， WANG Xiao-kai， etal.Keyword-based tree of the DNA sequence star more than the algorithm[J].Electronics Technology，2009，37（8）：1764-1850.

[7]王艷春，何東健.神經(jīng)網(wǎng)絡(luò)在蛋白質(zhì)二級(jí)結(jié)構(gòu)預(yù)測(cè)中的應(yīng)用[J].安徽農(nóng)業(yè)科學(xué)，2006（16）：4172-4174.

WANG Yan-chun；HE Dong-jian，Neural network in protein secondary structure prediction in two[J].Anhui Agricultural Sciences，2006（16）：4172-4174.

[8]阮曉鋼，孫海軍.編碼方式對(duì)蛋白質(zhì)二級(jí)結(jié)構(gòu)預(yù)測(cè)精度的影響[J].北京工業(yè)大學(xué)學(xué)報(bào)，2005，31（3）：227-235.

RUAN Xiao-gang，SUN Hai-jun.Researchon encode influencing protein secondary structure prediction[J].Journal of Beijing University of Technology，2005，31（3）：227-235.

[9]劉帥，馬志強(qiáng)，劉清雪，等.基于自適應(yīng)免疫遺傳算法的多序列比對(duì)[J].信息技術(shù)，2007（2）：15-17，111.

LIu Shuai， MA Zhi-qiang， LIU Qing-xue， et al.Adaptive immune genetic algorithm based on multiplesequence alignment[J].Information Technology，2007（2）：15-17，111.

[10]郭衛(wèi)斌，施保昌，王能超.多重生物序列對(duì)準(zhǔn)及其算法綜述[J].高技術(shù)通訊，2001，11（6）：96-102.

GUO Wei-bin， SHI Bao-chang， WANG Neng-chao.Multiple biological sequence alignment and its algorithm[J].High Technology，2001，11（6）：96-102.

[11]關(guān)敏，辜華良，常雅萍，等.DNA核苷酸堿基序列分析軟件的編寫和應(yīng)用[J]，白求恩醫(yī)科大學(xué)學(xué)報(bào)，2001，27（5）：467-469.

GUAN Min， GU Hua-liang， CHANG Ya-ping， et al.DNA nucleotide base sequence analysis software and application[J].BethuneUniversityofMedicalSciences，2001，27（5）：467-469.

[12]杜世平.隱馬爾可夫模型在生物信息學(xué)中的應(yīng)用[J].大學(xué)數(shù)學(xué)，2004，20（5）：24-29.

DU Shi-ping. HMM in bioinformatics applications[J].University Mathematics，2004，20（5）：24-29.