徐彭娜　魏　靜　林　劼　江育娥

(福建師范大學(xué)數(shù)學(xué)與信息學(xué)院　福建 福州 350108)

0　引　言

生物序列的聚類對生物信息學(xué)研究具有重要意義，聚類方法在生物序列分析和研究中受到了廣泛的重視和應(yīng)用。隨著信息技術(shù)的發(fā)展，基因測序技術(shù)愈發(fā)成熟，生物數(shù)據(jù)的數(shù)量急劇增長，傳統(tǒng)的方法對于海量的數(shù)據(jù)處理分析存在很多問題。數(shù)據(jù)挖掘技術(shù)是一種能從大量數(shù)據(jù)中提取有用的、潛在的有效信息的技術(shù)[1]。數(shù)據(jù)挖掘中的聚類能將具有某些相同特征的序列聚集在一起，從已知的功能、結(jié)構(gòu)的序列探索出未知序列的有效信息，具有重要的意義。

由于生物序列數(shù)量的持續(xù)性增長，以Trapnell 等[2]為代表的K-中心點聚類算法將具有相似表達(dá)趨勢的基因序列分為一組。當(dāng)所有類簇的中心點都不改變時算法收斂，該算法在小型數(shù)據(jù)集上運行良好。然而由于兩兩比對進(jìn)行聚類的方式在對大量數(shù)據(jù)聚類時存在計算量大、耗時久等問題[3]。因此在相似序列查找[4]和序列聚類上都提出用非比對方法解決兩兩比對存在的問題。以Bao等[5]為代表的非比對序列聚類算法無需對序列進(jìn)行兩兩比對。雖然在效率上有一定程度的提高，但存在挖掘結(jié)果的可解釋性不足和準(zhǔn)確率偏離實際生物意義的問題，并不能完全滿足生物學(xué)研究的需要。

針對以上問題，本文使用p穩(wěn)定分布局部敏感哈希方法降低查找相似序列的時間復(fù)雜度；利用位置信息熵作為哈希函數(shù)的特征向量提高準(zhǔn)確率；并在評估聚類結(jié)果時使用編輯距離作為距離度量以增強生物學(xué)可解釋性，在此基礎(chǔ)上提出基于位置信息熵的局部敏感哈希聚類方法LSH-E。該方法使用基于位置信息的標(biāo)準(zhǔn)熵作為局部敏感哈希函數(shù)的特征向量對生物序列進(jìn)行聚類，其算法執(zhí)行時間和數(shù)據(jù)集合大小成線性相關(guān)，對不同量級的數(shù)據(jù)集都有很好的實驗結(jié)果，其在模擬數(shù)據(jù)和真實數(shù)據(jù)的實驗結(jié)果均驗證了該算法的有效性。

1　相關(guān)工作研究

在生物信息學(xué)中，聚類分析可以用于識別未知類別的生物序列所屬的類別，揭示序列之間相互關(guān)系，進(jìn)而分析生物序列功能和生物序列進(jìn)化關(guān)系等[6]。

傳統(tǒng)聚類算法如基于劃分的K-medoid算法[7]、基于層次的全連接算法[8]等通過對序列進(jìn)行兩兩比對來聚類，時間復(fù)雜度較高，因此傳統(tǒng)算法不適用于海量數(shù)據(jù)的聚類分析。K-means算法需要確定聚類個數(shù)，序列數(shù)據(jù)的中心也不易計算，初始聚類中心具有隨機性使得聚類結(jié)果不穩(wěn)定，應(yīng)用到生物序列中聚類效果不佳?；贐AG圖[9]的聚類算法的結(jié)果雖然有效，但在類的分割時需要使用聚類單元引導(dǎo)，而基因庫中的序列數(shù)目過多，導(dǎo)致其使用無向圖表示過多的序列異常困難。Solovyov等[10]提出一種基于詞頻的高流通量中心聚類算法Afcluster，算法使用K詞統(tǒng)計生物序列詞頻，基于詞頻信息確定中心使用k-means聚類。算法無需對序列進(jìn)行兩兩比對，大大降低了時間復(fù)雜度，但在大數(shù)據(jù)量的情況下，隨著類個數(shù)的增加，該算法的效率降低且存在聚類迭代時收斂緩慢的情況。Comin等[11]提出一種基于質(zhì)量評價的非比對序列聚類算法Qcluster，由于聚類是基于序列的質(zhì)量，該算法在指定聚類個數(shù)相對確定的情況下具有較高的準(zhǔn)確度。但時間復(fù)雜度較高且運行時間不穩(wěn)定，在數(shù)據(jù)量大且最終類個數(shù)不明確的情況下，存在著聚類時間過長或無法得到聚類結(jié)果的問題。Bao等[5]提出一種基于海明距離的空間塊聚類算法Seed，該算法通過識別虛擬中心序列以及查找所有滿足相似性參數(shù)的鄰近序列來進(jìn)行聚類。該算法的時間復(fù)雜度和空間復(fù)雜度和序列數(shù)成線性相關(guān)，在數(shù)量大的生物序列集合也能在較短時間得到聚類結(jié)果。但基于海明距離的生物序列聚類結(jié)果的可解釋性和準(zhǔn)確率偏低，可能偏離實際生物意義，不能完全滿足生物學(xué)研究的需要。Fu等[12]提出一種基于并行的聚類算法CD-HIT，以減少序列冗余來應(yīng)對快速增長的下一代產(chǎn)生的測序數(shù)據(jù)量。測試表明并行化到24個核心以及最多達(dá)8個核心的實驗效果最佳，但其單機運行的時間效率偏低，對于邊界比較不清晰的大數(shù)據(jù)集聚類效果差。

