魏 靜 徐彭娜 江育娥 林 劼

(福建師范大學軟件學院 福建 福州 350108)

基于位置信息的非比對序列聚類方法

魏 靜 徐彭娜 江育娥 林 劼*

(福建師范大學軟件學院 福建 福州 350108)

非比對序列相似性模型直接采用序列自身的統(tǒng)計信息來計算序列之間的相似度，具有運算速度快、聚類結果準確等優(yōu)點。提出一種基于位置信息的非比對序列相似性模型，通過提取K詞模型中每個詞的Local Frequency(LF)，計算對應K詞的LF熵，并結合K詞頻率進行序列的特征提取，應用于蛋白質聚類。實驗結果表明該方法能夠有效地提取序列的信息，提高聚類的準確率。

K-詞 LF熵 K-means聚類 位置信息

0 引 言

在生物信息研究領域中，序列的特征提取和相似性檢測是十分重要的，對大量的生物序列進行聚類分析是生物數(shù)據(jù)挖掘的研究方向之一，其應用前景十分廣泛。近年來，快速發(fā)展的生物科學技術使得生物信息處理領域的數(shù)據(jù)資源快速增長。傳統(tǒng)的比對序列方法面對龐大的生物數(shù)據(jù)集，越來越不能滿足需求，而且比對序列法的計算過程是非常耗時的，而非比對法直接利用序列本身所攜帶的信息來計算序列之間的相似度。因此，在序列相似性研究中，非比對方法越來越受歡迎。

序列比對方法一般是采用BLAST[1]和FASTA[2]這兩類算法，他們均是基于識別“比對種子”的啟發(fā)式算法，并得到廣泛的應用。非比對法包含有圖形表示法、概率統(tǒng)計方法、K-詞的方法、文本壓縮方法以及信息理論方法等。Dai等[3]在序列比較的非比對法研究中，通過集成生物序列中字的重疊結構和背景信息，提出了一種新的統(tǒng)計方法。Bonham-Carter等[4]等在文獻中解釋幾個不同領域的非比對分析方法，并提供了幾個明確的例子來演示應用程序。Randic等[5]等通過距離矩陣法把蛋白質序列用圖形方法表示。在許多非比對方法研究中均是基于K-詞頻率，K-詞算法是非常受歡迎的非比對法。一條生物序列通過一個長度為K的滑動窗口，在窗口中的這一段序列是一個K-詞。K-詞頻率算法是計算每一個詞出現(xiàn)的頻數(shù)，建立基于頻率值的特征向量?；贙-詞頻率的非比對方法通常是把序列中的每個K-詞看作為獨立的個體，從而忽略詞與詞之間的聯(lián)系和整體性。序列特征不僅僅是指詞頻特征，K-詞出現(xiàn)的位置間的相關性和堿基的性質都包含大量的序列信息。余宏杰[6]根據(jù)序列的順序屬性，對K-詞定義一種復合變換，提出一種新的非比對序列的比較方法。鄧偉[7]在研究序列相似性和構建進化樹時，結合核苷酸的化學結構分類，將已有的混沌游走表達模型進行了改進，并提取DNA序列特征構建特征向量。Leimeister等[8]在非比對序列比較法研究中，提出使用間隔詞來降低相鄰詞匹配間的統(tǒng)計相關性，通過模式的“匹配”和“不相關”位置定義，使用遞歸散列和位操作快速實現(xiàn)。

本文通過詞的位置信息計算LF值并計算熵值，得出每條序列對應詞的LFE(即Local Frequency Entropy的縮寫)，結合蛋白質序列K-詞的詞頻特征構建序列的特征向量。實驗結果證明基于位置信息的非比對序列聚類方法是一種非常有效的序列聚類方法。

1 相關工作研究

