2015年深圳杯b题-dna 序列的k-mer index 问题

《2015年深圳杯b题-dna 序列的k-mer index 问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、封一答卷编号（参赛学校填写）：答卷编号（竞赛组委会填写）：论文题目：B题组别：本科生　参赛队员信息(必填)：姓名年级专业学号联系电话参赛队员114机制二班参赛队员214机制二班参赛队员314机制二班指导教师：____参赛学校：沈阳农业大学封二答卷编号（参赛学校填写）：答卷编号（竞赛组委会填写）：评阅情况（学校评阅专家填写）：学校评阅1.学校评阅2.学校评阅3____评阅情况（联赛评阅专家填写）：联赛评阅1.联赛评阅2.联赛评阅3.DNA序列的k-merindex问题摘要：随着生物技术和计算机技术交叉，合作的范围不断地扩大，深度不断地加深，字符串匹配在生物科

2、学的信息检索领域有着广泛的应用，生物研究对DNA序列的碱基信息快速搜索的要求也与日俱增，DNA序列的k-merindex问题研究日益突出。本文在查阅了相关文献资料后，基于“数据结构”中的“Sunday算法[7]”，我们给出了一种函数覆盖优化Sunday算法，对DNA序列的k-merindex问题中给出固定值k，进行碱基片段查找。函数覆盖优化Sunday算法对所给出的大量数据的碱基序列先运用函数覆盖，同时把DNA序列进行分组预处理。当数据链接时用函数覆盖，将整个DNA序列数据划分成若干个小的区域，然后再针对若干个小区域进行碱基片段的匹配。在划分小区域时，首先

3、将每个小区域的末端多划分四个属于下个区域的碱基，其次在匹配的过程中需要按给定k值对小区域进行分组，之后再用算法对碱基片段进行匹配，最后再统计所有小区域与所要查找的碱基片段的匹配信息。匹配时经过优化后的算法能够实现同时对划分的所有区域进行查找，直到与所有DNA序列都进行了匹配。当匹配成功时，首先会自动将char*格式强制转换成void*格式，然后通过DNA碱基片段中第一个字符的指针访问DNA序列，最后输出DNA碱基片段中第一个字符的（常量）地址。　　函数覆盖优化Sunday算法后的主要特点：查找速度简洁、高效、执行速度快。函数覆盖优化Sunday算法，因为快

4、速跳跃匹配和多区域同步搜索的特征使它可以快速的生成数据和信息。实现了对DNA序列数据库的查找，在DNA序列中可以得到固定k长度的碱基片段的位置。关键词：Sunday算法，函数覆盖，字符串匹配，碱基序列，数据库。第21页1问题重述　　给定一个DNA序列，这个系列只含有4个字母ATCG，如S=“CTGTACTGTAT”。给定一个整数值k，从S的第一个位置开始，取一连续k个字母的短串，称之为k-mer（如k=5，则此短串为CTGTA），然后从S的第二个位置，取另一k-mer（如k=5，则此短串为TGTAC），这样直至S的末端，就得一个集合，包含全部k-mer。如

5、对序列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值。　（

6、2）要求索引一旦建立，查询速度尽量快，所用内存尽量小。　（3）给出建立索引所用的计算复杂度，和空间复杂度分析。　（4）给出使用索引查询的计算复杂度，和空间复杂度分析。　（5）假设内存限制为8G，分析所设计索引方法所能支持的最大k值和相应数据查询效率。　（6）评价索引方法性能。包括：索引查询速度，索引内存使用，8G内存下，所能支持的k值范围，建立索引时间。2符号说明iostream类(文件输入流和输出流类)[2]a：构造方法：#include创建文件输入流类对象和已存在的文件相关联。文件不存在的话，并创建。如：#include

7、eam>(C:UsersdengxinDesktopDNA)；b：#include　创建文件输出流类对象和已存在的文件相关联，并设置该该流对文件的操作是否为续写。　　如：#include(C:UsersdengxinDesktopDNA，at+)；c:表示在#include对文件再次写入时，会在该文件的结尾续写，并不会覆盖掉。主要方法：#include写入字符串。当执行完此方法后，字符数据还并没有写入到目的文件中去。此时字符数据会保存在缓冲区中。此时在使用memcp

8、y函数就可以使数据将目标数组地址增加到要追加数据的地址，从而保存到