綜上所述，為了解決現(xiàn)有算法存在時間效率不高、準(zhǔn)確率較低、聚類結(jié)果的生物意義不明顯的問題，本文提出LSH-E算法。使用標(biāo)準(zhǔn)熵記錄生物序列的K詞位置信息，應(yīng)用編輯距離度量每對序列之間的距離，提高聚類分析的準(zhǔn)確性以及增強其實際的生物意義。

2　理論基礎(chǔ)

2.1　K詞

近年來，在生物序列建模的數(shù)據(jù)預(yù)處理中對生物序列使用固定長度的滑動窗口獲得K詞集合，在K詞的頻數(shù)、概率統(tǒng)計等方法的基礎(chǔ)上建立模型。生物序列的K詞集合包含了頻數(shù)和位置信息，體現(xiàn)了生物序列的特征和信息。由統(tǒng)計[13]可知，生物序列中的基因表達(dá)穩(wěn)定的前提是一個K詞的頻繁出現(xiàn)，如果一個K詞出現(xiàn)的極少，可能表示基因復(fù)制、基因表達(dá)被擾亂。在目前基于K詞建立的模型中，多數(shù)只是基于K詞的頻數(shù)，對K詞出現(xiàn)的位置信息未做處理，但是基因的重排、插入、轉(zhuǎn)換和顛換等記載著大量的位置信息。生物序列的位置信息與生物序列的相似性研究有著重要的意義，本文使用信息熵標(biāo)記K詞的位置信息。

2.2　信息熵

Shannon 借鑒了熱力學(xué)的概念將排除信息冗余的平均信息量稱為信息熵[14]，信息熵表示隨機變量的概率分布函數(shù)，解決了信息分布度量化問題。信息熵滿足對稱性、非負(fù)性、確定性、擴展性、可加性及極值性等特性。設(shè)集合Y={x1，x2，…，xi，…，xn}，i∈[1,n]，假定xi∈Y的概率pi=P(xi)，則Y的信息熵可定義為：

(1)

式(1)是信息熵公式，可以將其應(yīng)用到生物序列上計算生物序列的信息熵[14]。其中集合Y可以表示為生物序列中K詞的Locality Frequency集合，pi可以表示為每個K詞的離散概率P的第i個離散概率。

2.3　局部敏感哈希

局部敏感哈希LSH基本是對樣本數(shù)據(jù)進(jìn)行映射變換后的，使得在原始空間的相鄰點仍然保持大概率相鄰，而在原始空間的不相鄰點仍然保持大概率不相鄰[15]。LSH主要應(yīng)用于海量數(shù)據(jù)的檢索、查找相似數(shù)據(jù)等。

局部敏感哈希簇需要滿足兩個條件：

(1) 如果d(x,y)≤d1，則f(x)=f(y)的概率至少為p1；

(2) 如果d(x,y)≥d2，則f(x)=f(y)的概率至多為p2。

