基于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问题。

The Mathematical Model of k-mer Index for DNA Sequence Problem Based on Hash Algorithm

In this paper, we give the mode of building and searching index for DNA similar sequences. Based on the Hash algorithm,we establish the order index model and Hash indexing model which depend on the size of the k val-ue. In orter to avoid Hash-Clash, we chose DJBhash fuction under the larger k value. Finally, we give the time of buliding and searching index and the memory occupation with different k value which CPU is 2.6GHz,memory is 8G, operation system is window 7 at 64 bit, at the same time, we test 1 million of DNA sequence with the length of 100,solve the k-mer index problem of DNA sequence effectively.