分子量分解问题的参考解答.doc

一、分子量分解问题1. 问题的提出 生命蛋白质是由若干种氨基酸经不同的方式组合而成。在实验中，为了分析某个生命蛋白质的分子组成，通常用质谱实验测定其分子量x(正整数)，然后将分子量x分解为n个已知分子量ai(i=1,.,n)氨基酸的和的形式。某实验室所研究的问题中：n=18, x1000ai(i=1,.,18)分别为57, 71, 87, 97, 99, 101, 103, 113, 114, 115, 128, 129, 131, 137, 147, 156, 163, 186要求针对该实验室拥有或不拥有计算机的情况作出解答。2问题的分析 上述问题就是要将任意给定的正整数表示为若干已知正整数的倍数之和，亦即求解下列不定方程 （1）其中x是已知蛋白质的分子量，ai代表第i种氨基酸的分子量，xi代表该种蛋白质中所含第i种氨基酸的个数。 根据题意，我们作以下几点分析： （A1）对一些给定的值x，不定方程(1)可能无解；但对实际问题，应有解，若出现无解，说明数值x有偏差，应重新测定。 （A2）以m表示(1)右端x的上界。此时m=1000, n=18, 考虑用穷举法求出全部解，这时，每个mi的取值范围为0xi m/ai，所以穷举的次数要达到O(mn)，实际为 故穷举法在实际上是不可行的。 (A3) 考虑分解x的一个反问题，将若干个分子量ai(i=1,2,.,n)经组合，构成更大分子量的蛋白质，从中寻找具有分子量x的各种构成。 (A4) 若实验室没有计算机，我们事前仍可利用计算机求得一些便于查阅的工具或表格供实验室工作人员使用。3 .模型的建立（I）深度、广度搜索 先从穷举法着手，对给定的m,将其分解为ai的组合形式，具体过程可以分为深度搜索和广度搜索两种方式。但这两种方式，一方面计算量随着m的增大而指数增加，另一方面，面对几万、几十万种组合，无法方便筛选。（II）启发式搜索 考虑（A3）中的思想，对ai(i=1,2,.,n)不断求和。看是否能达到x？由于在求和中只考虑和数小于m的范围，因此对每个ai的求和过程的计算工作量为O(m)，整个求和过的计算工作量为O(mn)，这比穷举法的计算量O(mn)要少得多。 为了实现上述方法，先引入下列定义： Y=x|xm,x使（1）有解，x为正整数 L(ai)=0,ai,2ai,.,m/ai.ai 定义一种运算 其中U可为1，2，m的任何子集。开始令Y=，然后对i=1，2，n用下列运算不断扩大集合Y： Y：=Y 定义数组bi（i=1，2，m），开始时一切bx=0，若在求和过程中得到一个x，则令bx=1，表示该x的不定方程（1）有解：定义另一种数组si（i=1,2, ，m）,开始时一切sx=0, 以后在求和过程中每次得到一个x, 就令sx:= sx+1, 这样最终得到的sx相等于该x的不定方程(1)的解的个数.然而, 我们不仅要得到解的个数, 还要求得所有的解, 因此在求和过程中还应记录更多的信息。为此对不定方程(1)的解的构造作进一步的分析与提炼。设(x1,x2,xn)为相应于x的(1)非负整数解，又设xq为x1,x2,xn中最后一个非零项，即q1,n使xq+1=xq+2= =xn=0，q称为末项指标, 于是(1)可改写为 从而还可得到 （2） 若记第q个分量为1的n维单位向量为eq. 如果(x1,x2,xn)为相应于x的(1)的解，其末项指标为q，则(x1,x2,xn)-eq为相应于x-aq的(1)的解，其末项指标为pq，考虑到多解的情况，q可能有多种选择，因此在求和过程Y:=Y L(ai)中还应记录末项可能的种数，记为vx(vxn)及相应的末项指标qx,1, qx,2, , qx,vx. 有了一切vx及qx,vx后，我们可以利用（2）不断减少x来跟踪x的所有解的情况。为此将上述v及q，记录为解的跟踪信息表。 下面给出了x186时的跟踪信息表，以示求解的过程。 表1 跟踪信息表的一部分Xsxvxqx,.xsxvxqx,.5711114711157111215411487113156225,1697114158223,6991151601171011161631117103117168114113118170225,81141191711191151110172226,10128222,111741171291112184224,81311113185229,111371114186445,10,12,18144113 以x=170为例，表项指标有两个选择：5，8，由此得到x=170的（1）的两个解为 x=a2+a5, x=a1+a3 又以表中未列出的x=284为例，有关的跟踪信息为 x=284, sx=6, vx=4, qx,1=9, qx,2=11, qx3,=15, qx,4=16这些信息表明：解的总数s=6，末项指标有4种选择，分别为9、11、15、16，利用末项指标的信息，我们利用（2）得到x-a9=170, x-a11=156, x-a15=137, x-a16=128再对上述所得的4个数继续往前利用表1关于它们的跟踪信息，使末项指标不断下降，可得如下6个解： x=a2+a5+a9; x=a1+a8+a9; x=a1+a5+a11; x=a14+a15; x=a1+a2+a16; x=a11+a16 上述跟踪方式的求解步骤，可描述为一棵树，可以据此编制出一个完整的程序。对x1000, 解的个数最多可达几百个。 但对于没有计算机的实验室，我们可以给出xm(如x1000)的跟踪信息表用手算来实现跟踪也是可行的。4 .进一步讨论 因算法的计算量为O（mn），故计算时间上是可行的。由于存储解的跟踪信息表需一个mn的矩阵q，所以空间需求为O（mn），当m与n很大时，可以用压缩存放来发掘潜力。其次，实验得到的蛋白质分子量x有偏差时的情况是有实际意义的。如果偏差不超过3，则可对x、x1、x2、x3分别求解，其结果供决策人员