[發(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
• 代理公司: 福州君誠知識(shí)產(chǎn)權(quán)代理有限公司 35211
• 代理人: 戴雨君

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

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

(2)DNA片段序列中的字母集合為{A、C、G、T}，|∑|表示該字母集合中字母的個(gè)數(shù)，初始化待處理字的字長大小L，對(duì)DNA片段序列使用固定長度的滑動(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è)離散概率，即為部分和Q_t占總和Z的離散概率；

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

總和Z＝Q₁+Q₂+...+Q_n；

(3)計(jì)算特征向量：將熵值使用公式標(biāo)準(zhǔn)化得到標(biāo)準(zhǔn)熵值H_LF作為哈希函數(shù)的特征變量，標(biāo)準(zhǔn)熵值H_LF的計(jì)算公式如下：

h(Y_λ)是字Y_λ的熵，z代表待處理字出現(xiàn)的頻數(shù)；

(4)計(jì)算哈希矩陣HM：將N條DNA片段序列對(duì)應(yīng)的標(biāo)準(zhǔn)熵值H_LF采用Locality-SensitiveHashing方法進(jìn)行計(jì)算，使用num_f個(gè)哈希函數(shù)計(jì)算得到num_f*N的哈希矩陣HM，哈希函數(shù)的公式如下：

f_a,m(v)＝(a·v+m)/w

其中v為DNA片段序列的特征向量，a為與特征向量v個(gè)數(shù)相同的0到1之間的隨機(jī)向量，m為0到w的任一整數(shù)，w為任意正整數(shù)，這樣哈希函數(shù)f_a,m(v)將一個(gè)d維空間向量v映射為一個(gè)整數(shù)；

(5)計(jì)算拼接哈希矩陣PHM：使用變量b，將哈希矩陣HM分成b個(gè)桶，每個(gè)桶有r行，其中r＝num_f/b，對(duì)于每個(gè)桶的哈希矩陣HM，第i行表示第i個(gè)哈希函數(shù)，第j列表示第j條DNA片段序列，i∈[1,num_f]，j∈[1,N]，則HM_ij表示將第j條DNA片段序列的標(biāo)準(zhǔn)熵值采用第i個(gè)哈希函數(shù)進(jìn)行哈希映射后的整數(shù)值；然后對(duì)HM_ij只保留前三位，不足三位則高位補(bǔ)充0；最后將HM_j的每行進(jìn)行拼接作為哈希拼接值，得到b*N的拼接哈希矩陣PHM；

(6)計(jì)算候選DNA片段序列集合：對(duì)于DNA片段序列S_m，m∈[1,N]，當(dāng)在拼接哈希矩陣PHM中存在DNA片段序列S_n與S_m在同一行的哈希拼接值相同，n∈[1,N]，m≠n，則S_n是S_m的候選DNA片段序列，Sm的所有候選DNA片段序列構(gòu)成候選DNA片段序列集合Candidate；

(7)實(shí)現(xiàn)聚類：隨機(jī)選取一條未被聚類的DNA片段序列作為聚類中心，篩選該聚類中心對(duì)應(yīng)的候選DNA片段序列集合Candidate與該聚類中心的編輯距離小于指定的閥值d的候選序列作為一個(gè)聚類結(jié)果，將已經(jīng)被聚類的DNA片段序列存儲(chǔ)在clustered中，循環(huán)上述聚類步驟，直到所有DNA片段序列都被聚類。

2.根據(jù)權(quán)利要求1所述的基于標(biāo)準(zhǔn)熵的局部敏感哈希的DNA序列聚類，其特征在于：步驟(4)，w的取值為4。