dna序列的k-merindex问题-基于hash算法快速检索

《dna序列的k-merindex问题-基于hash算法快速检索》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2015山东科技大学数学建模竞赛承诺书我们仔细阅读了山东科技大学数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C中选择一项

2、填写）：我们的参赛序号为：所属学院（请填写完整的全名）：参赛队员(打印并签名)：1.2.3.日期：年月日基于Hash表在大量DNA序列中快速索引查找k-mer的算法摘要：为了解决在大量DNA数据中快速查找到k-mer所在位置，我们基于Hash算法思想建立适合此题的快速索引方法（桶式定址法），利用四进制转十进制的方式（）取得关键码值建立哈希表进行索引查询，8G内存限制下在codeblocks集成开发环境中，借助C语言进行编写使k支持1~14。针对问题将依次进行下列叙述：对建立索引的算法进行叙述和冲突分析；对建立索引算法的

3、计算复杂度和空间复杂度进行分析；对索引查询进行叙述及性能分析；分析整套算法程序在不同k值下内存占用及极限分析。总结分析整套索引算法性能，对算法进行缺陷分析及改进方案。关键词：索引算法、Hash表、k-mer快速索引、数据结构一、问题重述1.1背景给定一个DNA序列，这个系列只含有4个字母ATCG，如S=“CTGTACTGTAT”。给定一个整数值k，从S的第一个位置开始，取一连续k个字母的短串，称之为k-mer（如k=5，则此短串为CTGTA），然后从S的第二个位置，取另一k-mer（如k=5，则此短串为TGTAC），这

4、样直至S的末端，就得一个集合，包含全部k-mer。如对序列S来说，所有5-mer为｛CTGTA，TGTAC，GTACT，TACTG，ACTGT，TGTAT｝通常这些k-mer需一种数据索引方法，可被后面的操作快速访问。例如，对5-mer来说，当查询CTGTA，通过这种数据索引方法，可返回其在DNA序列S中的位置为｛1，6｝。1.2问题现在以文件形式给定100万个DNA序列，序列编号为1-1000000，每个基因序列长度为100。（1）要求对给定k，给出并实现一种数据索引方法，可返回任意一个k-mer所在的DNA序列编号

5、和相应序列中出现的位置。每次建立索引，只需支持一个k值即可，不需要支持全部k值。（2）要求索引一旦建立，查询速度尽量快，所用内存尽量小。（3）给出建立索引所用的计算复杂度，和空间复杂度分析。（4）给出使用索引查询的计算复杂度，和空间复杂度分析。（5）假设内存限制为8G，分析所设计索引方法所能支持的最大k值和相应数据查询效率。（6）按重要性由高到低排列，将依据以下几点，来评价索引方法性能·索引查询速度·索引内存使用·8G内存下，所能支持的k值范围·建立索引时间二、问题分析在生物技术快速发展的今天，人类分析人类自身编码的需

6、求也越来越高，人们利用计算机来处理分析大量DNA序列，k-mer快速查找也是处理大量数据的问题，所以必须依赖数据结构原理，建立模型构造算法，从而利用有限的资源解决复杂问题。针对问题一：按照给定k值，将所有数据按题目要求分组，求出每组数据的关键码值，并将关键码值与此组k-mer所在位置建立对应关系并存储到表中，从而建立哈希表。针对问题二：将要查找的k-mer序列求出其关键码值，直接输出其关键码值在表中对应位置信息，大大加快了索引查询速度。针对问题三：详见四-（二）-2，3。针对问题四：详见四-（三）-2，3。针对问题五：

7、根据k值大小动态分配内存建立哈希表，最终实现k支持1~14的范围，因为直接关键码值寻址输出，所以索引查询速度非常快。针对问题六：按照重要性首先考虑索引查询速度，其次动态内存分配尽量减少索引对内存的消耗，在8G内存限制下，使k值支持1~14，最后优化添加计数器记录已经存在地址的k-mer个数，倘若达到所有k-mer种类数，则停止建立索引，索引成功建立。三、符号说明符号符号说明H(x)关键码值生成函数，其中x代表一个k-mer代表A，T，C，G中的任意一个与Ci相对应的四进制数k一个k-mer的长度M内存空间占用（单位：G

8、B）四、算法设计思路及性能分析（代码见附录一）(一)哈希表设计：1、k-mer关键码值生成函数H(x)由于DNA序列由4个字母排列而成，所以每个k-mer都是一个四进制数，H(x)函数根据这个特征将四进制数转为十进制数作为哈希表关键码值。x=“CTGTA”如上图为每个字母代表的四进制数字，例如一个5-mer“CTGTA”可以表示为