312004 - 确定基因功能

人体基因是由一个序列组成,包含4个核苷酸,以A、C、G、T表示。

人体基因的确定由计算机辅助并通过一系列生物实验,一旦基因被确定,下一步的工作即是确定其功能。

一种方法是:通过数据库查询新的基因,这个数据存储了许多基因序列及其功能描述,当使用数据库查找时,数据库会返回相类似的基因。而生物学家假设序列相似代表功能的相似,所以,新基因可能会有的功能与相似基因的功能一样。当然,这需要一系列的实验确定。

你的职责是编制一个程序以比较两个相似的基因,如果你的程序有效,你的程序可能会作为数据库搜索功能的一部分。

例如:两个基因AGTGATG 和GTTAG,有多少相似度呢?

我们使用插入法:例如,插入一个空档在AGTGATG中间,使之变为AGTGAT–G,再插入三个空档在GTTAG中间,使之变为–GT––TAG,现在这两个基因长度相等。如下:

AGTGAT–G,
–GT––TAG

  我们可以看到,两个基因有四处相似,即:G都在第2位,T都在第3位,T都在第6位,G都在第8位。

下表是任何两个核苷酸相对应时的数字矩阵,例如A与A对应的分数为5,A与C对应的分数为-1,但要注意绝对不允许空档与空档匹配情况的出现。

则这两个基因根据该表格算出的分数为:(-3)+5+5+(-2)+(-3)+5+(-3)+5=9

但实际上,如果我们将这两个基因按如下方式插入空档,即:

AGTGATG
–GTTA–G

这种方式的分数为:(-3)+5+5+(-2)+5+(-1)+5=14。所以,这种插入方式要优于前面的插入方式,而实际上,这种插入方式的得分也是最高的,所以,这两个基因的相似程度应该为14。

输入

第一行为T值,代表测试的样例数,接下来每个测试样例包括两行,每行包括一个基因长度数和该基因序列,每个基因的序列长度最小为1,最大不超过100。

输出

每行包括一个数字,即每个样例的最大相似度。

样例

输入

2 
7 AGTGATG 
5 GTTAG 
7 AGCTATT 
9 AGCTTTAAA 

输出

14
21
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题