Human Gene Functions
Time Limit: 1000MS |
|
Memory Limit: 10000K |
Total Submissions: 10904 |
|
Accepted: 6015 |
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 file. 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
14
21
Source
题意:ATGC和空格互相对应有不同的分数(见表)
现在要求串1 和 串2匹配的最大分数
思路:最长公共子序列,不过状态方程有一点点出入
边界:
dp[i][0]=dp[i-1][0]+w(a[i],'-');
dp[0][i]=dp[0][i-1]+w(b[j],'-');
状态转移方程:
dp[i][j]=dp[i-1][j-1]+w(a[i],b[j]);
dp[i][j]=max(dp[i][j],max(dp[i-1][j]+w(a[i],'-'),dp[i][j-1]+w('-',b[j])));
my ugly code:
Source Code
Problem: 1080
|
|
User: bingshen
|
Memory: 172K |
|
Time: 0MS |
Language: C++ |
|
Result: Accepted
|
-
Source Code
#include<stdio.h>
#include<string.h>
char a[105],b[105];
int dp[105][105];
int w[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,0},
};
int num(char x)
{
if(x=='A')
return 0;
if(x=='C')
return 1;
if(x=='G')
return 2;
if(x=='T')
return 3;
}
int max(int a,int b)
{
if(a>b)
return a;
else
return b;
}
int main()
{
int i,j,t,l1,l2;
scanf("%d",&t);
while(t--)
{
memset(dp,0,sizeof(dp));
scanf("%d",&l1);
scanf("%s",a+1);
scanf("%d",&l2);
scanf("%s",b+1);
for(i=1;i<=max(l1,l2);i++)
{
dp[i][0]=dp[i-1][0]+w[num(a[i])][4];
dp[0][i]=dp[0][i-1]+w[4][num(b[i])];
}
for(i=1;i<=l1;i++)
for(j=1;j<=l2;j++)
{
dp[i][j]=dp[i-1][j-1]+w[num(a[i])][num(b[j])];
dp[i][j]=max(dp[i][j],max(dp[i-1][j]+w[num(a[i])][4],dp[i][j-1]+w[4][num(b[j])]));
}
printf("%d/n",dp[l1][l2]);
}
return 0;
}
分享到:
相关推荐
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
poj经典动态规划题目解题报告,包括经典的动态规划题目20多道,可以作为学习动态规划系统的资料,包括题目: Pku acm 1179 Polygon Pku acm 1125 Stockbroker Grapevine Pku acm 1160 post office Pku ...
北大POJ1080-Human Gene Functions POJ1080-Human Gene Functions
北大POJ1080-Human Gene Functions
北大POJ初级-动态规划 解题报告+AC代码
PKU Online Judge上面很全面的动态规划试题总结。动态规划是ACM考点中最重要的一大类算法之一,对于工作人员来说,动态规划也是实际开发中经常会遇到的算法。这是POJ上面很多DP题目的总结与深刻分析。利于算法学习,...
POJ上的DP分类: 容易: 1018, 1050, 1083, 1088, 1125, 1143, 1157, 1163, 1178, 1179, 1189, 1208, 1276, 1322, 1414, 1456, 1458, 1609, 1644, 1664, 1690, 1699, 1740(博弈), 1742, 1887, 1926(马尔科夫矩阵,求...
动态规划算法poj1088滑雪实验报告 动态规划算法poj1088滑雪实验报告
关于poj dp分类,我一直寻找dp的分类,终于找到了,也上传一下
北大POJ1015-Jury Compromise【动态规划DP】 解题报告+AC代码
动态规划DP题解 POJ HDU 动态规划解题报告
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
POJ 动态规划总结 背包之01背包、完全背包、多重背包详解 Dynamic+Programming 典型的动态规划,用递归下的记忆化搜索来实现 1088 POJ 动态规划加速原理之四边形不等式 基于连通性状态压缩的动态规划问题 对一些DP...
POJ 1170 动态规划。欢迎各种交流讨论。
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
动态规划DP题解 POJ HDU部分动态规划DP题解
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码