内容2015杯优秀学生

...........................................................................................................................1一、问题重 二、问题分 三、模型假 四、符号说 五、模型建 、问题分 、索引算法模 、给出哈希表相关定 、基本步 、查找算法模 、KMP字符串匹配相关概 、主要步骤示例 、数据分析与算法模型优 、每一种K-mer出现次数分 、每类K-mer的平均数组长度分析 、算法模型优 、算法模型流程 六、模型求 、建立索引表的复杂度分 、时间复杂 、空间复杂 、使用索引查询的复杂度分 、时间复杂 、空间复杂 、理论内存占用分 、模型实际效 、查询时 、支持k值范 、建立索引表的时 七、模型的比较与评 、模型的比 、字典树介 、顺序查 、模型的评 、本模型优 、本模型缺 八、参考文 附 DNA序列的k-mne找确定具体行号和位置号。当k临界值(10)KMPO(1)。最后，用VisualStudio2013进行c语言编程，将算法模型进行了实际检此模型组合了哈希表与KMP算法，相比于字典树、普通哈希表、顺序查找等方一、问题列的k-mer便是一种在生物研究中广泛应用的生物信息。现给出100万条DNA序列，每条序列由100个碱基（有四种类型：A、T、G、C）组合而对这些DNA序列的k-mer制定一种数据索引方法，使得可以在后面的操作中快速查找出某个k-mer在数据中的具置（行号和位置号。要求对给定k，给出并实现一种数据索引方法，可返回任意一个k-mer所在的DNA序列编号和相应序列中出现的位置。每次建立索引，只需支持一个k值即可，不需要支持全部k值。8G，k间二、问题依据题目要求，需要对给定的k建立索引，并且在建立之后能对目标k-mer快存占用和建立索引时间，以及支持的k的范围。为了满足查询速度快的要求，考虑建立哈希索引表，采用哈希查找与KMP匹配算法相结合的方式使得算法可以兼顾内存占用小与查询速度快。随后以k三、模型四、符号

