2000网易杯全国大学生数学建模竞赛题目 A题DNA序列分类 2000年6月,人类基因组计划中DMA全序列草图完成,预计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标识,供下载: 网易网址:ww163com 教育频道在线试题; 教育网 cu. edu. cn Newsmcm2000 教育网:w. cslam.edu.cn/mcm (2)在同样网址的数据文件Nat- model-data中给出了182个自然DNA序列,它们都较长。用你的分 类方法对它们进行分类,像(1)一样地给出分类结果 提示:衡量分类方法优劣的标准是分类的正确率,构造分类方法有许多途径,例如提取序列的某些特 征,给出它们的数学表示:几何空间或向量空间的元素等,然后再选择或构造适合这种数学表示的分类方 法:又例如构造概率统计模型,然后用统计方法分类等
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 标识，供下载： 网易网址： www.163.com 教育频道 在线试题； 教育网： www.cbi.pku.edu.cn Newsmcm2000 教育网： www.csiam.edu.cn/mcm （2）在同样网址的数据文件 Nat-model-data 中给出了 182 个自然 DNA 序列，它们都较长。用你的分 类方法对它们进行分类，像（1）一样地给出分类结果。 提示：衡量分类方法优劣的标准是分类的正确率，构造分类方法有许多途径，例如提取序列的某些特 征，给出它们的数学表示：几何空间或向量空间的元素等，然后再选择或构造适合这种数学表示的分类方 法；又例如构造概率统计模型，然后用统计方法分类等
Art-model-data 1. aggcacggaaaaacgggaataacggaggaggact tggcacggcattacacggaggacgaggtaaaggaggcttgtctacggacggaagt gaagggggatatgaccgcttgg 2. cggaggacaaacgggatggcggtat tggaggt ggcggactgttcggggaattattcggtt taaacgggacaaggaaggcggct ggaacaaocggacggtggcagcaaagga 3. gggacggatacggattctggccacggacggaaaggaggacacggcggacatacacggrggcaacggacggaacggaggaaggagggcggcaatcggtacggaggcggcgga 4. atggataacggaaacaaaccagacaaacttcggtagaaatacagaagct tagatgcatatgttttt taaataaaatttgtattattatggtatcataaaaaaaggttgcga 5. cggctggcggacaacggactggcggattccaaaaacggaggaggoggacggaggctacaccaccgtttcggcggaaaggcggagggetggcaggaggctcat tacggggag 6. atggaaaattttcggaaaggcggcaggcaggaggcaaaggcggaaaggaaggaaacggcggatat ttcggaagt ggatat taggagggcggaataaaggaacggcggcaca 7. atgggattattgaatggcggaggaagat ccggaataaaatatggcggaaagaacttgttttcggaaatggaaaaaggactaggaatcggcggcaggaaggatatggaggcg 8. atggccgatcggcttaggctggaaggaacaaataggcggaattaaggaaggcgttctcgcttttcgacaaggaggcggaccataggaggcggattaggaacggt tat gagg 9. atggcggaaaaaggaaatgtttggcatcggcgggctccggcaactggaggttcggccatggaggegaaaatcgt gggcggcggcagcgctggccggagtttgaggagcgcg 10. tggccgcggaggggcccgtcgggcgcggatttctacaagggcttcctgttaaggaggtggcatccaggcgtcgcacgctcggcgeggcaggaggcacgcgggaaaaaacg ll. gttagatttaacgttttttat ggaatttatggaattataaat t taaaaatt tatattttttaggtaagtaatccaacgtttttat tactttttaaaat taaatatttat 12. gtttaat tactt tatcatt taatttaggttttaattt taaat ttaatt taggtaagatgaatttggttttttt taaggtagt tat ttaattatcgttaaggaaagt taaa 13. gtattacaggcagaccttatttaggttattattattatttggattttttttttttttttttt taagttaaccgaat tattttctttaaagacgt tact taatgtcaat 14. gttagtcttttttagattaaat tat tagat tat gcagtttttttacataagaaaatttttttttcggagt tcatat tctaatctgtctttattaaatcttagagatatta 15. gtattatatttttttatttttattattttagaatataatttgaggtat gtgtttaaaaaaaatttttttttttttttttttttttttttttttaaaatttataaatttaa 16. gttatttttaaatttaattttaattttaaaatacaaaatttttactttctaaaat tggtctctggatcgataatgtaaacttattgaatctatagaat tacattattgat 17. gtatgtctatttcacggaagaatgcaccactatatgattt gaaat tatctat ggctaaaaaccct cagtaaaatcaatccctaaacoct taaaaaacggcggcctatccc 18. gttaattatttattccttacgggcaat taattatttattacggttttatttacaattttttttttttgtcctatagagaaat tact tacaaaacgttattttacatactt 19. gttacattatttattattatccgttatcgataattttttacctcttttttcgctgagtttttattcttactttttttcttctttatataggatctcatttaatatcttaa 20. gtatttaactctctttactttttttttcactctctacattttcatcttctaaaactgtttgatttaaacttttgtttctttaaggattttttttact tatcctctgttat 21. tttagctcagtccagctagctagtttacaatttcgacaccagtttcgcaccatcttaaatttcgatccgtaccgtaatttagcttagatttggatttaaaggatttagattga 22. tttagtacagtagctcagtccaagaacgatgtttaccgtaacgtqacgtaccgtacgctaccgttaccggattccggaaagccgattaaggaccgatcgaaaggg 23. cgggcggatttaggccgacggggacccgggattcgggacccgaggaaattcccggattaaggtttagcttcccgggatttagggcccggatggctgggaccc 24. tttagctagctactttagctattttagtagctagccagcctttaaggctagctttagctagcattgttctttattgggacccaagttcgacttttacgatttagttttgaccgt 25. gaccaaaggtgggctttagggacccgatgctttagtcgcagctggaccagttccccagggtattaggcaaaagctgacgggcaattgcaatttaggcttaggcca 26. gatttactttagcatttttagctgacgttagcaagcattagctttagccaatttcgcatttgccagtttcgcagctcagttttaacgcgggatctttagcttcaagctttttac ggattcggatttacccggggattggcggaacgggacctttaggtcgggacccattaggagtaaatgccaaaggacgctggtttagccagtccgttaaggcttag 28. tccttagatttcagttactatatttgacttacagtctttgagatttcccttacgattttgacttaaaatttagacgttagggcttatcagttatggattaatttagcttattttcga 29. ggccaattccggtaggaaggtgatggcccgggggttcccgggaggatttaggctgacgggccggccatttcggtttagggagggccgggacgcgttagggc 30. cgctaagcagctcaagctcagtcagtcacgtttgccaagtcagtaatttgccaaagttaaccgttagctgacgctgaacgctaaacagtattagctgatgactcgta 31. ttaaggacttaggctttagcagttactttagtttagttccaagctacgtttacgggaccagatgctagctagcaatttattatccgtattaggcttaccgtaggtttagcgt 32. gctaccgggcagtctttaacgtagctaccgtttagtttgggcccagccttgcggtgtttcggattaaattcgttgtcagtcgctctrtgggtttagtcattcccaaaagg 33. cagttagctgaatcgtttagccatttgacgtaaacatgattttacgtacgtaaattttagccctgacgtttagctaggaatttatgctgacgtagcgatcgactttagcac 34. cggttagggcaaaggttggatttcgacccagggggaaagcccgggacccgaacccagggctttagcgtaggctgacgctaggcttaggttggaacccggaaa 35. gcggaagggcgtaggtttgggatgcttagccgtaggctagctttcgacacgatcgattcgcaccacaggataaaagttaagggaccggtaagtcgcggtagcc 36. ctagctacgaacgctttaggcgcccccgggagtagtcgttaccgttagtatagcagtcgcagtcgcaattcgcaaaagtccccagctttagccccagagtcgacg 37. gggatgctgacgctggttagctttaggcttagcgtagctttagggccccagtctgcaggaaatgcccaaaggaggcccaccgggtagatgccasagtgcaccgt 38. aacttttagggcatttccagttttacgggttattttcccagttaaactttgcaccattttacgtgttacgatttacgtataatttgaccttattttggacactttagtttgggttac 39. ttagggccaagtcccgaggcaaggaattctgatccaagtccaatcacgtacagtccaagtcaccgtttgcagctaccgtttaccgtacgttgcaagtcaaatccat 40. ccattagggtttatttacctgtttatttttcccgagaccttaggtttaccgtactttttaacggtttacctttgaaatttttggactagcttaccctggatttaacggccagttt
Art-model-data 1.aggcacggaaaaacgggaataacggaggaggacttggcacggcattacacggaggacgaggtaaaggaggcttgtctacggccggaagtgaagggggatatgaccgcttgg 2.cggaggacaaacgggatggcggtattggaggtggcggactgttcggggaattattcggtttaaacgggacaaggaaggcggctggaacaaccggacggtggcagcaaagga 3.gggacggatacggattctggccacggacggaaaggaggacacggcggacatacacggcggcaacggacggaacggaggaaggagggcggcaatcggtacggaggcggcgga 4.atggataacggaaacaaaccagacaaacttcggtagaaatacagaagcttagatgcatatgttttttaaataaaatttgtattattatggtatcataaaaaaaggttgcga 5.cggctggcggacaacggactggcggattccaaaaacggaggaggcggacggaggctacaccaccgtttcggcggaaaggcggagggctggcaggaggctcattacggggag 6.atggaaaattttcggaaaggcggcaggcaggaggcaaaggcggaaaggaaggaaacggcggatatttcggaagtggatattaggagggcggaataaaggaacggcggcaca 7.atgggattattgaatggcggaggaagatccggaataaaatatggcggaaagaacttgttttcggaaatggaaaaaggactaggaatcggcggcaggaaggatatggaggcg 8.atggccgatcggcttaggctggaaggaacaaataggcggaattaaggaaggcgttctcgcttttcgacaaggaggcggaccataggaggcggattaggaacggttatgagg 9.atggcggaaaaaggaaatgtttggcatcggcgggctccggcaactggaggttcggccatggaggcgaaaatcgtgggcggcggcagcgctggccggagtttgaggagcgcg 10.tggccgcggaggggcccgtcgggcgcggatttctacaagggcttcctgttaaggaggtggcatccaggcgtcgcacgctcggcgcggcaggaggcacgcgggaaaaaacg 11.gttagatttaacgttttttatggaatttatggaattataaatttaaaaatttatattttttaggtaagtaatccaacgtttttattactttttaaaattaaatatttatt 12.gtttaattactttatcatttaatttaggttttaattttaaatttaatttaggtaagatgaatttggttttttttaaggtagttatttaattatcgttaaggaaagttaaa 13.gtattacaggcagaccttatttaggttattattattatttggattttttttttttttttttttaagttaaccgaattattttctttaaagacgttacttaatgtcaatgc 14.gttagtcttttttagattaaattattagattatgcagtttttttacataagaaaatttttttttcggagttcatattctaatctgtctttattaaatcttagagatatta 15.gtattatatttttttatttttattattttagaatataatttgaggtatgtgtttaaaaaaaatttttttttttttttttttttttttttttttaaaatttataaatttaa 16.gttatttttaaatttaattttaattttaaaatacaaaatttttactttctaaaattggtctctggatcgataatgtaaacttattgaatctatagaattacattattgat 17.gtatgtctatttcacggaagaatgcaccactatatgatttgaaattatctatggctaaaaaccctcagtaaaatcaatccctaaacccttaaaaaacggcggcctatccc 18.gttaattatttattccttacgggcaattaattatttattacggttttatttacaattttttttttttgtcctatagagaaattacttacaaaacgttattttacatactt 19.gttacattatttattattatccgttatcgataattttttacctcttttttcgctgagtttttattcttactttttttcttctttatataggatctcatttaatatcttaa 20.gtatttaactctctttactttttttttcactctctacattttcatcttctaaaactgtttgatttaaacttttgtttctttaaggattttttttacttatcctctgttat 21.tttagctcagtccagctagctagtttacaatttcgacaccagtttcgcaccatcttaaatttcgatccgtaccgtaatttagcttagatttggatttaaaggatttagattga 22.tttagtacagtagctcagtccaagaacgatgtttaccgtaacgtqacgtaccgtacgctaccgttaccggattccggaaagccgattaaggaccgatcgaaaggg 23.cgggcggatttaggccgacggggacccgggattcgggacccgaggaaattcccggattaaggtttagcttcccgggatttagggcccggatggctgggaccc 24.tttagctagctactttagctatttttagtagctagccagcctttaaggctagctttagctagcattgttctttattgggacccaagttcgacttttacgatttagttttgaccgt 25.gaccaaaggtgggctttagggacccgatgctttagtcgcagctggaccagttccccagggtattaggcaaaagctgacgggcaattgcaatttaggcttaggcca 26.gatttactttagcatttttagctgacgttagcaagcattagctttagccaatttcgcatttgccagtttcgcagctcagttttaacgcgggatctttagcttcaagctttttac 27.ggattcggatttacccggggattggcggaacgggacctttaggtcgggacccattaggagtaaatgccaaaggacgctggtttagccagtccgttaaggcttag 28.tccttagatttcagttactatatttgacttacagtctttgagatttcccttacgattttgacttaaaatttagacgttagggcttatcagttatggattaatttagcttattttcga 29.ggccaattccggtaggaaggtgatggcccgggggttcccgggaggatttaggctgacgggccggccatttcggtttagggagggccgggacgcgttagggc 30.cgctaagcagctcaagctcagtcagtcacgtttgccaagtcagtaatttgccaaagttaaccgttagctgacgctgaacgctaaacagtattagctgatgactcgta 31.ttaaggacttaggctttagcagttactttagtttagttccaagctacgtttacgggaccagatgctagctagcaatttattatccgtattaggcttaccgtaggtttagcgt 32.gctaccgggcagtctttaacgtagctaccgtttagtttgggcccagccttgcggtgtttcggattaaattcgttgtcagtcgctctrtgggtttagtcattcccaaaagg 33.cagttagctgaatcgtttagccatttgacgtaaacatgattttacgtacgtaaattttagccctgacgtttagctaggaatttatgctgacgtagcgatcgactttagcac 34.cggttagggcaaaggttggatttcgacccagggggaaagcccgggacccgaacccagggctttagcgtaggctgacgctaggcttaggttggaacccggaaa 35.gcggaagggcgtaggtttgggatgcttagccgtaggctagctttcgacacgatcgattcgcaccacaggataaaagttaagggaccggtaagtcgcggtagcc 36.ctagctacgaacgctttaggcgcccccgggagtagtcgttaccgttagtatagcagtcgcagtcgcaattcgcaaaagtccccagctttagccccagagtcgacg 37.gggatgctgacgctggttagctttaggcttagcgtagctttagggccccagtctgcaggaaatgcccaaaggaggcccaccgggtagatgccasagtgcaccgt 38.aacttttagggcatttccagttttacgggttattttcccagttaaactttgcaccattttacgtgttacgatttacgtataatttgaccttattttggacactttagtttgggttac 39.ttagggccaagtcccgaggcaaggaattctgatccaagtccaatcacgtacagtccaagtcaccgtttgcagctaccgtttaccgtacgttgcaagtcaaatccat 40.ccattagggtttatttacctgtttattttttcccgagaccttaggtttaccgtactttttaacggtttacctttgaaatttttggactagcttaccctggatttaacggccagttt
B题钢管订购和运输 要铺设一条的A→A2 →A5输送天然气的主管道,如图一所示(见下页)。经筛选后可以生产这种 主管道钢管的钢厂有S,S2,……S。图中粗线表示铁路,单细线表示公路,双细线表示要铺设的管道(假 设沿管道或者原来有公路,或者建有施工公路),圆圈表示火车站,每段铁路、公路和管道旁的阿拉伯数 字表示里程(单位km) 为方便计,1km主管道钢管称为1单位钢管。 一个钢厂如果承担制造这种钢管,至少需要生产500个单位。钢厂S在指定期限内能生产该钢管的最 大数量为S1个单位,钢管出厂销价1单位钢管为P万元,如下 Si 800 800 1000 2000 2000 2000 3000 P: 160 160 155 150 1单位钢管的铁路运价如下表 里程(km) 300301~350351~400401~450451-~500 运价(万元) 里程(km) 501~600 601~700 701~800801~900901~1000 运价(万元) 44 1000km以上每增加1至100km运价增加5万元 公路运输费用为1单位钢管每公里0.1万元(不足整公里部分按整公里计算)。 钢管可由铁路、公路运往铺设地点(不只是运到A→A →A15点,而是管道全线)。 1、请制定一个主管道钢管的订购和运输计划,使总费用最小(给出总费用)。 2、请就1的模型分析:哪个钢厂钢管的销价的变化对购运计划和总费用影响最大,哪个钢厂钢管的 产量的上限的变化对购运计划和总费用的影响最大,并给出相应的数字结果 3、如果要铺设的管道不是一条线,而是一个树形图,铁路、公路和管道构成网络,请就这种更一般 的情形给出一种解决办法,并对图二按1的要求给出模型和结果
B 题 钢管订购和运输 要铺设一条的 A1→A2→……→A15 输送天然气的主管道，如图一所示(见下页)。经筛选后可以生产这种 主管道钢管的钢厂有 S1，S2，……S7。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道(假 设沿管道或者原来有公路，或者建有施工公路)，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数 字表示里程(单位 km)。 为方便计，1km 主管道钢管称为 1 单位钢管。 一个钢厂如果承担制造这种钢管，至少需要生产 500 个单位。钢厂 Si 在指定期限内能生产该钢管的最 大数量为 Si 个单位，钢管出厂销价 1 单位钢管为 Pi 万元，如下表： i 1 2 3 4 5 6 7 Si 800 800 1000 2000 2000 2000 3000 Pi 160 155 155 160 155 150 160 1 单位钢管的铁路运价如下表： 里程(km) ≤300 301～350 351～400 401～450 451～500 运价(万元) 20 23 26 29 32 里程(km) 501～600 601～700 701～800 801～900 901～1000 运价(万元) 37 44 50 55 60 1000km 以上每增加 1 至 100km 运价增加 5 万元。 公路运输费用为 1 单位钢管每公里 0.1 万元（不足整公里部分按整公里计算）。 钢管可由铁路、公路运往铺设地点（不只是运到 A1→A2→……→A15 点，而是管道全线）。 1、请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用）。 2、请就 1 的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的 产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。 3、如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，请就这种更一般 的情形给出一种解决办法，并对图二按 1 的要求给出模型和结果
1200 49410300 205 图 15 720 500 210 195 All 606 图二
A1 3 2 5 80 10 10 31 20 12 42 70 10 88 10 70 62 70 30 20 20 30 450 104 301 750 606 194 205 201 680 480 300 220 210 420 500 600 306 0 195 202 720 690 520 170 690 462 160 320 160 110 290 1150 1100 1200 A2 A3 A4 A5 A6 A11 A7 11 A1 1 A8 A1 1 A9 11 A1 1 A10 A11 A12 A13 A14 A15 S1 S2 S3 S4 S5 S6 S7 图一 A1 3 2 5 80 10 10 31 20 12 42 70 10 88 10 70 62 70 30 20 20 30 450 104 301 750 606 194 205 201 680 480 300 220 210 420 500 600 306 0 195 202 720 690 520 170 690 462 160 320 160 110 290 1150 1100 1200 A19 130 190 260 100 A2 A3 A4 A5 A6 A7 A8 A1 1 A9 A10 A11 A12 A13 A14 A15 S1 S2 S3 S4 S5 S6 S7 A16 A17 A18 A20 (A21) 图二