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

此文档属于DNA索引类。

2015年吉林省大学生数学建模竞赛

承诺书

我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。

我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。

我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。

我们参赛选择的题号是（从A/B/C/D/E中选择一项填写）：B我们的报名参赛队号为（8位数字组成的编号）：所属学校（请填写完整的全名）：参赛队员(打印并签名)：1.2.指导教师或指导教师组负责人

(打印并签名)：3.（论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。以上内容请仔细核对，提交后将不再允许做任何修改。如填写错误，论文可能被取消评奖资格。）

日期：

年

月

日

此文档属于DNA索引类。

赛区评阅编号（由赛区组委会评阅前进行编号）：2015年吉林省大学生数学建模竞赛

编号专用页

赛区评阅编号（由赛区组委会评阅前进行编号）：

赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注

此文档属于DNA索引类。

DNA序列的k-merindex问题

摘

要

本研究在查阅了大量文献资料后，基于“数据结构”中的“哈希算法”我们给出了一种用进制转化的方法来抽出这个问题的本质。对DNA序列的k-merindex问题来实现固定给出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万行序列中的相应行数和位置。

关键词：哈希算法，单向数学函数，碱基序列，地址映射，大数据。

此文档属于DNA索引类。

一、问题重述

给定一个DNA序列，这个系列只含有4个字母ATCG，如S=“CTGTACTGTAT”。

给定一个整数值k，从S的第一个位置开始，取一连续k个字母的短串，称之为

k-mer（如k=5，则此短串为CTGTA），然后从S的第二个位置，取另一k-mer

（如k=5，则此短串为TGTAC），这样直至S的末端，就得一个集合，包含全部

k-mer。如对序列S来说，所有5-mer为

｛CTGTA，TGTAC，GTACT，TACTG，ACTGT，TGTAT｝

通常这些k-mer需一种数据索引方法，可被后面的操作快速访问。例如，对5-mer来说，当查询CTGTA，通过这种数据索引方法，可返回其在DNA序列S中的位置为｛1，6｝。解决以下问题：

现在以文件形式给定100万个DNA序列，序列编号为1-1000000，每个基因序列长度为100。

（1）要求对给定k，给出并实现一种数据索引方法，可返回任意一个k-mer所在的DNA序列编号和相应序列中出现的位置。每次建立索引，只需支持一个k值即可，不需要支持全部k值。

（2）要求索引一旦建立，查询速度尽量快，所用内存尽量小。（3）给出建立索引所用的计算复杂度，和空间复杂度分析。（4）给出使用索引查询的计算复杂度，和空间复杂度分析。

（5）假设内存限制为8G，分析所设计索引方法所能支持的最大k值和相应数据查询效率。

（6）评价索引方法性能。包括：索引查询速度，索引内存使用，8G内存下，所能支持的k值范围，建立索引时间。

二、算法分析

2.1首先根据题目所给的文件中有100万行的碱基序列，【2】其

中每行序列的长度为100，我们用二维数组a[1000000][100]存储所给的碱基序列，每行代表100个碱基序列，列代表序列的编号，我

此文档属于DNA索引类。

们要做的就是取定一个固定的k值，将每行序列分成100-k+1个长度为k的序列，查询某序列在所给碱基序列中的编号和位置。2.2

由于所给序列中的碱基种类只有A,C,G,T四种，根据哈希算法

进制转换的思想，现在令碱基【4】

A->0，C->1，G->2，T->3，

从而这四个碱基可以看成一个四进制的序列数，分别将A,C,G,T赋值0，1，2，3，我们可以根据四进制对十进制的转化方法（四进制化为十进制的方法为：假设取定一个序列ACTG，则

ACTG=0*4^3+1*4^2+3*4^1+2*4^0=30）就可以得到一个十进制数表示的碱基序列（30可以表示序列ACTG）。当取定一个k的值时，在每一行的长度为100的碱基序列中，可以按k-mer【1】的方法得到100-k+1（100为每行的长度，k为取定的值）个十进制的数，如此100万行的碱基全转化为十进制的数，每行100-k+1个。

2.3将输入的特定的k个碱基片段在100万行中以十进制的形式进行匹配。

2.4每当匹配到相同的十进制的数时，程序会对这个数进行回溯，即将它转化为四进制的长度为k的字符串ACGT的形式，（当然在这个过程中会得到重复的碱基片段都与多要查找的片段相同，在下面我们会进行分析和解决。）程序会输出碱基片段所在的行标，列标。

三、变量说明

FileWriter类(字符输出流类)【6】

此文档属于DNA索引类。

a:构造方法：FileWriterfw=newFileWriter(StringfileName);

创建字符输出流类对象和已存在的文件相关联。文件不存在的话，并创建。如：FileWriterfw=newFileWriter("F:\\middledata.txt");b:

FileWriterfw=newFileWriter(StringfileName,booleanappend);创建字符输出流类对象和已存在的文件相关联,并设置该该流对文件的操作是否为续写。

如：FileWriterfw=newFileWriter("F:\\middledata.txt",ture);c:表示在fw对文件再次写入时，会在该文件的结尾续写，并不会覆盖掉。主要方法：voidwrite(Stringstr)

写入字符串。当执行完此方法后，字符数据还并没有写入到目的文件中去。此时字符数据会保存在缓冲区中。此时在使用刷新方法就可以使数据保存到目的文件中去。d:

viod …… 此处隐藏：2999字，全部文档内容请下载后查看。喜欢就下载吧 ……