数学建模实例DNA序列分类Word文档下载推荐.docx

数学建模实例DNA序列分类Word文档下载推荐.docx

《数学建模实例DNA序列分类Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《数学建模实例DNA序列分类Word文档下载推荐.docx（34页珍藏版）》请在冰点文库上搜索。

1．各序列中DNA碱基三联组（即3字符串）的起始位置和基因表达不影响分类的结果。

2．64种3字符串压缩为20组后不影响分类的结果。

3．较长的182个自然序列与已知类别的20个样本序列具有共同的特征。

三.模型建立与求解

研究DNA序列具有什么结构，其A，T，C，G4个碱基排成的看似随机的序列中隐藏着什么规律，是解读人类基因组计划中DNA全序列草图的基础，也是生物信息学（Bioinformaties）最重要的课题之一。

题目给出了20个已知为两个类别的人工制造的DNA序列，要求我们从中提取特征，构造分类方法，从而对20个未标明类别的人工DNA序列和182个自然DNA序列进行分类。

这是模式识别中的“有人管理分类”问题，即事先规定了分类的标准和种类的数目，通过大批已知样本的信息处理找出规律，再用计算机预报未知。

给出的已知类别的样本称为学习样本。

对于此类问题，我们通过建立分类数学模型（这包括形成和提取特征以及制定分类决策）、考查分类模型的效率、预报未知这几个步骤来进行。

一．特征的形成和提取

为了有效地实现分类识别，首先要根据被识别的对象产生一组基本特征，并对基本特征进行变换，得到最能反映分类本质的特征。

这就是特征形成和提取的过程。

在列举了尽可能完备的特征参数集之后，就要借助于数学的方法，使特征参数的数目（在保证分类良好的前提下）减到最小。

这是因为：

1.多余的特征参数不但没有多少好处，而且会带来噪音，干扰分类和数学模型的建立。

2.为了保证样本数和特征参数个数的比值足够大，而又不必要用太多的样本，最好使特征参数的个数降至最少。

模式识别计算一般要求样本数至少为变量数的3倍，否则结果不够可靠。

本问题的学习样本数为20个，故特征参数的个数以6—8个为宜。

我们通过研究4个字符A,T,C,G在DNA序列中的排列、组合特性，主要是研究字符和字符串的排列在序列中出现的频率，从中提取DNA序列的结构特征参数。

（一）特征的形成

分别列举一个字符，2个字符，3个字符的排列在序列中出现的频率，构成基本特征集。

i.1个字符的出现频率

表1列出了20个样本中A，T，C，G这4个字符出现的频率。

由于在不用于编码蛋白质的序列片段中，A和T的含量特别多些，因此我们将A和T是否特别丰富作为一个特征。

在表一中，列出了A和T出现的频率之和。

（程序见附录一）

表1

ACTGA+T

1.29.7317.1213.5139.6443.24

2.27.0316.2215.3241.4442.34

3.27.0321.626.3145.0533.33

4.42.3410.8128.8318.0271.17

5.23.4223.4210.8142.3434.23

6.35.1412.6112.6139.6447.75

7.35.149.9118.9236.0454.05

8.27.9316.2218.9236.9446.85

9.20.7220.7215.3243.2436.04

10.18.1827.2713.6440.9131.82

11.35.454.5550.0010.0085.45

12.32.732.7350.0014.5582.73

13.25.4510.0051.8212.7377.27

14.30.008.1850.0011.8280.00

15.29.09.0064.556.3693.64

16.36.368.1846.369.0982.73

17.35.4524.5526.3613.6461.82

18.29.0911.8250.009.0979.09

19.21.8214.5556.367.2778.18

20.20.0017.2756.366.3676.36

2．2字符串的排列出现的频率

A，T，C，G这4个字符组成了16种不同的2字符串。

表2列出了20个样本中各2字符串出现的频率。

（用“滚动”算法，如attcg有at,tt,tc,cg共4个2字符串）（程序与附录一类似）

表2

AAACATAGTATCTGTTCACTCCCGGAGTGCGG

1.9.019.013.608.114.50.904.503.603.603.601.808.1111.712.705.4118.92

2.9.917.213.605.412.701.805.415.414.501.80.909.019.914.505.4121.62

3.5.4111.713.605.412.701.80.90.905.41.90.9014.4113.51.907.2123.42

4.18.925.4111.715.4110.811.805.4110.815.411.80.902.706.314.502.704.50

5.6.318.111.807.211.802.702.703.605.414.502.7010.819.91.909.0121.62

6.15.322.706.319.913.601.801.805.414.50.00.008.1110.81.908.1119.82

7.15.321.8010.817.214.502.706.315.41.901.80.906.3113.51.904.5016.22

8.8.113.606.319.915.413.602.707.212.703.601.808.1110.811.807.2116.22