眾所周知，一般的基于K-詞頻率的非比對方法研究只包含詞頻信息，并不能夠完全地提取出序列的特征，而特征向量的不完整性則會嚴重影響聚類的效果。生物序列中所包含的信息不僅僅是序列的組成，每個K-詞的位置分布以及每個詞產(chǎn)生的順序都蘊含了大量的信息。

Bao等[9]根據(jù)Local Frequency計算熵值，根據(jù)堿基的分類，位置分布特征和發(fā)生頻率，將一條DNA序列劃分為三個新序列，測量12維空間中的相似性，稱為Category-Position-Frequency 模型(簡稱CPF模型)。Li等[10]根據(jù)詞頻在整個原始序列中的位置信息，首次提出Global Frequency(簡稱GF)，計算序列的相似性。許景皓[11]在進行蛋白質結構功能預測時，利用氨基酸的位置信息計算氨基酸距離對，檢測蛋白質遠程同源性和計算蛋白質序列相似性。楊希武[12]通過獲取序列中K-詞的位置間的相互關系，簡化得到K-詞的位置序列并按照數(shù)值大小進行排序，序列間的相似性通過歐氏距離進行計算。吳迪[13]在對序列進行聚類操作前，將序列預處理為等長的向量，依據(jù)序列元素的相似度和Top-k最大序列模式提出一種新的序列聚類算法。Shi等[14]提出的TSM方法，利用核苷酸堿基及其化學性質將一條DNA序列分為三條符號序列，提取DNA序列的特征并進行序列相似性分析。黃玉娟[15]在進行DNA序列研究時，根據(jù) K-詞頻度和其位置信息，定義一個新的概率分布，為了降低堿基突變造成的影響，新的概率分布減去了背景概率，它們之間的相對差異性可以用來表征一條DNA序列。胡清銘[16]根據(jù)氨基酸殘基的位置，提出一種新的氨基酸殘基位置特征提取方法，獲得的特征向量維數(shù)低、計算簡單，而且能夠有效地提取氨基酸的位置信息。Kurgan等[17]在利用氨基酸組成方法的基礎上，根據(jù)氨基酸的位置信息，進行預測蛋白質結構和功能。唐杰[18]在序列相似性的比較上提出基于K-詞位置的序列非比對方法，用機器學習的一些方法來處理數(shù)據(jù)，然后對序列進行分類。

(1)

基于位置信息的非比對序列聚類方法，綜合考慮每個K-詞的位置信息和詞頻特征，盡可能完整地從生物序列中提取有效的特征，能夠準確地反映出生物序列信息和功能之間的關聯(lián)性。

2 基于位置信息的非比對序列的方法

本文的方法首先是將序列采用K-詞模型進行映射，預處理字長為K，從而獲得|Σ|k個特征詞，即K-詞，Σ是序列符號集合，|Σ|是序列符號集合大小。統(tǒng)計每個K-詞出現(xiàn)的位置及其頻數(shù)，通過式(2)計算出每個詞的LF值，LF值即為K-詞出現(xiàn)的相鄰兩個位置之間差的倒數(shù)；依次對所有詞根據(jù)式(2)進行該詞的LF值計算，并得到每條序列的每個詞的LF值序列，即每條序列經(jīng)過計算得到|Σ|k個LF值的數(shù)值序列。

定義LF值V為：

(2)

根據(jù)得到的LF值，由式(3)、式(4)、式(5)、式(6)計算出LF熵，即LFE。對于詞W的LFE計算過程如下：

1) 序列的部分和，令：

(3)

即：

2) 計算序列S的總和Z，即：

(4)

3) 計算每個位置t的離散概率，即：

(5)

4) 計算該序列的熵LFE的值VE，即：

(6)

結合LFE和詞頻信息作為序列的特征，來提取序列的信息。通過計算N條序列的VE構成N×|Σ|k的特征矩陣，結合蛋白質序列的每個K-詞的詞頻特征，構成N×2×|Σ|k的特征矩陣。通過K-means聚類方法對序列特征進行聚類。根據(jù)聚類結果計算出準確率和召回率。通過F-measure評價標準對模型進行評價。

