相似基因（动态规划）-白红宇

相似基因（动态规划）

阅读量：7199 次

发布时间：2019-06-29

本文共 1546 字，大约阅读时间需要 5 分钟。

相似基因

时间限制: 1 Sec 内存限制: 128 MB

提交: 19 解决: 12

[][][]

题目描述

大家都知道，基因可以看作一个碱基对序列。它包含了4种核苷酸，简记作A,C,G,T。生物学家正致力于寻找人类基因的功能，以利用于诊断疾病和发明药物。

在一个人类基因工作组的任务中，生物学家研究的是：两个基因的相似程度。因为这个研究对疾病的治疗有着非同寻常的作用。两个基因的相似度的计算方法如下：

对于两个已知基因，例如AGTGATG和GTTAG，将它们的碱基互相对应。当然，中间可以加入一些空碱基-，例如：

A	G	T	G	A	T	-	G
-	G	T	-	-	T	A	G

这样,两个基因之间的相似度就可以用碱基之间相似度的总和来描述，碱基之间的相似度如下表所示：

那么相似度就是：(-3)+5+5+(-2)+(-3)+5+(-3)+5=9。因为两个基因的对应方法不唯一，例如又有：

A	G	T	G	A	T	G
-	G	T	T	A	-	G

相似度为：(-3)+5+5+(-2)+5+(-1)+5=14。规定两个基因的相似度为所有对应方法中，相似度最大的那个。

输入

共两行。每行首先是一个整数，表示基因的长度；隔一个空格后是一个基因序列，序列中只含A,C,G,T四个字母。1<=序列的长度<=100。

输出

仅一行，即输入基因的相似度。

样例输入

7 AGTGATG5 GTTAG

样例输出

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #include
                    
                     #define mod 1000000007#define inf 0x3f3f3f3f#define pi acos(-1.0)using namespace std;typedef long long ll;const int N=500005;const int M=1005;ll power(ll a,int b,ll c) {ll ans=1;while(b) { if(b%2==1) {ans=(ans*a)%c;b--;}b/=2;a=a*a%c;}return ans;}int s[6][6]= { { 0,0,0,0,0,0}, { 0,5,-1,-2,-1,-3}, { 0,-1,5,-3,-2,-4}, { 0,-2,-3,5,-2,-2}, { 0,-1,-2,-2,5,-1}, { 0,-3,-4,-2,-1,0}};int change(char a) { if(a=='A') return 1; if(a=='G') return 3; if(a=='C') return 2; if(a=='T') return 4; else return 5;}int main() { int a1,b1; string as,bs; int a[101],b[101]; int dp[101][101]; cin>>a1>>as>>b1>>bs; for(int i=0; i

View Code

转载于:https://www.cnblogs.com/jianrenfang/p/5774975.html

你可能感兴趣的文章

读书笔记2013第9本：《注意力曲线----打败分心与焦虑》