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

徐彭娜　魏　靜　林　劼　江育娥

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

0　引　言

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

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

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

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

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

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

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

2　理論基礎(chǔ)

2.1　K詞

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

2.2　信息熵

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

(1)

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

2.3　局部敏感哈希

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

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

(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表示對(duì)樣本數(shù)據(jù)進(jìn)行哈希變換的函數(shù)。滿足以上兩個(gè)條件的哈希函數(shù)稱為(d1,d2,p1,p2)-sensitive。而通過一個(gè)或多個(gè)(d1,d2,p1,p2)-sensitive的哈希函數(shù)對(duì)原始樣本數(shù)據(jù)集合進(jìn)行哈希的過程稱為L(zhǎng)SH過程。

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

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

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

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

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

(2)

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

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

(3)

(4)

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

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

(5)

(6)

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

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

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

(7)

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

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

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

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

算法1LSH-E 算法描述

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

輸出：聚類集合ClusterSet。

1)for(s∈S)

2) y=Kmer(s)

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

3) T=getT(Y)

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

4) for(y∈Y)

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

6) else{LFy=calculateLF(y)}

//計(jì)算LF值

7) pst=sum(LFy)

//計(jì)算部分和

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

//計(jì)算離散概率

9) e=Standardization(entropy)

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

10) end for

11)end for

12)HM=hashs(E, num_h)

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

13)PHM=PasteHashMatrix(HM , r)

//對(duì)特征矩陣進(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　實(shí)驗(yàn)與結(jié)果分析

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

實(shí)驗(yàn)使用兩種數(shù)據(jù)集，真實(shí)數(shù)據(jù)集和模擬數(shù)據(jù)集。其中真實(shí)數(shù)據(jù)集RMAP[17]是二代測(cè)序數(shù)據(jù)集，每條序列的字符個(gè)數(shù)為47，該數(shù)據(jù)集中的總序列數(shù)為6 196 389，總體分布較均勻。模擬數(shù)據(jù)是先從真實(shí)數(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　實(shí)驗(yàn)步驟

LSH-E對(duì)DNA序列聚類的實(shí)驗(yàn)步驟如下：

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

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

表1　LSH-E實(shí)驗(yàn)參數(shù)

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

算法Seed、 Qcluster、Afcluster、CD-HIT對(duì)DNA聚類的實(shí)驗(yàn)步驟如下：

(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++對(duì)源代碼中的SEED.cpp文件進(jìn)行編譯，Qcluster、Afcluster和CD-HIT在linux系統(tǒng)中使用make進(jìn)行編譯操作；(2) 將DNA序列處理為實(shí)驗(yàn)需要的格式，其中Seed、Qcluster聚類實(shí)驗(yàn)需要.fastq格式的實(shí)驗(yàn)數(shù)據(jù)，由于RMAP數(shù)據(jù)集中的DNA數(shù)據(jù)無序列質(zhì)量信息，將所有的序列質(zhì)量信息置為相同的值，Afcluster、CD-HIT聚類實(shí)驗(yàn)直接使用.fasta格式的實(shí)驗(yàn)數(shù)據(jù)；(3) 對(duì)50k、100k、200k、400k和RMAP數(shù)據(jù)集計(jì)算Seed聚類結(jié)果，其中mismatch=3，shift=3，對(duì)50k、100k、200k、400k數(shù)據(jù)集計(jì)算Qcluster、Afcluster聚類結(jié)果，其中k值均設(shè)置為500，對(duì)50k、100k、200k、400k和RMAP數(shù)據(jù)集計(jì)算CD-HIT聚類結(jié)果，無需設(shè)置參數(shù)值。

4.3　評(píng)測(cè)指標(biāo)

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

(8)

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

(9)

(10)

使用式(11)計(jì)算F值。

(11)

4.4　實(shí)驗(yàn)結(jié)果及分析

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

圖1　五種不同方法得到的F值對(duì)比

圖2　五種不同方法得到的R值對(duì)比

圖3　五種不同方法得到的P值對(duì)比

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

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

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

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

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

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

表2LSH_E、Seed、Afcluster、Qcluster、CD-HIT聚類時(shí)間

秒

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

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

5　結(jié)　語

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

[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é)報(bào)自然科學(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ù)填補(bǔ)算法[J]. 計(jì)算機(jī)應(yīng)用, 2016, 36(2):397-401.

[16] 張勇. 基于高通量轉(zhuǎn)錄組測(cè)序的序列比對(duì)算法研究[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版.北京: 機(jī)械工業(yè)出版社,2007:315-319.