9.9.01.904.506.31.003.607.214.503.602.702.7011.717.213.6013.5118.02

10.6.363.641.826.361.825.452.733.645.453.644.5513.644.553.6413.6418.18

11.15.452.7314.552.7316.36.911.8230.00.91.91.911.822.734.55.002.73

12.13.64.9110.916.3615.451.821.8230.91.91.91.00.912.737.27.004.55

13.6.364.5510.004.5512.731.822.7334.552.732.731.821.823.644.551.822.73

14.8.18.9112.737.2713.646.361.8228.182.734.55.00.915.454.55.91.91

15.13.64.0012.731.8213.64.002.7348.18.00.00.00.001.823.64.00.91

16.16.363.6415.45.9113.644.554.5522.731.825.45.00.914.552.73.001.82

17.17.275.4510.911.8210.006.364.555.454.557.279.092.733.642.733.643.64

18.8.187.2711.821.8215.451.82.9130.913.643.641.822.731.823.64.912.73

19.2.732.7313.641.8214.559.09.9131.821.828.181.822.732.732.73.91.91

20.6.366.366.36.919.0910.003.6432.732.7313.64.91.001.823.64.00.91

3．3字符串的排列出现的频率

A，T，C，G这4个字符组成了64种不同的3字符串。

这64种3字符串构成生物蛋白质的20种氨基酸。

在参考文献[1]的Figur2中，给出了这20种氨基酸的编码（见图1）。

因此，在计算3字符串的出现频率时，我们根据图1将代表同一种氨基酸的3字符串合成一类，只统计20类3字符串的出现频率。

（不考虑字符串在序列片段中的起始位置，也采用“滚动”算法。

如acgtcc中就有acg,cgt,gtc,tcc共4个3字符串）见表3。

（程序与附录一类似）

Figure2.Symmetriesofthediamondcodesortthe64codonsinto20classes,indicatedhereby20colors.Allthecodonsineachclassspecifiedthesameaminoacid.

图1BrianHayes在论文“TheInventionoftheGeneticCode”中给出的图形

（注：

图中DNA被转录为RNA,“U”代表“T”）

表3

b1b2b3b4b5b6b7b8b9b10b11b12b13b14b15b16b17b18b19b20

11.773.542.650.880.000.007.960.884.422.6517.7010.623.544.424.427.081.773.5413.277.08

21.891.890.940.940.000.941.890.944.7212.267.5511.328.493.773.776.609.436.607.552.83

30.980.000.005.880.988.822.940.000.002.9410.785.8813.730.004.903.9219.611.968.825.88

40.000.000.000.870.000.8713.041.746.092.6111.3013.043.485.223.488.703.481.7414.78，7.83

52.860.000.003.810.953.813.810.003.813.819.529.5212.382.869.524.767.622.867.629.52

60.000.000.882.630.001.7513.160.884.391.7514.049.657.025.264.3911.402.631.7510.536.14

71.920.000.002.880.964.812.880.001.924.8112.506.7313.461.926.734.8110.583.859.627.69

82.563.420.000.850.850.8512.820.851.710.8520.512.563.429.405.9811.110.854.2711.973.42

90.000.000.002.972.979.902.970.000.993.966.931.9813.861.982.973.9623.762.978.916.93

101.870.933.742.800.000.002.800.007.488.419.357.483.7414.9512.150.002.804.677.487.48

110.000.890.000.000.001.798.040.005.364.4615.188.048.934.463.578.044.466.2513.395.36

122.730.000.912.730.913.644.553.643.641.829.095.453.645.456.367.278.185.4510.919.09

131.800.900.900.900.000.909.010.003.607.2114.418.117.216.317.214.501.807.2111.714.50

142.940.000.005.880.006.861.960.003.926.863.929.8013.730.985.882.9410.780.9810.789.80

152.911.942.911.940.005.831.940.001.949.715.838.7410.681.943.883.888.742.9111.6510.68

162.860.950.0011.431.901.902.860.004.763.815.718.578.576.679.524.765.712.867.627.62

171.920.961.924.811.923.851.920.960.966.734.818.6510.582.886.732.889.626.738.657.69

181.710.851.710.850.852.5616.240.851.710.8516.245.136.845.983.4211.111.715.1311.113.42

190.940.941.890.940.940.941.890.9410.387.555.669.438.498.497.555.666.6011.326.600.94

200.860.860.001.720.860.8617.240.862.591.7215.527.765.173.454.319.485.175.179.485.17

其中b1=aaa+atab2=aca+agab3=cac+ctcb4=ccc+cgc

b5=gag+gtgb6=gcg+gggb7=tat+tttb8=tct+tgt

b9=aac+caa+atc+ctab10=aag+gaa+atg+gta

b11=aat+taa+att+ttab12=acc+cca+agc+cga

