基于Hash算法的DNA序列k-mer index问题的数学建模

摘要：

针对查找DNA序列的相似序列问题,给出了建立索引和查找索引的数学模型,基于Hash算法,建立了依赖于k值大小的顺序索引模型和散列索引模型,特别对较大k值选用了DJBHash函数,有效的避免了Hash冲突问题.最后在硬件平台CPU为2.6GHz、内存为8G、操作系统为64位Windows 7的条件下,对100万条长度为100的DNA序列进行了测试,给出了不同k值下建立和查询索引的用时和占用内存情况,有效的解决了DNA序列的k-mer index问题.

关键词：Hash算法、索引问题、数学模型、复杂度分析

所属期刊栏目：38

分类号：O244(计算数学)

资助基金：国家自然科学基金NSFC:11326078

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

页数：共4页

页码：116-119