PID61 / DNA分子的最佳比对
题目描述

问题描述:

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

在生物进化过程中,DNA分子可能发生各种各样的突变。这种突变形成了生物遗传信息的改变,从而使生物得以分化,构成了生物的多样性。主要的突变有三种:(1)在一个DNA序列中插入一个新的核苷酸,(2)DNA序列中丢失了一个核苷酸,(3)DNA序列中的某个核苷酸被另一个核苷酸所取代。

所谓两个DNA序列的一个比对是寻找一种排列方式,使得两个DNA序列在同样的位置上有相同的核苷酸,而若在同样的位置上两个DNA序列的核苷酸不同,则是由三种突变之一得到。例如,对两个DNA序列M=ATCAG,N=ACTAG,可以按如下方式比对,

比对1:

M N

A A

T -- (“--”表示空白)

C C

-- T

A A

G G

也可以按如下方式比对

比对2:

M N

A A

T C

C T

A A

G G

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

对于两个DNA序列的一个比对,规定如下得分方式:(1)一个同样的位置上有相同的核苷酸对,则可得1分;(2)一个同样的位置上有不同的核苷酸对,则得0分;(3)如果在某个位置上一个序列有核苷酸,而另一个序列在该位置上为“--”,则得 -2分。例如,比对1的得分是0分,比对2的得分是3分。

问题求解:

对于两个DNA序列,寻找一种比对方式,使得它们的得分最高。

输入格式

输入数据共有2行。第1行为DNA序列M 第2行为DNA序列N。序列的长度不大于500。序列中的字母是英文大写字母。

输出格式

程序运行结束时,在屏幕上输出两个DNA序列比对的最高得分。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论