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

摘要

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