下载文档原格式
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类，1 1-20为B类。
请从中提取特征，构造分类方法，并用这些已知类别的序列，衡量你的方法是否足够好。
然后用你认为满意的方法，对另外20个未标明类别的人工序列（标号21—4 0）进行分类，把结果用序号（按从小到大的顺序）标明它们的类别（无法分类的不写入）：A类__________ ；B类_______________ 。
生物信息学札记（第4版）樊龙江浙江大学作物科学研究所浙江大学生物信息学研究所浙江大学IBM生物计算实验室2017年9月本材料已由浙江大学出版社出版：《生物信息学》，樊龙江主编，2017部分内容可通过下列网址获得：/bioinplant/札记前言第一版这份材料是我学习和讲授《生物信息学》课程时的备课笔记，材料大多是根据当时收集的一些外文资料翻译编辑而成。
学生在学习过程中经常要求我给他们提供一些中文的讲义或材料，这促使我把我的这份笔记整理并放到网上，供大家参考。
要提醒使用者的是，这份材料仅是根据我对生物信息学的一些浮浅的认识整理而成，其中的错误和偏颇只能请读者自鉴了。
2001年6月第二版自1999年开始接触生物信息学以来，一晃已近六年，而本札记也近四岁了。
2001和2002年中国科学院理论物理所的郝柏林院士在浙江大学首次开设生物信息学研究生课程，我作为他的助教系统地学习了生物信息学；同时，借着我国水稻基因组测序计划的机遇，在他的带领下从2001年开始从事水稻基因组分析，从此自己便完全投入到这一崭新、引人入胜的领域中来。
不断有来信向我索要本札记的电子版文件，同时在不少网站上看到推荐该札记的内容。
生物信息学、基因组学等发展很快，现在再回头审看该札记，有些部分已惨不忍读，这促使我下决心更新它。
但因时间和学识问题，还是有不少部分自己不甚满意，就只有待日后再努力了。
欢迎告诉我札记中的BUG，我的信箱*************.cn或******************.cn。
2005年3月30日第三版近年来高通量测序技术产生的序列数据大量出现（如小RNA和大规模群体SNP数据），本次更新根据这一进展增加了两章内容，分别是第七章有关小RNA的分析和第八章遗传多态性及正向选择检测。
两章内容由我的博士生王煜为主编写，李泽峰和刘云参与了文献整理。
另外还更新了第四章有关水稻基因组分析一节。
2010年1月第四版2014年浙江大学开展本科生教材建设工作，我当时作为系主任要带头，就承诺编写我主讲的《生物信息学》教材。
DNA 序列分类（2000年A 题）没有标准答案，以浙江大学 （韩轶平）为主。
一、解决问题的思路学习样品1－20； 判断样品 21—40。
根据学习样品1－20，提取A 、B 两类的特征，构造判断规则。
二、对于每一个DNA 序列X ，按照a c g t 在其中出现的频率分类a n ———— a 的百分含量 c n ———— c 的百分含量g n ———— g 的百分含量 t n ———— t 的百分含量则 1=+++t g c a n n n n 。
对于每一个DNA 序列都唯一对应一个三维向量),,(g c a n n n X =，称为特征向量。
按照样品的编号，各个样品的特征向量记为)40,2,1(, =i X i 。
对于每个已知的学习样品x ，都有A x ∈或B x ∈。
可以根据统计的方法找出A 、B 两类特征向量的总体特点或差异。
再对于未知类别的样品x ，根据它的特征向量X 与A 、B 两类特征向量的相似程度判别它所属的类型。
“物以类聚，人以群分”如何判断一颗恒星是否属于银河系假定：① 碱基的含量反映了DNA 序列的内容② 同类的DNA “聚集”在一起距离空间S 是一个集合，对于任何S y x ∈,都唯一确定一个实数),(y x ρ。
如果),(y x ρ满足以下三条公理，则称S 是一个距离空间，ρ 称为定义在S 上的距离。
① 非负性：0),(≥y x ρ；当且仅当y x =时0),(=y x ρ ② 对称性： ),(),(x y y x ρρ=③ 三角不等式：),(),(),(y z z x y x ρρρ+≤如，空间中两点),,(1111z y x P ),,(2222z y x P 之间的距离为2122122122112)()()(),(||z z y y x x P P P P -+-+-==ρ称为这两点间的欧氏距离。
又如向量⎪⎪⎭⎫ ⎝⎛=321a a a α，⎪⎪⎭⎫ ⎝⎛=321b b b β，它们的距离可以定义为)()(),(1βαβαβαρ-∙-=则2332222111)()()(),(a b a b a b -+-+-=βαρ，也称为α与β的欧氏距离，通常记为βα-可验证，对于任何三阶的正定矩阵V，)()(),(2βαβαβαρ--=T V 也是α与β的距离。
DNA的一级结构名词解释
DNA的一级结构，又称为核苷酸序列，指的是DNA分子中四种不同核苷酸的排列顺序。
这四种核苷酸分别是腺嘌呤（A）、胸腺嘧啶（T）、鸟嘌呤（G）和胞嘧啶（C）。
DNA的一级结构决定了基因的遗传信息和功能，因此对于生物体的生长、发育和遗传都至关重要。
DNA的一级结构是DNA分子的基本组成单位，这些单位按照特定的顺序排列，形成了DNA的序列。
DNA序列中核苷酸的排列顺序是由碱基的配对原则决定的，即A与T配对，G与C配对。
这种配对原则保证了DNA分子中的遗传信息能够准确地进行复制和传递。
在DNA的一级结构中，每个核苷酸都有一个特定的位置，这些位置是按照碱基的顺序来确定的。
不同的DNA序列具有不同的核苷酸排列顺序，这决定了它们所包含的遗传信息的差异。
因此，DNA的一级结构是生物多样性和遗传变异的基础。
除了核苷酸的排列顺序外，DNA的一级结构还可以包括其他的特征，如重复序列、单核苷酸变异等。
这些特征可以影响DNA的功能和表达，从而影响生物体的表型和行为。
因此，对于DNA一级结构的理解和研究，对于遗传学、生物信息学和分子生物学等领域都具有重要的意义。
用判别分析的方法判定DNA序列的类别摘要判别分析法是多元统计分析中的重要内容之一。
近年来，人们用判别分析的方法解决了不少在生产科研和日常生活中的实际问题。
本文用Fisher判别的思想，从变量检验入手，给出了对DNA序列进行不同分类的理论依据，并探讨错判概率与判别效率之间的关系。
通过对检验样本的回报情况分析可知，本文所建立的模型分辨率高（95%），错判率低（<1%），简单而易于运行，适合于各种长度的DNA序列的分类，因此实用性强，有较高的理论价值，为多元统计分析方法在生物信息学领域中应用的又一典型实例。
关键词：DNA序列、Fisher判别法、判别函数、错判率。
一、问题提出1．背景人类基因组计划中的DNA全序列图是一本记录着人类自生老病死及遗传进化的全部信息的“天书”。
这本大自然写成的“天书”是由4个字符A、C、G、T按一定的顺序排成的长约30亿的序列，其中没有断句，也没有标点符号，除了这4个字符表示4种碱基以外，人们对它包含的内容知之甚少，难以读懂，破译这部世界上最巨量信息的“天书”是二十世纪最重要的任务之一。
在这个目标中，研究DNA全序列具有什么结构，由这4个字符排成看似随机的序列中隐藏着什么规律，又是解读这部天书的基础，是生物信息学最重要的课题之一。
对DNA序列的逐步认识让人们相信DNA序列中存在着局部的和全局的结构，充分发掘序列的结构对理解DNA全序列是十分有意义的。
2．问题有20个已知类别的人工序列：A类，B类。
1. 从中提取特征，构造模型，找出合适的分类方法，并用该法对另20个给出的未知类别的人工序列进行分类，要求详述方法及给出计算程序。
2..对另给出的182个自然序列进行分类。
二．问题的分析本题重在从已知类别的DNA序列中提取某些特征，构造分类方法，提取的某些特征应满足以下条件：1）来源于已知样本。
2）具有给予未知类别的DNA序列分类的功能。
3）能较好的接受检验样本的检验。
全部地考虑各种因素（如碱基的排列组合，碱基间的键强及键长等等），无法得到分类方法。
DNA序列的分类模型汤诗杰,周亮,王晓玲,孙广中本文针对 DNA序列分类这个实际问题 ,提出了相应的数学模型 .为了很好的体现 DNA序列的局部性和全局性的特征 ,我们给出了衡量分类方法优劣的标准 ,即在满足一定限制条件的情况下 ,是否能充分反映序列的各方面特性 .依据我们提出的判别标准 ,单一标准的分类是无法满足要求的 .我们的方法是侧重点不同的三种方法的综合集成 .这三种方法分别体现了序列中元素出现的概率 ,序列中元素出现的周期性 ,序列所带有的信息含量 .利用这个方法 ,完成了对未知类型的人工序列及自然序列的分类工作 .最后 ,对分类模型的优缺点进行了分析 ,并就模型的推广作了讨论KB)关于DNA序列分类问题的模型冯涛,康喆雯,韩小军,贺明峰本文提出了一种将人工神经元网络用于 DNA分类的方法 .作者首先应用概率统计的方法对 2 0个已知类别的人工 DNA序列进行特征提取 ,形成 DNA序列的特征向量 ,并将之作为样本输入 BP神经网络进行学习 .作者应用了 MATLAB软件包中的 Neural Network Toolbox(神经网络工具箱 )中的反向传播( Backpropagation BP)算法来训练神经网络 .在本文中 ,作者构造了两个三层BP神经网络 ,将提取的 DNA特征向量集作为样本分别输入这两个网络进行学习 .通过训练后 ,将 2 0个未分类的人工序列样本和 1 82个自然序列样本提取特征形成特征向量并输入两个网络进行分类 .结果表明 :本文中提出的分类方法能够以很高的正确率和精度对 DNA序列进行分类 ,将人工神经元网络用于DNA序列分类是完全可行的KB)DNA分类模型杨健,王驰,杨勇,王鸣本模型充分利用了所给数据的特点 ,运用统计、最优化等数学方法 ,从已知样本序列中提炼出能较好代表两类特征的关键字符串 ,据此提出量化的分类标准 ,能较好的对任给 DNA序列进行分类 .首先 ,从已知样本序列中用广度优先法选出所有重复出现的字符串 ,并计算其标准化频率及分散度 .然后 ,利用样本数据结合最小二乘法确定两类字符串各自的优先级函数 ,并且逐步优化其参数使之达到稳定 ,提高了可信度 .最后 ,根据优先级函数找出关键词 ,然后确定权数 ,用层次分析法对未知样本进行分类 ,并定出显著水平 ,从而得到了一个比较通用的分类方法 .经过检验 ,此方法对 2 1— 4 0号待测样本进行了很好的分类 ,对后面的1 82个 DNA序列进行同样的操作 ,也有较好的效果KB)DNA序列的分类韩轶平,余杭,刘威,杨启帆本文对 A题中给出的 DNA序列分类问题进行了讨论 .从“不同序列中碱基含量不同”入手建立了欧氏距离判别模型 ,马氏距离判别模型以及 Fisher准则判定模型 ;又从“不同序列中碱基位置不同”入手建立了利用序列相关知识的相关度分类判别算法 ,并进一步研究了带反馈的相关度分类判别算法 .对于题中所给的待分类的人工序列和自然序列 ,本文都一一作了分类 .接着 ,本文又对其它各种常见的分类算法进行了讨论 ,并着重从分类算法的稳定性上对几种方法作了比较 .KB)DNA序列分类的数学模型吕金翅,马小龙,曹芳,陶大程本文从三个不同的角度分别论述了如何对 DNA序列进行分类的问题 ,依据这三个角度分别建立了三类模型 .首先 ,从生物学背景和几何对称观点出发 ,建立了 DNA序列的三维空间曲线的表达形式 .建立了初步数学模型 -积分模型 ,并且通过模型函数计算得到了 1到 2 0号 DNA序列的分类结果 ,发现与题目所给分类结果相同 ,然后我们又对后 2 0个 DNA序列进行了分类 .然后 ,从人工神经网络的角度出发 ,得到了第二类数学模型 -人工神经网络模型 .并且选择了三种适用于模式分类的基本网络 ,即感知机模型 ,多层感知机 ( BP网络 )模型以及 LVQ矢量量化学习器 ,同时就本问题提出了对 BP网络的改进 (改进型多层感知机 ) ,最后采用多种训练方案 ,均得到了较理想的分类结果 .同时也发现了通过人工神经网络的方法得到的分类结果与积分模型得到的分类结果是相同的 (前四十个 ) .最后 ,我们对碱基赋予几何意义 :分别表示右 .下 .左 .上 .用 DNA序列控制平面上点的移动 ,每个序列得到一个游动曲线 ,提取游动方向趋势作为特征 ,建立起了模型函数 ,同时也得到了后二十个 DNA序列的分类结果 ...KB)DNA序列中的结构与简化模型孟大志本文简述 2 0 0 0年全国大学生数学建模竞赛 A题的科学研究背景 ,以及题目的立意和设计 .进而对解答 A题的大学生们的出色方法进行介绍与评述KB)。
