哈希表应用于DNA序列的k-mer索引建模+代码(2)
时间:2019-10-17 20:06 来源:毕业论文 作者:毕业论文 点击:次
第三节 时间与空间复杂度分析 10 3.3.1 小规模k-mer索引模型的时间与空间复杂度 10 3.3.2 小规模k-mer查找模型的时间与空间复杂度 11 3.3.3 改进后k-mer索引模型的时间与空间复杂度 12 3.3.4 改进后k-mer查找模型的时间与空间复杂度 13 第四节 本章小结 14 第四章 仿真与结果分析 14 第一节 计算临界值K 14 第二节 仿真与结果展示 15 第三节 本章小结 17 第五章 结论与展望 17 第一节 结论 17 第二节 展望 18 参考文献 19 附录 19 第一章 绪论 第一节 研究背景 随着近些年来测序技术的飞速发展,人类产生了海量的生物序列数据,亟需通过有效的计算手段进行分析和处理。而在众多的生物序列分析与处理问题中,生物序列数据的k-mer索引是一种非常关键且重要的序列特征,它在序列比对、序列拼接、序列聚类、模式发现等诸多的问题上得到了广泛的应用[1]。面对大规模数据，k-mer索引的算法就显得至关重要。 由于DNA序列一般由成千上万甚至上百万的碱基对组成，所以DNA序列中的序列片段k-mer的数量往往很大，如果单纯使用穷举算法对于计算机的计算时间和内存使用非常巨大，所以需要采用更高效的算法来建立索引，通过深入的学习和研究，发现哈希表十分适合于k-mer的索引问题[6]。 哈希表[2]一般也叫散列表，是根据关键码值而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。 数学定义为：给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希表，函数f(key)为哈希函数。 针对DNA序列的k-mer索引问题，本文主要通过对问题的深入分析以及对数据的处理和理论推导，对于不同的k进行分析讨论，随后制定不同的哈希表，使得对于尽可能多的k能建立索引。在建立完索引后，优化不同哈希表中的k值的取值范围，使得索引的时间尽可能短。 第二节 主要研究内容 本文主要研究内容如下： 1）.对哈希表及哈希函数的原理与特点进行研究，从而为后续研究打好理论基础。 2）.根据DNA序列索引的实际情况，对于小规模的k-mer片段运用哈希表对于其索引与查找建立初步模型，并计算相应的时间与空间复杂度。 3）在小规模的索引-查找模型的基础上改进模型，是算法能应对大规模的数据量，并计算相应的时间与空间复杂度。 4）结合两种模型，并用c语言编程实现，使得程序能应对不同规模的问题，最后用实际数据仿真实验，确定两种模型的界限K。 第三节 论文的组织架构 第一章是绪论，介绍了论文的研究背景和意义，列出了论文的主要研究内容和论文的组织架构。 第二章是本文的研究基础。本章介绍了课题研究的相关技术，首先对哈希表进行了介绍，其次对哈希表应用于DNA序列的k-mer索引进行了阐述。 第三章研究了基于哈希表的k-mer索引-查找模型。本章根据k-mer的长度，先研究长度较小的k-mer索引与查找的模型，然后基于上述研究进行改进，实现对于长片段的k-mer索引-查找的改进模型，并且对于这两个模型计算时间与空间复杂度。 第四章对提出的两种模型进行结合,通过实际数据测定两种模型的界限值K，并对结果进行了分析。 (责任编辑：qin) |