耿彧 白涛

[摘 要]哈希表由于能够实现高效的数据存储和查找，操作时间可达到O（1）级，所以其被广泛应用于信息安全、操作系统、数据挖掘和生物信息等领域。本文对哈希方法在生物信息中的应用进行了探讨，同时介绍了其他特殊的哈希方法在生物信息相关问题中的解决策略。哈希方法的引入能更好地提高生物信息大数据的存储与检索性能。

[关键词]生物信息计算；哈希方法；最小哈希；相似哈希

doi：10.3969/j.issn.1673 - 0194.2018.12.064

[中图分类号]TP312；R28 [文献标识码]A [文章编号]1673-0194（2018）12-0-02

1 哈希方法在组装技术中的应用

哈希函数可把任意长度的输入通过一定的算法转换成固定长度的哈希值，将某种类型的数据元素尽量均匀随机地映射到一个整数空间。哈希表根据设定的哈希函数和处理冲突方法将一组关键字映射到一个有限的地址区间上，在实际中不可避免地产生哈希冲突，一个良好的哈希函数应保证散列均匀、冲突少。在基因序列组装技术中，通常采用不同的哈希方法对k-mers实现快速存储与查找。如Meta-IDBA采用一次哈希方法实现宏基因组序列组装，将k-mers存储于一个数组中，按数组类型的位数对k-mer进行分段，再对每段进行异或运算。然而，一次哈希函数建立的哈希表策略可能产生较高的冲突率，因此考虑采用多次哈希和多级哈希方法保证装填因子在更合理的情况下减少冲突率。多次哈希方法先采用一种哈希函数对关键字进行散列，然后对发生冲突的关键字采用不同哈希函数再次散列。……