Human Gene Functions
Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1892Accepted Submission(s): 1083
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
Source
题意:
给你你两个DNA串。s1,s2.然后给你对应腺苷组合所产生的价值。你可以在两个串中加空格。问你能产生的最大价值。
思路:
与经典的LCS相似。dp[i][j]表示处理好s1的前i个位置和s2的j个位置的最大价值。
若匹配s1与s2的第j个位置。
dp[i][j]=dp[i-1][j-1]+val[i][j]。val[i][j]为i,j组合产生的价值。
若不匹配。
dp[i][j]=dp[i-1][j]+val[i][-]。由于s1的i位置不和前s2的位置j匹配只能和-匹配了。
dp[i][j]=dp[i][j-1]+val[-][j]。由于s2的j位置不和s1的前i个位置匹配。。。。
详细见代码:
#include <iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
const int maxn=110;
int dp[maxn][maxn],gen1[maxn],gen2[maxn];
char s[maxn];
int val[5][5]=//记录价值
{
5,-1,-2,-1,-3,
-1,5,-3,-2,-4,
-2,-3,5,-2,-2,
-1,-2,-2,5,-1,
-3,-4,-2,-1,0xcfcfcfcf
};
int flect(char c)//建立映射
{
if(c=='A')
return 0;
else if(c=='C')
return 1;
else if(c=='G')
return 2;
else
return 3;
}
int main()
{
int i,j,t,len1,len2;
scanf("%d",&t);
// for(i=0;i<5;i++)
// {
// for(j=0;j<5;j++)
// printf("%d ",val[i][j]);
// printf("\n");
// }
while(t--)
{
scanf("%d%s",&len1,s);
for(i=0;i<len1;i++)
gen1[i+1]=flect(s[i]);
scanf("%d%s",&len2,s);
for(i=0;i<len2;i++)
gen2[i+1]=flect(s[i]);
dp[0][0]=0;
for(i=1;i<=len1;i++)//注意要初始化
dp[i][0]=dp[i-1][0]+val[gen1[i]][4];
for(i=1;i<=len2;i++)
dp[0][i]=dp[0][i-1]+val[4][gen2[i]];
for(i=1;i<=len1;i++)
{
for(j=1;j<=len2;j++)
{
dp[i][j]=max(dp[i-1][j]+val[gen1[i]][4],dp[i][j-1]+val[4][gen2[j]]);
dp[i][j]=max(dp[i-1][j-1]+val[gen1[i]][gen2[j]],dp[i][j]);
}
}
printf("%d\n",dp[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 1005.比较简单的一道题,有兴趣的可以看看。
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
图论〔Graph Theory〕是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系,用点代表事物,用连接两点的线表示相应两个...
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
lazycal的集训队报告:初探数位DP 以HDU 2089,HDU 3652, URAL 1057等题目为例,介绍了数位DP的算法
hdu 1166线段树代码