文档介绍：该【dna序列的k-merindex问题数模毕业论文 】是由【1875892****】上传分享，文档一共【20】页，该文档可以免费在线阅读，需要了解更多关于【dna序列的k-merindex问题数模毕业论文 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第2页,共1页重庆交通大学2015年第八届数学建模竞赛参赛论文论文选题:B题学生姓名学号所在学院联系电话:1E-mail地址:0DNA序列的k-merindex问题摘要本小组在查阅了相关文献资料后,基于“数据结构”中的“哈希算法[2][6]”、“倒排索引[1][2]”法及“BKDRHash算法[2]”,建立相应的数学模型,给出分析和结果,对DNA序列的k-merindex问题给出解决方案。本模型对不同k值采用不同算法建立索引。当k值较小时,利用基因序列其碱基种类较少(仅A,T,G,C四种)的特点,根据哈希算法进制转换的思想,可将k-mer看成一个四进制的序列数,将其转化为十进制数作为哈希表的关键字[2],并采用倒排索引的方法对哈希表关键字分类整理,建立相应的地址存储单元,实现索引;当k值较大时,考虑到内存溢出[6]的问题,采用“BKDRHash算法”对k-mer进行十进制转化,并结合“倒排索引[2]”法建立索引,从而对给定的k-mer片段进行精确查找,最终输出碱基片段所在位置。此方案将“哈希(Hash)算法”、“BKDRHash算法”和“倒排索引法”相结合,对哈希算法结构进行优化,提升了运算效率,操作简洁、高效。实现了在基因数据库[3][4]中对给定的碱基片段的位置进行查找的目的。关键词:倒排索引,哈希(Hash)算法,BKDRHash算法,碱基序列,基因数据库。第2页,-merindex问题给定一个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页,:把记录分成sumFile个文件存放sumK-mer1:K-mer的总个数sumK-mer2:K-mer可能出现的不重复的个数maxY:每个文件的最大行数maxX:平均每行字符数fileName:文件名fileNumber;文件编号,范围是0-sumFile-1hashKey1:将K_mer转化后的哈希关键字,是一个十进制整数position:记录K-mer所在的DNA序列及在每个序列中的位置HZJS:文件里平均每行的字符数&&:表示连接,如A&&,,其中每行序列的长度为100,给定一个固定的k值,则每行序列有(100-k+1)个k-mer,K-mer总数有1000000*(100-k+1)个。数据量级达到百万至千万,十分庞大,故考虑采用建立哈希表的方法实现索引。碱基序列由A、T、C、G四种碱基无序组合,当给定K值后,理论有种k-mer。比较1000000*(100-k+1)(实际值)和(理论值)的大小:当K小于等于13时,1000000*(100-k+1)>,即K_mer值会出现重复,K越接近1,重复的越多;当K大于13时,理论上不会出现重复值。第2页,,即,则实际上出现的k-mer的个数多于理论上可能出现的k-mer的个数,即K-mer有重复。此时k较小,以“哈希算法”和“倒排索引”相结合的方法建立索引。因为k-mer由四种碱基构成,根据进制转换思想[1],将K-mer化为四进制再换算为十进制作为哈希表的关键字。现令碱基A->0,T->1,G->2,C->3,从而这四个碱基可以看成一个四进制的序列数,分别将A,T,G,C赋值0,1,2,3,可以根据四进制对十进制的转化方法(四进制化为十进制的方法为:假设取定一个序列TCAGC,则以四进制13023表示,化为十进制:1*4^4+3*4^3+0*4^2+2*4^1+3*4^0=468)可以得到用十进制数表示的碱基序列(即468可以表示序列TCAGC,为一个哈希关键字)。采用倒排索引的方法对碱基序列进行分类整理:由于碱基序列号的最大值为1000000*(101-K),将整数以字符形式保存,最大占用7个字符,每行的K-mer序列最大值为101-K,最大占用3个字符,即每个记录最大占位11个字符,假定一个字符占用一个字节,则索引记录共计大小为1000000*(101-K)*11*1个字节,即11*(101-K)M的字节大小。考虑索引记录保存在一个文件中,会导致文件太大,不利于索引操作,故将记录保存到1000个文件中。将哈希关键字除1000取余,余数有0,1,2...999,共1000种,将余数作为文件编号fileNumber,文件名用fileNumber&&‘.tet’来表示;商作为记录在每个文件里面的唯一编号即行号Y,同时采用哈希表记录属性的位置,因此在保存记录时将不记录属性值,属性记录采用“碱基序列号&&每行的K-mer序列”的格式记录K_mer的位置;将记录保存在文件中。第2页,共1页4当K_mer出现重复时,按其出现的先后顺序依次放在同一行。另外,当k<5时,<1000,此时将记录保存到个文件中,较节约内存,其它过程同上。当K值比较大时,如K取100,根据此种方法算出的哈希值,计算机将无法表示,内存溢出,这种情况参考下述方法。,此时1000000*(101-k)<4^k,则实际上出现的K-mer个数少于理论上可能出现的k-mer个数,理论上k-mer序列不会出现重复,但考虑随机事件及内存溢出的问题,采用BKDRHash算法,计算k-mer的哈希值,作为哈希关键字。用“碱基序列号&&每行的K-mer序列&&k-mer”的格式记录位置信息,其它过程同上。,按照上面的方法即可确定对应的存储位置,到相应文件直接读出那一行数据即可;但当k的取值大于13,需对取出的数据进行筛选,选出正确的k-mer位置。第2页,[5]开始输入k值,建立索引输入k-mer,检索是否存在输出“无该k-mer值”输出位置结束 NY第2页,(流程图)将数据写入文件并清除内存文件读取完毕,将最后一份数据写入文件索引创建完成开始输入k判断是否达到内存上限按行读取文件,将每行的k-mer取出后存入内存初始化文件,内存上限YN第2页,,程序显示正在读取数据文件的函数第2页,[1][6]索引的时间复杂为:O(n)索引时,需要将待查序列的十进制数值与所有的k-mer的十进制数进行比较,所以时间复杂度为:O(n)-mer;该模型在建立索引上方法不同,K大于13时,需要筛选重复值,效率比K<<13时,1秒内可以出结果;K>13时,时间稍长,[2]索引时只需要一个两个int型变量,,所能支持的k值范围1-100第2页,共1页