MENU

P1140 相似基因

August 25, 2022 • Read: 139 • 编程

题目背景

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

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

题目描述

两个基因的相似度的计算方法如下:

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

41.png

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

40.png

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

42.png

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

7 AGTGATG
5 GTTAG

样例输出 #1

14

代码

#include<iostream>
#include<algorithm>
using namespace std;
int la,lb,a[110],b[110],f[110][110];
int d[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 main()
{
    cin>>la;
    for(int i=1;i<=la;i++)
    {
        char t;
        cin>>t;
        switch(t)
        {
        case 'A':
            a[i]=1;break;
        case 'C':
            a[i]=2;break;
        case 'G':
            a[i]=3;break;
        case 'T':
            a[i]=4;break;
        }
    }
    cin>>lb;
    for(int i=1;i<=lb;i++)
    {
        char t;
        cin>>t;
        switch(t)
        {
        case 'A':
            b[i]=1;break;
        case 'C':
            b[i]=2;break;
        case 'G':
            b[i]=3;break;
        case 'T':
            b[i]=4;break;
        }
    }
    f[0][0]=0;
    for(int i=1;i<=la;i++)
        f[i][0]=f[i-1][0]+d[a[i]][5];
    for(int i=1;i<=lb;i++)
        f[0][i]=f[0][i-1]+d[5][b[i]];
    for(int i=1;i<=la;i++)
        for(int j=1;j<=lb;j++)
            f[i][j]=max(f[i-1][j-1]+d[a[i]][b[j]],max(f[i-1][j]+d[a[i]][5],f[i][j-1]+d[5][b[j]]));
    cout<<f[la][lb]<<endl;
    return 0;
}
Archives QR Code
QR Code for this page
Tipping QR Code
Leave a Comment

已有 1 条评论
  1. 我最近在做类似的内容,直接用了python的distance包计算Levenshtein距离