#P2268. [HNOI2002] DNA分子的最佳比对

[HNOI2002] DNA分子的最佳比对

题目描述

DNA\operatorname{DNA} 分子是人类遗传信息的载体,它间接地指导蛋白质的合成。DNA\operatorname{DNA} 分子是由四种核苷酸组成的长链,这四种核苷酸分别是腺嘌呤核苷酸(用 A\operatorname{A} 代表)、鸟嘌呤核苷酸(用 G\operatorname{G} 代表)、胞嘧啶核苷酸(用 C\operatorname{C} 代表)和胸腺嘧啶核苷酸(用 T\operatorname{T} 代表)。习惯上用一个字符集为 {A,T,C,G}\{\operatorname{A,T,C,G}\} 的字符串来表示一个 DNA\operatorname{DNA} 分子序列,如 CGTTAGA\operatorname{CGTTAGA}

在生物进化过程中, DNA\operatorname{DNA} 分子可能发生各种各样的突变。这种突变形成了生物遗传信息的改变,从而使生物得以分化,构成了生物的多样性。

主要的突变有三种:

  1. 在一个 DNA\operatorname{DNA} 序列中插入一个新的核苷酸,

  2. DNA\operatorname{DNA} 序列中丢失了一个核苷酸,

  3. DNA\operatorname{DNA} 序列中的某个核苷酸被另一个核苷酸所取代。

所谓两个 DNA\operatorname{DNA} 序列的一个比对是寻找一种排列方式,使得两个 DNA\operatorname{DNA} 序列在同样的位置上有相同的核苷酸,而若在同样的位置上两个DNA序列的核苷酸不同,则是由三种突变之一得到。例如,对两个 DNA\operatorname{DNA} 序列 T1=ATCAGT_1 =\operatorname{ATCAG}T2=ACTAGT_2 =\operatorname{ACTAG} ,可以按如下方式比对,( - 表示空白)

比对一:

T1T_1 T2T_2
AA
TT -
CC
AA
- TT
GG

也可以按如下方式比对

比对二:

T1T_1 T2T_2
AA
TT CC
CC TT
AA
GG

如果两个 DNA\operatorname{DNA} 序列在相同的位置上有越多相同的核苷酸对,则表明它们之间越相似,即它们存在功能上的相似性和进化史上的亲缘关系。

对于两个 DNA\operatorname{DNA} 序列的一个比对,规定如下得分方式:

  1. 一个同样的位置上有相同的核苷酸对,则可得 11 分;

  2. 一个同样的位置上有不同的核苷酸对,则得 00 分;

  3. 如果在某个位置上一个序列有核苷酸,而另一个序列在该位置上为 -,则得 2-2 分。例如,比对一的得分是 00 分,比对二的得分是 33 分。

问题是:对于两个 DNA\operatorname{DNA} 序列,寻找一种比对方式,使得它们的得分最高。

输入格式

输入数据由文件名为INPUT.*的文本文件提供,共有2行。

第1行为DNA序列T1 , 第2行为DNA序列T2 。序列的长度不大于1000。序列中的字母是英文小写或者大写字母。

输出格式

程序运行结束时,在屏幕上输出所找出的最大的得分

Atcag
Actag
3