一种改进的基于Hash算法及概率的k-mer索引方法

摘要：

文章基于k-mer编码建立了Hash线性索引模型.其基本思想是统计碱基字符出现的频数,将字符进行哈弗曼编码以得到最短的字符编码方式,然后使用该编码方案对k-mer碱基串进行编码,最后得到唯一的Hash值.根据k值的大小,建立相应长度的Hash表,在每个Hash位置下以链表的形式挂接位置信息,从而建立了索引模型.提出一种将四叉树进行编码压缩的索引方案——"线性Hash编码索引模型",消除了四叉树索引模型中父节点内存浪费问题.同时,查询速度从树形的O(log4n)降到了线性的0(1),得到很大地提高.

关键词：k-mer、树形索引、Hash索引、哈弗曼编码、概率模型

所属期刊栏目：34

分类号：TP3;G35

资助基金：陕西省教育厅2015年教学改革研究项目:高校科学与工程计算能力创新培养模式研究;西安科技大学2016年教育改革项目:以计算思维为导向的Java程序设计课程改革与实践编号JG14103

在线出版日期：2017-08-02（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：70-72,74