当前位置: 代码迷 >> C语言 >> [讨论]需求分析
  详细解决方案

[讨论]需求分析

热度:390   发布时间:2006-09-07 13:26:00.0
[讨论]需求分析

需求分析

本程序中序列就是字符串,两者表达的意思相同。
本程序最终所要实现的功能:
在多个字符串中查找指定长度的具有一定模式匹配(该匹配可以是子字符串完全匹配或者是允许个别几个字符不匹配(不匹配的位置可以人为指定))的子字符串,并输出所有满足要求的子序列。


具体问题描述:
1、有一组字符串,每个字符串的长度相等为w(但w不确定为何值),字符串元素由{A , T , C , G}四个字母组成。字符串组的来源可以是文本格式或其他(不限);
2、寻找其中满足一定匹配模式的指定长度L(可自己指定)的子串。


表达方式:
序列是由 { A, C, T, G } 四个字母构成的。例如对于以下两条序列(字符串):
: A T T A G T C A T
: A T T G A C G C A
当寻找长度为3,允许的不匹配度为0时, “A T T” 就是所要找的子字符串。当要求寻找长度为4,允许的不匹配度为1时,A T T A 和A T T G就是所要找的子字符串。


定 义:
(1)给定一组序列{ },其中n为输入的序列个数。 , ,w为序列的长度。
(2)将一段长度为L的子序列转化为点,即 ,i指序列,j指第i条序列上子序列(子字符串)开始的位置。
例如:对于上面的两条序列 (当L取值为3时)有:
: ATT--- TTA--- TAG--- AGT--- GTC---- TCA---- CAT-----
:ATT--- TTG--- TGA--- GAC--- ACG--- CGC---- GCA---
(3)距离 ,如果 ,则 ,否则 。
例如:对于上面序列的点 和点 来说,有 (即不相等的字符的个数)
(4)父节点parent( ) :对于 上的点 而言, 上的点都为它的父结点。
(5)邻节点neighbor( ):对于 上的点 而言,只有 上的节点成为它的邻节点。


具体步骤:分为两个子程序。

子程序一:
(1) 输入一组序列 (n可以自己指定)
(2) 从第一条序列开始,定义节点 。
(3) 对于其他序列,重复执行步骤2。直到第n条序列。
(4) 对于第一条序列上的第一个点 (将其放入集合 中,即 ),检查该点与其它序列上的每个点的距离 , 如果 ,则将 加入 ,即有 ,其中i指第i条序列,j指在第i条序列上节点开始的位置。对第二条到第n条序列上的节点重复进行与点 的距离比较,满足条件就加入,从而得到最终的集合 。
(5) 对于第一条序列上的其它点,重复执行步骤4,得到其它点所对应的集合 。

子程序二:
(1) 对于每一个 。
(2) 按顺序查找它包括的第二条、第三条、……、第n条序列上的节点的父节点列表(parentlist ,其中j指在 中的第二条序列上的点)。并且在第n条序列的节点的父节点列表中,统计每个节点所代表的子字符串中相应位置出现频率最高的字母,从而得到最终想要的结果子序列并进行输出。
注:通过递归调用得到节点 的父节点列表parentlist :当节点 与其邻点的距离小于等于2d时,将邻点及其父节点列表加入节点 的父节点列表parentlist 。同时比较节点 与邻点的父节点列表中的其它节点 的距离,如小于等于2d,则保留,否则删除此节点 与它的父节点列表parentlist 。对于第一条序列上的节点其父节点列表为它本身。
跳出递归循环的条件:当某一条序列上的所有点 的邻点都不满足条件时、或当程序执行到最后一条序列时。
(3)对于其他 ,重复步骤2。

搜索更多相关的解决方案: 字符  需求  序列  长度  

----------------解决方案--------------------------------------------------------

以下为本人胡乱编的程序,有错误,但不知道如何改,请各位高手指教!