LFE強調每個詞出現(xiàn)的位置順序和這個詞在序列中的局部密度，一個LF不能包含這個詞的全局信息，但是一系列的LFE可以更加精確和清晰地表示出這個K-詞的全局分布。采用LF綜合考慮到在轉換后的特征空間包含足夠的原始序列信息，避免序列信息的丟失。以Local Frequency為基礎的計算而得的熵值能精確地反映序列的結構信息。序列的相似性作為生物信息學中的基本度量，在許多場合中都會有應用，包括預測一段未知序列的作用和功能、構建生物或者物種的系統(tǒng)進化樹、分析物種的同源性等。

3 實驗與結果分析

3.1 數(shù)據(jù)來源

實驗數(shù)據(jù)來源于PBIL的HOMOLENS[21]數(shù)據(jù)庫中的蛋白質數(shù)據(jù)集，從中隨機選取20個family進行實驗，同時為了驗證本實驗方法隨著實驗數(shù)據(jù)集的增加依然有效，隨機挑選出100個、200個、300個family進行同樣的實驗操作。雖然每個family中的蛋白質序列數(shù)量和序列的長度大小都有所區(qū)別，但是同一個family中的蛋白質序列都具有一定的相似性。

3.2 實驗步驟

在進行實驗之前對數(shù)據(jù)進行整理，將某些序列中含有的字母X刪除，因為字母X代表任意的氨基酸，無法對其進行相關的統(tǒng)計與處理。

將原始蛋白質序列按著K-詞模型進行映射，由于蛋白質序列是由20個字母組成，按照字母表順序依次映射為數(shù)值0到19，為了實驗的方便我們取K-詞模型的K值為1，從而獲得20k個待處理字，即K-詞。

(1) 將從原始數(shù)據(jù)集中獲取的蛋白質序列按K-詞模型進行映射得到對應的數(shù)字序列，預處理字長為K，獲得20k個待處理字。

(2) 統(tǒng)計每條序列中每個K-詞的頻度和位置，LF的值V等于相鄰兩個位置相減的倒數(shù)。

(3) 根據(jù)式(2)計算出所有詞對應的LF的值V，再分別根據(jù)式(3)、式(4)、式(5)計算出對應的累積和S、總和Z及離散概率P，最后根據(jù)式(6)計算出VE。由于V為相鄰位置差的倒數(shù)，當詞在序列中出現(xiàn)的頻度小于或者等于2時計算出的VE都為0，無法明確區(qū)分出詞的各個頻度特征，因此在本實驗中對于詞頻小于或等于2的情況進行了單獨處理，即頻度為0與頻度為4，頻度為1與頻度為3的情況進行對稱處理，頻度為2時，VE等于0。

頻度為1時，

VE=2×(1/2)×log2(1/2)=-1

頻度為0時，

VE=3×(1/3)×log2(1/3)=-1.584 963

(4) 計算的VE構成一個N×20k的特征矩陣，結合每個詞的頻度特征構成一個N×2×20k的特征矩陣。由于蛋白質序列存在長度差異，為了消除序列長度對詞頻的影響，在本實驗中對每個詞的詞頻進行標準化處理。

(5) 對由LFE和詞頻構成的特征進行K-means聚類。初始聚類中心對K-means聚類算法的聚類結果影響很大，由于每一次隨機選取的聚類中心不同，得到的聚類結果也是不同的，為了消除偶然性結果的干擾，進行多次重復實驗，取平均值。

3.3 模型評價方法

fm是選取的family數(shù)。

經(jīng)過K-means聚類后，通常一個family會被分為幾個不同的集群中，在具有相同的family標簽的集群的基礎上，計算一個family的精確度和召回率。

第i個family的精確度計算公式：

(7)

第i個family的召回率計算公式：

(8)

則第i個family的F值計算公式為：

(9)

實驗的聚類結果的F值：

(10)

