2015年深圳杯B题DNA序列论文要点分析.doc

封一 答卷编号（参赛学校填写）： 答卷编号（竞赛组委会填写）： 论文题目： 组 别： 参赛队员信息(必填)： 姓 名 年级专业 学 号 联系电话 参赛队员1 邓鑫 参赛队员2 14机制二班 参赛队员3 14机制二班 指导教师：_____ 参赛学校：  封二 答卷编号（参赛学校填写）： 答卷编号（竞赛组委会填写）： 评阅情况（学校评阅专家填写）： 学校评阅1. 学校评阅2. 学校评阅3___ _ 评阅情况（联赛评阅专家填写）： 联赛评阅1. 联赛评阅2. 联赛评阅31问题重述 　　给定一个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符号说明 iostream类(文件输入流和输出流类)[2] a：构造方法： #includeifstream 创建文件输入流类对象和已存在的文件相关联。文件不存在的话，并创建。 如：#includeifstream(C:\Users\dengxin\Desktop\DNA)； b：#includeofstream 　创建文件输出流类对象和已存在的文件相关联，并设置该该流对文件的操 作是否为续写。 　　如：#includeifstream(C:\Users\dengxin\Desktop\DNA，at+)； c: 表示在 #includeifstream 对文件再次写入时，会在该文件的结尾续写，并不会覆盖掉。主要方法：#includestring写入字符串。 当执行完此方法后，字符数据还并没有写入到目的文件中去。此时字符数据会保存在缓冲区中。此时在使用memcpy函数就可以使数据将目标数组地址增加到要追加数据的地址，从而保存到目的文件中去。 d:　定义函数：void exit(int status) 　　exit()用来正常终结目前进程的执行， 并把参数status 返回给父进程， 而进程所有的缓冲区数据会自动写回并关闭未关闭的文件.。在关闭后，再写入或者刷新 的话，会显示EOF异常。 字符串读写函数 a：定义一个头文件，此文件是输入类对象，头文件是关联于源文件。 #includestdio.h= #includeifstream b：主要方法 读字符函数fgets(字符数组名，n，文件指针)； 其中的n是一个正整数。表示从文件中读出的字符串不超过 n-1个字符。在读入的最后一个字符后加上串结束标志\0。 例如：fgets(str，n，fp)；的意义是从fp所指的文件中读出n-1个字符送入字符数组str中。 写字符函数fputc(字符量， 文件指针 )； fputc函数的功能是把一个字符写入指定的文件中。其中，待写入的字符量可以是字符常量或变量。 例如：fputc(a，fp)；其意义是把字符a写入fp所指向的文件中。 exit()用来正常终结目前进程的执行， 释放与之关联的所有资源。 数据块读写函数fread和fwrite；