其中x，y表示樣本數(shù)據(jù)，d(x,y)表示x、y之間的距離，d1p2，f表示對樣本數(shù)據(jù)進(jìn)行哈希變換的函數(shù)。滿足以上兩個條件的哈希函數(shù)稱為(d1,d2,p1,p2)-sensitive。而通過一個或多個(d1,d2,p1,p2)-sensitive的哈希函數(shù)對原始樣本數(shù)據(jù)集合進(jìn)行哈希的過程稱為LSH過程。

3　基于位置信息熵的局部敏感哈希聚類方法(LSH-E)

由于生物數(shù)據(jù)的急劇增長，現(xiàn)有的大部分聚類算法存在著如時間復(fù)雜度高，無法對大量數(shù)據(jù)進(jìn)行聚類，聚類準(zhǔn)確率低，聚類結(jié)果的可解釋性差等問題。為了解決時間復(fù)雜度高的問題，本文使用p穩(wěn)定分布局部敏感哈希方法降低查找相似序列的時間復(fù)雜度。為了解決準(zhǔn)確率低的問題，使用位置信息熵作為哈希函數(shù)的特征向量，利用位置信息來提高聚類的準(zhǔn)確率。對于聚類結(jié)果的可解釋性存在偏離實際生物意義的現(xiàn)象，本文在評估聚類結(jié)果時使用編輯距離作為距離度量。由于編輯距離被定義為將序列A映射到序列B所需操作({insert，delete，replace})的個數(shù)[16]，這與生物序列基因的重組、遺傳和變異等自然演變的實際生物意義相符。

3.1　基于信息位置的標(biāo)準(zhǔn)熵

對于一個給定的序列S=S[1,2,…,N]，假如其字符集合為∑，S[i]表示在序列中的某個字符;S[i…j] 表示序列的一個子字符串；一個K詞即指在序列S中的一個長度為k的一個子字符串。對于一個長度為N的序列S來說，其k的取值范圍從1到N。 當(dāng)k=1時，有N個長度為1的K詞；當(dāng)k=N時，有1個長度為N的K詞(即S本身)。因此，對于序列S來說，總共有N(N+1)/2 個K詞(k取值范圍為[1,N])。

對生物序列使用固定長度K(1≤K≤N)的滑動窗口獲得待處理K詞集合Y，即預(yù)處理字長度為K。K詞對生物序列符號使用長度為K的不重復(fù)生物序列集合，即K詞集合包含|∑|K個特征詞，其中生物序列符號集合為∑，|∑|是序列符號集合大小。統(tǒng)計每個特征詞出現(xiàn)的位置及頻數(shù)，使用式(2)計算每條序列的局部頻率值LF值。

(2)

LF是通過依次計算每條生物序列的每個特征詞出現(xiàn)的相鄰位置差的倒數(shù)。在式(2)中，Y表示待處理K詞集合，t表示同一個待處理K詞出現(xiàn)的位置順序，WtY表示待處理K詞Y的第t次出現(xiàn)在生物序列的位置，LFtY表示待處理K詞Y的第t個LF，z表示當(dāng)前待處理K詞頻數(shù)。

使用式(3)、式(4)計算每個特征詞的LF值的部分和ps、離散概率p。

(3)

(4)

式中：N為ps的個數(shù)。

使用式(5)計算每個特征詞的熵值，使用式(6)對熵值進(jìn)行標(biāo)準(zhǔn)化處理。

(5)

(6)

3.2　基于p-穩(wěn)定分布的局部敏感哈希

基于 p-穩(wěn)定分布的局部敏感哈希，其原理是利用一種隨機化局部哈希方式對樣本進(jìn)行降維，使在高維相近的兩個點在降維之后仍然大概率相近。該算法的具體過程是將樣本投影到隨機的直線上，對于隨機直線而言，兩兩之間的方向矢量的分量服從p-穩(wěn)定分布且互相獨立。由于p-穩(wěn)定分布的特性，兩個樣本的歐式距離與其投影距離是同分布的，因此兩個樣本的投影距離越小則表明其歐氏距離也就越小。將隨機直線按等比例劃分為線段，然后對各線段進(jìn)行編號，則投影樣本所在的線段編號值作為哈希函數(shù)的取值。該算法的哈希函數(shù)族可以表示為:

ha,b(v)=?(a·v+b)/w」

(7)

