2015年深圳杯“数学建模”B题(2)

5.2在100w行序列，k=15时，运行结果和生成的文件

运行结果：

图4

5.3

生成的文件：

图5

由于kmer长度如果过长，其hash值过大，会造成内存不够溢出的现象

5.4复杂度分析

索引的时间复杂为：O(n)

索引时，需要将待查序列的十进制数值与所有的k-mer的十进制数进行比较，所以时间复杂度为O(n)

六、算法检验

6.1贪婪算法的概念

贪婪算法是一种对某些求最优解问题的更简单、更迅速的设计技术。【9】用贪婪法设计算法的特点是一步步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有

此文档属于DNA索引类。

可能而必须消耗的大量时间，它采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解。6.2贪婪算法的求解

现在先假定ACGT四种碱基的标识分别为0123，把他们看作四进制的数，转化十进制为在100万行的序列中先讨论第一行的100个碱基。让这里面的转化的十进制的数去与第一行的100-k+1个十进制数匹配。查找出这一行里的最优解。如果没有则继续向下循环查找到100万行为止，得出它的位置。流程图如下：

开始

令ACGT

||||||||0123

100个碱基转化为十进制数个数S-k+1，让已知k长序列进行

匹配

如果所给k的十进制数=片段中的x

N

循环的匹配1-100万的每一行

Y

输出该碱基片段的位置

图6

贪婪算法流程图

此文档属于DNA索引类。

七、模型评价与推广

7.1模型评价7.1.1优点

1.我们都知道inputstream是一个字节一个字节的读取，每次读取都会执行一次IO，我们知道io的操作是很费时间的，【8】

这就必然会导致程序的效率，而bufferedreader很好的解决这一问题，它可以一次读取大量的数据，大大减少了io次数，效率也就上去了

2.碱基序列用四进制表示，节省内存开销。

3.采用哈希算法，查询速度快于其他的算法且简单，直接。7.1.2缺点

待查序列的十进制数与k-mer的十进制数进行比较相等的情况下，还需要回溯进行序列的匹配才能确定该k-mer是否为待查序列。

八、参考文献

【1】张鑫鑫《生物序列数据K-mer频次统计与可视化研究》第一期2014年。

【2】王红梅《数据结构》（C++版）清华大学出版社2011年6月【3】王红梅《算法分析与设计》清华大学出版社2012年6月

【4】陈波何继凌《生物序列数据K-mer频次统计问题的算法》第四期2014年。

【5】江裕钊辛培情《数学模型与计算机模拟》电子科技大学出版社1989【6】韦斯《数据结构与算法分析.java语言描述》清华大学出版社2009年1月

【7】葛秀慧田浩《数据结构与问题求解（java语言版）》清华大学出版社2011年8月

【8】吴孟达成礼智《数据建模的理论与实践》北京出版社1999年8月【9】白其峥《数据建模案例分析》高等教育出版社2000年1月

此文档属于DNA索引类。

源代码：

CreateData:

ut;

importjava.io.BufferedWriter;importjava.io.File;

importjava.io.FileWriter;publicclassCreateData{

finalintcolumn=1000000;finalintrow=100;

publicvoidcreateData(){try{

Filefile=newFile("F:\\biologicaldata.txt");if(!file.exists()){

file.createNewFile();}

FileWriterfw=newFileWriter(file.getAbsolutePath());BufferedWriterbw=newBufferedWriter(fw);for(inti=0;i<column;i++){

for(intj=0;j<row;j++){

StringBuffersb=newStringBuffer();doublea=Math.random()*4;if(a<1&&a>0){

sb.append('A');}elseif(a<2){

sb.append('C');}elseif(a<3){

sb.append('G');}elseif(a<=4){

sb.append('T');}

Strings=sb.toString();bw.write(s);}

bw.newLine();}

//bw.write(content);bw.close();

}catch(Exceptione){

e.printStackTrace();}

此文档属于DNA索引类。

}

publicstaticvoidmain(String[]args){

//TODOAuto-generatedmethodstubCreateDatacd=newCreateData();cd.createData();

//doublej=Math.random();//System.out.print(j);}}

CreateIndex:

ut;

importjava.io.BufferedReader;importjava.io.BufferedWriter;importjava.io.File;

importjava.io.FileInputStream;importjava.io.FileWriter;

importjava.io.InputStreamReader;

publicclassCreateIndex{

finalstaticintk=15;

publicstaticintexp(intn){

intresult=1;

for(inti=0;i<n;i++){

result=result*4;}

returnresult;}

publicstaticintcreateIndex(Strings){

char[]a=s.toCharArray();intresult=0;intj=0;

for(inti=a.length-1;i>=0;i--){

inttemp=a[j];

if((temp>='0')&&(temp<='3')){

此文档属于DNA索引类。

result=(result+((temp-'0')*exp(i)));j++;}}

returnresult;

}

publicstaticvoidcreateFinalFile(StringfilePath){

System.out.print("0");try{

Stringencoding="GBK";Filefile=newFile(filePath);

Filefile1=newFile("F:\\finaldata.txt");if(!(file1.exists())){file1.createNewFile();}

FileWriterfw=newFileWriter(file1.getAbsolutePath());BufferedWriterbw=newBufferedWriter(fw);

if(file.isFile()&&file.exists()){//判断文件是否存在

InputStreamReaderread=newInputStreamReader(newFileInputStream(file),encoding);//考虑到编码格式

BufferedReaderbufferedReader=newBufferedReader(read);

StringlineTxt=null;System.out.print("0");

while((lineTxt=bufferedReader.readLine())!=null){

for(inti=0;i<lineTxt.length()-k;i++){

Stringcell=lineTxt.substring(i,i+k);inttemp=createIndex(cell);Strings=Integer.toString(temp);bw.write(s);bw.write(",");}

bw.newLine();}

bw.close();read.close();

}else{

System.out.println("找不到指定的文件");}

}catch(Exceptione){

此文档属于DNA索引类。

System.out.println("读取文件内容出错");e.printStackTrace();}

}

publicstaticvoidmain(String[]args){

//TODOAuto-generatedmethodstub

CreateIndex.createFinalFile("F:\\middledata.txt");//String

s="1021313113113201013021123321100132331303311031313323013212220000203011323101002332210023023023030302";

//System.out.print(createIndex(s.substring(0,14)));}}

Index:

ut;

importjava.io.BufferedReader;importjava.io.File;

importjava.io.FileInputStream;importjava.io.I …… 此处隐藏：3888字，全部文档内容请下载后查看。喜欢就下载吧 ……