2001年全国大学生数学建模竞赛题目(本科组).doc

2001年全国大学生数学建模竞赛题目(本科组)l 全部题目(包括数据)可以从以下网址下载：/mcm 网易教育频道A题 血管的三维重建 断面可用于了解生物组织、器官等的形态。例如，将样本染色后切成厚约如m的切片，在显微镜下观察该横断面的组织形态结构。如果用切片机连续不断地将样本切成数十、成百的平行切片，可依次逐片观察。根据拍照并采样得到的平行切片数字图象，运用计算机可重建组织、器官等准确的三维形态。假设某些血管可视为一类特殊的管道，该管道的表面是由球心沿着某一曲线(称为中轴线)的球滚动包络而成。例如圆柱就是这样一种管道，其中轴线为直线，由半径固定的球滚动包络形成。现有某管道的相继100张平行切片图象，记录了管道与切片的交。图象文件名依次为0.bmp、1.bmp、99.bmp，格式均为BMP，宽、高均为512个象素(pixel)。为简化起见，假设：管道中轴线与每张切片有且只有一个交点；球半径固定；切片间距及图象象素的尺寸均为1。取坐标系的Z轴垂直于切片，第1张切片为平面Z=0，第100张切片为平面Z=99。Z=Z切片图象中象素的坐标依它们在文件中出现的前后次序为 (256，256，Z)，(256，255，Z)，(256，255，Z) (255，256，Z)，(255，255，Z)，(255，255，Z) (255，256，Z)，(255，255，Z)，(255，255，Z)。 试计算管道的中轴线与半径，给出具体的算法，并绘制中轴线在XY、YZ、ZX平面的投影图。下面是100张平行切片图象中的6张，全部图象请从网上下载。关于BMP图象格式可参考：1VisualC+ +数字图象处理第12页2.3.1节。何斌等编著，人民邮电出版社，2001年4月。2http：www.dcs.ed.ac.ukhomemxrgfx2dBMP.txtB题 公交车调度公共交通是城市交通的重要组成部分，作好公交车的调度对于完善城市交通环境、改进市民出行状况、提高公交公司的经济和社会效益，都具有重要意义。下面考虑一条公交线路上公交车的调度问题，其数据来自我国一座特大城市某条公交线路的客流调查和运营资料。该条公交线路上行方向共14站，下行方向共13站，下面给出的是典型的一个工作日两个运行方向各站上下车的乘客数量统计。公交公司配给该线路同一型号的大客车，每辆标准载客100人，据统计客车在该线路上运行的平均速度为20公里小时。运营调度要求，乘客候车时间一般不要超过10分钟，早高峰时一般不要超过5分钟，车辆满载率不应超过120，一般也不要低于50。 试根据这些资料和要求，为该线路设计一个便于操作的全天(工作日)的公交车调度方案，包括两个起点站的发车时刻表；一共需要多少辆车；这个方案以怎样的程度照顾到了乘客和公交公司双方的利益；等等。 如何将这个调度问题抽象成一个明确、完整的数学模型，指出求解模型的方法；根据实际问题的要求，如果要设计更好的调度方案，应如何采集运营数据。某路公交汽车各时组每站上下车人数统计表 上行方向：A13开往A0站名 A13A12AllA10A9A8A7A6A5A4A3A2A1A0站间距(公里)1.60.510.732.041.262.2911.20.4111.030.535：006：00上3716052437690488385264545110下08913204845813218242585576：007：00上1990376333256589594315622510176308307680下0991051642395885428004072083002889216157：008：00上3626634528447948868523958904259465454990下0205227272461105810971793801469560636187114598：009：00上2064322305235477549271486439157275234600下010612316930063462197144024533940811327599：0010：00上118620516614728130417232426778143162360下0817512018140741155125013618723377448310：0011：00上92315112010821521411921220175123112260下052558113629928044217810515316753238511：0012：00上95718115713325426413525326074138117300下054588413132129142019611915915353434012：0013：00上87314114010821520412923222165103112260下046497111126325638916411113414848833313：0014：00上779141103841861851032111736610897230下03941701032211972971378511311638426314：0015：00上6251041088216218090185170497585200下036394778189176339139809712038323915：0016：00上635124988215218080185150498585200下0363957882091963391298010711035322916：0017：00上1493299240199396404210428390120208197490某路公交汽车各时组每站上下车人数统计表 上行方向：A13开往A0某路公交汽车各时组每站上下车人数统计表 上行方向：A0开往A13下0808513519445044173133515725525180055717:0018:00上2011379311230497479296586508140250259610下0110118171257694573957390253293378122879318:0019:00上69112410789167165108201194539382220下04548801082372313901508913112542833619:0020;00上3506455469185508889274847110下0222334631161081968348646620413920:0021:00上304504336727540776022383790下01617243880841435934464716011721:0022:00上209373226535529475216282760下0141421337863125623040411289222:0023:00上193325535513210下03358181727127993221 站名A0A2A3A4A5A6A7A8A9A10AllA12A13站间距(公里)15610441，209722913207310，51，625：006：00上22342443331100下02116775342396：007：00上795143167841511881091371304553160下070404018420519514793109751082717：008：00上2328380427224420455272343331126138450下02941561577107808495453744442653739588：009：00上27063744922244045323333453541201534600下026615814975682785652936742823737611679：0010：00上15562042741252353081622031987699270下01571008041051149833619927613621955610：0011：00上902147183821552061201501435059180下010359592463463201911471859615443811：0012：00上847130132671271501081041074148150下09448481992382561751221436812834612：0013：00上70690118661051449295883440120下07040401742152051271031196598261某路公交汽车各时组每站上下车人数统计表 上行方向：A0开往A1313：0014：00上7709712659102133971021043643130下0754343166210209136901276011530914：0015：00上839133156691301651011181204249150DNA序列的分类模型汤诗杰， 周 亮， 王晓玲指导老师： 孙广中(中国科技大学，合肥 230026)编者按：本文提出了DNA序列分类的三种模型其一，基于A、G、T、C四种碱基出现的频率；具二利用了同碱基在序列中的间隔。这一信息是单纯考虑频率所不能包含的；在第三种模型中作者把DNA序列视为一个信息流考虑每增加一个字符所带来的信息增量尽管文中信息量的定义方式仍可讨论，但本文思想新颖活跃，有其独特之处本文最后的分类方法足以上三种的综合使用摘要：本文针对DNA序列分类这个实际问题，提出了相应的数学模型为了很好的体现DNA序列的局部性和全局性的特征我们给出厂衡量分类方法优劣的标准，即在满足一定限制条件的情况下是否能充分反映序列的各方面特性 依据我们提出的判别标准。单一标准的分类是无法满足要求的，我们的方法是侧重点不同的三种方法的综合集成这三种方法分别体现了序列中元素出现的概率，序列中元素出现的周期性，序列所带有的信息含量利用这个方法完成了对未知类型的人工序列及自然序列的分类工作最后。对分类模型的优缺点进行了分析,并就模型的推广作了讨论1 问题的提出(略)2 问题的分析 这是一个比较典型的分类问题，为了表述的严格和方便，我们用数学的方法来重述这个问题已知字母序列其中；有字符序列集合A，B，满足并当时，现要求考虑当与集合A及集合B的关系 在这里，问题的关键就是要从已知的分好类的20个字母序列中提取用于分类的特征知道了这些特征，我们就可以比较容易的对那些未标明类型的序列进行分类下面我们将首先对用于分类的标准问题进行必要的讨论3 分类的标准及评价 首先，我们提取的特征应该满足以下两个条件： (1)所取特征必须可以标志A组和B组也就是说，我们利用这些特征应该可以很好的区分已经标示分类的20个序列这是比较显然的一个理由(2)所取特征必须是有一定的实际意义的这一点是决不能被忽视的比如，如果不考虑模型的实际意义，我们就可以以序列的开头字母为分类标准：已知在B类中的十个序列都是以gt开始的，而已知在A类中10个序列没有以z2开始的，甚至以算开始的都没有显然这是满足上面的第一个条件的如果仅因此就认为这种特征是主要的，并简单的利用这个特征将所有待分类的序列分成两类，显然是不甚合理的对于这样的一个复杂的分类问题，需要考虑的因素很多，也是就说，可供我们使用的分类特征有许多如何从众多的因素中提取分类的主要因素，是我们处理这个问题的困难之处上面的第一个条件是我们的分类方法所必须满足的，可以看作是个限制条件；而第二个条件是我们在设计分类方法时必须考虑到的，可以看作是对分类方法优劣的一种衡量，是某种意义下的目标函数4 模型的建立及分析由上面的分析可知，由于DNA序列本身的复杂性，我们很难在不知道确切的分类标准的情况下，使用单一的方法来处理这个分类问题由于，DNA序列同时具有局部性和全局性的特征，我们尝试综合使用几种设计思想不同的方法来处理这个问题，以使该分类方法具有好的分类性能和相当的健壮性下面我们先从不同的角度出发，提出三种侧重点不同的分类方法，第一种从频率角度出发，第二种从字母出现的周期性的角度出发，第三种从序列所带的某方面的信息量出发，并给出它们单独使用时的分类结果我们认为，这三方面综合考虑，可以较好的体现出序列各个方面的特征，最后，从这三种方法出发，得到一个综合系统的分类方法，并利用它得到了最终的182个序列的分类结果方法1 基于字母出现频率不同段的DNA中，每个碱基出现的概率并不相同，从生物理论中，我们知道，编码蛋白质的DNA中G、C含量偏高，而非编码蛋白质的DNA中A、T含量偏高因此，A、G、T、C的频率中会含有很多的信息，下面给出A、B组的频率统计见表1，表2(略)由统计的数字可以看出，A组的碱基构成与B组的碱基构成有较大的不同A组的G含量较高，B组的T含量较高为做定量化的分析，引入数学中的内积概念，即将A、T、G、C的频率分别作为四维向量的四个分量()，现在我们得到两组向量，然后将未知的序列2140作为一个新的向量C，要将它归人A组或B组，我们可以尝试在Hilbert空间中将向量归一化后求C与A组和B组的平均距离记、为归一化后的向量为此，我们计算内积和，其中内积定义为欧氏度量引导出的内积(c1，c2，c3，c4)(a1,a2,a3,a4)clal+c2a2+c303+c4a4.即内积小的两个序列，我们可以认为它们的相关性小，而内积大的序列，我们就认为其相关性大因此，如果则认为C应归人A类，否则认为它应归人B类由此，我们找到了区分C组的一种方法，这种比较的方法，我们可以归纳为一个目标函数F1(l)，即 表3未知的序号与A组的内积与B组的内积属于的类型未知的序号与A组的内积与B组的内积属于的类型123456789100.8157810.9269220.9397270.7885240.9481940.8012010.953019.07460710.9310070.8977740.9388140.8039520.6568270.9371350.7720760.9301210.766950.9680350.6131930.844082BAABABABAA111213141516171819200.8522310.8669760.8609550.9616890.9603220.9042820.9447240.758620.8856310.755840.9209570.85396709171220.676780.7390890.7475780.7236640.9546520.8118370.941BABAAAABAB方法一讨论 这种方法是从概率统计的角度分析问题，通过对每个字母出现频率的计算，找出A，B两类DNA链中的频率特性，建立四维向量空间，然后对待求分类的序列统计频率，与已知分类的向量进行内积运算，找出量化的关联性，从而将其分类但这种方法也有其局限性，在统计字母出现的频率时，忽略了字母所在位置以及各个字母之间的相互关系，造成用这种方法对已知分类的序列进行检验时，个别频率特性不明显的序列不太容易分类所以，这种方法虽然有其科学性，但还不够完善，不能完全体现序列的所有特征 方法二 基于字母出现周期性 在以上进行了基于字母出现频率的分类之后，我们认为，一个序列所含的信息远不止每个字母出现的频率，还有字母出现和它前后若干个字母的相关联性，字母在序列中出现的规律性等等前一个问题我们留到下面讨论，现在我们想办法处理后一个问题对于某单个字母，以d为例，假设它在序列中第九，扎。，扎+，个位置出现，我们试图找出这些数字之间的关联首先，可以认识到考查乙的分布及绝对值是意义不大的，因为序列是一大段DNA中的一个片断，片断的起始段不同会导致乙的不同于是为了抵消打的线性位移，考虑下面一组值 即字母“出现的间距可以看出，序列的大小包含的信息是“的“稠密度”，也可看成一个与频率有关的量，前面已经处理过所以我们可以考虑序列 的波动幅度，幅度越小，说明的值越趋于统一，即a的出现周期性越大而表征波动幅度的量在统计中是中心矩现求，；的二阶中心矩，即方差 同理，可以求出Varg，、Vart，、Varc, 由所得数据知，对Varg与Vart，上述方法对A、B组的区分率很高，就有良好的可分辨性为了强调这种特征的显著性，我们用F2VargVart作为这种方法的目标函数 由图1可以看出点与原点连线的斜率在A组中和B组中有显著差别，根据这个特征，A组和B组可以很好地区分开来。并且较好地弥补了方法一中的不全面之处方法二讨论 这种方法是从序列中相邻相同字母之间的距离即字母出现的周期性着手分析的它统计了每个字母在序列中两次出现的间隔，并且用方差度量这种间隔的波动大小，由此找到了一个能较好区分A，B组的目标函数，综合地考虑了序列全局和局部的性质 方法3 基于序列熵值 我们可以把一串DNA序列看成一个信息流，这与生物学的基础知识是相应的关于A、B的分类，可以考虑其单位序列所含信息量(即熵)的多少从直观上来看，我们可以认为，重复得越多，信息量越少这是我们通过观察A、B组的特点而归纳出的方法设序列为L（a1,a2,a3,an）,前m个字符所带的信息量为记 即为加上第m个字母之后所增加的信息量然后，由，得为整个序列所带的信息量。即为单位长度所带的信息量，现在的问题就归结为如何找出一个合适的。 我们有理由认为：g具有以下性质： 性质即任意加上一个字符，它或多或少带有一定信息量； 性质2：第m个字符(或者是以它结尾的较短序列)与前面的序列(信息流)重复得越多，的值必然越小； 性质3：第m个字符(或者是以它结尾的较短序列)如果和与它靠得越近的重复，的值越小；和与它离得越远的重复， 的值越大； 性质对此，我们可以构造如下函数：其中b为防止分母为零而设的一个小正数；以第m-t个字符结尾的i字串且与以第t个字符结尾的i字串完全相同否则 a为一个小于1的数，其存在体现了A的性质3，即如果越近的位置出现重复，认为字串信息量越少，反之较多 的表达式中，t表示两个相同字串之间的距离，i表示宇串长度，这个表达式定量的给出距离和信息量之间的关系 又由于长度不同的字串重复对信息量的影响是不同的，所以必须在前乘上一个权值,由概率统计的知识可知，这种影响是呈指数上升的，则可选择一适当的常数c1，使得ti，这个表达式定量的给出长度和信息量之间的关系 可以认为，宇串长度太大的重复非常少见，则可将户取为某一固定的正数那么，给出a、b、c、p参数，就可以把严格确定下来通过反复上机搜索，我们认为，取，即只检查长度为1到6的字串即可 另外，职可以将A、B组值分得较开，并可以用来处理未知数据 方法三讨论 这种方法从序列的信息量(熵)人手，认为当序列中有大量的重复元素时，信息量就会比重复少的序列所含有的信息少所以，其侧重点是是序列前后的重复性，也就是序列元素的相关性从所给的A，B两类中可以很清楚地看到B中序列重复量大，所含的信息明显少于A组，而这个特征就被我们定义的熵函数凸显出来将DNA序列看成一个信息流的方法由于其在实际问题中的广泛背景，将会是一个很有价值的想法，统计学和信息论的一套非常成熟的强大工具也会在DNA研究中发挥巨大的作用 综合模型的建立 以上我们分别用三种方法得出了分类方案，这三种方案分别基于三种不同的方面对问题进行分析第一种方法主要考虑的是单个字母出现的频率；第二种方法主要考虑每个字母的出现是否具有周期性；而第三种方法则考虑的是每条DNA所蕴含的信息量我们将这三种方法对A、B组自身进行了检验，都得到了较令人满意的结果，但因为每个模型都只突出考虑序列某一方面的特征，所以，总有一些不尽如人意的地方，于是，我们认为应该把三种方法综合起来考虑，使序列各方面的特征都能得到体现，以使分类更加科学 下面就是我们将几种方法综合考虑得到最后结果 以上我们用三种方法得到了三个目标函数：，这三个目标函数可以作为分类的判别标准将它们看成定义在序列空间，作用于实轴上的函数现在，我们必须找到一个函数F，使得F可以体现序列的各个特征。 由于的值域范围差别很大，为了有效的比较这三个函数，我们必须将它们归一化，将看成一定义在上空间上的随机变量，A，为L的子集，则将归一化得 （1）代入（1）即得现估计投射L的点到实轴上后，的分界点其中 以为例，A的10个样本点和B的10个样本点不能被一个分界点分开，有极大似然估计的思想，分界点应该把尽可能多的点分开，即 由于的分布未知，故只能假设其满足较均匀的分布，则A，B的分界点的最好估计为而（由g的定义），恰好是分界点的最佳估计。同理，分界是对应分界点的最佳估计。令，则其分界点由F的构造方法知，F作用到A样本上大于零，作用到B样本上小于零，我们确定适当的权值，以此作为A，B的分类法即可。根据不同的实际情况，可以相应调节这三个权值，以体现分类中的不同因素所在的比重，在下面的计算中，我们简单的取a1=1, a2=-1, a3=0.5.得到的结果如表4，表5所示。表4序号目标函数值序号目标函数值序号目标函数值序号目标函数值A组123451.802881.758942.58870.275822.1781A组6789101.753551.251151.413711.90111.97282B组1112131415-1.38528-1.22372-0.940004-0.93612-2.27462B组1617181920-2.60295-0.0165438-1.31022-2.6043-3.603表5序号目标函数值类别序号目标函数值类别21222324252627282930-1.964540.8732792.32887-1.480051.21328-1.1841.22569-3.716162.692720.550393BAABABABAA31323334353637383940-1.06638-0.668504-0.8770532.609041.695351.222981.83991-3.014660.499763-2.77993BBBAAAABAB由以上数据可以看出，我们构造的目标函数具有较好的区分度对于A组，目标函数值都大于零；而对B组，目标函数值都小于零也就是说，用这种方法，对A、B组样本的区分率已达到了100正如前面所说，这种方法综合了序列中的许多信息因此，我们完全可以采用这个标准来区分C组表5是对C组区分的结果对20个未标明分类的人工序列的分类结果为：A类：22，23，25，27，29，30，34，35，36，37，39 B类：2l，24，26，28，31，32，33，38，40同样的，我们利用这种方法对所给的182个自然序列进行了分类，结果如下所示(略)5 模型的评价及推广在我们的模型基础上提出的分类方法可以很好的验证已知的20个序列，并且很好的完成了对未知类型序列的分类我们认为这种模型，同时考虑了序列中元素的局部性质和序列的全局性质，具有相当的实际背景当我们知道分类标准的更多信息时，我们可以很方便的调整模型中的参数，使之符合新的情况，具有很好的自学习性但这个模型比较复杂，在实际计算中参数选择需要花费大量计算时间进行搜索我们在模型中使用的基于信息流的方法中，如果选取更为合适的熵函数，一定可以使它更加符合实际情况；在三种方法综合的时候，所取的权值也是可以采用更为有效的方法选取，如应用层次分析法；还可以选取其他分类方法加入这些都是本模型可以改进的地方参考文献1 姜启源数学模型(第：版)高等教育出版社，19922刘郁强等序列空间方法广东科技出版社19963刘祖洞遗传学(第二版高等教育出版社：19914姜 丹钱玉美信息理论与编码，中国科学技术大学出版社.19925王玲玲等常用统计方法华东师范大学出版社.19946陆 璇应用统计.清华大学出版社1999DNA序列中的结构与简化模型孟大志（北京工业大学，北京 100022）摘要：本文简述2000年全国大学生数学建模竞赛A题的科学研究背景，以及题目的立意和设计进而对解答A题的大学生们的出色方法进行介绍与评述1 引 子 这是我第一次参与全国大学生数学建模竞赛，深深地被这一十分有意义的赛事蒸蒸日上的发展所鼓舞，为在赛事中涌现出来的青年学生们聪明才智和对科学强烈的热爱而惊喜，为自己在这次参与中学到的和感受到的十分有益的影响而兴奋2000年7月清华的唐云教授电话约我为竞赛出一道题，出于个人兴趣，也出于希望青年学生更关注在重大科学问题中运用数学和发展数学，于是就在全世界被人类基因组计划的成果掀起的巨大热潮中，找一个题目，以期诱导有志青年投入这一二十一世纪的科学热点中我和领导建模比赛的全国组委会的一些教授们(叶其孝、姜启源、王强、唐云等)共同讨论了这个题目，反复修改和润色，希望更适合中国大学生的实际但一直担心这样一个热点科学中引出的问题，一个开放式问题的太大的自由度是否会为难青年学生结果出人意料，特别是重点大学的参赛队，十分热烈地选择A题作为他们一显身手的考卷，而且答出了同样出乎意料的水平然而在A题的理解、解法及评判的一系列问题中，仍有许多问题需要明确，于是我应组委会之邀，特写此文力窥全豹，也对参与竞赛的师生们作一个交待2 A题的背景 2000年6月26日，“人类基因组计划”规定的禁发时间(EMBARGO)北京时间18：00刚过，新华社、法新社、美联社、路透社各国新闻发布机构以第一条消息发布了人类基因组草图绘就的重要消息美国总统克林顿在白宫举行的庆祝仪式上表示，人类基因组草图是迄今“人类所绘制的最为奇妙的图谱”；英国首相布莱尔说：“这是21世纪第一项伟大的科技成就医学科学领域一场革命，其意义远远超过抗生素的发现”；日本首相森喜郎在声明中指出，人类基因组草图绘制成功，代表人类在破解自身构成方面向前迈出巨大的一步；许多国家的元首，科技官员和著名科学家纷纷发表谈话，赞扬人类基因组草图的完成，评估这一伟大成果的意义直到6月28日，中国主席江泽民在中央思想政治工作会议上也对人类基因组的意义作出评价并赞扬了中国科学家在其中的出色工作1 显然，当7月份组委会提出建模赛题一事时，顺应这一世纪科学大事，在其中构造赛题，将引导青年学子关注世界科技热点，鼓励学生敢于投身到科学重大问题中去，培养学生用数学为工具去解决科学技术问题的能力方面都具有了特殊的意义 2003年将完成人类基因组DNA全序列的测序，它将带给人类一本“自身的说明书”，这对人类认识自己，保护自身，发展新的生物产业都将是意义重大的在许多科普读物中，将人类基因组全序列这部“书”描绘成一座巨大金矿，解读这部书就是从中发掘出无量的财富，这种比喻一点儿也不过分生命科学称这一研究阶段为“后基因组时期”或“后基因组计划”(PostGenome Project)，而将数学与计算机科学融人这一计划之中，又常被人称为生物信息学(Bioinformation)人类基因组研究中已经浮现出大量的数学问题，已为世界上众多数学家关注2作为解读基因组这一庞大计划的一个十分重要而又基础的部分，就研究基因组的结构，而其中更基础的是DNA序列的结构“结构”这个词在这里的含义是十分广泛的，也就是说，作为由A、T、C、G四个字符组成的一个有序字符串，任何呈现规律性的特征都可以称为结构由于规律呈现范围不同，我们又可以分为局部结构与整体结构，或称小尺度结构与大尺度结构，这些结构的揭示将大大有助于人们对于基因与基因组的解读这一点可以形象地比喻为一部100万页的书，如果我们能够知道这部“天书”的篇、章、节的结构，甚至段落、语句或词的结构都清楚了，要读懂这部书的内容就变得容易了从这种意义上说，DNA序列的结构的研究显然是生物信息学中重要的内容之一 本届数学建模比赛的A题是在这一世界科学发展的大背景下，作为二十世纪最后一届比赛，以翘首二十一世纪的姿态，选择基因组研究为命题的学科领域以后基因组计划中生物信息的DNA序列结构作为课题，是顷应时代潮流的具有前瞻性的选题，3 A题的立意 在A题设计之前，立意就很明确：源于科学实际，解法充分开放 本题取材于DNA的结构的研究，这里的结构指的是在DAN序列中重复出现的有特征的片断，这种重复出现形成丁规律由于结构的含义是广泛的，担心学生因此而无从下手，我们特别举出三种结构为例，其目的仅仅是为了说明，DNA序列貌似随机地由A、T、C、G四个字符组成，但它之所以有“万能”的功能，正是由于在随机的外衣下隐藏着大量的结构，正是这种结构决定了功能因此，在生物信息学中，人们普遍相信这样一个信条：序列结构一一功能这一信条引导人们成功地在DNA序列中挖掘出许多与生物功能相关的自然规律。在A题中举出的三种结构是十分基础而且在科学界广泛为人们所接受的一种是四种碱基的丰度，对于DNA序列的不同的片段常常表现出碱基丰度的差别，因此碱基的丰度往往成为区别不同序列片段的特征；第二种是三联子对蛋白质的编码，它首先由发现DNA双螺旋结构的克里克和南非的分子生物学家西德尼布伦纳确定的，这种不重叠的三联子组成的编码区(Exon)与非编码区的交替出现形成了DNA序列中一个重要的结构如果读者想了解这一方面的知识只要在互联网上搜索ExonIntron Structure”，你会得到供选读的大量文献；A题举的第三个例子是所谓DNA序列的长程相关性，这一规律最早由CKPeng等人在1992年Nature上报导3，此后人们研究了各种DNA长序列，分别发现了DNA序列在大尺度的范围内具有统计相关性，然而这种相关性的细节及意义至今还是一个迷A题中举出这三种结构，也为了说明在DNA序列的结构中既有大尺度全局性的，也有局部性的，研究和发现DNA序列中的这些规律均有重要意义 正由于这种结构的多样性和一般性，为求解A题确定了解法的开放性虽然事实上许多试卷都把这一结构理解成为编码区与非编码区，但这种局限性的理解并没有比一般性理解结构的试卷更好些A题定义结构的一般性，有两方面的理由一方面希望在求解A题时对生物知识的依赖不要太多，除了最基本的DNA序列的背景外，解题中并不需要有更多的基因组结构的知识(例如，是否知道Exon与Intron并无大关系)这样做是为了在“数学建模”这一基本的专业性质下平等第二个方面就是希望这种开放性，可以使从初等到高等的许多数学模型化方法均能对A题做出一定水平的解答而且也希望发现一些富有创造性的、十分有效的方法事实上，本届比赛中也的确涌现出大量富有创意的方法，实在令命题者兴奋不已 解答方法的开放性，是A题的命题领域本身就决定了的事实上，仅在编码区预测的文献中就有了许多不同的方法有通过核苷酸片段差异的区分方法4，同源比较算法5，隐马尔可夫模型(HiddenMarkovModel，HMM)这种方法将DNA序列的形成看作随机过程，而HMM可自动找出其隐藏的统计规律性6大家熟知的动态规划方法7，以及傅立叶分析8，线性判别分析(Linear Discriminant Analysis，LDA)9此外许多专门的方法用于DNA的结构分析与寻找：法则系统(rulebased system)10，语言系统(1inguistic)11，决策树(decisiontree)12这些方法对于从DNA序列中找出编码序列均有很好效果，有些准确率高达90有兴趣的读者可以在最近出版的解码生命13一书中查到有关评论 A题将DNA结构的研究具体化为不同序列的分类，这种分类对于寻找出序列的结构具有基础的价值它是寻找结构的一种简化而有效的变形，这种具体化在帮助学生模型化是有益的然而这种具体化也给出题带来一定困难，为了方便广大参赛队对这种分类方法的理解与数值实验，我们设计了两套数据。一套是人工构造的数据，而另套是来源于自然的DNA数据库显然这两套数据既有联系又有明显的差别，这种差别使得企图用比较简单的方法而不加区别地处理这两类数据将不会得到好的效果正如自然界给人类提出的问题不太可能恰好满足我们希望的数学条件一样，A题也要求解题者具有立足于实际，从有限而不完全的已知数据去探索更复杂的数据中的未知规律这样一种研究素质4 阅卷随想 在评阅试卷时，老师们对年轻学子在A题解法中表现出的热情、智慧、严谨和富予创造性都留下极深刻的印象作为命题人，更对本科学生能在短短的三天中所做出的成果惊喜，并在许多十分聪明的解法中学习到了新的东西A题的试卷几乎令所有阅卷老师叹服：中国大学生年轻有为! 学生论文的立意大多在“特征提取一分类方法”这一模式，这显然是最容易想到的，大多数试卷也在这一立意之下，选择好的方法而得到较好的结果特征的选择，首先易于让人想到的是A、T、C、G四个字符在字符串中出现的频率，这在文献中常称为“单个碱基丰度”，单纯使用这一特征，许多学生的文章对人工数据得到好的结果，但对后面182个序列的分类却常常不太理想在优秀论文中浙江大学的一个队将这种特征提取后形成四维特征向量，然后分别用欧氏距离、马氏距离分类法和Fisher判别模型，对人工数据得到理想的分类，对自然数据(182个)也得到很高的分类正确率，是这一类算法中较突出的卷例另有一些试卷在这一特征基础上考虑到字符的顺序，将模型做得更复杂些更多的论文是用4个字符的字符串作为特征，由于这时特征一下子增加了许多，于是需要从其中评判挑选并排出特征的重要性顺序，这种特征的提取往往可以得到较好的效果特别是对于自然序列，大连理工大学的一个队通过概率统计方法首先对已知的人工序列集进行特征提取，从而形成特征向量较为全面地表达分类特征，当然也出现了高维问题的计算复杂性，他们得到了很好的分类效果值得指出的是，由于竞赛题一方面源于生物学实际问题，同时又相对地独立于生物而形成适当抽象的“试题”，因此试题并不是基因组中某种结构的翻版有些试卷过多地研究了生物学的来源，而且将A题仅局限于他们所想象的结构(例如Exon结构)，于是三联子编码成为分类的唯一特征，而三联码的不重叠性又使他们在阅读框的起始位置前不知所措，以至所产生的结果不理想 在分类方法上，统计的方法(特别是聚类方法)是最易于想到的，许多试卷从而构造了好的方法但是简单而不加修正地使用统计方法并不能得到好的结果这是因为人工已知序列的样本数只有20个，而且都很短，待分类的自然数据样本数182且都长得多，因此从小样本中得到的统计规律在处理大样本时效果显然不佳这是众多用统计方法所得到结果不理想的一个直接原因有些学生看到并指出了这一点，而且有的试卷注意到人工数据与自然数据的生物学的差别而在分类自然序列时修改了分类方法而得到较好的结果，显然概念的清楚与思维的灵活得到很好的统一用各种方式构造判别函数的方法以及神经网络的方法，特别对于非线性系统的识别很有效因此通过构造各种神经网络来进行分类，更多的队得到很好的效果例如大连理工大学的一个队，用统计方法提取较好的特征又用BP网络进行分类，方法严谨，考虑细致，对自然序列的分类正确率高达88而科技大学的一个队通过对神经网络方法的逐层的改进，又辅以统计方法，产生了比较精细的网络算法，也得到分类自然数据的正确率达65的好效果除了上述大量“正规方法”以外，一些试卷有创意地提出了一些十分新颖的思想，有些还取得了很好的效果例如中国科技大学的一个队将序列看作信息流，注意到字母出现的特征是熵的改变，是十分新意的，他们最终又将设计好的几个模型形成综合判别的目标函数，也得到好的分类效果，对自然数据分类正确性达58而北京大学的一个队将DNA字符串看作一篇文章，而利用了类似文本分类中的特征判别方法定义关键词标准，进而使用优选法，找出关键词的特征，然后使用层次分类他们的方法精细，尽管分类最终效果并不十分理想，仍不失为值得一读的好文章由于篇幅有限，有些文章虽然没有作为优秀论文刊出，但是在其中仍然表现出学生丰富的想象力和创造精神篇十分有趣的文章是大连理工大学的另一个队，这些学生既没有拘泥于“特征提取+分类”的模式，也没有局限自己的思维于“概率统计”“神经网络”“判别函数”等“大路”方法他们深入地分析了序列问题的生物来源，又观察人工序列的数学结构和数值试验结果，在一些DNA序列几何表达文献的启发下，提出了简捷的几何分类法，得到了出色的分类结果对自然数据分类的正确率高达94而且这种不依赖训练集的方法，属于目前研究基因组结构的令人关注的方向应当指出，科研能力的表现是多方面的在试卷中，我们注意到许多学生十分用心于科学文献的检索、阅读与借鉴例如一些试卷研究了我国著名学者，中科院院士张春霆教授的Z曲线方法14，并简化用于A题分类(例如中国科技大学的另一个队)，也取得好的结果此外，特别值得指出的是香港城市大学的论文，该文的思路清晰，表述严谨，图表数据完整，行文流畅，作为本科学生三天完成的科研论文值得赞赏!综上所述，作为A题的命题人，原先的担心与顾虑被事实扫得干干净净学生的聪明才智、扎实的数学功底和运用于实际问题的灵活性、创造性证明，中国大学生完全可以适应更贴近科学研究实际，更贴近工程技术实际，更贴近社会经济生活实际的数学建模比赛问题中国大学生在数学建模比赛的锻炼中必将大大提高应用数学的能力，在二十新科技的发展中做出出色的成绩参考文献1子言，基因：讲述生命的故事经济日报出版社2000年7月2Mathematics：Frontiers and PerspectlvesAMSProvldence2000M Auyah前言.3Peng CK BuldyrevSV G01dberger， A 1 Hav“nS Sxiortlno， F Simonso, M. And Stanley, H. E. Longrange correlatlon in nucleotldc sequences。nature 356：168一1704C1averle J MComputanonal methOds fOr the identlflCatlon Ofgenes in vertebrategenomlc sequence hum Mol Ge-net，19976(10)：173517445Green P. Llpman D，Hillier L，WaterstonR，Stares D，C1aVierieJMAncientconserved regions in new gene se-quences and the Protein databases. Science1993，259：17111716.6Kroyh A，Mlan I S，Hanssler DA hidden Markov model that finds genes in E. co1i DNANucleic Acids Res，199422(22)：476847787Gelfand M S，Roytberg M A Predlction of the exonintron structure by a dynamic programming approach Bmsystems，1993，30(13)：1731828Tiwavi S. Ramachandran S. Bhattacharga A，Bhattacgarga S，Ramaswamy R. PrediCtlOn O(prObable genes by Fourler analysis ofgenomlc sequencescomput Appl Biosci, 1997，13(3)：263270.9Fickett JM. Tung C SAssessment of protem coding measuresNuclelc Acids Res，1992，20(24)：64416450.10Guigo RKnudsen S，Dr3ke NSmith TPredlctlon of gene structureJ Mo1 Biol, 1992, 226(1)：141157.11Dong S，Searls D BGene structure predlotion by linguistic methodsGenomics，23(3)：54055112Sal2berg SLocatlng protein coding regions in human DNA using a decsion tree algorlthm, J Comput Bio1, 2(3): 47348513贺林主编. 解码生命人类基因组计划和后基因组计划科学出版社2000年14ZHAN Ghun-Tlng. LIN ZhesualYNA Ming, ZHAN RenA Novel Approach to Distinguish Between Intron-containing and Intronless Genes Based on Format of Z CurvesJ theor Bio1, 1998，192：467473管道订购与运输问题杨志江， 李国欣， 张 敏指导老师： 中国矿业大学数模教练组(中国矿业大学江苏徐州 221008)编者按：本文采用将待铺设管道按单位长度分解成n个需求点，建立运输模型的方法避免了问题一和三的差别模型切合原赛题要求并针对原问题的规模，对算法作y-定的改进，得到了较好的结果本刊予以摘要发表摘 要：本文在详细分析的基础上，通过合理假设并引人等价转换原则，将管道订购与运输问题转化为单一的公路运输问题运用组合优化的思想和方法，给出了数学模型产量未定的运输模型针对此模型，我们设计了“改进的最小元素法”和“改进的伏格尔Ph，先求得了个初始解。再通过“试探法”和“迭代法”进行调调优化最后得出结果：对第问最小总费用为1279019万元；对第三问最小总费用为1407383万元1 问题的重述(略)2 基本假设 (1)只考虑订购费用和运输费用，不考虑装卸等其它费用 (2)钢管单价与订购量、订购次数、订购日期无关 (3)订购汁划是指对每个厂商的定货数量；运输方案是指具有如下属性的(4)订购汁划是指对每个厂商的定货数量；运输方案是指具有如下属性的一批记录：管道区间，供应厂商，具体运输路线 (4)将每一单位的管道所在地看成一个需求点，向一单位管道的所在地运输钢管即为向一个点运输钢管3 符号说明 M：钢厂总数. n：单位管道总数. 第i个钢厂 第i个钢厂的产量上限。 第i个钢厂单位钢管的销售价 管道线上第i个站点。 管道线上第i个单位管道的位置。 F：总费用。 从钢厂到点的最低单位费用。4 问题分析 运输费用等价转换法则：按单位运费相等原则将任意两点间的最短铁路线转换为公路线对于铁路线上的任意两点，用F1oyd算法找出两点间最短铁路路线的长度查铁路运价表求得，对应的铁路单位运费;又设与该段铁路等费用的公路长度为，则： 由此，我们就在之间用一条等价的公路线来代替间的最短铁路线如果之间原来就有公路，就选择新旧公路中较短的一条这样，我们就把铁路运输网络转换成了公路运输网络销价等价转换法则：按单位费用相等将任意钢厂的单位销价转换为公路单位运价对于钢厂Si的销售单价Pi，我们可以虚设一条公路线，连接钢厂Si及另一虚拟钢厂，其长度为，并且满足；从而将钢厂的销售单价转换成公路运输单价，而新钢厂的销售价为0.将铁路和销价转换为公路的过程可以由计算机编程实现通过上述的分析，我们可以将原问题化为一个相对简单的产量未定的运输问题，利用之间的管道距离和钢厂和站点之间的公路距离建立一个产量未定的运输问题的模型但是由于并不能代表所有的实际需求点(实际需求点是n个单位管道)，因此，我们可以用F1oyd算法进一步算出7个钢厂到所有实际的n个需求点(对于问题一，n5171;对于问题三，n5903)的最短路径，并由此得出一个具有7个供应点、n个需求点的产址未定的运