数学建模实例DNA序列分类.docx

数学建模实例DNA序列分类.docx

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

数学建模实例DNA序列分类

2000全国大学生数学建模竞赛题目

A题 DNA序列分类 

2000年6月，人类基因组计划中DNA全序列草图完成，预计2001年可以完成精确的全序列图，此后人类将拥有一本记录着自身生老病死及遗传进化的全部信息的“天书”。

这本大自然写成的“天书”是由4个字符A，T，C，G按一定顺序排成的长约30亿的序列，其中没有“断句”也没有标点符号，除了这4个字符表示4种碱基以外，人们对它包含的“内容”知之甚少，难以读懂。

破译这部世界上最巨量信息的“天书”是二十一世纪最重要的任务之一。

在这个目标中，研究DNA全序列具有什么结构，由这4个字符排成的看似随机的序列中隐藏着什么规律，又是解读这部天书的基础，是生物信息学（Bioinformatics）最重要的课题之一。

虽然人类对这部“天书”知之甚少，但也发现了DNA序列中的一些规律性和结构。

例如，在全序列中有一些是用于编码蛋白质的序列片段，即由这4个字符组成的64种不同的3字符串，其中大多数用于编码构成蛋白质的20种氨基酸。

又例如，在不用于编码蛋白质的序列片段中，A和T的含量特别多些，于是以某些碱基特别丰富作为特征去研究DNA序列的结构也取得了一些结果。

此外，利用统计的方法还发现序列的某些片段之间具有相关性，等等。

这些发现让人们相信，DNA序列中存在着局部的和全局性的结构，充分发掘序列的结构对理解DNA全序列是十分有意义的。

目前在这项研究中最普通的思想是省略序列的某些细节，突出特征，然后将其表示成适当的数学对象。

这种被称为粗粒化和模型化的方法往往有助于研究规律性和结构。

作为研究DNA序列的结构的尝试，提出以下对序列集合进行分类的问题：

   1）下面有20个已知类别的人工制造的序列（见下页），其中序列标号1—10为A类，11-20为B类。

请从中提取特征，构造分类方法，并用这些已知类别的序列，衡量你的方法是否足够好。

然后用你认为满意的方法，对另外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亿的序列，其中没有“断句”也没有标点符号。

虽然人类对它知之甚少，但也发现了其中的一些规律性和结构。

例如，在全序列中有一些是用于编码蛋白质的序列片段，即由这4个字符组成的64种不同的3字符串，其中大多数用于编码构成蛋白质的20种氨基酸。

又例如，在不用于编码蛋白质的序列片段中，A和T的含量特别多些，于是以某些碱基特别丰富作为特征去研究DNA序列的结构也取得了一些结果。

此外，利用统计的方法还发现序列的某些片段之间具有相关性，等等。

这些发现让人们相信，DNA序列中存在着局部的和全局性的结构，充分发掘序列的结构对理解DNA全序列是十分有意义的。

目前在这项研究中最普通的思想是省略序列的某些细节，突出特征，然后将其表示成适当的数学对象。

作为研究DNA序列的结构的尝试，提出以下对序列集合进行分类的问题：

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