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。

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