五、模型希表索引算法模型。采取KMP匹配算法来寻找具体的位置。哈希表是根据关键码值(Keyvalue)而直接进行的数据结构。也就是说，射函数叫做哈希函数。在本题中，关键码就是每个k-mer。f(A)=00，f(C)=01，f(G)=10，f(T)= 这样对于每一个k-mer，都有唯一的一组长度为2k位的二进制数与其对应。 ； （B）.建立寻址方法编号为从到，每一个k-mer序列S，将其行号存于表头编号为f（S）后面的链表中。、KMP字符串匹配相关，先从S[0]与T[0]S[0T[0]，则比较S[1]与T[1S[5]不等于T[5]后，并不从头再寻找，由于面的比较中，已经保留了S与T匹配成功位置上的信息，发现T[0]T[1T[3]T[4]=S[3]S[4]T接比较T[2]与S[5]，如图3所示。从而快速匹配成功。，图 KMP算法的第二趟匹配过而常规的匹配算法只会将T后错一位，将T[0]与S[1]进行比较。这使得以及的T的信息没有利用起来。而KMP弥补了这一点，高效地利用信息从而达到、每一种K-mer出现次数分对于给定k值k个碱基能k-mer种类为4𝑘。对于一百万条长度均为100的DNA来讲，假设每个k-mer不一样，实际上出现的种类最多1000000×(101− 设f(k)=4𝑘 ×(101− 210-

8x 4f(k)如图3所示，当k大于13以后，4𝑘≫ ×(101−k),也就是说，此时实际上出现的k-mer序列的种类远远小于理论上的种类，如果对k大于13建立哈希表的话将会出现有很多表头后面链表长度为0的情（因为有些k-mer种类，、每类K-merL(k)= (k≤4) ×(101−L(k) (k> 5x9876543210 图5L(k)表 k取不同值时L(k)的大k8951通过对程序的实际30万条DNA建表后k=10时测试的链表长度大20-35100DNA，链表长度大约为90由此可见，当k过大时，链表长度过短，索引表过于稀疏，造成浪费，当k过1k1010①当k<10时，直接建立4𝑘个表头的哈希表查找时，（待查找的k-mer到关键码为f（M）的链表中提取行号，再用KMP算法到该行查找M出现的具的前10位即M1进行，到关键码为f（M1）的数组中提取行号，再到每个可能的行里用KMP算法匹配查找S并输出具置（由于k大于10后，每个链表长度大概为80，查找并不会耗费太多时间。6 M，计算7否8六、模型T(n)= 由于k取值为多少，哈希表消耗的内存都是较为固定的常值（后面的内S(n)= 已知主字符串为S，待匹配的字符串串T，由于KMP算法的思想是主串不回溯的简化算法，匹配的时候只会将T不断右移进行比较，所以字符比较最多的情况就是遍历S中所有的元素，则时间复杂度为O（LenthS）,即KMP算法的时间复杂度为O（n。对于本模型来讲，查找DNA长度固定100则比较次数平均为100*80次，与k的选取以及总数据量无直接关系，所以查询位置号的时间复杂度为O(1)。哈希表是通过计算关键码值（待查找k-mer对应的哈希函数值）来定位元素位置，所以只需一次即可，复杂度为O(1)。T(n)=O(1)+O(1)= 𝑆1(n)= 为O（lenthT）.对于本模型来讲，长度为常值，所以空间复杂度为:𝑆2(𝑛)= S(n)=O(1)+O(1)= 90，链表的每一个节点占用8B（8）内存，。则：理论总占用内存=4^10×908B=运行环境为windows764位操作系统下，CPU为InCorei3处理器。k=7的查询时间为0.68s。k=10的查询时间为0.000sk=230.00000sk2-100k=5耗时11.46s建立索引。 k=21，耗时17.96秒建立索引小于18s。

9若扫描结束后，仍未找到关键字等于K的结点，则查找失败2k（本文模型建表时间查询时间建表时间查询时间消耗内存查询时间消耗内存307000000000500O（n）查找时间复杂度、查找空间复杂度均为O(1)。并在实际检验中有很好的八、参考[1]谢金星.数学模型[M].4.：高等教育, .数据结 ,附k-merIndex4.cpp源程支持单进程8G内存#include"stdafx.h"#defineFILEPATH"newfile.dat"#defineSEQLEN100#defineSEQCOUNT#defineINDEXMAX_K10charSequenceString[SEQCOUNT][SEQLEN+1];//所有的母序intChildSeqCount;//根据kcharChildString[SEQLEN1]'\0'structNode//{Node*next;struct{Node*end;//标志链表尾部unsignedintStringToNum(charstringintk);//将子串转化为其对应的数字voidGet_next(charT[],intk,intnext[]);intIndex_KMP(charScharT[],intk,intpos);//k为k-merintInsertNode(TableHead*Head,intsequence,unsignedintnum);//往索引表TableHead*BuildTable(intk);//建立索引表，返回值为表头，k为k-mer值voidDestroyLink(TableHead*LinkheadTableHead*Intersection(Node*LinkHead1,Node*LinkHead2);//求两个子序列都位voidSearch(TableHead*Head,intk,charstring[]);//查找子序列所在母序列的voidSearchSolution_1(TableHead*Head,charstring[],intk);//当k>=10时，选//voidSearchSolution_2(TableHead*Head,charstring[],intk);//当k>=20时，voidSearchSolution_2(TableHead*Headcharstring[],intk);//当k小于10int{clock_tstart,finish;doubleduration;start=clock();finish=clock();duration=(double)(finish-start)/CLOCKS_PER_SEC;TableHead*Head;intk;start=clock();if(k>=10) Head=BuildTable(INDEXMAX_K);Head=BuildTable(k);finish=clock();duration=(double)(finish-start)/charstring[SEQLEN+1];scanf_s("%s",string,_countof(string));while(strlen(string)!=k){scanf_s("%s",string,}start=clock();Search(Head,k,string);finish=clock();duration(double)(finishstart)CLOCKS_PER_SEC;printf("查找用时%fseconds\n",duration);return}void{FILE*if(fopen_s(&fp,FILEPATH,"rb")!={printf("can'topenthefile\n");}for(inti=1;i ;{fread(SequenceString[i-1],sizeof(char),SEQLEN,fp);SequenceString[i-1][SEQLEN]='\0';if(!feof(fp))}}unsignedintStringToNum(charstring[],int{unsignedintnum=0;for(inti=0;i<k;i++){num=num<<2;{case'A':num+=0;break;case'C':num+=1;break;case'G':num+=2;break;case'T':num+=3;break;}}return}intInsertNode(TableHead*Head,intsequence,unsignedint{Node*node;//=(Node*)malloc(sizeof(Node));if(!(node=(Node*)malloc(sizeof(Node)))){printf("结点生成失败，此时母序列为%d\n",}1node->next=NULL;TableHead*p=Head+num;if(p->head==NULL){p->headp->endnode;return1;}{if((sequence+1)p->end->sequence)//倘若该子序列所在的母序列已经{p->end->next=node;p->end=node;return1;}{}}}TableHead*BuildTable(int{TableHead*ChildSeqCount=(int)pow(4.0,if(!(Head={}for(inti0;iChildSeqCount;i+{(Headi)->headHeadi)->endNULL;(Head+i)->count=0;//测试语句}intposition0;intcount0;//测试用，测试完要删除FILE*fp;if(fopen_s(&fp,"D:\\Bakup\\桌面\\校内选拔赛题目\\B题附件\\myfile.txt","w")!=0)//测试用{}for(inti=0;i<SEQCOUNT;//for(inti=0;i<{count0;/for(position1;positionSEQLENk1position++)//将每一个{for(intj=0;j<k;ChildString[j]=SequenceString[i][position+j-ChildString[k]= num=StringToNum(ChildString,改}}return}voidDestroyLink(TableHead*{Node*p=Linkhead->head;Node*temp=NULL;Linkhead->head=Linkhead->end=NULL;while(p){temp=p=p-}}voidGet_next(charT[intk,intnext[])//T的长度为{inti=0;next[0]=-1;intj=-1;while(i<k-{if(j==-1||T[i]=={i++;next[i]=}j=}}intIndex_KMP(charScharT[],intk,intpos)//k为k-mer{//intnext[2*INDEXMAX_K];intnext[SEQLEN];Get_next(T,k,next);inti=pos-1,j=while(i<=SEQLEN-1&&j<=k-{if(j==-1||S[i]=={i++;}j=}if(j>=returni+1-k;return0;//无子串T则返回}TableHead*Intersection(TableHead*LinkHead1,TableHead*{Node*p1=LinkHead1->head;Node*p2=LinkHead2->head;TableHead*intersection=(TableHead*)malloc(sizeof(TableHead));intersection->head=intersection->end=NULL;Node*node=NULL;while(p1&&p2){if(p1->sequence==p2-{if(!(nodeNode*)malloc(sizeof(Node{}node->sequence=p1->sequence;node->next=NULL;if(intersection->head==intersection->head=intersection->end=node;{intersection->end->next=node;intersection->end=node;}}elseif(p1->sequence>p2->sequence)p2=p2->next;p1=p1-}return}voidSearchSolution_1(TableHead*Head,charstring[],int{//chartemp[INDEXMAX_K+1]={'\0'};chartemp[SEQLEN+1]={'\0'};for(inti=0;i<INDEXMAX_K;i++)temp[i]=string[i];unsignedintnum=StringToNum(temp,Node*p=(Head+num)->head;intsequence;{sequence=p->sequence;intpos=1;while(pos>=1&&pos<=SEQLEN-k+{posIndex_KMP(SequenceString[sequence1],string,k,pos);if(pos)//当pos不为0时，表示有子串{printf("存在于第%d个DNA序列，位置为%d\n",sequence,pos);} }p=p-}}voidSearchSolution_2(TableHead*Head,charstring[],int{unsignedintnum=StringToNum(string,k);Node*p=(Head+num)->head;intpos;while(p){sequence=p->sequence;pos=1;while(pos>=1&&pos<=SEQLEN-k+{posIndex_KMP(SequenceString[sequence1],string,k,pos);if(pos)//当pos不为0时，表示有子串{printf("存在于第%d个DNA序列，位置为%d\nsequence,pos);} }p=p-}}voidSearch(TableHead*Head,intk,charstring[])//支持的k值都大于等于{//if(k>=10&&k<20)if(k>=10)SearchSolution_1(Head,string,//SearchSolution_2(Head,string,k);SearchSolution_2(Head,string,}字典树源程序（CodeBlocks软件）#include<bits/stdc++.h>#include<windows.h>usingnamespacestd;constintSTR_LEN=105;typedefpair<int,int>position;pii.first/SeqIndexpii.second/posInSeq为相应序列中出现的位置charCHAR_SET[]=inlineintidx(constchar&c)for(inti=0;CHAR_SET[i];i++)if(c==CHAR_SET[i])returni;return-1;}struct{TrieNode*nxt[4];TrieNode(){for(inti=0;i<4;i++)nxt[i]=}voidadd(constint&SeqIndex,constint{posList.push_back(SeqIndex*1000+posInSeq-'

voidshow()for(unsignedi=0;i<posList.size();i++)cout<<posList[i]/1000<<','<<posList[i]%1000+1}cout<<}struct{intTrieNodeKmerTrie()root=new}voidinsert(constchar*str,constint{for(inti=0;i+k<=100;i++){insert(str+i,SeqIndex,i+1);}}voidinsert(constchar*substr,constint&SeqIndex,constint&posInSeq){TrieNode*target=findNode(substr,true);target->add(SeqIndex,posInSeq);}TrieNode*query(constchar{returnfindNode(str,}TrieNode*findNode(constchar*str,constbool{TrieNode*now=root;for(inti=0;i<k;i++)if(now->nxt[idx(str[i])]=={if(!create)returnnewTrieNode();now->nxt[idx(str[i])]=newTrieNode();}now=now-}return}KmerTriekmer;voidreadAndInsert()cin>>kmer.k;DWORDt_begin,t_end;t_begin=