基于優(yōu)化遞歸算法的分子量分解問題

1、基于優(yōu)化遞歸算法的分子量分解問題摘要：本文討論的問題是：在實驗室擁有或不擁有計算機的情況下，如何將已知分子量x的蛋白質(zhì)分解成18種已知分子量的氨基酸的問題，并滿足蛋白質(zhì)含氮量在15%17%的物理性質(zhì)。在實驗室有計算機的情況下，本文首先考慮了窮舉算法，該問題就等效為十八元一次方程求整數(shù)解的問題，表示為每種氨基酸構(gòu)成蛋白質(zhì)數(shù)量root(i)的上限為+1，取x最大為1000時，有種，運算量過大難以實現(xiàn)。我們又考慮了遞歸算法,即從分子量最大的第18種氨基酸開始考慮，第18種氨基酸分子構(gòu)成蛋白質(zhì)的個數(shù)，對root進行分類取值，在取值已知的情況下再考慮第17種氨基酸，此時分子量減去第18種氨基酸總分子質(zhì)量

2、，得到新的分子量，將大大減少計算量。抽象歸納為的取值圍如下：該算法同樣滿足含氮量的約束條件。我們借助C語言編寫程序并對程序進行優(yōu)化，大大加快了運行速度。 在實驗室無計算機的情況下，由氨基酸的結(jié)構(gòu)通式得出，每個氨基酸都存在結(jié)構(gòu)，分子量為56。本文將18種氨基酸的分子量都減去56，得到18種氨基酸R基的分子量。先將任一分子量除以56取整，得到構(gòu)成該蛋白質(zhì)的氨基酸數(shù)目的圍（即），再根據(jù)b的取值進行分類討論從而選擇R基，后根據(jù)蛋白質(zhì)含氮量對結(jié)果進行驗證，在人工的情況下，此方法相對于遞歸法大減少了計算量。關(guān)鍵詞：分子量分解問題 遞歸優(yōu)化法 含氮量 C語言 結(jié)構(gòu)通式1、問題重述 生命蛋白質(zhì)是由若干種氨基酸

3、經(jīng)不同的方式組合而成。在實驗中，為了分析某個生命蛋白質(zhì)的分子組成，通常用質(zhì)譜實驗測定其分子量x (正整數(shù))，然后將分子量x分解為n個已知分子量ai(i=1,.,n)氨基酸的和的形式。某實驗室所研究的問題中：n=18, x1000，ai(i=1,.,18)分別為57, 71, 87, 97, 99, 101, 103, 113, 114, 115, 128, 129, 131, 137, 147, 156, 163, 186。要求針對該實驗室擁有或不擁有計算機的情況，對如何分解分子量x作出解答，即針對任意一個分子量x具體給出由哪些ai(i=1,.,n)氨基酸組成。 2、問題分析 題目中給出18種

4、氨基酸分子量，要求解出已知分子量的蛋白質(zhì)由哪幾種氨基酸組成。初步分析，這是十八元一次方程求整數(shù)解的問題，方程形式為其中為已知量，為18種氨基酸分子量，未知數(shù)為組成蛋白質(zhì)的每種氨基酸的個數(shù)。3、模型假設(shè) （1）假設(shè)氨基酸組合形成蛋白質(zhì)時不脫水。 （2）假設(shè)蛋白質(zhì)中肽鍵不存在多鍵或成環(huán)情況，兩個氨基酸之間只形成一條肽鍵。 （3）假設(shè)每種氨基酸出現(xiàn)的概率都一樣。4、符號設(shè)定 第種氨基酸的分子量； 第種氨基酸的數(shù)量； 第種氨基酸分子中氮原子的個數(shù)； 蛋白質(zhì)分子量； 第種氨基酸基的分子量； 蛋白質(zhì)中所含氨基酸的總數(shù)；5、模型建立與求解5.1實驗室有計算機時的模型建立5.1.1窮舉法模型我們首先考慮用窮舉

5、算法求解方程，根據(jù)上文符號設(shè)定，該方程可以表示為其中且為整數(shù)。利用窮舉法，對每個分別取，1，找出符合上述方程的每個的取值，所得的每組解的集合即為最終解。窮舉算法利用MATLAB實現(xiàn)，程序代碼見附錄一。 用上述算法，我們發(fā)現(xiàn)，如果的取值太大，MATLAB警告“busy”，程序無法運行。假如，求出每一個的最大值，如表一所示：表一 最大值i123456789101112131415161718a(i)5771879799101103113114115128129131137147156163186root(i)17141110109988877776665運算次數(shù)為次，MATLAB無法進行如此大數(shù)量

6、級的運算，導(dǎo)致可求解的具有很大的局限性。所以我們建立下文中的新模型，從而減少運算次數(shù)，提高運算速度，增強運算可行性。5.1.2遞歸法模型 為減少冗余次數(shù)，我們設(shè)計思路如下：從分子量最大的氨基酸開始考慮，初步確定第18種氨基酸分子個數(shù)后，對剩下17種氨基酸的確定，則不需要再用作為衡量標(biāo)準(zhǔn)，而可以將蛋白質(zhì)中所含第18種氨基酸總分子質(zhì)量減掉后，得到新的分子量，則剩下的17種氨基酸可以用新的分子量來確定。按照此思路分析，的新取值圍如下：利用這種模型，可以有效減少運算次數(shù)，使程序可以順利運行。5.1.3結(jié)果篩選我們考慮通過查閱資料了解到測定蛋白質(zhì)的常用指標(biāo)是含氮量，一般蛋白質(zhì)的含氮量在15%17%左右。

