{"trustable":false,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cscript type\u003d\u0027text/x-mathjax-config\u0027\u003eMathJax.Hub.Config({tex2jax: { inlineMath: [[\u0027$\u0027,\u0027$\u0027],[\u0027\\[\u0027,\u0027\\]\u0027]] } }); \u003c/script\u003e\n\u003cscript type\u003d\u0027text/javascript\u0027 src\u003d\u0027https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\u0027\u003e\u003c/script\u003e\n\u003cscript type\u003d\u0027text/javascript\u0027\u003esetTimeout(function(){MathJax.Hub.Queue([\u0027Typeset\u0027, MathJax.Hub, \u0027left_view\u0027]);}, 2000);\u003c/script\u003e\n\u003cdiv class\u003d\"panel_content\"\u003e\n 众所周知,人类基因可以被认为是由四个核苷酸组成的序列,它们简单地由四个字母A,C,G和T表示。生物学家一直对识别人类基因和确定其功能感兴趣,因为这些可以用于诊断人类疾病并为他们设计新的药物。\n \u003cbr\u003e \n \u003cbr\u003e可以通过一系列耗时的生物实验来识别人类基因,通常在计算机程序的帮助下进行。一旦得到基因的序列,下一个工作就是确定其功能。生物学家用于确定其刚鉴定的新基因序列的功能的方法之一是用新基因作为查询搜索数据库。要搜索的数据库存储许多基因序列及其功能 - 许多研究人员已经将其基因和功能提交到数据库,并且数据库可以通过因特网自由访问。 \n \u003cbr\u003e \n \u003cbr\u003e数据库搜索将返回数据库中与查询基因相似的基因序列表。生物学家认为序列相似性往往意味着功能相似性。因此,新基因的功能可能是来自列表的基因的功能之一。要确定哪一个是正确的,需要另一系列的生物实验。 \n \u003cbr\u003e \n \u003cbr\u003e你的工作是制作一个比较两个基因并确定它们的相似性的程序,如下所述。如果可以提供有效的程序,则可能会将程序用作数据库搜索的一部分。\n \u003cbr\u003e \n \u003cbr\u003e给定两个基因AGTGATG和GTTAG,它们有多相似?测量两个基因相似性的方法之一称为对齐。在排列中,如果需要,将空间插入基因的适当位置以使它们相等长,并根据评分矩阵评分所得基因\n \u003cbr\u003e \n \u003cbr\u003e例如,一个空格被插入到AGTGATG中以产生AGTGAT-G,并且在GTTAG中插入三个空格以产生-GT-TAG。空格用减号( - )表示。两个基因现在的长度相等。这两个字符串对齐:\n \u003cbr\u003e \n \u003cbr\u003eAGTGAT-G \n \u003cbr\u003e-GT--TAG \n \u003cbr\u003e \n \u003cbr\u003e在这种对准中,有四个匹配,即第二个位置的G,第三个是T,第六个是T,第八个是G。每对对齐的字符根据以下评分矩阵分配一个分数。\n \u003cbr\u003e \n \u003ccenter\u003e \n \u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/5d14276bf1efe76383ea05ede5021b14?v\u003d1499476258\" SRC\u003d\"CDN_BASE_URL/5d14276bf1efe76383ea05ede5021b14?v\u003d1499476258\"\u003e \n \u003c/center\u003e \n \u003cbr\u003e* 表示不允许空格匹配。上面对齐的得分是 (-3)+5+5+(-2)+(-3)+5+(-3)+5\u003d9. \n \u003cbr\u003e \n \u003cbr\u003e当然,许多其他的比对是可能的。一个如下所示(将不同数量的空格插入到不同的位置)\n \u003cbr\u003e \n \u003cbr\u003eAGTGATG \n \u003cbr\u003e-GTTA-G \n \u003cbr\u003e \n \u003cbr\u003e\n这个对齐给出了一个分数 (-3)+5+5+(-2)+5+(-1) +5\u003d14.所以,这比一个更好。事实上,这是一个最佳的,因为没有其他对齐可以有更高的分数。所以,据说两个基因的相似性是 14. \n \u003cbr\u003e \n\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"输入由T个测试用例组成。 测试用例数) (T在输入的第一行给出。每个测试用例由两行组成: 每行包含一个整数, 基因的长度,其次是基因序列. 每个基因序列的长度至少为1,不超过 100. \n\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"输出应打印每个测试用例的相似度,每行一个. \n\u003cbr\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e2 \n7 AGTGATG \n5 GTTAG \n7 AGCTATT \n9 AGCTTTAAA \u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003e14 \n21 \u003c/pre\u003e"}}]}