技术类未知acm诚信承诺我保证没有抄袭他人作业

1、POJ1080HumanGeneFunctions解题计算机05 级吴连龙00548047 A B，允许插入适当空格使长度相同，定义相应位置不同关键码组合的形似度矩阵 Weight，求最佳插入方式使得i B j 个基因结尾的最佳相似度。不插入空格，问题转化为 Simi-1j-1的子问题，加上 GeneAi和 格和 GeneBj的匹配权值。格和 GeneAi的匹配权值。可以用反证法证明，子问题的最优解一定是当前 i，j 问题的最优解的构成Simij=maxSimi-1j-+WeightGeneAiGeneBjSimij-1 + Weight空格 GeneBjSimi-1j + Weight Ge

2、neAiO（1O（N2O（N2O（NPOJ 0ms28KB。/ Problem: POJ / Title : Human Gene / Method : Dynamic / : O( N2 /Space :O(N) #include char Weight55 5,-1,-2,-1,-3,-1,5,-3,-2,-4,-2,-3,5,-2,-2,-1,-2,-2,5,-1,-3,-4,-2,-int LenA, LenB, i, int Sum; / 测试数据个数bool Cur; / 当前阶段游标char char char GeneA101, short / 函数说明：返回两个shortin

3、line short max( short ValA, short ValB return ValA ValB ? ValA : void FA=0; FC=1; FG=2; scanf(%d, &Sum); while ( Sum- 0 scanf(%d%s,&LenA,&Str); for ( i = 0; i LenA; i+ GeneAi+1=FStri; scanf( %d %s, &LenB, &Str); for ( i = 0; i LenB; i+ )GeneB i+1 = F Str i Sim00 = for ( j = 1; j = LenB; j+ Sim0j = S

4、im0 j-1 + Weight4 GeneB j for ( i = 1, Cur = 1; i = LenA; i+, Cur = !Cur SimCur0=Sim!Cur0+WeightGeneAi4; for ( j = 1; j = LenB; j+ )/ 情况1: 不插入空格基因A第i位和基因B第jSimCurj = Sim!Curj-1 + / 情况2: 在基因A第i位插入空格和基因B第jSimCurj=max(SimCurj,SimCurj-1+Weight4GeneBj/ 情况3: 在基因B第j位插入空格和基因A第iSimCurj = max( SimCurj, Sim!Cu

5、rj + WeightGeneAi4 NOI2003DNA分子的最佳比对，Fjoi2003 目录。LenA，LenB GeneA，GeneB 对应显然更不容易出错。579494040-NOI2003 福建省选手选拔赛试试题三、DNA 分子的最佳比对（本题满分 40 分问题描述苷酸组成的长链，这四种核苷酸分别是腺嘌呤核苷酸（用 A 代表、鸟嘌呤核苷酸（用 G 代表、胞嘧啶核苷酸（C 代表）和胸腺嘧啶核苷酸（T 代表A，T，C，G的字符串来表示一个 DNA 分子序列，如 CGTTAGA在生物进化过程中，DNA分子可能发生各种各样的突变。这种突变形成了生物遗传信（1）（2）DNA（3）DNADNAD

6、NA序列在同样的位 DNAT =ATCAG，T2=ACTAG，可以按如下方式比对，1：T“-C-T（1） （2） （3）023编程任务DNA数据输入INPUT3.*21DNAT , 2DNAT25000。序列中的结果输出DNA输入文件示输出示Human Gene Time Limit:1000MSMemoryLimit:10000K Total Submit:2255 Accepted:1440It is well known that a human gene can be considered as a sequence, consisting of fournucleotides,whi

7、charesimplydenotedbyfourletters,A,C,G,andT.Biologists have been interested in identifying human genes and determining their functions, because these can be used to diagnose human diseases and to design new drugs for A human gene can be identified through a series of time-consuming biological experim

8、ents,oftenwiththehelpofcomputerprograms.Onceasequenceofageneis obtained, the next job is to determine its function.One of the methods for biologists to use in determining the function of a new gene sequence that they have just identified is to search a database with the new gene as a query.Thedataba

9、setobesearchedstoresmanygenesequencesandtheirfunctionsmanyresearchershavebeensubmittingtheirgenesandfunctionstothedatabaseand the database is freely accessible through the Internet.Adatabasesearchwillreturnalistofgenesequencesfromthedatabasethatare similar to the query gene.Biologistsassumethatseque

10、ncesimilarityoftenimpliesfunctionalsimilarity.So,the function of the new gene might be one of the functions that the genes from the list have. To exactly determine which one is the right one another series of biological experiments will be needed.Your job is to make a program that compares two genes

11、 and determines their similarityasexplainedbelow.Yourprogrammaybeusedasapartofthedatabase search if you can provide an efficient one.GiventwogenesAGTGATGandGTTAG,howsimilararethey?Oneofthemethods to measure the similarityoftwogenesiscalledalignment.Inanalignment,spacesareinserted,ifnecessary,in appr

12、opriate positions ofthegenestomakethemequallylongandscoretheresultinggenesaccordingtoa scoring matrix.For example, one space is inserted into AGTGATG to result in AGTGAT-G, and threespacesareinsertedintoGTTAGtoresultinGT-TAG.Aspaceisdenotedbya minus sign (-). The two genes are now of equallength.The

13、setwostringsareAGTGAT-GT-In this alignment, there are four matches, namely, G in the second position, T in the third,Tinthesixth,andGintheeighth.Eachpairofalignedcharactersisassigneda score according to the following scoring matrix.denotesthataspace-spacematchisnotallowed.Thescoreofthealignmentabove

14、is Ofcourse,manyotheralignmentsarepossible.Oneisshownbelow(adifferent number of spaces are inserted into different positions):-GTTA-This alignment gives a score of (-3)+5+5+(-2)+5+(-1) +5=14. So, this one is better thanthepreviousone.Asamatteroffact,thisoneisoptimalsincenootheralignment can have a higher score. So, it is said that thesimilarityofthetwogenesisThe input consists of T test cases. The number of test cases ) (T is given in the first lineoftheinputfile.Eachtestcaseconsistsoftwolines:eac