资源描述：
《北航软件技术基础作业2》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、,匕京空巔;夭大爭BEIHANGUNIVERSITY软件技术基础作业院（系）名称计算机学院学生姓名杨立群学号BY16061442016年11月目录目录1概述1i.i作业内容及目标11.2思路与方案12原示例程序分析22」原示例程序处理流程22.2原示例程序不能处理的情况32.2.1substr与H9N2-2009兀配的位置不止一个32.2.2substr的子串与H9N2-2009后续位置匹配43算法设计53・1MutantKMPmatching53.2主程序流程6结论81概述1・1作业内容及目标比较DNA字符串DNA2009和DNA2
2、010。找出两者之间所有相同长度大于16的基因段，相同的段尽可能取最长的长度显示出相同的段以及在两个DNA中的位置。1.2思路与方案主要采用一种变异的KMP算法(MutantMKPmatching,MKMP)。该算法在主要的字符串比对部分于KMP算法相同，但针对本次作业的实际情况做出了一定的优化。具体比对过程为：从H9N1-2010首个字符开始，逐个选取以第一个、第二个、第三个……字符开始且长度为16的子串，使用MKMP算法比较该字串与H9N2-2009,获取能够匹配的H9N2-2009中的全部位置(而非初次匹配的位置)。最后从这些位
3、置开始，先输出16个字符，再从第17个字符开始逐个比对两个序列对应位置，相同则输岀，直到不相同为止。2原示例程序分析2.1原示例程序处理流程作业给出了一个示例程序，该程序实现了KMP算法，并通过调用该算法，进行DNA序列比对，其流程为:0UJ+16]Q2-2009iddressi(1)取j=0；(2)取出长度为16个字符的字符串:substr=H9Nl-2010[j:j+16],利用KMP算法，比较H9N2-2009与substr,返回首次匹配的位置i；(1)取offset=16；(2)substr+=H9N2-2009[i+offs
4、et],offset++；(3)若H9Nl-2010[j+offset]==H9N2-2009[i+offset],返冋(4),否则进入(6)⑹输Mli>j>substr,取j二j+offset,若j>len(H9N1-2010)-16,结朿，否则返回(2)。2.2原示例程序不能处理的情况221substr与H9N2-2009匹配的位置不止一个由于示例程序中调用KMP算法只返回substr与H9N1-2010匹配的首个位置，因此若H9N1-2010后续部分仍有与substr匹配的部分不会被发现。一个实例如下：H9N2-2009：ATG
5、GAAACAATAGCACTATGGAAACAATAGCACH9N1-2010：ATGGAAACAATAGCACTAATAGCTATACTATTA上例中，程序开始时所取substr为前16个字符（黄色部分）。N9N2-2009中于substr匹配的子串有两个（红色部分），而示例程序只发现第一个。运行结果如下：齢提帚-□XC.0149998664856*：学习DNACheck(l)>pythonDNACheck.py>gi13785594271gbIJQ609664.11InfluenzaAvirus(A/chicken/Engla
6、nd/^1415-51184/201C(H9N1))segment4hemagglutinin(HA)gene,completecds[*>gi*,'378559427','gb','JQ609664.1','InfluenzaAvirus(A/chicken/England/1415-51184/2010(H9N1))segment4hemagglutinin(HA)gene,completecds‘]ATGGAAACAATAGCACTATGGAAACAATAGCAC>gi12849300921gb：GU471874.11Inf
7、luenzaAvirus(A/chicken/Zhejiang/E5/2009(H9N2))segment4hemagglutinin(HA)gene,completecdsV>giT,'284930092','gb','GU471874.1','InfluenzaAvirus(A/chicken/Zhejiang/E5/2009(H9N2))segment4hemagglutinin(HA)gene,completecds']ATGGAAACAATAGCACTAATAGCTATACTATTATheDNAofH9N12010beg
8、inat1isequaltoDNAofH9N22009beginat1ThesameDNAsegementisTGGAAACAATAGCACTAIhesameDNAsegementlengthis17Thesimilar
