龙源期刊?/p>
http://www.qikan.com.cn
哈希方法在生物信息学研究中的应用探讨
作者:耿彧
白涛
来源:《中国管理信息化?/p>
2018
年第
12
?/p>
[
?/p>
?/p>
]
哈希表由于能够实现高效的数据存储和查找,操作时间可达?/p>
O
?/p>
1
)级,所以其
被广泛应用于信息安全、操作系统、数据挖掘和生物信息等领域。本文对哈希方法在生物信?/p>
中的应用进行了探讨,同时介绍了其他特殊的哈希方法在生物信息相关问题中的解决策略。哈
希方法的引入能更好地提高生物信息大数据的存储与检索性能?/p>
[
关键?/p>
]
生物信息计算;哈希方法;最小哈希;相似哈希
doi
?/p>
10.3969/j.issn.1673 - 0194.2018.12.064
[
中图分类?/p>
]TP312
?/p>
R28 [
文献标识?/p>
]A [
文章编号
]1673-0194
?/p>
2018
?/p>
12-0-02
1
哈希方法在组装技术中的应?/p>
哈希函数可把任意长度的输入通过一定的算法转换成固定长度的哈希值,将某种类型的?/p>
据元素尽量均匀随机地映射到一个整数空间。哈希表根据设定的哈希函数和处理冲突方法将一
组关键字映射到一个有限的地址区间上,在实际中不可避免地产生哈希冲突,一个良好的哈希
函数应保证散列均匀、冲突少。在基因序列组装技术中,通常采用不同的哈希方法对
k-mers
实现快速存储与查找。如
Meta-IDBA
采用一次哈希方法实现宏基因组序列组装,?/p>
k-mers
?/p>
储于一个数组中,按数组类型的位数对
k-mer
进行分段,再对每段进行异或运算。然而,一?/p>
哈希函数建立的哈希表策略可能产生较高的冲突率,因此考虑采用多次哈希和多级哈希方法保
证装填因子在更合理的情况下减少冲突率。多次哈希方法先采用一种哈希函数对关键字进行散
列,然后对发生冲突的关键字采用不同哈希函数再次散列。多级哈希方法根据关键字的哈希?/p>
对数据元素进?/p>
?/p>
分类
?/p>
,如
SOAPdenovo
采用二级哈希方法实现组装,第一级哈希函数将
k-
mer
进行循环冗余程序计算,按照所得哈希值查找已确定的循环冗余校验表,得到对应的桶号
?/p>
0
?/p>
255
),然后对每个桶再次建立第二级哈希表?/p>
以染色体
chr19
为参考序列,分别采用一次哈希、二次哈希和二级哈希方法,从装填?/p>
子、冲突率和平均查找长度几个性能指标对不同长度的
k-mer
进行分析,为基因组序列组装中
哈希方法的选择提供参考依据。输入数据为双末端读段,插入距离服从正态分?/p>
N
?/p>
500 bp
?/p>
49 bp
),读段长度?/p>
100 bp
。一次哈希方法中哈希函数采用分段叠加法,每段长度?/p>
27 bp
?/p>
二次哈希方法中第一次哈希函数采用分段异或法,第二次哈希函数采用分段叠加法;二级哈希
方法中第一级哈希函数采用低八位?/p>
255
进行按位与运算,产生
256
个桶,再用第二级哈希?/p>
数分段叠加法实现桶内的哈希存储。对于生物信息中涉及的大数据,用公共溢出区的方法按顺
序查找空位,其效率相对较低,所以通常采用链地址法解决冲突?/p>