7、所以我們設(shè)定限制條件利用此條件，可以把不符合蛋白質(zhì)基本性質(zhì)的結(jié)果篩選出去，剩下的解即為該問題的最終結(jié)果。根據(jù)題目中給出的18種氨基酸的分子量，我們可以查找出題目中18種氨基酸的種類、分子式，從而得到每種氨基酸分子中氮原子個數(shù)，如表二所示（題目中按照氨基酸兩端成鍵給出分子量，故在寫分子式時也考慮為兩端成鍵）：表二 18種氨基酸信息一覽表分子量名稱分子式分子中含氮原子個數(shù)氨基酸含N量57甘氨酸10.2471丙氨酸10.1987絲氨酸10.1697脯氨酸10.1499纈氨酸10.14101氨酸10.14103半胱氨酸10.14113亮氨酸/異亮氨酸10.12114天冬酰胺20.24115天冬氨酸10

8、.12128谷酰胺/賴氨酸20.22129谷氨酸20.22131蛋氨酸10.11137組氨酸10.10147苯丙氨酸30.29156精氨酸10.09163酪氨酸40.34186色氨酸10.08根據(jù)5.1.2中的遞歸模型以與5.1.3中的篩選條件，我們利用C語言編程實現(xiàn)，程序代碼見附錄二。當(dāng)時，用此程序計算結(jié)果如表三所示：表三 當(dāng)時利用遞歸法求解結(jié)果i123456789101112131415161718a(i)5771879799101103113114115128129131137147156163186root1100001100000 000000root2011000100000000

9、000root30030000000000000005.1.4優(yōu)化遞歸算法在附錄二的程序中，我們調(diào)用了遞歸函數(shù)求解，而層層調(diào)用遞歸函數(shù)往往會使預(yù)算速度變慢，不利于該方法的實際應(yīng)用價值的發(fā)揮。所以，我們對程序進行優(yōu)化，不再調(diào)用遞歸函數(shù)，而取一個數(shù)列，將上次運算后的結(jié)果儲存在的每一個格子中，這樣可以避免多次調(diào)用遞歸函數(shù)導(dǎo)致的冗余運算，并將結(jié)果以格式輸出，不再結(jié)果框中顯示結(jié)果，從而大大加快程序運行速度，優(yōu)化后程序見附錄3。當(dāng)時，優(yōu)化前運算時間為，優(yōu)化后運算時間不到。5.2實驗室無計算機時的模型建立氨基酸結(jié)構(gòu)通式為（兩端成鍵，為任意元素或基），不難得出，每種氨基酸都存在基本結(jié)構(gòu)，該基本結(jié)構(gòu)分子量為56

10、，故可以得到18種氨基酸基分子量。先將任一分子量除以56取整，得到構(gòu)成該蛋白質(zhì)的氨基酸數(shù)目的圍（即），再根據(jù)b的取值進行分類討論從而選擇R基，后根據(jù)蛋白質(zhì)含氮量對結(jié)果進行驗證，基分子量如表四所示：表四 18種氨基酸基分子量i123456789101112131415161718a(i)5771879799101103113114115128129131137147156163186r(i)11531414345475758597273758191100107130仍以x=261為例，因為，所以下面分4種情況進行分類討論： （1）b=1 ，表示蛋白質(zhì)由一個氨基酸構(gòu)成，存在一個R基等于261-56

11、=205，=130,故該情況不成立。（2）b=2，表示蛋白質(zhì)由兩個氨基酸構(gòu)成，存在兩個R基之和等于261-56*2=149，58+91=149，即261=114+147，含N量為26%，不符合要求。故該情況也不成立。（3） b=3,表示蛋白質(zhì)由三個氨基酸構(gòu)成，存在三個R基之和等于261-56*3=93：93145479315314793313131931191當(dāng)261=57+57+147時，含氮量為27%，此情況舍去。故存在三種情況：261571011032617187103261878787（4）b=4，表示蛋白質(zhì)由四個氨基酸構(gòu)成，存在四個R基之和等于261-56*4=37，不存在任一情況使

12、之成立。6、模型分析 在實驗室有計算機的情況下，本文結(jié)合化學(xué)基本知識，采用遞歸算法，并用C語言編程。與此同時，我們對C語言程序進行了優(yōu)化，使得速度大大提升，方便用于實際計算與測量中。 在實驗室無計算機的情況下，本文找出了氨基酸的結(jié)構(gòu)通式，明確了氨基酸基本結(jié)構(gòu)，將問題從氨基酸組合轉(zhuǎn)化為基組合，使計算量大大減小。但當(dāng)x較大時，人工方法難以避免較大的計算量。7、模型推廣在實際計算與測量中，蛋白質(zhì)的物理性質(zhì)和化學(xué)性質(zhì)是不容忽視的。本文中只利用蛋白質(zhì)含氮量這一個條件對結(jié)果進行篩選，但得出的結(jié)果未必全部滿足蛋白質(zhì)的其他性質(zhì)，故在實際生產(chǎn)生活中，如想要準(zhǔn)確測定某種蛋白質(zhì)的組成，還需要借助其他專業(yè)儀器，從多方

