[發(fā)明專利]基于標(biāo)準(zhǔn)熵的局部敏感哈希的DNA序列聚類

有效

• 申請(qǐng)?zhí)枺?/td>: 201710285598.7
• 申請(qǐng)日: 2017-04-27
• 公開（公告）號(hào): CN107103206B
• 公開（公告）日: 2019-10-18
• 發(fā)明（設(shè)計(jì)）人: 江秉華;江育娥;徐彭娜;林劼
• 申請(qǐng)（專利權(quán)）人: 福建師范大學(xué)
• 主分類號(hào): G16B30/00
• 分類號(hào): G16B30/00;G06K9/62
• 代理公司: 福州君誠(chéng)知識(shí)產(chǎn)權(quán)代理有限公司 35211
• 代理人: 戴雨君

本發(fā)明公開基于標(biāo)準(zhǔn)熵的局部敏感哈希的DNA序列聚類，通過對(duì)原始的DNA序列按著L?Gram模型進(jìn)行映射，通過計(jì)算N條序列的LF熵值構(gòu)成的矩陣，進(jìn)而得出其標(biāo)準(zhǔn)熵，使用Locality?Sensitive Hashing對(duì)標(biāo)準(zhǔn)熵進(jìn)行哈希映射，得到DNA片段序列的候選集合，在候選集合中計(jì)算編輯距離小于d的DNA片段序列得到聚類結(jié)果。本發(fā)明綜合考慮到在轉(zhuǎn)換后的特征空間包含足夠的原始DNA信息，避免DNA信息的丟失，將每一段DNA序列轉(zhuǎn)為一個(gè)新的空間，并計(jì)算每一條DNA片段序列的候選DNA片段序列集合，可以提高運(yùn)算速度和精確度。

技術(shù)領(lǐng)域

本發(fā)明涉及生物信息處理領(lǐng)域，尤其涉及基于標(biāo)準(zhǔn)熵的局部敏感哈希的DNA序列聚類。

背景技術(shù)

隨著互聯(lián)網(wǎng)時(shí)代的到來和信息技術(shù)的發(fā)展，基因測(cè)序技術(shù)發(fā)展地愈發(fā)成熟，加之各項(xiàng)基因項(xiàng)目的開展，生物數(shù)據(jù)的數(shù)量呈暴增式增長(zhǎng)，傳統(tǒng)的方法已經(jīng)無法滿足海量的數(shù)據(jù)處理分析。生物信息學(xué)是指將生物學(xué)與計(jì)算機(jī)技術(shù)結(jié)合，與數(shù)學(xué)學(xué)科交互，獲取生物信息對(duì)其加工、提取、分析、存儲(chǔ)等，挖掘遺傳物質(zhì)的位置信息。數(shù)據(jù)挖掘技術(shù)是一種能從大量數(shù)據(jù)中提取有用的、潛在的有效信息的技術(shù)。數(shù)據(jù)挖掘中的聚類能將具有某些相同特征的序列聚集在一起，更好的分析數(shù)據(jù)的功能或結(jié)構(gòu)，從已知的功能和結(jié)構(gòu)的序列探索出未知序列的有效信息是具有極大意義的。

現(xiàn)有的序列聚類方法存在很多的缺陷。基于劃分的K-medoid算法、基于層次的全連接(complete-link)算法，這些傳統(tǒng)聚類算法，需要對(duì)序列進(jìn)行兩兩比對(duì)，時(shí)間復(fù)雜度高，如今的DNA序列數(shù)量增長(zhǎng)極快，傳統(tǒng)算法無法應(yīng)用于海量數(shù)據(jù)中。K-means算法需要確定聚類個(gè)數(shù)，序列數(shù)據(jù)的質(zhì)心也不易計(jì)算，初始聚類中心隨機(jī)使得聚類結(jié)果不穩(wěn)定，應(yīng)用到生物序列數(shù)據(jù)聚類效果不佳。基于BAG圖的聚類算法的結(jié)果有效，但在類的分割時(shí)需要使用聚類單元引導(dǎo)，而基因庫中的序列數(shù)目過多，導(dǎo)致其使用無向圖表示過多的序列異常困難。

發(fā)明內(nèi)容

本發(fā)明的目的在于克服現(xiàn)有技術(shù)的不足，提供基于標(biāo)準(zhǔn)熵的局部敏感哈希的DNA序列聚類。

為了實(shí)現(xiàn)上述目的，本發(fā)明采用以下技術(shù)方案：

基于標(biāo)準(zhǔn)熵的局部敏感哈希的DNA序列聚類，包括以下步驟：

(1)采用第二代測(cè)序技術(shù)對(duì)整條待測(cè)序列進(jìn)行測(cè)序，得到一批DNA短片段，每一個(gè)短片段稱為DNA片段序列；

(2)DNA片段序列中的字母集合為{A、C、G、T}，|∑|表示該字母集合中字母的個(gè)數(shù)，初始化待處理字的字長(zhǎng)大小L，對(duì)DNA片段序列使用固定長(zhǎng)度的滑動(dòng)窗口獲得待處理字Y集合，待處理字Y集合中待處理字Y的個(gè)數(shù)為|∑|^L，，根據(jù)每個(gè)待處理字的位置信息X_t計(jì)算其熵值h；

所述待處理字的位置信息X_t是指待處理字在DNA片段序列中兩次出現(xiàn)時(shí)對(duì)應(yīng)的兩個(gè)位置間的距離的倒數(shù)；

其中，Y表示待處理字，t表示待處理字出現(xiàn)的位置順序，LF_t^Y表示待處理字Y的第t次出現(xiàn)在DNA片段序列的位置，Y_λ表示第λ個(gè)預(yù)處理字；λ表示待處理字的編號(hào)；z代表待處理字出現(xiàn)的頻數(shù)；P[t]為離散概率P的第t個(gè)離散概率，即為部分和S_t占總和Z比的離散概率；

部分和S_t表示位置信息X_t之和，S_t＝X₁+X₂+...+X_t；

總和Z＝S₁+S₂+...+S_n；