{"trustable":false,"sections":[{"title":"","value":{"format":"MD","content":"众所周知,人类基因可以被视为由四个核苷酸组成的序列,这四个核苷酸简单地由四个字母A、C、G和T表示。生物学家一直对识别人类基因并确定其功能感兴趣。因为它们可以用来诊断人类疾病并为其设计新药。\n\n人类基因可以通过一系列耗时的生物实验来识别,通常需要借助计算机程序。一旦获得基因序列,下一步的工作就是确定其功能。\n\n生物学家在确定他们刚刚识别的新基因序列的功能时使用的方法之一是以新基因作为查询来搜索数据库。待检索的数据库存储了许多基因序列及其功能——许多研究人员已将他们的基因和功能提交到该数据库,并且该数据库可以通过互联网免费访问。\n\n数据库搜索将返回数据库中与查询基因相似的基因序列列表。\n生物学家认为序列相似性通常意味着功能相似性。因此,新基因的功能可能是列表中基因所具有的功能之一。为了准确确定哪一个是正确的,需要进行另一系列的生物学实验。\n\n您的工作是编写一个程序来比较两个基因并确定它们的相似性,如下所述。如果您可以提供高效的程序,您的程序可能会用作数据库搜索的一部分。\n\n\n\n给定两个基因 AGTGATG 和 GTTAG,它们有多相似?\n\n测量两个基因相似性的方法之一称为对齐。\n在对齐中,如有必要,可在适当的位置插入空格使它们的基因等长,并根据评分矩阵对所得基因进行评分。\n\n例如,AGTGATG 中插入 1 个空格,则为 AGTGAT-G;GTTAG 中插入 3 个空格,则为 –GT--TAG。空格由减号 (-) 表示。现在这两个基因是等长的。这两个字符串对齐:\n\nAGTGAT-G\n-GT--TAG\n\n在这种对齐方式中,有四个匹配项,即 G 在第二个位置,T 在第三个位置,T 在第六个位置,G 在第八个位置。根据以下评分矩阵为每对对齐的字符分配一个分数。\n\u003cimg src\u003d\"CDN_BASE_URL/fcf3938cf314f4598e568b157e91a600?v\u003d1710127435\"\u003e\n表示不允许空间-空间匹配。\n上述比对的得分为(-3)+5+5+(-2)+(-3)+5+(-3)+5\u003d9。\n\n当然,许多其他排列也是可能的。如下所示(不同位置插入不同数量的空格):\n\nAGTGATG\n-GTTA-G\n\n该比对给出的分数为(-3)+5+5+(-2)+5+(-1)+5\u003d14。\n所以,这一篇比上一篇更好。事实上,这个是最佳的,因为没有其他比对可以有更高的分数。所以说\n两个基因的相似度为14。\n\n"}},{"title":"Input 输入","value":{"format":"MD","content":"输入由 T 个测试用例组成。测试用例的数量 ) (T 在输入文件的第一行给出。每个测试用例由两行组成:每行包含一个整数,一个基因的长度,后面跟着一个基因序列。每个基因的长度序列至少为 1,不超过 100。"}},{"title":"Output 输出","value":{"format":"MD","content":"输出应打印每个测试用例的相似性,每行一个。"}},{"title":"Sample","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2 \n7 AGTGATG \n5 GTTAG \n7 AGCTATT \n9 AGCTTTAAA \u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e14\n21 \u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}