b13=acg+gac+ctg+gtcb14=act+tca+agt+tga

b15=cag+gac+ctt+ttcb16=cat+tac+ctt+ttc

b17=ccg+gcc+cgg+ggcb18=cct+tcc+cgt+tgc

b19=gat+tag+gtt+ttgb20=gct+tcg+ggt+tgg

综合起来，形成了有41个变量的基本特征集。

（二）特征的提取

上述基本特征集中有41个变量，即样本处于一个高维空间中。

特征的提取就是通过变换的方法用低维空间来表示样本，使得X的大部分特性能由Y来表达，即将p维随机向量X变换成q维随机向量Y（q<

p）。

我们用主成分分析法进行特征的提取，其步骤是：

1．求X的均方差矩阵V的特征根，记为：

λ1≥λ2≥……≥λk＞0λk+1=……=λP=0

2．求λ1,λ2……λK对应的标准正交的特征向量r1，r2……rK

得到第i个主成分为yi=riX,i=1,2……K

3．求第i个主成分的贡献率ui=λi/

λj,i=1,2……K及前m个主成分的累计贡献率vm=

ui.

4．求得q，使得Vq≥V0（V0一般在0.85到1之间），则取

W=（r1,r2,……,rq）

Y=XW

第3步所求的贡献率，代表主成分表达X的能力，贡献率越大，对应的主成分表达X的能力越强。

只要前q个主成分的累计贡献率超过给定的百分比V。

就可以用低维特征Y=（y1,y2,……yq）来反映高维特征（x1,x2……xp）的变化特性。

现将反映20个已知类别样本的41个特征的随机向量X进行特征提取。

计算得前4个主成分的累计贡献率为96%，故提取特征为4个变量，取

W=（r1,r2,r3,r4），则Y=XW，Y的4个分量就是从基本特征集提取所得的特征参数向量。

（程序及结果见附录二）

二．分类决策的制定

前面已选取了特征参数，把特征参数张成的多维空间称为特征空间。

分类决策就是在特征空间中用统计的方法把被识别对象归为某一类别。

基本作法是在学习样本集的基础上确定某个判决规则，使按这种判决规则对被甄别对象进行分类所造成的错误识别率最小或引起的损失最少。

这里，我们的分类决策选取Fisher线性判别法。

即选取线性判别函数U（x），使得：

U（x）={E1[U（x）]-E2[U（x）]}2/{D1[U（x）]+D2[U（x）]}=max

（1）

其中Ei与Di分别表示母体i的期望和方差运算，i=1，2。

（1）式的含义是：

构造一个线性判别函数U（x）对样本进行分类，使得平均出错概率最小。

即应在不同母体下，使U（x）的取值尽量分开。

具体地说，要使母体间的差异（E1（U（x））-E2（U（x）））2相对于母体内的差异D1[U（x）]+D2[U（x）]为最大。

取

U（x）=（

1-

2）＇（∑1+∑2）-1X

就可满足

（1）。

其中

i为第i类母体的均值矩阵的估计，∑i为第i类母体的方差矩阵的估计。

取分类门槛值为：

U0=U（α*

1+（1-α）*

2）

其中0<

α<

1，本问题中两类样本的个数相等，可取α=1/2。

若U（

1）>

U0,U（

2）<

U0,则当U（X）>

U0.,就认为X取自母体1；

当U（X）<

U0,就认为X取自母体2。

用上面得出的4个主成分构成的特征组和此分类决策，对20个学习样本进行分类，能得出正确的结果。

但是，若取W=（r1,r2,r3），求Y=XW，以Y的3个分量作为特征参数向量，再用Fisher线性判别法对20个学习样本进行分类，则第四个样本不能正确分类。

因此，得出分类的数学模型为：

（1）特征选取：

取W=（r1,r2,r3,r4），求Y=XW，得出特征参数向量就是Y的4个列向量。

其中X是反映20个学习样本的41个特征的随机向量。

（2）分类决策：

Fisher线性判别法。

三.分类模型的有效性考查

前面建立的分类数学模型对20个学习样本进行了正确分类。

为了进一步考查分类模型的有效性和可靠性，我们采用的方法是：

预先留一部分学习样本不参加训练，然后用分类决策模型对其作预报，将预报成功率作为预报能力的指标。

每次取出一个学习样本，以其余学习样本作训练集，用分类决策模型对取出的一个样本作预报，同时对给出的后20种样本作预报。

结果见表4。

表4

取出样品序号

取出样本类别预报

后20组样本中A类序号预报

1

A

22，23，25，27，29，34，35，36，37

2

3

4

23，25，27，29，34，35，36，37

5

6

7

8

9

10

11

B

12

13

14

15

22，23，25，27，29，34，35，36，37，39

16

17

22