Human Gene Functions
Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1307Accepted Submission(s): 752
Problem Description
It is well known that a human gene can be considered as a sequence, consisting of four nucleotides, which are simply denoted by four letters, A, C, G, and T. Biologists have been interested in identifying human genes and determining
their functions, because these can be used to diagnose human diseases and to design new drugs for them.
A human gene can be identified through a series of time-consuming biological experiments, often with the help of computer programs. Once a sequence of a gene is obtained, the next job is to determine its function. One of the methods for biologists to use in
determining the function of a new gene sequence that they have just identified is to search a database with the new gene as a query. The database to be searched stores many gene sequences and their functions – many researchers have been submitting their genes
and functions to the database and the database is freely accessible through the Internet.
A database search will return a list of gene sequences from the database that are similar to the query gene. Biologists assume that sequence similarity often implies functional similarity. So, the function of the new gene might be one of the functions that
the genes from the list have. To exactly determine which one is the right one another series of biological experiments will be needed.
Your job is to make a program that compares two genes and determines their similarity as explained below. Your program may be used as a part of the database search if you can provide an efficient one.
Given two genes AGTGATG and GTTAG, how similar are they? One of the methods to measure the similarity of two genes is called alignment. In an alignment, spaces are inserted, if necessary, in appropriate positions of the genes to make them equally long and score
the resulting genes according to a scoring matrix.
For example, one space is inserted into AGTGATG to result in AGTGAT-G, and three spaces are inserted into GTTAG to result in –GT--TAG. A space is denoted by a minus sign (-). The two genes are now of equal length. These two strings are aligned:
AGTGAT-G
-GT--TAG
In this alignment, there are four matches, namely, G in the second position, T in the third, T in the sixth, and G in the eighth. Each pair of aligned characters is assigned a score according to the following scoring matrix.
* denotes that a space-space match is not allowed. The score of the alignment above is (-3)+5+5+(-2)+(-3)+5+(-3)+5=9.
Of course, many other alignments are possible. One is shown below (a different number of spaces are inserted into different positions):
AGTGATG
-GTTA-G
This alignment gives a score of (-3)+5+5+(-2)+5+(-1) +5=14. So, this one is better than the previous one. As a matter of fact, this one is optimal since no other alignment can have a higher score. So, it is said that the similarity of the two genes is 14.
Input
The input consists of T test cases. The number of test cases ) (T is given in the first line of the input. Each test case consists of two lines: each line contains an integer, the length of a gene, followed by a gene sequence. The
length of each gene sequence is at least one and does not exceed 100.
Output
The output should print the similarity of each test case, one per line.
Sample Input
2
7 AGTGATG
5 GTTAG
7 AGCTATT
9 AGCTTTAAA
Sample Output
输入
2
7 AGTGATG
5 GTTAG
7 AGCTATT
9 AGCTTTAAA
输出
14
21
题意:两个字符串,每个字符串中都可以插入'-',保证最后两串的长度相等,之后让两串对齐,两串相同位置的字母组成的字符匹配有一个值,问这些值的和最大是多少,是第一题的变形
下图为字符匹配所得价值的表
dp[i][j]表示0到i-1跟0到j-1配对的最大价值
状态转移:
①dp[i][j]由dp[i-1][j]转移过来,代价是a[i-1]跟'-'匹配
②由dp[i][j-1]转移过来,代价是b[j-1]跟'-'匹配
③由dp[i-1][j-1]转移过来,代价是a[i-1]跟b[j-1]匹配
#include<stdio.h>
#include<string.h>
int max[500][500];
int map[150][150];
void match()
{
map['A']['A']=5;map['A']['C']=-1;map['A']['G']=-2;map['A']['T']=-1;map['A']['-']=-3;
map['C']['A']=-1;map['C']['C']=5;map['C']['G']=-3;map['C']['T']=-2;map['C']['-']=-4;
map['G']['A']=-2;map['G']['C']=-3;map['G']['G']=5;map['G']['T']=-2;map['G']['-']=-2;
map['T']['A']=-1;map['T']['C']=-2;map['T']['G']=-2;map['T']['T']=5;map['T']['-']=-1;
map['-']['A']=-3;map['-']['C']=-4;map['-']['G']=-2;map['-']['T']=-1;//map['-']['-']=-3;
}
int main()
{
int i,j,t,len1,len2;
char q1[500],q2[500];
match();
scanf("%d",&t);
while(t--)
{
scanf("%d %s",&len1,q1+1);
scanf("%d %s",&len2,q2+1);
memset(max,0,sizeof(max));
max[0][0]=0;
for(i=1;i<=len1;i++)
//max[i][0]=map[q1[i]]['-'];//哎 这里初始化搞错了 阿弥陀佛
max[i][0]=max[i-1][0]+map[q1[i]]['-'];
for(j=1;j<=len2;j++)
// max[0][j]=map['-'][q2[j]];
max[0][j]=max[0][j-1]+map['-'][q2[j]];
for(i=1;i<=len1;i++)
for(j=1;j<=len2;j++)
{
max[i][j]=(max[i-1][j-1]+map[q1[i]][q2[j]])>(max[i-1][j]+map[q1[i]]['-'])?
(max[i-1][j-1]+map[q1[i]][q2[j]]):(max[i-1][j]+map[q1[i]]['-']);
max[i][j]=max[i][j]>(max[i][j-1]+map['-'][q2[j]])?max[i][j]:(max[i][j-1]+map['-'][q2[j]]);
}
printf("%d\n",max[len1][len2]);
}
return 0;
}
分享到:
相关推荐
HDU的一题........HDU DP动态规
动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时,...
HDU上DP大集合,里面包括题,题解,代码,对DP入门者很实用,对DP老手也是有很大的提高
动态规划DP题解 POJ HDU部分动态规划DP题解
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
hdu 1005.比较简单的一道题,有兴趣的可以看看。
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的ACM,非常的好 涉及了很多算法,例如二分匹配、博弈、组合、最小生成树、搜索、动态规划、贪心算法
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu1290 解题报告 献给杭电五十周年校庆的礼物 (切西瓜问题,即平面分割空间)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu acm讲义 很经典 很多专题
hdu 1166线段树代码