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

An Improved K-mer Index Method Based on Hash Index and Probability

作　　者：史晓楠[1] 徐澜[2] 徐丹丹[3] 高慧慧[2] 

机构地区：[1]西安科技大学计算机科学与技术学院,陕西西安710054 [2]西安科技大学测绘科学与技术学院,陕西西安710054 [3]西安科技大学电气与控制工程学院,陕西西安710054

出　　处：《通信电源技术》2017年第3期70-72,74,共4页Telecom Power Technology

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

摘　　要：文章基于k-mer编码建立了Hash线性索引模型。其基本思想是统计碱基字符出现的频数,将字符进行哈弗曼编码以得到最短的字符编码方式,然后使用该编码方案对k-mer碱基串进行编码,最后得到唯一的Hash值。根据k值的大小,建立相应长度的Hash表,在每个Hash位置下以链表的形式挂接位置信息,从而建立了索引模型。提出一种将四叉树进行编码压缩的索引方案——"线性Hash编码索引模型",消除了四叉树索引模型中父节点内存浪费问题。同时,查询速度从树形的O(log4n)降到了线性的0(1),得到很大地提高。This paper established a Hash linear index model based on k-mer encoding.The basic idea was to count the frequency of the base characters,the characters were subjected to the Huffman encoding to obtain the shortest character encoding,and then used the coding scheme to encode the k-mer base string,and finally got the unique Hash value.According to the size of the K value,a Hash table of the corresponding length was established,and the position information was linked in the form of a linked list in each Hash position,so an index model was established.An index scheme for encoding and decoding four binary trees called linear Hash coding index model is proposed.This eliminated the memory waste problem of the parent node in the four tree index model.At the same time,the query speed was from the tree type O（log4^n）down to the linear 0（1）.It has been greatly improved.

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]