论文部分内容阅读
[摘 要]哈希表由于能夠实现高效的数据存储和查找，操作时间可达到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进行分段，再对每段进行异或运算。然而，一次哈希函数建立的哈希表策略可能产生较高的冲突率，因此考虑采用多次哈希和多级哈希方法保证装填因子在更合理的情况下减少冲突率。多次哈希方法先采用一种哈希函数对关键字进行散列，然后对发生冲突的关键字采用不同哈希函数再次散列。多级哈希方法根据关键字的哈希值对数据元素进行“分类”，如SOAPdenovo采用二级哈希方法实现组装，第一级哈希函数将k-mer进行循环冗余程序计算，按照所得哈希值查找已确定的循环冗余校验表，得到对应的桶号（0～255），然后对每个桶再次建立第二级哈希表。
以染色体chr19为参考序列，分别采用一次哈希、二次哈希和二级哈希方法，从装填因子、冲突率和平均查找长度几个性能指标对不同长度的k-mer进行分析，为基因组序列组装中哈希方法的选择提供参考依据。输入数据为双末端读段，插入距离服从正态分布N（500 bp，49 bp），读段长度为100 bp。一次哈希方法中哈希函数采用分段叠加法，每段长度取27 bp；二次哈希方法中第一次哈希函数采用分段异或法，第二次哈希函数采用分段叠加法；二级哈希方法中第一级哈希函数采用低八位与255进行按位与运算，产生256个桶，再用第二级哈希函数分段叠加法实现桶内的哈希存储。对于生物信息中涉及的大数据，用公共溢出区的方法按顺序查找空位，其效率相对较低，所以通常采用链地址法解决冲突。
（1）在无变异的情况下。k值分别取23 bp、45 bp和63 bp，覆盖度为100×。装填因子、冲突率和平均查找长度的比较如图1所示。
一次哈希方法和二次哈希方法中所用哈希表长度均为227，k值越大k-mer数目越少。装填因子与k值成正比，冲突率、平均查找长度与k值成反比，即k取值越大哈希效果越好。通过分析可见，二次哈希方法性能更优。
（2）对性能较优的二次哈希方法，覆盖度取值为30×，k-mer取值为63 bp，实现不同变异率下的比较分析，变异率分别为0、10-4和10-5。从图2可见，随着变异率的增大，装填因子、冲突率及平均查找长度均有所增加。
2 其他Hash方法
2.1 最小哈希（Minhash）
Minhash可以用来快速估算两个集合的相似度。Yang将Minhash用于DNA序列的聚类；VICUNA引入Minhash解决片段重叠群（Contig）中的读段聚类问题。Jaccard Index是距离的一种度量标准，用来计算集合的相似性。对于集合A和B，当A∪B中具有最小哈希值的元素也在A∩B中，则hmin（A）=hmin（B）。其中，hmin（S）表示集合S中的元素经过哈希函数后，具有最小哈希值的元素。集合A和B的相似度为集合A和B经过哈希函数运算后取得最小哈希值相等的概率，即J（A，B）=Pr[hmin（A）=hmin（B）]。根据Minhash思想计算两个集合的相似度时，可采用单哈希函数和多哈希函数的解决策略。使用多哈希函数时，如哈希函数个数为k，用k个哈希函数分别对集合A和B求哈希值。每种哈希函数都会得到一个相应的最小哈希值，min（A）={a1，…，ak}，min（B）={b1，…，bk}那么A和B的相似度为：J（A，B）=（min（A）k∩min（B）k）/（min（A）k∪min（B）k）。
2.2 相似哈希（Similarity Hash）
相似哈希是一种局部敏感哈希函数，不仅能定性地判断同类型数据元素是否相同，还能进一步定量分析同类数据元素之间的相似度，即越相似的元素相似哈希值越相近，反之，哈希值相差越远。将相似哈希的思想引入比对技术中，将读段拆分为不覆盖的k段，每一段转换为一个特征集合，该集合是一个n维的向量V，给特征集合中的每个特征都赋予一个权重，由于读段中每个位点的地位是均等的，所以每个特征的权值都置为1。由于MD5函数产生的哈希值具有随机性强的特点，所以对读段中的k段可采用MD5作为哈希函数进行散列，得到一个n位的哈希值h；如果h的第i位为1，则向量V的第i位加上权值；如果h的第i位为0，则向量V的第i位减去权值；将读段的k段按位统计，进行累加，如果第i维的累加值大于0，则将相似哈希值中该位置为1，否则置为0，所得结果即为此序列的相似哈希值。
3 结 语
哈希函数可以实现快速索引功能，具有O（1）级的时间复杂度，使其得到了广泛应用。然而哈希表是基于数组创建的，很难再次拓展，而且装填因子的大小会影响哈希函数的性能。目前衍生出了许多哈希方法，但不同的应用对哈希函数有着不同的要求。
主要参考文献
[1]Peng Y，Leung H C M， Yiu S M.Meta-IDBA：a De Novo Assembler for Metagenomic Data[J].Bioinformatics，2011（13）.
[2]Li R，Zhu H，Ruan J.De novo Assembly of Human Genomes with Massively Parallel Short Read Sequencing[J].Genome Research，2010（2）.
[3]Yang X，Charlebois P，Gnerre S.De Novo Assembly of Highly Diverse Viral Populations[J].Bmc Genomics，2012（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进行分段，再对每段进行异或运算。然而，一次哈希函数建立的哈希表策略可能产生较高的冲突率，因此考虑采用多次哈希和多级哈希方法保证装填因子在更合理的情况下减少冲突率。多次哈希方法先采用一种哈希函数对关键字进行散列，然后对发生冲突的关键字采用不同哈希函数再次散列。多级哈希方法根据关键字的哈希值对数据元素进行“分类”，如SOAPdenovo采用二级哈希方法实现组装，第一级哈希函数将k-mer进行循环冗余程序计算，按照所得哈希值查找已确定的循环冗余校验表，得到对应的桶号（0～255），然后对每个桶再次建立第二级哈希表。
以染色体chr19为参考序列，分别采用一次哈希、二次哈希和二级哈希方法，从装填因子、冲突率和平均查找长度几个性能指标对不同长度的k-mer进行分析，为基因组序列组装中哈希方法的选择提供参考依据。输入数据为双末端读段，插入距离服从正态分布N（500 bp，49 bp），读段长度为100 bp。一次哈希方法中哈希函数采用分段叠加法，每段长度取27 bp；二次哈希方法中第一次哈希函数采用分段异或法，第二次哈希函数采用分段叠加法；二级哈希方法中第一级哈希函数采用低八位与255进行按位与运算，产生256个桶，再用第二级哈希函数分段叠加法实现桶内的哈希存储。对于生物信息中涉及的大数据，用公共溢出区的方法按顺序查找空位，其效率相对较低，所以通常采用链地址法解决冲突。
（1）在无变异的情况下。k值分别取23 bp、45 bp和63 bp，覆盖度为100×。装填因子、冲突率和平均查找长度的比较如图1所示。
一次哈希方法和二次哈希方法中所用哈希表长度均为227，k值越大k-mer数目越少。装填因子与k值成正比，冲突率、平均查找长度与k值成反比，即k取值越大哈希效果越好。通过分析可见，二次哈希方法性能更优。
（2）对性能较优的二次哈希方法，覆盖度取值为30×，k-mer取值为63 bp，实现不同变异率下的比较分析，变异率分别为0、10-4和10-5。从图2可见，随着变异率的增大，装填因子、冲突率及平均查找长度均有所增加。
2 其他Hash方法
2.1 最小哈希（Minhash）
Minhash可以用来快速估算两个集合的相似度。Yang将Minhash用于DNA序列的聚类；VICUNA引入Minhash解决片段重叠群（Contig）中的读段聚类问题。Jaccard Index是距离的一种度量标准，用来计算集合的相似性。对于集合A和B，当A∪B中具有最小哈希值的元素也在A∩B中，则hmin（A）=hmin（B）。其中，hmin（S）表示集合S中的元素经过哈希函数后，具有最小哈希值的元素。集合A和B的相似度为集合A和B经过哈希函数运算后取得最小哈希值相等的概率，即J（A，B）=Pr[hmin（A）=hmin（B）]。根据Minhash思想计算两个集合的相似度时，可采用单哈希函数和多哈希函数的解决策略。使用多哈希函数时，如哈希函数个数为k，用k个哈希函数分别对集合A和B求哈希值。每种哈希函数都会得到一个相应的最小哈希值，min（A）={a1，…，ak}，min（B）={b1，…，bk}那么A和B的相似度为：J（A，B）=（min（A）k∩min（B）k）/（min（A）k∪min（B）k）。
2.2 相似哈希（Similarity Hash）
相似哈希是一种局部敏感哈希函数，不仅能定性地判断同类型数据元素是否相同，还能进一步定量分析同类数据元素之间的相似度，即越相似的元素相似哈希值越相近，反之，哈希值相差越远。将相似哈希的思想引入比对技术中，将读段拆分为不覆盖的k段，每一段转换为一个特征集合，该集合是一个n维的向量V，给特征集合中的每个特征都赋予一个权重，由于读段中每个位点的地位是均等的，所以每个特征的权值都置为1。由于MD5函数产生的哈希值具有随机性强的特点，所以对读段中的k段可采用MD5作为哈希函数进行散列，得到一个n位的哈希值h；如果h的第i位为1，则向量V的第i位加上权值；如果h的第i位为0，则向量V的第i位减去权值；将读段的k段按位统计，进行累加，如果第i维的累加值大于0，则将相似哈希值中该位置为1，否则置为0，所得结果即为此序列的相似哈希值。
3 结 语
哈希函数可以实现快速索引功能，具有O（1）级的时间复杂度，使其得到了广泛应用。然而哈希表是基于数组创建的，很难再次拓展，而且装填因子的大小会影响哈希函数的性能。目前衍生出了许多哈希方法，但不同的应用对哈希函数有着不同的要求。
主要参考文献
[1]Peng Y，Leung H C M， Yiu S M.Meta-IDBA：a De Novo Assembler for Metagenomic Data[J].Bioinformatics，2011（13）.
[2]Li R，Zhu H，Ruan J.De novo Assembly of Human Genomes with Massively Parallel Short Read Sequencing[J].Genome Research，2010（2）.
[3]Yang X，Charlebois P，Gnerre S.De Novo Assembly of Highly Diverse Viral Populations[J].Bmc Genomics，2012（1）.