13、面著手。8、結(jié)論 在實驗室有計算機的情況下，本文建立遞歸算法模型，根據(jù)蛋白質(zhì)含氮量在15%17%的物理性質(zhì)，對所得結(jié)果進行篩選。并利用C語言編程，優(yōu)化了程序，形成“優(yōu)化遞歸算法”，大大加快運行速度。 在實驗室無計算機的情況下，每個氨基酸都存在結(jié)構(gòu)，分子量為56。所以本文得到18種氨基酸R基的分子量，再根據(jù)已知量x，按照所含氨基酸個數(shù)進行分類討論。此方法相對于遞歸法，大減少了計算量，方便在無計算機的情況下解出最終結(jié)果。9、參考文獻1Mark M.Meerscharert，數(shù)學(xué)建模方法與分析，：機械工業(yè)，2005。17 / 18附錄1：MATLAB程序（窮舉法）S=zeros(1,18);for

14、a=0:fix(x/57) for b=0:fix(x/71) for c=0:fix(x/87) for d=0:fix(x/97) for e=0:fix(x/99) for f=0:fix(x/101) for g=0:fix(x/103) for h=0:fix(x/113) for i=0:fix(x/114) for j=0:fix(x/115) for k=0:fix(x/128) for l=0:fix(x/129) for m=0:fix(x/131) for n=0:fix(x/137) for o=0:fix(x/147) for p=0:fix(x/156) for q

15、=0:fix(x/163) for r=0:fix(x/186) if 57*a+71*b+87*c+97*d+99*e+101*f+103*g+113*h+114*i+115*j+128*k+129*l+131*m+137*n+147*o+156*p+163*q+186*r=x S=S;a b c d e f g h i j k l m n o p q r; end end end end end end end end end end end end end end end end end endendS附錄2：C程序（遞歸法）#include <cstdio>#include

16、 <iostream>#include <fstream>using namespace std;/global setting int weight18=57, 71, 87, 97, 99, 101, 103, 113, 114, 115, 128, 129, 131, 137, 147, 156, 163, 186; int root18=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0; int N_number18=1,1,1,1,1,1,1,1,2,1,2,2,1,1,3,1,4,1;int K=0;double root_number

17、=0;double root_number2=0;ofstream fout("E:/TestDir/cfiletest.txt");void Digui(int n,int x)int branch_number = x/weightn;/printf("%d",branch_number);if(x<0)return;if(n = 0)int i = branch_number;for(i = branch_number;i >= 0;i-)rootn = i;if( x-i*weight0 = 0)double N_content=0;

18、int k=0;for(k=0;k<18;k+)N_content=N_content+N_numberk*rootk*14;/printf("K:%dn",K);/printf("K*0.15:%fn",K*0.15);/printf("%fn",N_content);/printf("K*0.17:%fn",K*0.17);if( N_content>K*0.15 && N_content<K*0.17)root_number = root_number + 1;int j=0

19、;printf("root:");fout<<"root"<<root_number<<":"for(j=0;j<18;j+)printf("%d ",rootj);fout<<rootj<<" "printf("n");fout<<endl;root_number2=root_number2+1;return;elseint i = branch_number;for(i = branch_num

20、ber;i >= 0;i-)rootn = i;/printf("x: %dn",x-i*weightn);/printf("n-1:%dn",n-1);Digui(n-1,x-i*weightn); return; int main()int x;printf("Please input K:");scanf("%d",&K);x=K;int i=0;printf("weight:");for(i=0;i<18;i+)printf("%d ",weigh

21、ti);printf("n");Digui(17,x);printf("total:");printf("%f n",root_number);printf("unstrict total:");printf("%f n",root_number2);return 0;附錄3：C程序（優(yōu)化遞歸算法）#include <stdio.h>/global setting int weight18=57, 71, 87, 97, 99, 101, 103, 113, 114, 115, 12

22、8, 129, 131, 137, 147, 156, 163, 186; int root18=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0; int x=0;double root_number=0;int temp18;int main()printf("Please input x:");scanf("%d",&x);int i;int j18;for(j17=x/weight17;j17>=0;j17-)temp17=x-weight17*j17;for(j16=temp17/weight16;j16>=0;j16-)temp16=temp17-weight16*j16;for(j15=temp16/weight15;j15>=0;j15-)temp15=temp16-weight15*j15;for(j14=temp15/weight14;j14>=0;j14-)temp14=temp15-weight14*j14;for(j13=temp14/weight13;j13>=0;j13-)temp13=temp14-weight13*j13;for(j12=temp13/weight12;j12>=0;j12-)temp12=temp13-weight12