一、問題重 二、問題分 三、模型假 四、符號(hào)說 五、模型建 、問題分 、索引算法模 、給出哈希表相關(guān)定 、基本步 、查找算法模 、KMP字符串匹配相關(guān)概 、主要步驟示例 、數(shù)據(jù)分析與算法模型優(yōu) 、每一種K-mer出現(xiàn)次數(shù)分 、每類K-mer的平均數(shù)組長(zhǎng)度分析 、算法模型優(yōu) 、算法模型流程 六、模型求 、建立索引表的復(fù)雜度分 、時(shí)間復(fù)雜 、空間復(fù)雜 、使用索引查詢的復(fù)雜度分 、時(shí)間復(fù)雜 、空間復(fù)雜 、理論內(nèi)存占用分 、模型實(shí)際效 、查詢時(shí) 、支持k值范 、建立索引表的時(shí) 七、模型的比較與評(píng) 、模型的比 、字典樹介 、順序查 、各種算法模型與本模型的比 、模型的評(píng) 、本模型優(yōu) 、本模型缺 八、參考文 附 DNAk-mix找確定具體行號(hào)和位置號(hào)。當(dāng)k臨界值(10)KMPO(1)。列的k-mer便是一種在生物研究中廣泛應(yīng)用的生物信息。面的操作中快速查找出某個(gè)k-mer在數(shù)據(jù)中的具置（行號(hào)和位置號(hào)。要求對(duì)給定k，給出并實(shí)現(xiàn)一種數(shù)據(jù)索引方法，可返回任意一個(gè)k-mer個(gè)k值即可，不需要支持全部k值。間內(nèi)存占用和建立索引時(shí)間，以及支持的k的范圍。為了滿足查詢速度快的要求，考慮建立哈希索引表，采用哈希查找與KMP匹配算法相結(jié)合的方式使得算法可以兼顧內(nèi)存占用小與查詢速度快。隨后以k

希表索引算法模型。采取KMP匹配算法來尋找具體的位置。射函數(shù)叫做哈希函數(shù)。在本題中，關(guān)鍵碼就是每個(gè)k-mer。f(A)=00，f(C)=01，f(G)=10，f(T)= ；k=5 編號(hào)為從到，每一個(gè)k-mer序列S，將其行號(hào)存于表頭編號(hào)為f（S）后面的鏈表中。、KMP，先從S[0]與T[0]S[0T[0]，則比較S[1]與T[1]S[5]配成功位置上的信息，發(fā)現(xiàn)T[0]T[1T[3]T[4]=S[3]S[4]T直接比較T[2]與S[5]，如圖3所示。從而快速匹配成功。，圖3KMP1000000×(101? 設(shè)f(k)=4?? ×(101? 210

8x 4f(k)如圖3所示，當(dāng)k大于13以后，4??? ×(101?k),也就是說，L(k)= (k≤4) ×(101?L(k) (k> 5x9876543210 圖5L(k)1kL(k)k895120-35，100DNA，901k1010（長(zhǎng)度大概為80，查找并不會(huì)耗費(fèi)太多時(shí)間。678T(n)= S(n)= 雜度為O(1)。位置，所以只需一次即可，復(fù)雜度為O(1)。T(n)=O(1)+O(1)= ??1(n)= 為O（lenthT）.對(duì)于本模型來講，長(zhǎng)度為常值，所以空間復(fù)雜度為:??2(??)= S(n)=O(1)+O(1)= 908B（8）內(nèi)存，。則：理論總占用內(nèi)存=4^10908B=運(yùn)行環(huán)境為windows764位操作系統(tǒng)下，CPU為InCorei3處理器。k=7的查詢時(shí)間為0.68s。k=10的查詢時(shí)間為0.000sk=230.00000sk2-100k=5耗時(shí)11.46s建立索引。 k=21，耗時(shí)17.96秒建立索引小于18s。該繼續(xù)進(jìn)行檢索；

9若掃描結(jié)束后，仍未找到關(guān)鍵字等于K的結(jié)點(diǎn)，則查找失敗2k（本文模型建表時(shí)間查詢時(shí)間建表時(shí)間查詢時(shí)間消耗內(nèi)存查詢時(shí)間消耗內(nèi)存307000000000500[1]謝.數(shù)學(xué)模型[M].4.：高等教育, .數(shù)據(jù)結(jié) ,k-merIndex4.cpp支持單進(jìn)程8G內(nèi)存#defineFILEPATH"newfile.dat"#defineSEQLEN100#defineSEQCOUNT#defineINDEXMAX_K10charChildString[SEQLEN1]'\0'{Node*next;struct{Node*end;//標(biāo)志鏈表尾部unsignedintStringToNum(charstringintk);//將子串轉(zhuǎn)化為其對(duì)應(yīng)的數(shù)字voidGet_next(charT[],intk,intnext[]);intIndex_KMP(charS[charT[intk,intpos);//k為k-merintInsertNode(TableHead*Head,intsequence,unsignedintnum);//往索引表TableHead*BuildTable(intk);//建立索引表，返回值為表頭，k為k-mer值TableHead*Intersection(Node*LinkHead1Node*LinkHead2);//求兩個(gè)子序列都位voidSearch(TableHead*Head,intk,charstring[]);//查找子序列所在母序列的voidSearchSolution_1(TableHead*Head,charstring[],intk);//當(dāng)k>=10時(shí)，選//voidSearchSolution_2(TableHead*Head,charstring[],intk);//當(dāng)k>=20時(shí)，voidSearchSolution_2(TableHead*Head,charstring[],intk);//當(dāng)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("查找用時(shí)%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';}}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("結(jié)點(diǎn)生成失敗，此時(shí)母序列為%d\n",}1node->next=NULL;TableHead*p=Head+num;if(p->head==NULL){p->headp->endnode;return1;}{if((sequence+1)p->end->sequence)//倘若該子序列所在的母序列已經(jīng){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;//測(cè)試語句}intposition0;/intcount0;//測(cè)試用，測(cè)試完要?jiǎng)h除FILE*fp;"w")!=0)//測(cè)試用{}for(inti=0;i<SEQCOUNT;//for(inti=0;i<{count0for(position1;positionSEQLENk1;position++)//將每一個(gè){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(charTintkintnext[])//T的長(zhǎng)度為{inti=0;next[0]=-1;intj=-1;while(i<k-{if(j==-1||T[i]=={i++;next[i]=}j=}}intIndex_KMP(charS[charT[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;}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-{{}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[sequence1string,kpos);if(pos)//當(dāng)pos不為0時(shí)，表示有子串{printf("存在于第%d個(gè)DNA序列，位置為%d\nsequence,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[sequence1string,kpos);if(pos)//當(dāng)pos不為0時(shí)，表示有子串{printf("存在于第%d個(gè)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,}#include<bits/stdc++.h>#include<windows.h>usingnamespacestd;constintSTR_LEN=105;typedefpair<int,int>position;pii.first/SeqIndexpii.second/posInSeq為相應(yīng)序列中出現(xiàn)的位置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=GetTickCount(); FILE*input=fopen("dna.txt",for(inti=1;fscanf(input,"%s",buf)!=EOF;{kmer.insert(buf,if(i%10000==0)printf("%d\n",} FI