式中:v為d維的特征向量，a為與特征向量v個數(shù)相同的0到1之間的符合p-穩(wěn)定分布的向量，b為0到w的任一整數(shù)，w為任意正整數(shù)，這樣哈希函數(shù)ha,b(v)將一個d維空間向量v映射為一個整數(shù)。

3.3　基于位置信息熵的局部敏感哈希聚類方法

已知序列集合S={s1,s2,…,sn}，對每條序列進(jìn)行K詞處理，根據(jù)式(2)至式(6)計算每條序列的基于位置信息的標(biāo)準(zhǔn)熵，得到序列位置信息熵集合E={e1,e2,…,e|∑|}。根據(jù)式(7)構(gòu)造哈希個數(shù)為num_h的基于 p-穩(wěn)定分布的局部敏感哈希集合H={h1,h2,…,hnum_h}，將位置信息熵E作為哈希函數(shù)的特征向量，計算特征矩陣。將特征矩陣均分為r個行條，每個行條中哈希值相同的序列為同一個聚類，得到聚類個數(shù)為num_c的集合ClusterSet={cs1,cs2,…,csc,… ,csnum_c}。

LSH-E算法描述如算法1所示。步驟4)至步驟11)計算序列S的標(biāo)準(zhǔn)熵E，將序列轉(zhuǎn)化為標(biāo)準(zhǔn)熵矩陣E表示，其中步驟6)、步驟7)、步驟8)分別使用式(2)、式(3)、式(4)計算，步驟9)使用式(5)和式(6)計算；步驟12)將標(biāo)準(zhǔn)熵作為特征向量，對其使用num_h個哈希計算得到哈希矩陣HM；步驟13)將HM均分為r個行條，每個行條中包含num_h/r行，將同一個行條的列拼接得到拼接哈希矩陣PHM；步驟15)至19)為聚類過程，其中步驟16)表示將至少有一個拼接值相同的序列聚為一類，步驟17)表示將已經(jīng)被聚類的序列排除。

算法1LSH-E 算法描述

輸入：序列集合S，哈希函數(shù)個數(shù)num_h，行條數(shù)r。

輸出：聚類集合ClusterSet。

1)for(s∈S)

2) y=Kmer(s)

//對s進(jìn)行K詞處理得到Y(jié)

3) T=getT(Y)

//對K詞結(jié)果計算頻數(shù)并記錄位置集合T

4) for(y∈Y)

5) if(Ty.length<=1){LFy=-1}

6) else{LFy=calculateLF(y)}

//計算LF值

7) pst=sum(LFy)

//計算部分和

8) p(t)= pst/ sum(ps)

//計算離散概率

9) e=Standardization(entropy)

//計算熵并對其標(biāo)準(zhǔn)化

10) end for

11)end for

12)HM=hashs(E, num_h)

//對特征矩陣進(jìn)行分行條

13)PHM=PasteHashMatrix(HM , r)

//對特征矩陣進(jìn)行拼接

14)i=1, Clustered=null

15)while(Clustered.length

16) temp=equal(PHM[,i])

17) csc=removeClustered(temp , Clustered)

18) if(i∈Clustered){i++}

19)end while

20)return ClusterSet

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

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

實驗使用兩種數(shù)據(jù)集，真實數(shù)據(jù)集和模擬數(shù)據(jù)集。其中真實數(shù)據(jù)集RMAP[17]是二代測序數(shù)據(jù)集，每條序列的字符個數(shù)為47，該數(shù)據(jù)集中的總序列數(shù)為6 196 389，總體分布較均勻。模擬數(shù)據(jù)是先從真實數(shù)據(jù)集RMAP中選取編輯距離大于7的500條序列作為中心，再生成與每條中心編輯距離小于2的100條、200條、400條和800條序列，分別加上中心序列形成的50 500、100 500、200 500和400 500條 DNA生物序列集合，下文將其分別稱為50k、100k、200k和400k。

4.2　實驗步驟

LSH-E對DNA序列聚類的實驗步驟如下：

(1) 由于DNA序列中堿基集合為{A、C、G、T}，|∑|=4，k=2，獲得16個K詞,對序列S進(jìn)行K詞模型映射處理，得到預(yù)處理字集合Y；(2) 根據(jù)式(2)、式(3)、式(4)計算每個特征詞的LF值、部分和ps、離散概率p，本實驗中對Y中只出現(xiàn)一次或未出現(xiàn)的K詞的LF賦為-1；(3) 根據(jù)式(5)計算每個特征詞的熵值，使用式(6)對熵值進(jìn)行標(biāo)準(zhǔn)化處理；(4) 將熵值作為哈希函數(shù)簇的特征向量，計算DNA序列的特征矩陣；將特征矩陣進(jìn)行分行條和拼接處理得到PHM矩陣；(5) 根據(jù)PHM計算聚類結(jié)果。