由于K-means聚類結果與所選取的初始聚類中心有很大的關系，為了消除偶然性結果的干擾，選取的family數(shù)從5到20時，對每一次隨機選定的數(shù)據(jù)集，重復試驗10次，計算出這10次的精確度和召回率以及F值，然后分別計算它們的平均值。

隨機分別選取100、200、300 family進行同樣的實驗，分別計算出F值，精確度和召回率，與Bao等的實驗結果進行比較。

3.4 實驗結果及分析

在20個family實驗過程中使用LFE和詞頻特征來提取蛋白質序列的特征。蛋白質序列由20個family組成，實驗過程中隨機抽取5到20個family進行聚類分析，計算F值，并且與Bao等在文獻[9]中的CPF模型計算的F值進行對比，另外對這兩組數(shù)據(jù)進行T檢驗。如圖1所示。

圖1 family數(shù)從5到20的F值情況

圖1是選擇的family數(shù)從5到20情況下F值的情況。每次選定family數(shù)后重復10次隨機實驗，計算10次F值，取平均值。從圖中可以看出在family數(shù)量的從5到20的實驗過程中，LFE模型所得到的F值要大于Bao等[9]的CPF模型計算的F值，雖然在family數(shù)為17和18時效果不理想，但是總體而言本文的LFE模型計算的F值相對較高。

兩組F值T檢驗后，p-value=0.007 662；p值小于0.05，可以確定LFE的聚類效果顯著優(yōu)于CPF模型。

圖2和圖3分別是選擇的family數(shù)從5到20情況下精確度和召回率的情況。從圖中可以看出LFE的模型計算的精確度和召回率要明顯高于CPF模型。

圖2 family數(shù)從5到20的精確度情況

圖3 family數(shù)從5到20的召回率情況

圖4是family數(shù)為100、200、300時，重復10次實驗的F值、準確率和召回率的平均值，從左到右分別是HOG100、HOG200、HOG300時，LFE方法計算的F值、CPF方法計算的F值，LFE方法計算的準確率、CPF方法計算的準確率，LFE方法計算的召回率、CPF方法計算的召回率。

圖4 family數(shù)為100、200和300時F值準確率和召回率情況

從上圖的實驗結果可以看出，隨著數(shù)據(jù)集的增加，LFE模型聚類結果的F值、精確度和召回率均比CPF模型好。對HOG100數(shù)據(jù)集、HOG200數(shù)據(jù)集、HOG300數(shù)據(jù)集使用LFE方法、CPF方法得到的F值，對其T檢驗的p-value值分別為8.17E-05、0.001 496和0.016 31。p值明顯小于0.05，可以確定LFE的聚類效果顯著優(yōu)于CPF模型。

4 結 語

本文對蛋白質數(shù)據(jù)采用了基于位置信息的非比對序列的方法進行聚類。通過K-詞模型進行映射得到20k個K-詞，將詞的位置信息與詞頻特征相結合作為序列的特征向量，對特征向量進行K-means聚類，計算精確率和召回率，用F-measure對本文的方法進行評估。隨機分別抽取20、100、200、300個family的蛋白質序列進行聚類研究，實驗結果表明隨著實驗數(shù)據(jù)集的增加，本文實驗方法同樣取得很好的效果，相比于Bao等[9]的CPF模型的聚類結果，本實驗的聚類效果顯著提高。

[1] Altschul S F,Gish W,Miller W,et al.Basic local alignment search tool[J].Journal of Molecular Biology,1990,215(3):403-410.

[2] Pearson W R.Rapid and sensitive sequence comparison with FASTP and FASTA[J].Method in Enzymology,1990,183:63-98.

[3] Dai Q,Li L H,Liu X Q,et al.Integrating overlapping structures and background information of words significantly improves biological sequence comparison[J].Plos One,2011,6(11):e26779.