#include <string.h>
#define n 5
#define w 10
#define L 3
#define m 100
int i,j,u,v,k;
char s[n][w],V[n][w-L+1],g[w-L+1][m];

int dis(V[i][j],V[u][v])
{
int d=0;
for(i=1;i<=n;i++)
for(j=1;j<=w-L+1;j++)
for(u=1;u<=n;u++)
for(v=1;v<=w-L+1;v++)
for(k=0;k<=L-1;k++)
if(s[i][j+k]!=s[u][v+k])
d++;
return d;
}

char parent(V[i][j])
{
char p[m][m]={};
for(u=1;u<=i-1;u++)
for(v=1;v<=w-L+1;v++)
strcat(p[u][],V[u][v]);
return (p[u][]);
}

char neighbor(V[i][j])
{
char neighbor[m][m]={};
for(v=1;v<=w-L+1;v++)
strcat(neighbor[v][],V[i-1][v]);
return (neighbor[v][]);
}

char parentlist(V[i][j])
{
char parentlist[m][m]={};
for(j=1;j<=w-L+1;j++)
parentlist(V[1][j])=V[1][j];
for(i=2;i<=n;i++)
for(j=1;j<=w-L+1;j++)
{
if(dis(V[i][j],neighbor(V[i][j]))<='2'&&dis(V[i][j],parentlist(neighbor(V[i][j]))<='2')
{
parentlist[i][]=strcat(parentlist[i][],neighbor(V[i][j]));
parentlist[i][]=strcat(parentlist[i][],parentlist(neighbor(V[i][j]));
}
else
break;
}
return (parentlist[i][]);
}

main()
{
int h,max=0,A[L],C[L],T[L],G[L];
char put[m][L],result[m][L],parentlist[m][m];

for(i=1;i<=n;i++)
for(j=1;j<=w;j++)
scanf("%s",&s[i][j]);
for(i=1;i<=n;i++)
for(j=1;j<=w-L+1;j++)
for(k=j;k<=j+L;k++)
V[i][j]=strcat(s[i][k],s[i][k+1]);
for(i=1;i<=w-L+1;i++)
g[i][]=V[1][i];
for(i=1;i<=w-L+1;i++)
for(j=2;j<=n;j++)
for(k=1;k<=w-L+1;k++)
if(dis(V[1][i],V[j][k])<='2')
g[i][]=strcat(g[i][],V[j][k]);


for(i=1;i<=L;i++)
A[i]=C[i]=T[i]=G[i]=0;
h=1;
for(j=1;j!='\0';j++)
{
put[h][((j-1)%L)+1]=parentlist[n][j];
if(j%L=='1')
h++;
}
for(i=1;i<=h;i++)
for(j=1;j<=L;j++)
{
if(put[i][j]=='A')
A[j]++;
if(put[i][j]=='C')
C[j]++;
if(put[i][j]=='T')
T[j]++;
if(put[i][j]=='G')
G[j]++;
}
for(i=1;i<=L;i++)
{
if(max<A[i])
max=A[i];
if(max<C[i])
max=C[i];
if(max<T[i])
max=T[i];
if(max<G[i])
max=G[i];
h=1;
if(max==A[i])
{
for(j=1;j<=h;j++)
if(put[j][i]=='A')
result[h++][]=put[j][];
}
else if(max==C[i])
{
for(j=1;j<=h;j++)
if(put[j][i]=='C')
result[h++][]=put[j][];
}
else if(max==T[i])
{
for(j=1;j<=h;j++)
if(put[j][i]=='T')
result[h++][]=put[j][];
}
else
{
for(j=1;j<=h;j++)
if(put[j][i]=='G')
result[h++][]=put[j][];
}
printf("The result is :\n");
for(i=1;i<=h;i++)
{
for(j=1;j<=L;j++)
printf("%s",result[i][j]);
printf("\n");
}
}


----------------解决方案--------------------------------------------------------
  相关解决方案