2000网易杯全国大学生数学建模竞赛题目 A题DNA序列分类 2000年6月,人类基因组计划中DNA全序列草图完成,预计2001年可以完成精确的 全序列图,此后人类将拥有一本记录着自身生老病死及遗传进化的全部信息的“天书”这 本大自然写成的“天书”是由4个字符A,T,C,G按·定顺序排成的长约30亿的序列,其中 没有“断句”也没有标点符号,除了这4个字符表示4种碱基以外,人们对它包含的“内容”知 之甚少,难以读懂破译这部世界上最巨量信息的“天书”是二十一世纪最重要的任务之 在这个目标中,研究DNA全序列具有什么结构,由这4个字符排成的看似随机的序列中隐 臧着什么规律,又是解读这部天书的基础,是生物信息学( Boinfom atics最重要的课题之 虽然人类对这部“天书”知之甚少,但也发现了DNA序列中的一些规律性和结构例 如,在全序列中有一些是用于编码蛋白质的序列片段,即由这4个字符组成的64种不同的 3字符串,其中大多数用于编码构成蛋白质的20种氨基酸又例如,在不用于编码蛋白质的 序列片段中,A和T的含量特别多些,于是以某些碱基特别丰富作为特征去研究DNA序列 的结构也取得了一些结果此外,利用统计的方法还发现序列的某些片段之间具有相关性 等等这些发现让人们相信,DNA序列中存在着局部的和全局性的结构,充分发掘序列的 结构对理解DNA全序列是十分有意义的目前在这项研究中最普通的思想是省略序列的 某些细节,突出特征,然后将其表示成适当的数学对象这种被称为粗粒化和模型化的方法 往往有助于研究规律性和结构 作为研究DNA序列的结构的尝试,提出以下对序列集合进行分类的问题 1)下面有20个已知类别的人工制造的序列(见反面),其中序列标号10为A类,11 20为B类请从中提取特征,构造分类方法,并用这些已知类别的序列,衡量你的方法是 否足够好然后用你认为满意的方法,对另外20个未标明类别的人工序列(标号2140)进 行分类,把结果用序号(按从小到大的顺序)标明它们的类别(无法分类的不写入) B类 请详细描述你的方法,给出计算程序如果你部分地使用了现成的分类方法,也要将方 法名称准确注明 这40个序列也放在如下地址的网页上,用数据文件 A rhode-data标识,供下载 网易网址:www163m教育频道在线试题 教育网:www.chiakieducNewsmam2000 教育网:www.csiam.educn/mam 2)在同样网址的数据文件 Natmodel-data中给出了182个自然DNA序列,它们都较 长用你的分类方法对它们进行分类,像1)一样地给出分类结果 提示衡量分类方法优劣的标准是分类的正确率,构造分类方法有许多途径,例如提取 序列的某些特征,给出它们的数学表示几何空间或向量空间的元素等,然后再选择或构造 适合这种数学表示的分类方法又例如构造概率统计模型,然后用统计方法分类等 2 01995-2004 Tsinghua Tongfang Optical Disc Co, Lid. All rights reserved.2000 网易杯全国大学生数学建模竞赛题目 A 题 D NA 序列分类 2000 年 6 月, 人类基因组计划中DNA 全序列草图完成, 预计 2001 年可以完成精确的 全序列图, 此后人类将拥有一本记录着自身生老病死及遗传进化的全部信息的“天书”. 这 本大自然写成的“天书”是由 4 个字符A , T , C, G 按一定顺序排成的长约 30 亿的序列, 其中 没有“断句”也没有标点符号, 除了这 4 个字符表示 4 种碱基以外, 人们对它包含的“内容”知 之甚少, 难以读懂. 破译这部世界上最巨量信息的“天书”是二十一世纪最重要的任务之一. 在这个目标中, 研究DNA 全序列具有什么结构, 由这 4 个字符排成的看似随机的序列中隐 藏着什么规律, 又是解读这部天书的基础, 是生物信息学(B io info rm atics) 最重要的课题之 一. 虽然人类对这部“天书”知之甚少, 但也发现了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 个序列也放在如下地址的网页上, 用数据文件A rt2m odel2data 标识, 供下载: 网易网址: www. 163. com 教育频道 在线试题; 教育网: www. cb i. pku. edu. cn N ew s m cm 2000 教育网: www. csiam. edu. cnöm cm 2) 在同样网址的数据文件N at2m odel2data 中给出了 182 个自然DNA 序列, 它们都较 长. 用你的分类方法对它们进行分类, 像 1) 一样地给出分类结果. 提示: 衡量分类方法优劣的标准是分类的正确率, 构造分类方法有许多途径, 例如提取 序列的某些特征, 给出它们的数学表示: 几何空间或向量空间的元素等, 然后再选择或构造 适合这种数学表示的分类方法; 又例如构造概率统计模型, 然后用统计方法分类等. 2 数 学 的 实 践 与 认 识 31 卷 © 1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved