数学建模实例DNA序列分类Word格式.docx
《数学建模实例DNA序列分类Word格式.docx》由会员分享,可在线阅读,更多相关《数学建模实例DNA序列分类Word格式.docx(30页珍藏版)》请在冰点文库上搜索。
然后用你认为满意的方法,对另外20个未标明类别的人工序列(标号21—40)进行分类,把结果用序号(按从小到大的顺序)标明它们的类别(无法分类的不写入):
A类
;
B类
。
请详细描述你的方法,给出计算程序。
如果你部分地使用了现成的分类方法,也要将方法名称准确注明。
这40个序列也放在如下地址的网页上,用数据文件Art-model-data标识,供下载:
网易网址:
教育频道
在线试题;
教育网:
News
mcm2000
2)在同样网址的数据文件Nat-model-data中给出了182个自然DNA序列,它们都较长。
用你的分类方法对它们进行分类,像1)一样地给出分类结果。
提示:
衡量分类方法优劣的标准是分类的正确率,构造分类方法有许多途径,例如提取序列的某些特征,给出它们的数学表示:
几何空间或向量空间的元素等,然后再选择或构造适合这种数学表示的分类方法;
又例如构造概率统计模型,然后用统计方法分类等。
Art-model-data
1.aggcacggaaaaacgggaataacggaggaggacttggcacggcattacacggaggacgaggtaaaggaggcttgtctacggccggaa
gtgaagggggatatgaccgcttgg
2.cggaggacaaacgggatggcggtattggaggtggcggactgttcggggaattattcggtttaaacgggacaaggaaggcggctggaa
caaccggacggtggcagcaaagga
3.gggacggatacggattctggccacggacggaaaggaggacacggcggacatacacggcggcaacggacggaacggaggaaggaggg
cggcaatcggtacggaggcggcgga
4.atggataacggaaacaaaccagacaaacttcggtagaaatacagaagcttagatgcatatgttttttaaataaaatttgtattatt
atggtatcataaaaaaaggttgcga
5.cggctggcggacaacggactggcggattccaaaaacggaggaggcggacggaggctacaccaccgtttcggcggaaaggcggaggg
ctggcaggaggctcattacggggag
6.atggaaaattttcggaaaggcggcaggcaggaggcaaaggcggaaaggaaggaaacggcggatatttcggaagtggatattaggag
ggcggaataaaggaacggcggcaca
7.atgggattattgaatggcggaggaagatccggaataaaatatggcggaaagaacttgttttcggaaatggaaaaaggactaggaat
cggcggcaggaaggatatggaggcg
8.atggccgatcggcttaggctggaaggaacaaataggcggaattaaggaaggcgttctcgcttttcgacaaggaggcggaccatagg
aggcggattaggaacggttatgagg
9.atggcggaaaaaggaaatgtttggcatcggcgggctccggcaactggaggttcggccatggaggcgaaaatcgtgggcggcggcag
cgctggccggagtttgaggagcgcg
10.tggccgcggaggggcccgtcgggcgcggatttctacaagggcttcctgttaaggaggtggcatccaggcgtcgcacgctcggcg
cggcaggaggcacgcgggaaaaaacg
11.gttagatttaacgttttttatggaatttatggaattataaatttaaaaatttatattttttaggtaagtaatccaacgttttta
ttactttttaaaattaaatatttatt
12.gtttaattactttatcatttaatttaggttttaattttaaatttaatttaggtaagatgaatttggttttttttaaggtagttat
ttaattatcgttaaggaaagttaaa
13.gtattacaggcagaccttatttaggttattattattatttggattttttttttttttttttttaagttaaccgaattattttctt
taaagacgttacttaatgtcaatgc
14.gttagtcttttttagattaaattattagattatgcagtttttttacataagaaaatttttttttcggagttcatattctaatctg
tctttattaaatcttagagatatta
15.gtattatatttttttatttttattattttagaatataatttgaggtatgtgtttaaaaaaaattttttttttttttttttttttt
ttttttttaaaatttataaatttaa
16.gttatttttaaatttaattttaattttaaaatacaaaatttttactttctaaaattggtctctggatcgataatgtaaacttat
tgaatctatagaattacattattgat
17.gtatgtctatttcacggaagaatgcaccactatatgatttgaaattatctatggctaaaaaccctcagtaaaatcaatccctaa
acccttaaaaaacggcggcctatccc
18.gttaattatttattccttacgggcaattaattatttattacggttttatttacaattttttttttttgtcctatagagaaatta
cttacaaaacgttattttacatactt
19.gttacattatttattattatccgttatcgataattttttacctcttttttcgctgagtttttattcttactttttttcttctt
tatataggatctcatttaatatcttaa
20.gtatttaactctctttactttttttttcactctctacattttcatcttctaaaactgtttgatttaaacttttgtttctttaa
ggattttttttacttatcctctgttat
21.tttagctcagtccagctagctagtttacaatttcgacaccagtttcgcaccatcttaaatttcgatccgtac
cgtaatttagcttagatttggatttaaaggatttagattga
22.tttagtacagtagctcagtccaagaacgatgtttaccgtaacgtqacgtaccgtacgctaccgttaccggat
tccggaaagccgattaaggaccgatcgaaaggg
23.cgggcggatttaggccgacggggacccgggattcgggacccgaggaaattcccggattaaggtttagcttcc
cgggatttagggcccggatggctgggaccc24.tttagctagctactttagctatttttagtagctagccagcc
tttaaggctagctttagctagcattgttctttattgggacccaagttcgacttttacgatttagttttgaccgt
25.gaccaaaggtgggctttagggacccgatgctttagtcgcagctggaccagttccccagggtattaggcaaaa
gctgacgggcaattgcaatttaggcttaggcca
26.gatttactttagcatttttagctgacgttagcaagcattagctttagccaatttcgcatttgccagtttcgc
agctcagttttaacgcgggatctttagcttcaagctttttac
27.ggattcggatttacccggggattggcggaacgggacctttaggtcgggacccattaggagtaaatgccaaag
gacgctggtttagccagtccgttaaggcttag
28.tccttagatttcagttactatatttgacttacagtctttgagatttcccttacgattttgacttaaaattta
gacgttagggcttatcagttatggattaatttagcttattttcga
29.ggccaattccggtaggaaggtgatggcccgggggttcccgggaggatttaggctgacgggccggccatttcg
gtttagggagggccgggacgcgttagggc30.cgctaagcagctcaagctcagtcagtcacgtttgccaagtcagt
aatttgccaaagttaaccgttagctgacgctgaacgctaaacagtattagctgatgactcgta
31.ttaaggacttaggctttagcagttactttagtttagttccaagctacgtttacgggaccagatgctagctag
caatttattatccgtattaggcttaccgtaggtttagcgt32.gctaccgggcagtctttaacgtagctaccgtt
tagtttgggcccagccttgcggtgtttcggattaaattcgttgtcagtcgctctrtgggtttagtcattcccaaaagg
33.cagttagctgaatcgtttagccatttgacgtaaacatgattttacgtacgtaaattttagccctgacgtttag
ctaggaatttatgctgacgtagcgatcgactttagcac
34.cggttagggcaaaggttggatttcgacccagggggaaagcccgggacccgaacccagggctttagcgtaggct
gacgctaggcttaggttggaacccggaaa
35.gcggaagggcgtaggtttgggatgcttagccgtaggctagctttcgacacgatcgattcgcaccacaggataaa
agttaagggaccggtaagtcgcggtagcc
36.ctagctacgaacgctttaggcgcccccgggagtagtcgttaccgttagtatagcagtcgcagtcgcaattcgc
aaaagtccccagctttagccccagagtcgacg
37.gggatgctgacgctggttagctttaggcttagcgtagctttagggccccagtctgcaggaaatgcccaaagga
ggcccaccgggtagatgccasagtgcaccgt
38.aacttttagggcatttccagttttacgggttattttcccagttaaactttgcaccattttacgtgttacgat
ttacgtataatttgaccttattttggacactttagtttgggttac
39.ttagggccaagtcccgaggcaaggaattctgatccaagtccaatcacgtacagtccaagtcaccgtttgcag
ctaccgtttaccgtacgttgcaagtcaaatccat
40.ccattagggtttatttacctgtttattttttcccgagaccttaggtttaccgtactttttaacggtttacctt
tgaaatttttggactagcttaccctggatttaacggccagttt
DNA序列分类
摘要本问题是一个“有人管理分类问题”。
首先分别列举出20个学习样本序列中1字符串、2字符串、3字符串出现的频率,构成含41个变量的基本特征集,接着用主成分分析法从中提取出4个特征。
然后用Fisher线性判别法进行分类,得出了所求20个人工制造序列及182个自然序列的分类结果如下:
1)20个人工序列:
22,23,25,27,29,34,35,36,37为A类,其余为B类。
2)182个自然序列:
1,4,8,10,27,29,32,41,43,48,54,63,70,72,75,76,81,86,90,92,102,110,116,119,126,131,144,150,157,159,160,161,162,163,164,165,166,169,170,182为B类,其余为A类。
最后通过检验证明所用的分类数学模型效率较高。
一.问题重述
人类基因组计划中DNA全序列草图是由4个字符A,T,C,G按一定顺序排成的长约30亿的序列,其中没有“断句”也没有标点符号。
虽然人类对它知之甚少,但也发现了其中的一些规律性和结构。
1)请从20个已知类别的人工制造的序列(其中序列标号1—10为A类,11-20为B类)中提取特征,构造分类方法,并用这些已知类别的序列,衡量你的方法是否足够好。
然后用你认为满意的方法,对另外20个未标明类别的人工序列(标号21—40)进行分类,把结果用序号(按从小到大的顺序)标明它们的类别(无法分类的不写入)
2)同样方法对182个自然DNA序列(它们都较长)进行分类,像1)一样地给出分类结果。
二.模型的合理假设
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