实验报告 4
实验名称:数据结构与软件设计实习
题 目:双序列比对得分矩阵的实现
专业:生物信息学 班级:01 姓名: 学号:实验日期:2010.07.24
一、实验目的:
设计动态规划算法程序
得分矩阵的实现
二、实验要求:
列出基本递归方程:
F(i-1, j-1)+σ(S[i],T[j])
F(i,j)=max F(i-1,j)+σ(-,T[i])
F(i,j-1)+σ(S[i],-)
由初始值开始,求出整个比对过程的最优解。
三、实验内容:
对于两个序列 S 和 T,令[S]和[T]分别为序列 S 和 T 的长度,S[i]和 T[j](其中正整数 i,j 满足 0≤j<
[S]和 0≤j <[T])都属于字符集 Ω={A,T,C,G,-},对 Ω 中的任何元素和空符号。
设计 S[i]和 T[j]两两之间的一个记分值来比较序列间的同一性的优劣,用记分函数 σ(x,y)表示,
σ(S[i],T[j])=2 ( S[i]=T[j]≠-) ; σ(S[i],T[j])= -1 ( S[i]≠T[j],S[i]≠-,T[j]≠-) ; σ(S[i],T[j])= -2
(S[i]orT[j]=-)。
四、实验编程结果或过程:
1. 数据定义
typedef struct
{
char bp[k];
int size;
}sequence;
2. 函数如下,代码详见文件“序列比对打分矩阵.cpp”
int pairs(sequence &seq1,sequence &seq2,int
i,int j)
{
int d=0;
if(seq1.bp[j-1]==seq2.bp[i-1])
d=3;
else
d=-1;
return d;
}
int domax(int a,int b,int c)
{
if(a>=b&&a>=c)
return a;
else
if(b>=a&&b>=c)
return b;
else
return c;
}
void alig(sequence &seq1,sequence &seq2,int
db[][k])//比对
{
int a=0,b=0,c=0;
for(int i=0;i<=seq1.size;i++)
db[0][i]=0-i*2;
for(int j=0;j<=seq2.size;j++)
db[j][0]=0-j*2;
for(int m=1;m<=seq2.size;m++)
{
for(int n=1;n<=seq1.size;n++)
{
a=db[m][n-1]-2;
b=db[m-1][n]-2;
c=db[m-1][n-
1]+pairs(seq1,seq2,m,n);
db[m][n]=domax(a,b,c);
}
}
}
评论4