论文哈希方法在生物信息学中的应用，本文是关于生物信息学方面毕业论文范文和生物信息学和哈希和哈希方法方面论文写作资料范文.
［摘 要］哈希表由于能够实现高效的数据存储和查找,操作时间可达到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).
小结：该文是一篇适合生物信息学和哈希和哈希方法论文写作的大学硕士及关于生物信息学本科毕业论文，相关生物信息学开题报告范文和学术职称论文参考文献.
参考文献：
1、 融合教学模式在生物信息处理课改中的应用 摘 要生物信息处理是一门较新的具有很强理论性和实践性的课程 将以团队为基础的学习、以案例为基础的学习和以问题为中心的学习……多种教学形式引入生物信息处理的课堂,就是借鉴软件工程项目团队建设、案例教学、.
2、 任务驱动教学法在生物信息学教学中的实践和 邹先琼,林军,廖锦锋（桂林医学院生物技术学院,广西桂林541100）摘要任务驱动教学法是将学生的学习活动与教学任务或问题相结合,以解决问题和完成任务来提高学生学习兴趣的教学法 生物信息学是一门以研究生.
3、 生物信息学分析和预测Snai1的靶向作用miRNA分子 1 南华大学附属郴州市第一人民医院消化内科 湖南省郴州市 4230002 南华大学附属郴州市第一人民医院ICU 湖南省郴州市 423000【摘 要】目的通过生物信息学方法预测和寻找Snai1 的靶向作.
4、 科技图书馆信息服务能力评估方法探析 文江西省图书馆 陈清【摘要】现代的世界是一个信息网络发达的时代,很多领域和行业都在采用高科技的方式来完成相应的工作,很多领域也都面临或者已经进行了革新来应对自身发展的需要 对于图书馆来说,原有图书馆的.
5、 阅读社区：阅读推广视角的社群信息学实践 摘 要 虽然阅读社区是“微社群”,但同样是一个复杂的有机体,采用社群信息学的观点对阅读社区进行研究既有利于推动图书馆学与信息学的深度交流,也有利于深入挖掘阅读社区的全民阅读推广.