《分子量分解问题》

分子量分解问题组号：第12小组程引0905020322算法设计论文撰写刘静伟0907060104C程序编程论文撰写李海欣0905020329matlaB程序实现1问题提出生命蛋白质是由若干种氨基酸经不同的方式组合而成。在实验中，为了分析某个生命蛋白质的分子组成，通常用质谱实验测定其分子量x(正整数)，然后将分子量x分解为n个已知分子量a[i](i=1,2……n)氨基酸的和的形式。某实验室所研究的问题中：n=18,x1000a[i](i=1,2……18)分别为57,71,87,97,99,101,103,113,114,115,128,129,131,137,147,156,163,186要求针对该实验室拥有或不拥有计算机的情况作出解答。2问题分析问题本身有一些不符合实际的情况如下：1）氨基酸组成蛋白质的时候会失去一分子的水，而且氨基酸组合方式不同形成不同形状的蛋白质如链形、环形等会失去不同个数的水分子；2）蛋白质水解的程度不同所得到的氨基酸分子的质量也不同；3）蛋白质中有些氨基酸是相互依存的，即，一种氨基酸的存在是以其他某一种或某几种氨基酸的存在为前提的；4）当给定的蛋白质重量增加时，所得到的解的个数可能成指数倍数上升，计算量庞大3模型假设针对2中对问题的分析，我们做一下假设：1）不考虑蛋白质水解时水分子的量，即，给定的蛋白质分子量就是几个已知分子量的和。2）不考虑蛋白质水解程度的不同；3）被测定的蛋白质仅由给定分子量的氨基酸组成，而不含有其他物质或元素4）氨基酸组合成蛋白质的过程是任意排列组合的，一种氨基酸的存在不是以其他某一种或某几种氨基酸的存在为前提的；4模型分析与建立给定蛋白质的分子量X和各种氨基酸的分子量a(i)，测定蛋白质的组成，即求解n元线性方程Xxanii1i的所有整数解的问题。当n=18时即为本题所要求解的问题Xxaii181i①ix是非负整数(i=1,2,3……18)再拥有和不拥有计算机的情况下可以使用不同的算法，，这里分别为“优化穷举法”和“矩阵”解法4.1在拥有计算机的情况下求解——“优化穷举法”利用传统穷举法，我们可以先计算给定的蛋白质分子量X包含ia的最多的个数[X\ia]，即ix{0,1,2…[X\ia]}，所以当全部结果都列举出来时，利用排列组合可以算出，要穷举的次数为]\[181iiaX,当X=1000时将达到2.4*10^17次，显然在实际计算中是不可行的。我们可以发现，在传统穷举法中有些运算得出的结果是超过给定的蛋白质分子总量X的，比如当1-ia取到[X\1-ia]时，ia不可能取到[X\ia]（i=18）；也有些运算结果虽然不比X大但是远小于给定的蛋白质分子总量X的，例如当ix都取0时。这些都是造成运算时间延长的多余运算量，而且X越大多余的运算次数越多。所以我们没必要简单的把每一个可能的运算都列出来，如果我们把这些和数超出X的运算次数和都除去就可以大大的减少运算次数。因此聪明和这个思想出发，我们可以反向思考问题，不是把每一各氨基酸的分子量相加得到的数和X相比较，而是把X拆分，直到拆分到X的分子量为零，或者小于其中任何一个氨基酸的分子量。于是得到不同个数的氨基酸分子组合，那些可以把拆分到X的分子量为零的组合就是其中一个解。例如X=500可以拆分2个186，还剩128，拆分出1个128，还剩0，故ix={0，0，0，0，0，0，0，0，0，0，1，0，0，0，0，0，0，2}是一组解，如果把X拆分出1个186，还剩314，可以再拆分出1个163，还剩153，再拆分出1个147，还剩6，此时X小于其中任何一个氨基酸的分子量，于是ix={0，0，0，0，0，0，0，0，0，0，0，0，0，0，1，0，1，1}不是X=500的解。求解数据见下表：X的值解的个数花费时间10000.00020040.000300140.001400450.0015001580.0026005220.00570015080.01280042910.030900112490.0771000282680.191N-X拟合曲线图N-T拟合曲线图4.2在不用有计算机的情况下求解——“矩阵”解法对方程①，可按以下矩阵法求解：列n1n的矩阵：eeeaaAn000000a21，对其进行有限次换元、消去列初等变换可得：'121'2122221'1111211d000nnnnnnnnnnCCCCCCCCCCCCB其中d=(naaa，，，21)设d=dX，XCCinin''则将B的第n列乘以X得'121'2122221'1111211d000nnnnnnnnnnCCCCCCCCCCCCC则方程①的通解为：nnnnnnnnnnnnnnCKCKCKCxCKCKCKCxCKCKCKCx1122112112222121211112121111iK可取I内任意非负整数，将这些整数带入到通解中便可以得到解ix的组合。5模型推广本文通过通用模型的分析与建立，对有关求解n元一次方程的同类问题有一定的可适用性和指导意义。6结论本文采用C语言，优化了算法，相对减少了运算量，提高了运行效率，缩短了运算时间，但是随着X的增大，接的个数和运算时间迅速增加，因此运算程序还有待改进之处。对于改进的方向，主要是使运算中涉及非解组合的个数减少，或寻找有效的减少变量的方法，简化求解过程，再者增加一定的有效的约束条件，限制ix的取值范围。7参考文献[1]赵静，但琦.数学建模与数学实验[M]，北京：高等教育出版社，2008[2]谭浩强.C程序设计[M]，北京：清华大学出版社，2005附录C语言程序代码一：求解的个数和所用时间#includestdio.h#includetime.h#includestdlib.h#defineX1000intm[18]={0};inta[18]={57,71,87,97,99,101,103,113,114,115,128,129,131,137,147,156,163,186};intx[18]={0};intn=0;digui(intx1,inta1,intm1,inti){intml;for(x1=m1/a1;x1=0;x1--){ml=a1*x1;m[i-1]=m1-ml;x[i]=x1;if(m[i-1]==0)n=n+1;else{if(i-10)digui(x[i-1],a[i-1],m[i-1],i-1);elseif(i-1==0){x[0]=m[0]/a[0];if(x[0]*a[0]==m[0])n=n+1;}}}}main(){clock_tstart,finish;start=clock();m[17]=X;digui(x[17],a[17],m[17],17);printf(所以当X=%d时，有%d个解\n,X,n);finish=clock();printf(Itcosts%fseconds\n,difftime(finish,start)/1000);}C语言程序代码二：求解的个数和每个x(i)的值#includestdio.h#defineX800intm[18]={0};inta[18]={57,71,87,97,99,101,103,113,114,115,128,129,131,137,147,156,163,186};intx[18]={0};intn=0;digui(intx1,inta1,intm1,inti){intml,j;for(x1=m1/a1;x1=0;x1--){ml=a1*x1;m[i-1]=m1-ml;x[i]=x1;if(m[i-1]==0){n=n+1;for(j=0;j18;j++)printf(x[%d]=%3d,j+1,x[j]);printf(\n\n);}else{if(i-10)digui(x[i-1],a[i-1],m[i-1],i-1);elseif(i-1==0){x[0]=m[0]/a[0];if(x[0]*a[0]==m[0]){n=n+1;for(j=0;j18;j++)printf(x[%d]=%3d,j+1,x[j]);printf(\n\n);}}}}}main(){m[17]=X;digui(x[17],a[17],m[17],17);printf(所以当X=%d时，有%d个解\n,X,n);}matlaB程序代码一：N-X拟合曲线N=Columns1through900431474544158Columns10through1820252269415082197429163371124916885Column1928268X=Columns1through9100150200250300350400450500Columns10through18550600650700750800850900950Column191000eq=Inlinefunction:eq(a,x)=a(1)*exp(a(2)*x)+a(3)matlaB程序代码二：N-T拟合曲线T=Columns1through6000000Columns7through1200000.01500.0150Columns13through180.01500.02000.03000.04000.08000.1200Column190.1870X=Columns1through5100150200250300Columns6through10350400450500550Columns11through15600650700750800Columns16through198509009501000eq=Inlinefunction:eq(a,x)=a(1)*exp(a(2)*x)+a(3)