其中50k～400k、RMAP數(shù)據(jù)集的聚類實驗參數(shù)如表1所示。

表1　LSH-E實驗參數(shù)

表1中，a、b、w為式(7)中的參數(shù)，在實驗中a為16維的0到1之間的符合p-穩(wěn)定分布的向量，在不同w值的實驗對比中發(fā)現(xiàn)，當(dāng)w=7效果最佳；b選取0～7之間的中位數(shù)4；在不同num_h值的實驗對比中發(fā)現(xiàn)對于50k～400k的數(shù)據(jù)，當(dāng)num_h=480，r=16時，效果最佳，對于數(shù)據(jù)集RMAP，當(dāng)num_h=300，r=30時，效果最佳。

算法Seed、 Qcluster、Afcluster、CD-HIT對DNA聚類的實驗步驟如下：

(1) 下載Seed(http://manuals.bioinformatics.ucr.edu/home/seed)、Qcluster(http://www.dei.unipd.it/～ciompin/main/qcluster.html)、Afcluster(https://github.com/luscinius/afcluster)和CD-HIT(https://github.com/weizhongli/cdhit)聚類方法的源代碼，其中Seed源代碼在linux系統(tǒng)中使用g++對源代碼中的SEED.cpp文件進(jìn)行編譯，Qcluster、Afcluster和CD-HIT在linux系統(tǒng)中使用make進(jìn)行編譯操作；(2) 將DNA序列處理為實驗需要的格式，其中Seed、Qcluster聚類實驗需要.fastq格式的實驗數(shù)據(jù)，由于RMAP數(shù)據(jù)集中的DNA數(shù)據(jù)無序列質(zhì)量信息，將所有的序列質(zhì)量信息置為相同的值，Afcluster、CD-HIT聚類實驗直接使用.fasta格式的實驗數(shù)據(jù)；(3) 對50k、100k、200k、400k和RMAP數(shù)據(jù)集計算Seed聚類結(jié)果，其中mismatch=3，shift=3，對50k、100k、200k、400k數(shù)據(jù)集計算Qcluster、Afcluster聚類結(jié)果，其中k值均設(shè)置為500，對50k、100k、200k、400k和RMAP數(shù)據(jù)集計算CD-HIT聚類結(jié)果，無需設(shè)置參數(shù)值。

4.3　評測指標(biāo)

實驗采用精度P值(Precision值)、召回率R值(Recall值)、F值(F-measure值)、算法執(zhí)行時間作為評估指標(biāo)。由于真實數(shù)據(jù)集中沒有明確的聚類結(jié)果，本文規(guī)定序列間的編輯距離小于等于3的序列真實為一個類。使用BCubed基準(zhǔn)[18]對給定的數(shù)據(jù)集中的每條序列計算其精度和召回率，其評估方式如式(10)和式(11)所示。一條序列的精度表示用一個類中有多少個其他序列與該序列同屬于一個類，一條序列的召回率表示有多少同一類的序列被分配在相同類中。

(8)

式中:(1≤i≤n)是實驗結(jié)果的oi的類別， 是真實數(shù)據(jù)中oi的類別， 表示兩個對象oi和oj(1≤i，j≤n，i≠j)在真實數(shù)據(jù)中的關(guān)系的正確性。

(9)

(10)

使用式(11)計算F值。

(11)

4.4　實驗結(jié)果及分析

對模擬數(shù)據(jù)和真實數(shù)據(jù)進(jìn)行LSH-E實驗，分別計算其F值、R值和P值，與Seed模型、Qcluster模型、Afcluster模型、CD-HIT模型的實驗結(jié)果進(jìn)行比較，其實驗結(jié)果如圖1-圖4所示。

圖1　五種不同方法得到的F值對比

圖2　五種不同方法得到的R值對比

圖3　五種不同方法得到的P值對比

圖4　數(shù)據(jù)RMAP的不同方法的P值、R值和F值比較

圖1是實驗數(shù)據(jù)為50k、100k、200k和400k在五種方法(LSH_E、Seed、Afcluster、Qcluster、CD-HIT)下計算得出的F值。從圖中可以看出，LSH_E模型所得到的F值明顯大于Afcluster模型和Seed模型計算的到的F值，與Qcluster模型計算的F值相近。但 LSH_E模型得到的R值結(jié)果優(yōu)于Qcluster模型(見圖2)，在時間效率上比Qcluster模型高了近百倍，CD-HIT模型所得的F值略優(yōu)于LSH-E模型的F值。

圖2是實驗數(shù)據(jù)為50k、100k、200k、400k在五種方法(LSH_E、Seed、Afcluster、Qcluster、CD-HIT)下計算的R值。從圖中可以看出，LSH_E模型所得到的R值明顯大于Afcluster模型，優(yōu)于Qcluster模型計算的到的R值。雖然LSH_E模型所得到的R值略小于Seed模型計算的R值，但LSH_E模型得到的P值結(jié)果顯著優(yōu)于Seed模型的P值(如圖3所示)，CD-HIT模型所得的R值略優(yōu)于LSH-E模型的R值。

圖3是實驗數(shù)據(jù)為50k、100k、200k、400k在五種方法(LSH_E、Seed、Afcluster、Qcluster、CD-HIT)下計算的P值。從圖中可以看出，LSH_E模型所得到的P值明顯大于Seed模型和Afcluster模型計算的到的P值，LSH_E模型所得到的P值略小于Qcluster模型計算的P值，CD-HIT模型所得的P值略優(yōu)于LSH-E模型的P值。

圖4是實驗數(shù)據(jù)為RMAP在LSH_E、Seed模型下計算的P、R、F值，Afcluster模型和Qcluster模型在實驗數(shù)據(jù)為真實數(shù)據(jù)RMAP時得不到聚類結(jié)果。從圖中可以看出，LSH_E模型所得到的P值和F值均優(yōu)于Seed模型，LSH_E模型所得到的P值、R值和F值均優(yōu)于CD-HIT模型約20%。在Afcluster模型和Qcluster下對RMAP數(shù)據(jù)聚類，由于算法執(zhí)行時間過長(>24 h)，未得到實驗結(jié)果。

為了更詳細(xì)地展示實驗結(jié)果效率，本文統(tǒng)計了LSH_E、Seed、Afcluster、Qcluster和CD-HIT五種模型聚類時間作對比，時間對比如表2所示。

表2LSH_E、Seed、Afcluster、Qcluster、CD-HIT聚類時間

秒

由表2可知，在50k～400k的實驗結(jié)果中，LSH-E的算法執(zhí)行時間明顯低于Afcluster和Qcluster的算法執(zhí)行時間；在50k、100k、200k的實驗中，LSH-E的算法執(zhí)行時間少于Seed的算法執(zhí)行時間，在400k、RMAP的實驗中，LSH-E的算法執(zhí)行時間高于Seed的算法執(zhí)行時間；在50k～400k的實驗中，LSH-E的算法執(zhí)行時間略高于CD-HIT的算法執(zhí)行時間，在RMAP的實驗中，LSH-E的算法執(zhí)行時間顯著少于CD-HIT的算法執(zhí)行時間。

在50k～400k數(shù)據(jù)中，LSH-E實驗的P值、R值和F值均高于Seed模型和Afcluster模型。LSH-E模型的R值高于Qcluster模型，P值和F值略低于Qcluster模型。LSH-E實驗的P值、R值和F值均低于CD-HIT模型，說明CD-HIT適合邊界比較清晰的聚類情況。在RMAP真實數(shù)據(jù)中，Afcluster模型和Qcluster模型均無法計算結(jié)果，LSH-E模型的P值和F值均高于Seed模型，LSH-E模型的P值、R值和F值均高出CD-HIT模型約20%。由實驗結(jié)果可知，LSH-E模型在兩種數(shù)據(jù)集合均取得很好的實驗結(jié)果，具有更高的時間效率和更好的生物解釋性。

5　結(jié)　語

本文對DNA序列數(shù)據(jù)采用了基于位置信息熵的局部敏感哈希聚類方法進(jìn)行聚類。使用長度為K的滑動窗口得到待處理K詞集合和位置，計算K詞的信息熵并對其標(biāo)準(zhǔn)化，作為局部敏感哈希簇的特征向量計算特征矩陣進(jìn)行聚類，計算其P值、R值、F-measure值、和算法執(zhí)行時間，對實驗結(jié)果進(jìn)行評估。使用模擬數(shù)據(jù)和真實數(shù)據(jù)集合進(jìn)行LSH-E聚類，與Seed聚類、Qcluster聚類、Afcluster聚類結(jié)果進(jìn)行對比。與Seed模型相比，LSH-E實驗結(jié)果的具有更好的實驗結(jié)果，在RMAP數(shù)據(jù)集的聚類中，LSH-E的F值較Seed的高出4.16%；與Qcluster模型相比，LSH-E在損失較小精度的情況下，在時間上是Qcluster模型1/100；與Afcluster模型相比，LSH-E模型無論在時間效率還是P值、R值、F值均得到了很大的提升；與CD-HIT模型相比，LSH-E模型在邊界比較清晰的聚類中結(jié)果稍遜于CD-HIT模型，但在RMAP數(shù)據(jù)集的聚類中，LSH-E模型在時間上是CD-HIT模型的1/150，F(xiàn)值較CD-HIT的高出23.17%。實驗結(jié)果表明，LSH-E在聚類時間上具有較大提高，隨著數(shù)據(jù)集的增大，LSH-E同樣取得很好的實驗效果，且更具有生物解釋性和實際意義。

[1] 宋建林. K-means聚類算法的改進(jìn)研究[D]. 安徽大學(xué), 2016.

[2] Trapnell C, Cacchiarelli D, Grimsby J, et al. The dynamics and regulators of cell fate decisions are revealed by pseudotemporal ordering of single cells[J]. Nature Biotechnology, 2014,32(4):381.

[3] 周洋. 基因表達(dá)譜數(shù)據(jù)聚類分析的研究[D]. 咸陽: 西北農(nóng)林科技大學(xué), 2014.

[4] Lin J, Adjeroh D A, Jiang B H, et al. K2: Efficient alignment-free sequence similarity measurement using the Kendall statistic[C]//IEEE International Conference on Bioinformatics and Biomedicine. IEEE, 2017:1128-1132.

[5] Bao E, Jiang T, Kaloshian I, et al. SEED: efficient clustering of next-generation sequences[J].Bioinformatics, 2011,27(18):2502.

[6] 楊恒宇. 生物序列數(shù)據(jù)挖掘技術(shù)研究[J]. 合肥工業(yè)大學(xué)學(xué)報自然科學(xué)版, 2012,35(9):1212-1216.

[7] 戴偉. 基于MapReduce的K-Medoids并行算法研究[D]. 遼寧工程技術(shù)大學(xué), 2015.

[8] 熊赟. 生物序列模式挖掘與聚類研究[D].復(fù)旦大學(xué), 2007.

[9] 陳榮安. 基于改進(jìn)的Bag-of-Features模型的圖像分類研究[D]. 蘭州大學(xué),2015.

[10] Solovyov A, Lipkin W I. Centroid based clustering of high throughput sequencing reads based on n-mer counts[J].Bmc Bioinformatics, 2013,14(1):268.

[11] Comin M, Leoni A, Schimd M. Clustering of reads with alignment-free measures and quality values[J].Algorithms for Molecular Biology Amb, 2015,10(1):1-10.

[12] Fu L, Niu B, Zhu Z, et al. CD-HIT: accelerated for clustering the next-generation sequencing data[J]. Bioinformatics, 2012, 28(23):3150.

[13] 鄧偉. 生物序列的相似性分析及k詞模型研究[D]. 山東大學(xué), 2015.

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

[15] 鄭奇斌, 刁興春, 曹建軍,等. 結(jié)合局部敏感哈希的k近鄰數(shù)據(jù)填補算法[J]. 計算機應(yīng)用, 2016, 36(2):397-401.

[16] 張勇. 基于高通量轉(zhuǎn)錄組測序的序列比對算法研究[D]. 中國科學(xué)技術(shù)大學(xué), 2016.

[17] Yang X, Chockalingam S P, Aluru S. A survey of error-correction methods for next-generation sequencing[J].Briefings in Bioinformatics, 2013,14(1):56.

[18] Han J W, Kamber M. 數(shù)據(jù)挖掘:概念與技術(shù)[M].范明,孟小峰,譯.3版.北京: 機械工業(yè)出版社,2007:315-319.