法律状态公告日
法律状态信息
法律状态
2023-04-04
未缴年费专利权终止 IPC(主分类):G16B30/00 专利号:ZL2017102855987 申请日:20170427 授权公告日:20191018
专利权的终止
2019-10-18
授权
授权
2018-11-13
著录事项变更 IPC(主分类):G06F19/20 变更前: 变更后: 申请日:20170427
著录事项变更
2017-09-22
实质审查的生效 IPC(主分类):G06F19/20 申请日:20170427
实质审查的生效
2017-08-29
公开
公开
技术领域
本发明涉及生物信息处理领域，尤其涉及基于标准熵的局部敏感哈希的DNA序列聚类。
背景技术
随着互联网时代的到来和信息技术的发展，基因测序技术发展地愈发成熟，加之各项基因项目的开展，生物数据的数量呈暴增式增长，传统的方法已经无法满足海量的数据处理分析。生物信息学是指将生物学与计算机技术结合，与数学学科交互，获取生物信息对其加工、提取、分析、存储等，挖掘遗传物质的位置信息。数据挖掘技术是一种能从大量数据中提取有用的、潜在的有效信息的技术。数据挖掘中的聚类能将具有某些相同特征的序列聚集在一起，更好的分析数据的功能或结构，从已知的功能和结构的序列探索出未知序列的有效信息是具有极大意义的。
现有的序列聚类方法存在很多的缺陷。基于划分的K-medoid算法、基于层次的全连接(complete-link)算法，这些传统聚类算法，需要对序列进行两两比对，时间复杂度高，如今的DNA序列数量增长极快，传统算法无法应用于海量数据中。K-means算法需要确定聚类个数，序列数据的质心也不易计算，初始聚类中心随机使得聚类结果不稳定，应用到生物序列数据聚类效果不佳。基于BAG图的聚类算法的结果有效，但在类的分割时需要使用聚类单元引导，而基因库中的序列数目过多，导致其使用无向图表示过多的序列异常困难。
发明内容
本发明的目的在于克服现有技术的不足，提供基于标准熵的局部敏感哈希的DNA序列聚类。
为了实现上述目的，本发明采用以下技术方案：
基于标准熵的局部敏感哈希的DNA序列聚类，包括以下步骤：
(1)采用第二代测序技术对整条待测序列进行测序，得到一批DNA短片段，每一个短片段称为DNA片段序列；
(2)DNA片段序列中的字母集合为{A、C、G、T}，|∑|表示该字母集合中字母的个数，初始化待处理字的字长大小L，对DNA片段序列使用固定长度的滑动窗口获得待处理字Y集合，待处理字Y集合中待处理字Y的个数为|∑|L，，根据每个待处理字的位置信息Xt计算其熵值h；
所述待处理字的位置信息Xt是指待处理字在DNA片段序列中两次出现时对应的两个位置间的距离的倒数；
其中，Y表示待处理字，t表示待处理字出现的位置顺序，LFtY表示待处理字Y的第t次出现在DNA片段序列的位置，Yλ表示第λ个预处理字；λ表示待处理字的编号；z代表待处理字出现的频数；P[t]为离散概率P的第t个离散概率，即为部分和St占总和Z比的离散概率；
部分和St表示位置信息Xt之和，St＝X1+X2+...+Xt；
总和Z＝S1+S2+...+Sn；
(3)计算特征向量：将熵值使用公式标准化得到标准熵值HLF作为哈希函数的特征变量，标准熵值HLF的计算公式如下：
h(Yλ)是字Yλ的熵，z代表待处理字出现的频数；
(4)计算哈希矩阵HM：将N条DNA片段序列对应的标准熵值HLF采用LSH方法进行计算，使用num_f个哈希函数计算得到num_f*N的哈希矩阵HM，哈希函数的公式如下：
其中v为DNA片段序列的特征向量，a为与特征向量v个数相同的0到1之间的随机向量，m为0到w的任一整数，w为任意正整数，这样哈希函数fa,m(v)将一个d维空间向量v映射为一个整数；
(5)计算拼接哈希矩阵PHM：使用变量b，将哈希矩阵HM分成b个桶，每个桶有r行，其中r＝num_f/b，对于每个桶的哈希矩阵HM，第i(i∈[1,num_f])行表示第i个哈希函数，第j(j∈[1,N])列表示第j条DNA片段序列，则HMij表示将第j条DNA片段序列的标准熵值采用第i个哈希函数进行哈希映射后的整数值；然后对HMij只保留前三位，不足三位则高位补充0；最后将HMj的每行进行拼接作为哈希拼接值，得到b*N的拼接哈希矩阵PHM；
(6)计算候选DNA片段序列集合：对于DNA片段序列Si(i∈[1,N])，当在拼接哈希矩阵PHM中存在DNA片段序列Sj(j∈[1,N]，i≠j)与Si在同一行的哈希拼接值相同，则Sj是Si的候选DNA片段序列，Si的所有候选DNA片段序列构成候选DNA片段序列集合Candidate；
(7)实现聚类：随机选取一条未被聚类的DNA片段序列作为聚类中心，筛选该聚类中心对应的候选DNA片段序列集合Candidate与该聚类中心的编辑距离小于指定的阀值d的候选序列作为一个聚类结果，(由于已进行聚类的序列不再作为聚类中心或出现在其他聚类结果中)，将已经被聚类的DNA片段序列存储在clustered中，循环上述聚类步骤，直到所有DNA片段序列都被聚类(即clustered中包含所有的序列)。
其中，编辑距离反映两条序列之间的不相似度，编辑距离越大说明越不相似。在聚类过程中，我们希望将相似的序列聚在一起，因此会指定一个阀值d，编辑距离小于d说明这两条序列符合定义的相似的要求。
进一步，所述步骤(4)，w的取值为4。
本发明采用以上技术方案，在众多的DNA序列分析方法中，我们通过对原始的DNA序列按着L-Gram模型进行映射，即由于DNA序列是由{A,T,C,G}四个字母组成，预处理字长为L，从而获得|∑|L个待处理字；从而原始DNA序列经过映射得到一个新的数字序列。通过计算N条序列的Local>L的矩阵，进而得出其标准熵作为特征向量；使用Locality-Sensitive>
附图说明
以下结合附图和具体实施方式对本发明做进一步详细说明：
图1为本发明基于标准熵的局部敏感哈希的DNA序列聚类的流程图。
具体实施方式
如图1所示，本发明基于标准熵的局部敏感哈希的DNA序列聚类，其包括以下步骤：
(1)采用第二代测序技术对整条待测序列进行测序，得到一批DNA短片段，每一个短片段称为DNA片段序列；
(2)DNA片段序列中的字母集合为{A、C、G、T}，|∑|表示该字母集合中字母的个数，初始化待处理字的字长大小L，对DNA片段序列使用固定长度的滑动窗口获得待处理字Y集合，待处理字Y集合中待处理字Y的个数为|∑|L，根据每个待处理字的位置信息Xt计算其熵值h；
所述待处理字的位置信息Xt是指待处理字在DNA片段序列中两次出现时对应的两个位置间的距离的倒数；
其中，Y表示待处理字，t表示待处理字出现的位置顺序，LFtY表示待处理字Y的第t次出现在DNA片段序列的位置，Yλ表示第λ个预处理字；λ表示待处理字的编号；z代表待处理字出现的频数；P[t]为离散概率P的第t个离散概率，即为部分和St占总和Z比的离散概率；
部分和St表示位置信息Xt之和，St＝X1+X2+...+Xt；
总和Z＝S1+S2+...+Sn；
(3)计算特征向量：将熵值使用公式标准化得到标准熵值HLF作为哈希函数的特征变量，标准熵值HLF的计算公式如下：
h(Yλ)是字Yλ的熵，z代表待处理字出现的频数；
(4)计算哈希矩阵HM：将N条DNA片段序列对应的标准熵值HLF采用LSH方法进行计算，使用num_f个哈希函数计算得到num_f*N的哈希矩阵HM，哈希函数的公式如下：
其中v为DNA片段序列的特征向量，a为与特征向量v个数相同的0到1之间的随机向量，m为0到w的任一整数，w为任意正整数，这样哈希函数fa,m(v)将一个d维空间向量v映射为一个整数；
(5)计算拼接哈希矩阵PHM：使用变量b，将哈希矩阵HM分成b个桶，每个桶有r行，其中r＝num_f/b，对于每个桶的哈希矩阵HM，第i(i∈[1,num_f])行表示第i个哈希函数，第j(j∈[1,N])列表示第j条DNA片段序列，则HMij表示将第j条DNA片段序列的标准熵值采用第i个哈希函数进行哈希映射后的整数值；然后对HMij只保留前三位，不足三位则高位补充0；最后将HMj的每行进行拼接作为哈希拼接值，得到b*N的拼接哈希矩阵PHM；
(6)计算候选DNA片段序列集合：对于DNA片段序列Si(i∈[1,N])，当在拼接哈希矩阵PHM中存在DNA片段序列Sj(j∈[1,N]，i≠j)与Si在同一行的哈希拼接值相同，则Sj是Si的候选DNA片段序列，Si的所有候选DNA片段序列构成候选DNA片段序列集合Candidate；
(7)实现聚类：随机选取一条未被聚类的DNA片段序列作为聚类中心，筛选该聚类中心对应的候选DNA片段序列集合Candidate与该聚类中心的编辑距离小于指定的阀值d的候选序列作为一个聚类结果，(由于已进行聚类的序列不再作为聚类中心或出现在其他聚类结果中)，将已经被聚类的DNA片段序列存储在clustered中，循环上述聚类步骤，直到所有DNA片段序列都被聚类。
下面就本发明的处理过程做详细的说明：
为了更清楚描述本发明中DNA序列的处理过程，随机抽取12条DNA编码序列作为分析对象，以这些DNA序列为样例对发明实施过程进行详细的描述。基于标准熵的局部敏感哈希的DNA序列聚类步骤如下：
(1)采用第二代测序技术对整条待测序列进行测序，得到一批DNA短片段，每一个短片段称为DNA片段序列；
表1 12条DNA片段
(2)DNA片段序列中的字母集合为{A、C、G、T}，|∑|表示该字母集合中字母的个数，初始化待处理字的字长大小L，对DNA片段序列使用固定长度的滑动窗口获得待处理字Y集合，待处理字Y集合中待处理字Y的个数为|∑|L，根据每个待处理字的位置信息Xt计算其熵值h；
所述待处理字的位置信息Xt是指待处理字在DNA片段序列中两次出现时对应的两个位置间的距离的倒数；
其中，Y表示待处理字，t表示待处理字出现的位置顺序，LFtY表示待处理字Y的第t次出现在DNA片段序列的位置，Yλ表示第λ个预处理字；λ表示待处理字的编号；z代表待处理字出现的频数；P[t]为离散概率P的第t个离散概率，即为部分和St占总和Z比的离散概率；
部分和St表示位置信息Xt之和，St＝X1+X2+...+Xt；
总和Z＝S1+S2+...+Sn；
(3)计算特征向量：将熵值使用公式标准化得到标准熵值HLF作为哈希函数的特征变量，标准熵值HLF的计算公式如下：
h(Yλ)是字Yλ的熵，z代表待处理字出现的频数；
根据公式计算得到特征向量表如下：
表2特征向量表
(4)计算哈希矩阵HM：将N条DNA片段序列对应的标准熵值HLF采用LSH方法进行计算，使用num_f个哈希函数计算得到num_f*N的哈希矩阵HM，哈希函数的公式如下：
其中v为DNA片段序列的特征向量，a为与特征向量v个数相同的0到1之间的随机向量，m为0到w的任一整数，w为任意正整数，这样哈希函数fa,m(v)将一个d维空间向量v映射为一个整数；在本实施例中num_f＝8，w＝4；
表3哈希矩阵
(5)计算拼接哈希矩阵PHM：使用变量b，将哈希矩阵HM分成b个桶，每个桶有r行，其中r＝num_f/b，对于每个桶的哈希矩阵HM，第i(i∈[1,num_f])行表示第i个哈希函数，第j(j∈[1,N])列表示第j条DNA片段序列，则HMij表示将第j条DNA片段序列的标准熵值采用第i个哈希函数进行哈希映射后的整数值；然后对HMij只保留前三位，不足三位则高位补充0；最后将HMj的每行进行拼接作为哈希拼接值，得到b*N的拼接哈希矩阵PHM；
(6)计算候选DNA片段序列集合：对于DNA片段序列Si(i∈[1,N])，当在拼接哈希矩阵PHM中存在DNA片段序列Sj(j∈[1,N]，i≠j)与Si在同一行的哈希拼接值相同，则Sj是Si的候选DNA片段序列，Si的所有候选DNA片段序列构成候选DNA片段序列集合Candidate；
下表是候选DNA片段序列集合表，为了便于理解，将本实施例中的12条序列的候选DNA片段序列集合表统计如下：
表4候选序列集合表
(7)实现聚类：随机选取一条未被聚类的DNA片段序列作为聚类中心，筛选该聚类中心对应的候选DNA片段序列集合Candidate与该聚类中心的编辑距离小于指定的阀值d的候选序列作为一个聚类结果，(由于已进行聚类的序列不再作为聚类中心或出现在其他聚类结果中)，将已经被聚类的DNA片段序列存储在clustered中，循环上述聚类步骤，直到所有DNA片段序列都被聚类。
本发明采用以上技术方案，在众多的DNA序列分析方法中，我们通过对原始的DNA序列按着L-Gram模型进行映射，即由于DNA序列是由{A,T,C,G}四个字母组成，预处理字长为L，从而获得|∑|L个待处理字；从而原始DNA序列经过映射得到一个新的数字序列。通过计算N条序列的Local>L的矩阵，进而得出其标准熵作为特征向量；使用Locality-Sensitive>
机译： 一种基于熵信息和贝叶斯SOM的基于排序文档的聚类调整方法
机译： 基于熵信息和贝叶斯SOMS自组织特征图的基于等级文档聚类的重新调整方法
机译： 对象聚类，用于基于感知标准渲染基于对象的音频内容
