搜索
DNA序列分类模型摘要本文分析了已知类别的人工DNA序列的特征，建立了聚类分析延拓模型和马尔可夫模型，分别对未知类别的人工DNA序列和自然序列进行分类，根据分类效果选出了较优模型。首先对数据进行预处理，得到人工DNA序列的单个碱基丰度和不同碱基丰度之比等特征量，进而分析A、B两类的差异，得到合适的特征判定条件对未知类别的DNA序列进行分类。计算人工DNA序列的特征量，给出各序列的统计数据。其次用聚类分析延拓模型进行分类。用A、B两类具有明显差异的特征作为样品特征变量，得到欧式空间中表征编号1-20人工DNA序列的特征向量，计算两两之间的Lance和Williams距离进行相似性度量，逐步选择相似性较大的归为一类，同时不断更新类内的标准比较特征向量，对聚类方法进行延拓，最终得到类内差异小、类间差异大的A、B两类，建立了聚类分析延拓模型。再对选取的特征变量进行改进，提高模型的分类效果。最后，借助均值、方差和相关系数等参数对改进模型的分类效果进行分析。再次用马尔可夫模型进行分类。将DNA序列看成是马尔可夫链，求出编号1-10和11-20人工DNA序列在已知当前碱基种类的条件下，下一个碱基出现任一种的概率，结果存入概率转移矩阵1和2，再利用矩阵1和2分别求出编号1-20中任一条DNA序列出现的概率，选择较大的一个作为该DNA序列的分类，建立马尔可夫模型。再进行与聚类分析延拓模型类似的改进和检验工作，然后对编号21-40人工DNA序列和182条自然序列进行分类，得到最终结果。最后，用层次分析法综合评价模型一与模型二，选择聚类分析延拓模型作为最终模型，其分类结果作为最终结果，具体如下：编号21-40人工DNA序列中属于A类的样品编号为：22，23，25，27，29，30，34，35，36，37，39；属于B类的样品编号为：21，24，26，28，31，32，33，38，40。182条自然序列中，属于B类的样品编号为：7，10，12，22，23，24，26，28，30，34，43，48，50，54，57，65，75，76，80，84，85，86，92，98，103，107，110，114，116，119，121，122，123，127，128，129，130，131，137，138，140，142，143，144，146，151，156，159，161，162，163，166，168，170，173，174，175，179，180，181，182；其余为A类。关键词DNA序列分类聚类分析延拓法Lance和Williams距离马尔可夫法一、问题重述1.1题目背景（1）2000年6月，人类基因组计划中DNA全序列草图完成，预计2001年可以完成精确的全序列图，此后人类将拥有一本记录着自身生老病死及遗传进化的全部信息的“天书”。（2）这本“天书”是由4个字符A，T，C，G按一定顺序排成的无间隔的长约30亿的序列，除了这4个字符表示4种碱基以外，人们对它包含的“内容”知之甚少。因此，破译这部世界上最巨量信息的“天书”是二十一世纪最重要的任务之一。（3）为解读这部“天书”，首先要研究DNA全序列具有什么结构，以及由这4个字符排成的看似随机的序列中隐藏着什么规律，这也是生物信息学最重要的课题。1.2题目信息（1）DNA序列分为编码区与非编码区。编码区是用于编码蛋白质的序列片段，即由这4个字符组成的64种不同的3字符串，其中大多数用于编码构成蛋白质的20种氨基酸。（2）在不用于编码蛋白质的序列片段中，A和T的含量特别多些，于是以某些碱基特别丰富作为特征去研究DNA序列的结构也取得了一些结果。（3）利用统计的方法还发现序列的某些片段之间具有相关性。这些发现说明DNA序列中存在着局部的和全局性的结构，充分发掘序列的结构对理解DNA全序列有十分重要的意义。目前在这项研究中最普通的思想是省略序列的某些细节，突出特征，然后将其表示成适当的数学对象。1.3题目要求（1）有20个已知类别的人工制造的DNA序列（见附件1），其中序列标号1—10为A类，11-20为B类。从中提取特征，构造分类方法，并用这些已知类别的序列，衡量所选分类方法是否足够好。（2）用（1）中的分类方法对另外20个未标明类别的人工序列（见附件1，标号21—40）进行分类，根据分类效果对方法不断完善，将得到的最终结果用序号（按从小到大的顺序）标明它们的类别（A类或B类，无法分类的不写入）。要求详细描述所选的分类方法，给出计算程序。若论文中部分地使用了现成的分类方法，应将方法名称准确注明。（3）已知182个自然DNA序列（见附件2），它们都较长。同样用以上所选的分类方法对它们进行分类，并根据分类效果对方法不断完善，像（2）中一样给出最终的分类结果。二、名词解释1.编码区与非编码区：编码区是指DNA上编码蛋白质的序列片段，而非编码区不用于编码蛋白质。2.聚类分析：由已知数据，计算各个观察个体或变量之间亲疏关系的统计量。再根据某种准则（最短距离法、最长距离法、中间距离法、重心法等），使同一类内的差别较小，而类与类之间的差别较大，最终将观察个体或变量分为若干类的分类方法。其中，对样品所作的分类为Q-型聚类，对变量所作的分类为R-型聚类。3.相似性度量：对数值型数据而言，两个个体的相似度是指它们在欧氏空间中互相邻近的程度；而对分类型数据而言，两个个体的相似度与它们取值相同的属性的个数有关。4.样品：每个观察个体即每条DNA序列为一个样品。5.样品变量：每个样品所具有的不同特征用不同的变量来表示，变量数等于特征数。6.碱基丰度：每条DNA序列中碱基A、G、C或T出现的频率。三、问题分析DNA序列分类问题要求在对DNA序列的一些规律和结构有所了解的基础上，从20个已知类别的人工制造的DNA序列中提取特征，构造分类方法，并用所选择的分类方法对其余未知类别的20个人工制造的DNA序列以及182个自然DNA序列进行分类。3.1建模目标的分析DNA序列分类是一个复杂的统计分析问题，数据量大，影响因素多，无法直接从20条已知类别的人工制造的DNA序列中提取出所有的有效特征，因此有必要对这20条DNA序列进行预处理。观察并分析数据预处理结果，归纳总结出A类和B类的有效特征，将其表示成适当的数学对象，并选择适当的分类方法，建立普遍意义下数学模型，再用得到的模型对其余未知类别的20个人工制造的DNA序列以及182个自然DNA序列进行分类。由题意，建立的数学模型应该保证分类结果具有以下特点：（1）类别间差异尽量大；（2）类别内差异尽量小；（3）样品能够尽可能的落入A、B范围，且只能落入其中的一个。3.2建模及求解方向1.分析已知类别的DNA序列1-20的结构，提取出相应的特征。主要的特征有：碱基的丰度、碱基或碱基序列的重复出现情况、碱基或碱基序列之间的相邻情况、不同碱基的丰度之比（如碱基A与碱基T的丰度之比）等。2.根据提取出的特征，选用合适的分类方法。对数据进行预处理后，尝试以下方法建立模型：（1）根据聚类分析法，建立模型一。由题意，DNA序列分类属于对样品所做的分类，为Q-型聚类。首先引入样品变量，例如可选择碱基T的丰度、碱基G的丰度、碱基T与碱基G的丰度之比、碱基A与碱基T的丰度之比等。由已知数据，计算出每条已知类别的人工制造的DNA序列的各个样品变量值，存入向量中。根据相似性度量原理，计算20个样品两两之间的Lance和Williams距离，选择相距最远的两个样品（假设为样品3和样品16）分别作为A类和B类，再分别以样品3和样品16为标准点，通过分别计算样品3和样品16与其余18个样品之间的Lance和Williams距离，找出与其相距最近的一个样品（假设为样品1和样品18）归为一类。此时，新的标准点变为样品1与样品3的中点、样品16与样品18的中点。然后再以新的标准点为基准，分别找出与其相距最近的一个样品归为一类。逐步进行下去，直至20个样品被明显分成A、B两类。（2）根据马尔可夫法，建立模型二。以单个碱基为单位，分别统计编号1-10和编号11-20人工制造的已知类别的DNA序列中4种碱基出现的次数，再以相邻的两个碱基为单位（共16种组合情况），分别统计编号1-10和编号11-20的DNA序列中16种碱基对出现的次数。为满足大样本需求，将A类和B类中的10条DNA序列组合起来看作两个大样品，单个碱基或碱基对出现（不包括上一条链的末尾碱基与下一条链的初始碱基组合的情况）的次数为10条序列之和。由条件概率的思想，分别求出A类和B类大样品中在已知当前碱基种类（可以为A、G、C、T中任何一个）的条件下，下一个碱基分别为A、G、C、T的概率，存入两个矩阵1和2中。对于任何一条给定的DNA序列，可将其看作一个已经发生的事件，说明该事件发生的概率比较大。用矩阵1和矩阵2分别求出这一事件发生（即形成当前DNA序列）的概率，若用矩阵1算出该编号的DNA序列出现的概率较大，则该编号的DNA序列属于A类，否则属于B类。3.模型的初步检验与改进。用编号1-20已知类别的序列，分别衡量模型一与模型二中所选方法是否足够好，不断改进，尽可能使1-20号DNA序列在所选分类方法下，所得结果与已知分类完全一致。改进时，对于聚类分析法，可以尝试改变样品变量的个数或者改变样品变量的组合方式；对于马尔可夫法，可以尝试引进中间变量，运用隐马尔可夫法求解。4.模型的进一步检验与完善。（1）用以上的得到的两种分类方法对编号20-40未知类别的人工序列、182个自然序列进行分类。（2）通过计算样品方差、均值等比较两种分类方法得到的分类结果与建模目标——类别间差异尽量大、类别内差异尽量小、样品能够尽可能的落入A、B范围，且只能落入其中的一个——的接近程度。（3）选择更接近建模目标的一种分类方法作为最终的分类方法，其分类结果即为最终结果。四、基本假设1.假设所给的DNA序列片段中没有断句和标点符号。2.假设具有特殊碱基的DNA序列中，特殊碱基可以剔除，其影响可以忽略。3.较长的182个自然序列与已知类别的20个样本序列具有共同的特征。4.假设给定的DNA序列均是从全序列中随机截取出来的,无法确定序列的起始位,无法从序列中辨认出氨基酸，所以，在对DNA序列分类时,从碱基层次上进行分类,而不是从氨基酸层次上分类。五、定义与符号说明in：各个样品中碱基i出现的数量，i为A、T、C或GiN：第i个样品的总碱基数目iF：各个样品中碱基i的丰度，i为A、T、C或Gix：各个样品的第i个特征变量ijf：各个样品中碱基i和碱基j的比值，i，j为A、T、C或GiY：第i个样品的特征向量ijd：向量iY和向量jY间的Lance和Williams距离p：特征向量的分量个数，即向量的维数k：特征向量的第k个分量n：样品的个数ikx：特征向量i的第k个分量maxd：不同向量代表的p维空间中任意两点间Lance和Williams距离的最大值mind：不同向量代表的p维空间中任意两点间Lance和Williams距离的最小值iy：聚类分析中i类的标准向量，i为A或B六、数据预处理1.A类和B类样品单个碱基丰度的计算用maTlab编写程序（见附件3），分别求出20条已知类别的人工制造的DNA序列中，4种碱基的丰度，绘出散点图如下：图6.1.1单个碱基丰度比较图分析上图可得，A类和B类DNA序列中碱基T和碱基G的丰度有明显差异，而碱基A和碱基C的丰度则比较接近。2.A类和B类样品不同碱基丰度之比的计算用matlab编写程序（见附件4），分别求出20条已知类别的人工制造的DNA序列中，不同碱基的丰度之比，包括TAf、CAf、GAf、CTf、GTf、GCf，绘出散点图如下：图6.1.2不同碱基丰度之比的比较图分析上图可得，A类和B类DNA序列中，碱基T与碱基A的丰度之比、碱基G与碱基A的丰度之比、碱基C与碱基T的丰度之比、碱基G与碱基T的丰度之比有明显差异，而碱基C与碱基A的丰度之比、碱基G与碱基C的丰度之比则比较接近。3.将编号1-40人工制造的DNA序列的中，碱基T的丰度、碱基G的丰度、碱