[4] Bonham-Carter O,Steele J,Bastola D.Alignment-free genetic sequence comparisons:a review of recent approaches by word analysis[J/OL].Bioinformatics,2014,15(6):890-905.http://bib.oxfordjournals.org/content/15/6/890.

[5] Randic M,Zupan J,Balaban A T,et al.Graphical representation of proteins[J].Chemical Review,2011,111(2):790-862.

[6] 余宏杰.生物序列特征信息提取方法及其應[D].合肥:中國科學技術大學,2013.

[7] 鄧偉.生物序列的相似性分析及K詞模型研究[D].濟南:山東大學,2015.

[8] Leimeister C A,Boden M,Horwege S,et al.Fast alignment-free sequence comparison using spaced-word frequencies[J].Bioinformatics,2014,30(14):1991-1999.

[9] Bao J,Yuan R,Bao Z.An improved alignment-free model for DNA sequence similarity metric[J].BMC Bioinformatics,2014,15(1):1-15.

[10] Li C,Wang J.Relative entropy of DNA and its application[J].Physica A Statistical Mechanics & Its Applications,2005,347(C):465-471.

[11] 許景皓.基于序列順序信息的DNA結合蛋白質識別與遠程同源性檢測[D].哈爾濱:哈爾濱工業(yè)大學,2014.

[12] 楊希武.DNA序列比較的K-詞非頻率模型研究及應用[D].大連:大連理工大學,2013.

[13] 吳迪.基于加權相似度的序列聚類算法研究[D].燕山:燕山大學,2014.

[14] Shi L,Huang H.DNA sequences analysis based on classifications of nucleotide bases[C]//International Colloquium on Computing,communication,Control,and Management,2010:379-384.

[15] 黃玉娟.基于K詞的DNA序列分析的模型研究及應用[D].大連:大連理工大學,2012.

[16] 胡清銘.蛋白質序列特征提取及其在亞細胞定位中的應用[D].長沙:湖南大學,2013.

[17] Kurgan L,Homaeian L.Prediction of Structural classes for protein sequences and domains-impact of prediction algorithms,sequence representation and homology and test procedures on accuracy[J].Pattern recognization,2006,39(12):2323-2343.

[18] 唐杰.基于K-字位置的新序列比較方法[D].楊凌:西北農(nóng)林科技大學,2015.

[19] Wei D,Jiang Q,Wei Y,et al.A novel hierarchical clustering algorithm for gene sequences[J].Bmc Bioinformatics,2012,13(1):1-15.

[20] Wei D,Jiang Q.A DNA sequence distance measure approach for phylogenetic tree construction[C]//IEEE Fifth International Conference on Bio-Inspired Computing:Theories and Applications.IEEE,2010:204-212.

[21] HOGENOM:Database of complete genome homologous genes families[DB/OL].http://pbil.univ-lyon1.fr/databases/hogenom/home.Php.

ALIGNMENT-FREEMODELFORSEQUENCECLUSTERINGMETHODBASEDONLOCATIONINFORMATION

Wei Jing Xu Pengna Jiang Yu’e Lin Jie*

(FacultyofSoftware,FujianNormalUniversity,Fuzhou350108,Fujian,China)

Alignment-free similarity model for sequence calculates the similarity between the sequences by using the statistical information of the sequences, which has the advantage of fast calculation and high precision. Alignment-free model for sequence clustering method based on position information was proposed. The features of sequences can be obtained by combining the LF entropy of the corresponding word which was calculated from the Local Frequency of every word with the K-mers model, and the frequency of every word. This new method can be applied to protein clustering. The experimental results showed this new method improved the accuracy of clustering effectively.

K-mers Local frequency entropy Sequence clustering Position information

2017-01-23。國家自然科學基金項目(61472082)；福建省自然科學基金項目(2014J01220)。魏靜，碩士生，主研領域：數(shù)據(jù)挖掘。徐彭娜，碩士生。江育娥，教授。林劼，副教授。

TP3

A

10.3969/j.issn.1000-386x.2017.12.008