qq_37002610
李小小白
采纳率100%
2016-12-12 14:37

新人c++编程问题求助 相似基因序列问题

已采纳

Description
众所周知,人类基因可以看作一个碱基对序列,它包含了4种核苷酸,简记为A,C,G,T。让我们观察这样一段基因序列 “ACCAGGTT”,这段序列共由8个核苷酸构成,其中第1位和第4位是碱基“A”,第2位和第3位是碱基“C”,第5位和第6位是碱基“G”,第7位和第8位是碱基“T”。Tom构造了这样一个0,1矩阵:

1, 0, 0, 1, 0, 0, 0, 0

0, 1, 1, 0, 0, 0, 0, 0

0, 1, 1, 0, 0, 0, 0, 0

1, 0, 0, 1, 0, 0, 0, 0

0, 0, 0, 0, 1, 1, 0, 0

0, 0, 0, 0, 1, 1, 0, 0

0, 0, 0, 0, 0, 0, 1, 1

0, 0, 0, 0, 0, 0, 1, 1

如果第i位的碱基与第j位的碱基一样,那么0,1矩阵的i行j列为1,否则为0。如果基因序列X与基因序列Y等长且具有相同的0,1矩阵,Tom就会认为X与Y是相似的基因序列。 现在的问题是:给你两段长度为N的基因序列,请你帮助Tom判断它们是否相似。

Input
可以有多组测试数据,每组数据第1行输入一个正整数N(1≤N≤1000000),第2行和第3行分别输入两段长度为N的基因序列(只由A,C,G,T四种字符构成)。输入直至N=0为结尾。

Output
每组数据输出仅一行,如果相似则输出 YES,否则输出 NO。

Sample Input
2
AA
TG
6
ACCGTT
GAATCC
0

Sample Output
NO
YES

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享
  • 邀请回答

7条回答

  • zhagoodwell zhagoodwell 5年前

    首先找规律用矩阵是不行的 利用率不高 代码如下 如有问题可以联系我:嘿嘿 ,我编的有不足的地方 但结果是对的;

    include

    include

    define N 10001 //如果想录入x个字节那么就把N的数值改成x+1

    int gainchar(char *a,int min,int max);//返回字符串长度
    int BF(char a[],char b[],int *d);//a为主串,b为被检验的串,d为从第几个开始,d[0]不用
    void main(){
    int i,j,length[2],*p[4]={NULL,NULL,NULL,NULL};
    int pipei[8][N]={0,0,0,0,0,0,0,0};//初始化
    char a[2][N];
    char SS[][3]={"一","二"},moban[][2]={"A","C","G","T"};
    for(i=0;i do{
    printf("输入第%s个基因大写序列:长度(1--%d)\n",SS[i],N-1);
    length[i]=gainchar(a[i],1,N);
    if(i&&length[0]-length[1])
    printf("两个基因序列长度不等,请重新");
    }while(i&&(length[0]-length[1]));
    for(i=0;i for(j=0;j pipei[i*4+j][0]=BF(a[i],moban[j],pipei[i*4+j]);
    for(i=0;i for(j=4;j if(pipei[i][1]==pipei[j][1]&&pipei[i][0]==pipei[j][0])
    p[i]=&pipei[j][0];
    if(p[0]&&p[1]&&p[2]&&p[3]) //如果是一一对应则继续检查
    {
    for(i=0;i for(j=0;j if(pipei[i][j]!=p[i][j])
    printf("NO!");
    if(i==4) //如果检查完了没问题 则为YES
    printf("YES!");
    }
    else
    printf("NO");//如果不是一一对应则NO
    return 0;
    }
    int gainchar(char *a,int min,int max)//对*a输入范围(min,max),如果字符数组中存在'\n',将其改为'\0'
    {
    int c;
    do{
    fgets(a,max,stdin);
    c=strlen(a);
    c=a[c-1]=='\n'&&c if(c>=max-1)
    while(getchar()!='\n');
    else
    a[c]='\0';
    if(c&&(c>max||c printf("输入有误,请重新输入只录入(%d--%d)字节:\n",min,max-1);
    }while(c>max||c<min);
    return c;
    }
    int BF(char *a,char *b,int *d)//a为主串,b为被检验的串,d为匹配的下标
    {

    int c[2];
    int i=0,j=0,k=1;
    c[0]=strlen(a);
    c[1]=strlen(b);

    while (i <=c[0])
    if(a[i]==b[j]&&j<c[1])
    {
    i++;
    j++;
    }
    else
    {
    if(j==c[1])
    d[k++]=i-c[1];
    else
    i-=j-1;
    j=0;
    }
    return k; //返回匹配的个数k
    }

    点赞 2 评论 复制链接分享
  • qq_37002610 李小小白 5年前

    个人想法是将XY序列中A,T,C,G的个数都分别算出,然后按个数将它们换成字符1,2,3,4,然后比较XY序列。但表达不了,求各位大神指教。

    点赞 1 评论 复制链接分享
  • zhagoodwell zhagoodwell 5年前

    代码被弄的不全了 我重新写了一下 过会森和通过就有了 地址:http://my.csdn.net/

    点赞 评论 复制链接分享
  • csdncqmyg csdncqmyg 5年前

    伪代码给你写一个。。 arry代表你的基因段 num代表数组矩阵
    a[N]=arry;
    num[N][N]={0};
    for i in 0 to N
    for j in 0 to N
    if a[i]=a[j] num[i][j]=1

    点赞 评论 复制链接分享
  • zhagoodwell zhagoodwell 5年前

    晚上给你代码和解释图片说明

    点赞 评论 复制链接分享
  • chenruicsdn DogeAndCat 5年前

    ATCGATCG的矩阵是这样的
    1, 0, 0, 0, 1, 0,0,0
    0, 1, 0, 0, 0, 1,0,0
    0, 0, 1, 0, 0, 0,1,0
    0, 0, 0, 1, 0, 0,0,1
    1, 0, 0, 0, 1, 0,0,0
    0, 1, 0, 0, 0, 1,0,0
    0, 0, 1, 0, 0, 0,1,0
    0, 0, 0, 1, 0, 0,0,1

    而AACCGGTT的矩阵是这样的
    1, 1, 0, 0, 0, 0,0,0
    0, 0, 1, 1, 0, 0,0,0
    0, 0, 0, 0, 1, 1,0,0
    0, 0, 0, 0, 0, 0,1,1
    1, 1, 0, 0, 0, 0,0,0
    0, 0, 1, 1, 0, 0,0,0
    0, 0, 0, 0, 1, 1,0,0
    0, 0, 0, 0, 0, 0,1,1
    所以并不是都是 11111111

    点赞 评论 复制链接分享
  • chenruicsdn DogeAndCat 5年前

    遍历数组,逐一比较,若a[i]和a[j]相同,直接赋值为1 遍历完了之后,所有不为1的空间,全部赋值为0.

    点赞 评论 复制链接分享