《全国大学生数学建模竞赛题选讲[pdf]》由会员分享，可在线阅读，更多相关《全国大学生数学建模竞赛题选讲[pdf]（28页珍藏版）》请在金锄头文库上搜索。
1、全国大学生数学建模竞赛题选讲全国大学生数学建模竞赛题选讲 2000A题DNA序列分类 2000A题: DNA序列分类 2000年年6月月, 人类基因组计划中人类基因组计划中DNA全序列草图完成全序列草图完成, 预计预计2001年可以完成精确的全序列图年可以完成精确的全序列图, 此后人类将拥有一此后人类将拥有一 本记录着自身生老病死及遗传进化的全部信息的本记录着自身生老病死及遗传进化的全部信息的“天书天书”。 这本大自然写成的这本大自然写成的“天书天书”是由是由4个字符个字符A,T, C, G按一定顺按一定顺 序排成的长约序排成的长约30亿的序列亿的序列,其中没有其中没有“断句断句”也没有标点符
2、也没有标点符 号号, 除了这除了这4个字符表示个字符表示4种碱基以外种碱基以外, 人们对它包含的人们对它包含的“内内 容容”知之甚少知之甚少,难以读懂难以读懂。破译这部世界上最巨量信息的破译这部世界上最巨量信息的 “天书天书”是二十一世纪最重要的任务之一是二十一世纪最重要的任务之一。在这个目标中在这个目标中, 研究研究DNA全序列具有什么结构全序列具有什么结构, 由这由这4个字符排成的看似个字符排成的看似 随机的序列中隐藏着什么规律随机的序列中隐藏着什么规律, 又是解读这部天书的基础又是解读这部天书的基础, 是生物信息学是生物信息学(Bioinformatics)最重要的课题之一最重要的课题之
3、一。 虽然人类对这部虽然人类对这部“天书天书”知之甚少知之甚少, 但也发现了但也发现了DNA 序列中的一些规律性和结构序列中的一些规律性和结构。例如例如, 在全序列中有一些是在全序列中有一些是 用于编码蛋白质的序列片段用于编码蛋白质的序列片段, 即由这即由这4个字符组成的个字符组成的64种种 不同的不同的3字符串字符串, 其中大多数用于编码构成蛋白质的其中大多数用于编码构成蛋白质的20种种 氨基酸氨基酸。又例如又例如, 在不用于编码蛋白质的序列片段中在不用于编码蛋白质的序列片段中,A和和 T的含量特别多些的含量特别多些, 于是以某些碱基特别丰富作为特征去于是以某些碱基特别丰富作为特征去 研究研
4、究DNA序列的结构也取得了一些结果序列的结构也取得了一些结果。此外此外, 利用统计利用统计 的方法还发现序列的某些片段之间具有相关性的方法还发现序列的某些片段之间具有相关性, 等等等等。这这 些发现让人们相信些发现让人们相信, DNA序列中存在着局部的和全局性的序列中存在着局部的和全局性的 结构结构, 充分发掘序列的结构对理解充分发掘序列的结构对理解DNA全序列是十分有意全序列是十分有意 义的义的。目前在这项研究中最普通的思想是省略序列的某目前在这项研究中最普通的思想是省略序列的某 些细节些细节, 突出特征突出特征, 然后将其表示成适当的数学对象然后将其表示成适当的数学对象。这这 种被称为粗粒
5、化和模型化的方法往往有助于研究规律性种被称为粗粒化和模型化的方法往往有助于研究规律性 和结构和结构。 作为研究作为研究DNA序列的结构的尝试序列的结构的尝试，提出以下对序列集合进提出以下对序列集合进 行分类的问题行分类的问题： 1)下面有下面有20个已知类别的人工制造的序列个已知类别的人工制造的序列(见下页见下页)，其中其中 序列标号序列标号110 为为A类类, 11-20为为B类类。请从中提取特征请从中提取特征, 构构 造分类方法造分类方法, 并用这些已知类别的序列并用这些已知类别的序列,衡量你的方法是否衡量你的方法是否 足够好足够好。然后用你认为满意的方法然后用你认为满意的方法, 对另外对
6、另外20个未标明类个未标明类 别的人工序列别的人工序列(标号标号2140)进行分类进行分类, 把结果用序号把结果用序号(按从按从 小到大的顺序小到大的顺序)标明它们的类别标明它们的类别(无法分类的不写入无法分类的不写入): A类类_;B类类_ 请详细描述你的方法请详细描述你的方法，给出计算程序给出计算程序。如果你部分地使用如果你部分地使用 了现成的分类方法了现成的分类方法，也要将方法名称准确注明也要将方法名称准确注明。 这这40个序列也放在如下地址的网页上个序列也放在如下地址的网页上，用数据文件用数据文件Art- model-data 标识标识，供下载供下载. (网址略网址略) 1.aggca
7、cggaaaaacgggaataacggaggaggacttggcacggcattacacgg aggacgaggtaaaggaggcttgtctacggccggaagtgaagggggatatgaccg cttgg 2.cggaggacaaacgggatggcggtattggaggtggcggactgttcggggaattat tcggtttaaacgggacaaggaaggcggctggaacaaccggacggtggcagcaaa gga (310略略) 11.gttagatttaacgttttttatggaatttatggaattataaatttaaaaatttatattttt tag
8、gtaagtaatccaacgtttttattactttttaaaattaaatatttatt 12.gtttaattactttatcatttaatttaggttttaattttaaatttaatttaggtaagatga atttggttttttttaaggtagttatttaattatcgttaaggaaagttaaa (1320略略) 21.tttagctcagtccagctagctagtttacaatttcgacaccagtttcgcaccatcttaa atttcgatccgtaccgtaatttagcttagatttggatttaaaggatttagattga 22.tttagta
9、cagtagctcagtccaagaacgatgtttaccgtaacgtqacgtaccgtac gctaccgttaccggattccggaaagccgattaaggaccgatcgaaaggg 23.cgggcggatttaggccgacggggacccgggattcgggacccgaggaaattcccg gattaaggtttagcttcccgggatttagggcccggatggctgggaccc 24.tttagctagctactttagctatttttagtagctagccagcctttaaggctagctttagc tagcattgttctttattgggacccaagttc
10、gacttttacgatttagttttgaccgt 25.gaccaaaggtgggctttagggacccgatgctttagtcgcagctggaccagttccc cagggtattaggcaaaagctgacgggcaattgcaatttaggcttaggcca (2640略略) 2) 在同样网址的数据文件在同样网址的数据文件Nat-model-data 中给出了中给出了182个个 自然自然DNA序列序列，它们都较长它们都较长。用你的分类方法对它们进用你的分类方法对它们进 行分类行分类，像像1) 一样地给出分类结果一样地给出分类结果。 提示提示：衡量分类方法优劣的标准是分类的正确率衡
11、量分类方法优劣的标准是分类的正确率，构造分构造分 类方法有许多途径类方法有许多途径，例如提取序列的某些特征例如提取序列的某些特征，给出它们给出它们 的数学表示的数学表示：几何空间或向量空间的元素等几何空间或向量空间的元素等，然后再选择然后再选择 或构造适合这种数学表示的分类方法或构造适合这种数学表示的分类方法；又例如构造概率统又例如构造概率统 计模型计模型，然后用统计方法分类等然后用统计方法分类等。 1)tgacctcttgtcctgtatagcaacctatttggtaatgattccagcactcacagaaaagcttgcaca catacacacacaccccacccctccccact
12、aacaaatgcaagttggtaaacaaattccaaaaaggc ataacaaaccttatatatatagacaaatatatattaaagttttttagtctgtactagaaagagcttca gacagaactgaccaccattccattgctcatcaatttcctgggacagcacctgagcgtgcgcttacgc gcgtacacacacatagacacgcactgcgatacaagtcctgatttgggagtccgtccttttaaaaac agccacatgctttcacgctctgagacccacccgtttctgtgagcagggggagggcaagg
13、aaagcc ctggcctcagtccagccttttctctgcttccacctgctcaggctgtgtgctcttggttctgtcctgcactt gtgtgaattccaaaactgtttttttaaaaaatggcccgcaccccaaatgtctccctgccccatactttg caacaagagaaaactttaggatgcttctcttttgggtggcggaggttgttaacttcaagaatttaga agaatcattgctccgacaaatccactgtctcctgagttttctttattcatgttaacaaggcaagagtca gagaaaagggaga
14、cttggtctgcttcccacatgcagctgagcggaggggccgtcacagcacagg gtcacctgcagagctgaagccgctcctcaggctccccctccaagagggctggggcaaggtccctg ggctgaggcctcccaggggggcctgggcaaggcttccttgggttctggatcccccctgcaatgctg ccccatcctgcccccacccccacgtcattaaacacgatggagggtttttcggtcggttggttggttgg tgttctaaatcaaggaaaatggtccgactggaccccttgtctctct
15、ctctacagactgcttcacggac tctttgctgttgacgatctcctggtagcatgaccttttggcctttgttaagacacacagcctttctgtat caagccccctgtctaacctacgacccagagtgactgacggctgtgta (2182略略) 背景 出题人:北京工业大学 孟大志 2000年6月26日, “人类基因组计划”规定 的禁发时间（北京时间18:00）刚过, 新华社 、法新社、美联社、路透社各国新闻 发布机构以第一条消息发布了人类基金组 草图绘就的重要消息。 作为解读基因组这一庞大计划的一个十分 重要而又基础的部分,就是研究基因组
16、的结 构,而其中更基础的是DNA序列的结构. 这里这里“结构结构”这个词的含义十分广泛这个词的含义十分广泛: 作为由作为由 A、T、C、G四个字符组成的一个有序字符四个字符组成的一个有序字符 串串, 任何呈现规律性的特征都可以称为结构任何呈现规律性的特征都可以称为结构 局部结构局部结构(小尺度结构小尺度结构) 整体结构整体结构(大尺度结构大尺度结构) 这些结构的揭示将大大有助于人们对于基这些结构的揭示将大大有助于人们对于基 因与基因组的解读因与基因组的解读. 在这一世界科学发展的大背景下在这一世界科学发展的大背景下, 2000年数年数 学建模比赛学建模比赛A题就取材于题就取材于DNA结构的研究结构的研究. 立意 源于科学实际源于科学实际,解法充分开放解法充分开放 A题将题将DNA结构的研究具体化为不同序列的结构的研究具体化为不同序列的 分类分类 由于由于”结构结构“的含义是广泛的的含义是广泛的,担心学生因此担心学生因此
