2015年深圳杯“数学建模”B题.pdf

2015年吉林省大学生数学建模竞赛 承 诺 书 我们仔细阅读了 《全国大学生数学建模竞赛章程》和 《全国大学生数学建模 竞赛参赛规则》（以下简称为 竞赛章程和参赛规则”，可从全国大学生数学建 模竞赛网站下载）。 我们完全明白，在竞赛开始后参赛队员不能以任何方式 （包括电话、电子邮 件、网上咨询等）与队外的任何人 （包括指导教师）研究、讨论与赛题有关的问 题。 我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的 成果或其他公开的资料 （包括网上查到的资料），必须按照规定的参考文献的表 述方式在正文引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。 如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。 我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行 公开展示 （包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表 等）。 我们参赛选择的题号是（从A/B/C/D/E 中选择一项填写）： B 8 我们的报名参赛队号为（ 位数字组成的编号）： 所属学校（请填写完整的全名）： 长春工业大学 参赛队员 (打印并签名) ： 1.张晓丽 2.张 慧 3.余森瑾 指导教师或指导教师组负责人 (打印并签名)： （论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。以 上内容请仔细核对，提交后将不再允许做任何修改。如填写错误，论文可能被取 消评奖资格。） 日期： 年 月 日 赛区评阅编号（由赛区组委会评阅前进行编号）： 2015年吉林省大学生数学建模竞赛 编 号 专 用 页 赛区评阅编号（由赛区组委会评阅前进行编号）： 赛区评阅记录（可供赛区评阅时使用）： 评 阅 人 评 分 备 注 DNA序列的k-mer index 问题 摘 要 本研究在查阅了大量文献资料后，基于 数据结构”中的 哈希算法”我们 给出了一种用进制转化的方法来抽出这个问题的本质。对DNA序列的k-mer index问题来实现固定给出k 的值对碱基片段查找的解决方法。 哈希算法的主要特点：查找速度快捷、直接、简单。对所给的大量数据的 碱基序列先运用其碱基种类较少的特点将其赋予特定的值，然后在100万行碱基 序列中以单向数学函数 （哈希函数）的方法对碱基序列进行地址映射，就得到了 一个有序的碱基片段的地址存储单元，对这个有序列进行按位查找。 对问题进行分析：要求对给定k， 给出并实现一种数据索引方法，可返回 任意一个k-mer所在的DNA序列编号和相应位置，所给序列中的碱基种类只 有 A,C,G,T 四种，根据哈希算法【3】进制转换的思想，令碱基 A-0， C-1，G-2，T-3，从而 k-mer 可以看成一个四进制的序列数，根 据四进制对十进制的转化方法可得到一个十进制数,当取定一个 k 的值时，在每一行的长度为 100 的碱基序列中，可得到 100-k+1 个 十进制数，将输入的特定的 k 个碱基片段在 100 万行中以十进制的 形式进行匹配，程序会输出碱基片段所在的行标，列标。 正是哈希的这种单向特征和数据长度固定的特征是的它可以生成数据和消 息。根据它的原理来实现了对大数据的查找，在结果中可以得到该k长度的碱基 片段在100万行序列中的相应行数和位置。 关键词：哈希算法，单向数学函数，碱基序列，地址映射，大数据。 1 第 页 一、 问题重述 给定一个DNA序列，这个系列只含有