DNA序列的聚类问题.doc

DNA序列的聚类问题DNA序列分类问题不同于传统的聚类问题，它本身有其特殊性和复杂性12。特殊性是指DNA序列片断只是由4个字符A、T、C、G组成的串。复杂性是指已知分类的DNA序列数据不等长度。即使等长度，由于其作为字符串长度很大，也不能直接通过数学运算进行分类。如果采用数学方法研究DNA序列分类，首先要把DNA序列用一个向量数据表示，即进行DNA序列特征（聚类要素）提取。向量型数据对应着DNA序列特征。不同的特征提取方法有不同的特性，它将很大程度上影响聚类的结果，所以我们选取的方法必须符合实际要求的特点。已有的DNA序列特征提取方法有下面几种：顾俊华等在模糊聚类分析方法在DNA序列分类中的应用15一文中使用的基于4种碱基的丰度13的方法，即采用序列中的碱基A、T、C、G的含量百分比作为该序列的特征，从而将DNA序列特征构造为四维向量，进而聚类分析。岳晓宁等在基于聚类分析的DNA序列分类研究16一文中利用生物学中密码子（三联子）的概念，以密码子的含量作为DNA序列的特征。具体作法：统计每个DNA序列中aaa、aat、aac、aag、ttt出现的个数，这样DNA序列由一个64（）维的向量表示。这样64维序列又有三种解读方式：对于一个给定的DNA序列，分别从开始的1、2、3号位置分别截取产生三种不同的表示。如序列aggcacggaaaa可分成(agg)(cac)(gga)(aaa)或(ggc)(acg)(gaa)或(gca)(cgg)(aaa)。这3种不同的截法所产生三种不同的密码信息，需要对其进行处理。周玉元等在DNA序列分类的Fisher判别法17一文中，由生物学和生物化学知识，用碱基互补配对原则，将64个密码子对应20种氨基酸和一类终止信息，这样DNA序列可用一个21维向量来表示，从而突出生物特征、降低了维数。采用碱基丰度提取特征的方法缺点很明显，即很可能出现不同类别的DNA序列有着相同的判别特征，也就是说它们的各种碱基含量是相同的，导致标记它们的4维向量也是相同的，没有考虑到DNA序列中字符的顺序结构。根据生物工程理论，A、T、C、G看成四个独立结构单元，它们在DNA链上排列的顺序称为碱基序列。DNA根据碱基序列可以转录成RNA，RNA可翻译成蛋白质，所以用三个碱基为一组的碱基组(即密码子)出现频率作为分类的标准是可以反映生物学意义的。本文在已有的研究基础上，将基于密码子的DNA序列聚类方法应用于更大量的数据，从而进行验证，并对结果提出分析。其后，在基于密码子的DNA序列模糊聚类分析的基础上，提出另一种DNA序列判别特征的提取方法基于向量距离的DNA序列模糊聚类分析，进而考虑DNA序列的排序性，挖掘DNA序列中的更多性息，提高DNA序列分类的准确性和客观性。第一节 基于密码子的DNA序列模糊聚类分析基于本章第一节的数据，现将先以三个碱基为一组（密码子），提取其百分含量构成64维向量，再由这64维向量作为一个DNA序列的数据表征（即聚类要素），然后用模糊聚类的一般方法进行聚类分析。一、基于密码子的DNA序列判别特征提取现在用数学的语言描述上述问题：A、T、C、G为DNA的四种碱基，将64种密码子按1,2,3,64依次编号，编号顺序为aaa，aat，aac，aag，ata，att，atc，atg，aga，agt，agc，agg，taa，tat，tac，tag，tta，ttt，ttc，ttg，gga，ggt，ggc，ggg；三种不同解读DNA序列的方式是指分别从开始的1、2、3号位置分别截取连续的三个碱基，后面则依次截取密码子（3个连续的碱基），从而产生三种不同的表示。例如：人工制造DNA序列的第1号序列前12个碱基为aggcacggaaaa，三种不同解读为(agg)(cac)(gga)(aaa)和a(ggc)(acg)(gaa)aa和ag(gca)(cgg)(aaa)a；表示人工制造DNA序列的第号序列；表示按三种不同解读方式得到的第号序列中含有第个密码子的个数；表示按三种不同解读方式得到的第个密码子在第号序列中平均百分含量，即第个密码子在第号序列中出现的频率；表示按三种不同解读方式得到的第号序列中含有密码子的总数。则有如下关系可以提取DNA序列的判别特征：，其中由于数据的庞大，本文借用了计算机作为辅助工具，从而处理复杂的数据。文中以Visual C+ 6.0软件为平台，在其上逻辑编程，实现数据处理。对于三种不同解读DNA序列的方式，本文提出了转化，这样可以便于计算机的实现。如上例，人工制造DNA序列的第1号序列前12个碱基为aggcacggaaaa，三种不同解读为(agg)(cac)(gga)(aaa)和a(ggc)(acg)(gaa)aa和ag(gca)(cgg)(aaa)a，现可转化为(agg)cacggaaaa，a(ggc)acggaaaa，ag(gca)cggaaaa，agg(cac)ggaaaa，aggc(acg)gaaaa，aggcacg(gaa)aa，aggcacgg(aaa)a，aggcacgga(aaa)，这样可包含上述三种不同解读全部情况的密码子，且仅包含上述三种不同解读全部情况的密码子。根据本文的转化方法，提取DNA序列判别特征数据的程序见附录四。经程序运算，1-20号DNA序列（到）中64种密码子的统计频率分布如下（以下数据按四舍五入法保留小数点后4位。为了显示清楚，现将的矩阵以10个为一组，且纵横坐标相互交换，并不表示前10个DNA序列属于同一类，而后20个DNA序列属于另一类。）：表 4-1 1-10号DNA序列中64种密码子的统计频率分布u1u2u3u4u5u6u7u8u9u1010.03670.02750.00920.11010.03670.06420.06420.00920.05500.037020.00920.00910.00920.02750.00000.01830.04590.01830.01830.000030.01830.03670.01830.03670.01830.01830.00920.01830.00920.009340.02750.02750.01830.01830.00920.05500.03670.03670.00920.018550.01830.00000.01830.04590.00000.02750.02750.01830.00000.000060.00920.02750.00920.02750.01830.02750.01830.01830.00000.009370.00000.00000.00920.00920.00000.00000.01830.00920.01830.009380.00920.00920.00000.03670.00000.00920.04590.01830.02750.000090.00920.02750.02750.02750.01830.00920.00000.01830.00000.0093100.00920.00920.00000.00920.00920.00000.01830.00000.00920.0000110.00920.00920.00000.00920.01830.00000.00000.00920.00000.0000120.06420.02750.00920.00920.03670.01830.00000.00920.00000.0278130.00000.00000.00000.03670.00000.00000.01830.00000.00000.0000140.00920.00000.00000.00000.00000.00920.00000.00000.00920.0000150.00000.00920.00000.00920.00000.00000.00000.00000.01830.0000160.07340.04590.05500.00920.06420.09170.05500.10090.03670.0648170.01830.00920.00000.03670.00000.00920.00920.00920.00000.0093180.00920.01830.00000.04590.00000.01830.02750.00920.00000.0000190.01830.00000.02750.00920.01830.00000.00000.00000.00000.0093200.00000.00000.00000.01830.00000.00920.00920.03670.00000.0000210.00920.01830.00000.03670.00920.00920.00920.03670.00000.0093220.00000.00920.00000.04590.00920.02750.01830.01830.01830.0093230.00000.01830.00920.00920.01830.01830.00920.01830.00920.0185240.02750.00920.00000.01830.00000.00000.01830.00000.01830.0000250.00000.00000.00000.00920.00920.00000.00000.00000.00000.0000260.00920.00000.00920.00000.00000.00000.00000.00920.00000.0093270.00000.00000.00000.00000.00920.00000.00920.00000.00920.0185280.00000.01830.00920.00920.00920.01830.01830.02750.02750.0278290.01830.00000.00000.00000.00000.00000.00920.00920.00920.0000300.00920.00920.00000.01830.00000.00000.00920.00000.00920.0093310.00000.00000.00000.01830.00000.00000.00000.00000.00000.0000320.01830.04590.00920.01830.02750.01830.04590.01830.05500.0185330.00000.03670.01830.01830.01830.00920.00000.01830.00920.0093340.00920.00000.00920.01830.00920.00000.00000.00920.01830.0093350.02750.00000.02750.00000.01830.00920.00000.00000.00000.0185360.00000.00920.00000.01830.00920.01830.00920.00000.00920.0185370.00920.00000.00000.00000.00920.00000.00920.00000.00000.0093380.02750.00000.00000.01830.00000.00000.00920.01830.00000.0093390.00000.00000.00000.00000.00920.00000.00000.00920.00920.0093400.00000.01830.00920.00000.02750.00000.00000.00920.01830.0093410.00000.00000.00920.00920.01830.00000.00000.00920.00920.0093420.00000.00000.00000.00000.00000.00000.00000.00000.00000.0093430.00000.00000.00000.00000.00000.00000.00000.00000.00000.0093440.01830.00920.00000.00000.00920.00000.00920.00920.01830.0185450.00920.00000.00000.00920.00000.00000.00000.01830.00920.0000460.00000.00000.00000.00000.00920.00000.00000.00920.00920.0185470.00920.00000.00000.00000.00000.00000.00000.00920.01830.0556480.06420.00920.14680.01830.10090.08260.05500.04590.07340.0556490.03670.02750.02750.02750.00920.07340.08260.04590.02750.0093500.00920.00920.01830.01830.00920.01830.02750.1830.00000.0093510.02750.03670.04590.04590.02750.00000.00920.01830.00000.0000520.04590.01830.03670.00000.05500.01830.01830.02750.04590.0278530.00920.00920.00920.02750.00000.00000.00000.00000.00000.0000540.00000.01830.00000.01830.00920.00000.00920.01830.02750.0093550.00920.00000.00000.00000.00000.00000.00000.00000.00000.0185560.00920.01830.00000.00000.00000.00920.00000.00000.00920.0093570.02750.01830.01830.00920.00920.03670.00920.00000.02750.0370580.01830.00920.00000.00920.03670.00000.00000.02750.01830.0185590.00920.00000.00920.00000.00000.00000.00000.00920.01830.0185600.00000.02750.04590.00920.04590.04590.03670.03670.07340.0648610.09170.10090.13760.01830.10090.11010.11010.08260.05500.4630620.00920.03670.00920.02750.00000.00000.00000.00920.00920.0093630.04590.04590.07340.00000.09170.08260.04590.06420.10090.0833640.03670.03670.01830.00000.02750.00920.00920.00000.01830.0463表 4-2 11-20号DNA序列中64种密码子的统计频率分布u11u12u13u14u15u16u17u18u19u2010.06480.02780.00930.03700.08330.07410.10190.02780.00000.027820.06480.06480.02780.03700.04630.08330.03700.04630.01850.000030.01850.00000.00930.00000.00000.00930.02780.00930.00000.027840.00930.03700.01850.00930.00000.00000.00930.00000.00000.009350.02780.00000.00000.02780.03700.02780.00930.01850.03700.000060.00930.08330.08330.07410.08330.00930.02780.10190.06480.037070.00930.01850.00000.01850.00000.01850.03700.00000.03700.018580.01850.00930.01850.00930.00930.00930.03700.00000.00000.000090.00000.00000.00930.00930.00000.01850.00000.02780.00930.0093100.00930.00930.00930.00000.00000.01850.00930.01850.00930.0556110.00000.00000.01850.00000.00000.00000.02780.00000.00930.0000120.01850.00000.00930.00000.00000.00000.01850.02780.00000.0000130.00930.00930.01850.04630.00930.00930.00930.01850.00000.0000140.00930.01850.00930.02780.00000.00000.00930.00000.00930.0000150.00000.00000.00000.00000.00000.00000.00000.00000.00000.0000160.00930.03700.01850.00000.00930.00000.00000.00000.00930.0093170.06480.00930.03700.03700.04630.06480.03700.01850.02780.0370180.07410.02780.06480.04630.08330.03700.06480.06480.08330.0278190.00930.00930.01850.00930.00000.02780.00000.06480.02780.0278200.01850.02780.00930.03700.00930.00930.00000.00930.00930.0000210.12040.13890.12040.10190.08330.08330.01850.12960.11110.0648220.17590.16670.21300.15740.39810.11110.01850.15740.17590.2130230.00000.00000.00930.02780.00000.00930.00930.00930.03700.0370240.00000.00930.00930.00000.00930.02780.00930.00930.00000.0185250.00000.00930.00930.00930.00000.00000.02780.00000.00930.0185260.00000.00000.00930.04630.00000.03700.01850.00000.05560.0741270.00930.00000.00000.00000.00000.00000.01850.01850.00930.0093280.00000.00930.00000.00930.00000.00930.00000.00000.01850.0000290.00000.00930.00000.00000.00930.01850.01850.00000.00930.0093300.00000.00000.00930.00930.01850.00930.00930.00930.00000.0278310.00000.00000.00930.00930.00000.00000.00930.00000.00000.0000320.01850.00930.00930.00000.00000.01850.00930.00000.00000.0000330.00930.00000.00930.00000.00000.00930.00930.02780.00000.0000340.00000.00930.00000.01850.00000.00930.00000.00930.01850.0185350.00000.00000.00000.00000.00000.00000.02780.00000.00000.0093360.00000.00000.01850.00930.00000.00000.00930.00000.00000.0000370.00000.00000.00000.00930.00000.01850.05560.00930.00000.0185380.00930.00930.02780.02780.00000.01850.00930.02780.05560.0556390.00000.00000.00000.00000.00000.00930.00930.00000.01850.0463400.00000.00000.00000.00930.00000.00930.00000.00000.00930.0185410.00930.00000.00000.00000.00000.00000.00930.00000.00000.0000420.00000.00000.00930.00000.00000.00000.03700.01850.00930.0093430.00000.00000.00000.00000.00000.00000.03700.00000.00000.0000440.00000.00000.00930.00000.00000.00000.00000.00000.00930.0000450.00000.00000.00930.00000.00000.00930.00000.00000.00930.0000460.01850.00930.00930.00000.00000.00000.00000.00930.00930.0000470.00000.00000.00000.00000.00000.00000.00000.00000.00930.0000480.00000.00000.00000.00930.00000.00000.02780.01850.00000.0000490.01850.01850.00930.00930.00930.01850.02780.00930.00000.0000500.00930.00930.00930.02780.00000.02780.00930.00000.01850.0185510.00000.00000.01850.00000.00000.00000.00000.00000.00000.0000520.00000.00000.00000.01850.00930.00000.00000.00930.00930.0000530.01850.01850.00930.00000.01850.00930.01850.00000.00000.0093540.02780.05560.02780.02780.00930.00930.00000.02780.02780.0278550.00000.00000.00930.01850.00000.00930.00930.00930.00000.0000560.00000.00000.00000.00000.00930.00000.00000.00000.00000.0000570.00000.00000.00930.00930.00000.00000.00930.00930.00000.0000580.00000.00000.00000.00000.00000.00000.00930.00000.00930.0000590.00000.00000.00000.00000.00000.00000.00930.00000.00000.0000600.00000.00000.00000.00000.00000.00000.00930.00000.00000.0000610.01850.00930.00930.00930.00000.00930.00930.00000.00930.0093620.00930.03700.00930.00000.00930.00930.00000.00930.00000.0000630.00000.00000.00930.00000.00000.00000.02780.00930.00000.0000640.00000.00000.00000.00000.00000.00000.00000.00930.00000.0000上述提取的DNA序列判别特征可以构成模糊聚类分析中待分类对象的数据表征。以下将根据模糊聚类分析的一般步骤及方法，分析DNA序列的聚类情况。二、基于聚类要素建立模糊相似矩阵按第三章第二节介绍的模糊聚类分析的一般步骤和方法进行分析。需要说明的是上述DNA序列所提取的聚类要素可以不再进行初始化。这是因为上述DNA序列判别特征的单位相同，即都为百分比，其单位为1，而且数据的取值范围在之间。下面就将DNA序列所提取的聚类要素作为标准化后的数据进行处理。现在要基于DNA序列聚类要素（提取的判别特征）来计算分类对象之间的相似系数，从而得到相似系数的矩阵，它是自反且对称的。在第三章第二节中，已经介绍了建立模糊相似矩阵的一些方式，如数量积法、相关系数法、指数相似系数法、非参数方法、最大最小法、算术平均最小法、几何平均最小法、绝对值指数法、绝对值减数法、绝对值倒数法。现在选用夹角余弦法，如第三章第二节中的介绍：令，取同样，用计算机以Visual C+ 6.0软件为平台进行数据处理。代码见附录。得到的模糊相似矩阵为图4-1：图 4-1 基于密码子的DNA序列分类的模糊相似矩阵三、聚类分析模糊聚类的方法有很多种，如第三章第二节介绍的聚类编网法和最大树法，但为了方便计算机的实现，现采用传递闭包法求DNA序列的模糊等价矩阵，即传递闭包。为了简化计算，本文采用平方法求其传递闭包。由上面求得的模糊相似矩阵，至多经过步便可求得模糊等价矩阵。计算机编程代码见附录。求得的模糊等价矩阵（数据保留小数点后3位）为图4-2：图 4-2 基于密码子的DNA序列分类的模糊等价矩阵最后，聚类分析：取不同的值，得到各截矩阵为：当时，截矩阵为单位阵，分为20类；当时，截矩阵如图4-3，分为6类：，；图 4-3 基于密码子的DNA序列分类的截矩阵后面的分析省略截矩阵的图，分析方法相同。当时，根据截矩阵的分析方法 ，分为4类：，；当时，根据截矩阵的分析方法 ， 分为2类：，；当时，根据截矩阵的分析方法 ， 分为1类：；聚类图如下图4-4：四、结果分析当时，1、2、3、5号DNA序列聚合成一类，6-8号DNA序列聚合成一类，9、10号DNA序列聚合成一类，1-16、18、19、20号DNA序列聚合成一类。说明：1、2、3、5号DNA序列，6-8号DNA序列，9、10号DNA序列，1-16、18、19、20号DNA序列分别具有较好的相似性，相似程度高。当时，1、2、3、5-10号DNA序列聚合成一类，4、11-20号DNA序列聚合成一类。说明：1、2、3、5-10号DNA序列比1-20号的其他DNA序列更加相似；4、11-20号DNA序列也比1-20号的其他DNA序列具有更大的相似性。在模糊聚类分析中，由于提取判别特征（聚类要素）的方法不同或聚类方法的选取不当，有时会出现误判的现象14。因此，已知类别的序列分类的正确率或误判率常常作为衡量聚类方法优劣的标准。一般地，有：。本文选用正确率来衡量聚类方法的优劣，正确率的构造如下：对已知类别的1-20号人工DNA序列聚类。属于A类的对象成功地被判定为A类，或者属于B类的对象成功地被判定为B类，称为判定正确。设判定正确的个数为，总共的个数为（本文中），正确率为，则：由上面的聚类分析结果可知：当时，4号DNA序列自成一类；当时，4号DNA序列被判定归为B类DNA序列。而已知的4号DNA序列属于A类DNA序列，所以4号DNA序列无法通过上述方法进行聚类，则，即正确率为95%。上述方法是考虑到碱基在生物学上的特殊意义，基于密码子的概念解决DNA序列分类问题的，但是它没有考虑到DNA序列的序列排序性，遗漏了DNA序列的某些组合意义上的信息。下面将提出另一种提取DNA序列特征的方法，弥补上述方法在排列性上的不足。第二节 基于向量距离的DNA序列模糊聚类分析一、基于向量距离的DNA序列模糊聚类基本思想除了第三章第二节介绍的模糊聚类一般方法以外，常见的聚类分析方法还有系统聚类法、动态聚类法等。我们可以参考它们的做法，对模糊聚类法中模糊相似关系的建立提供其他的方法。在系统聚类法中用到了距离的概念来进行聚类。系统聚类法的基本思想是首先定义待分类对象之间的距离和类与类之间的距离。初始将各个待分类对象各自看成一类(每一类只包含一个对象)，这时类与类之间的距离与待分类对象间的距离是等价的，然后将距离最近的两类合并成新类，并计算新类与其他类之间的距离，再按最小距离准则合并类，这样每次缩小一类，直到所有的样品都并成一类为止。对于这里的距离，我们可以理解如下：把每一个分类对象的个聚类要素看成维空间的个坐标轴，则每一个分类对象的个要素所构成的维数据向量就是维空间中的一个点。这样，各分类对象之间的差异性就可以由它们所对应的维空间中点之间的距离度量。上述距离是事物之间差异性的测度，而相似系数则是其相似性的测度，所以距离和相似系数都是聚类分析的依据和基础。我们可以借用距离的概念，并做一下修改，将其应用到模糊聚类分析当中，从而标定与的相似程度，得到相似矩阵，再用模糊聚类法进行聚类分析。修改如下：令为第个分类对象与第个分类对象之间的距离，则其中为一适当选择的正数，使得计算的方法，我们可以参考常用的距离公式：1） 绝对值距离（海明距离）2） 欧氏距离3） 闵科夫斯基距离其中。当时，即为海明距离；当时，即为欧氏距离。4） 切比雪夫距离这是闵科夫斯基距离时的特殊情况。选择不同的距离，聚类结果会有所差异。在实际的应用中，我们可以也选取其他计算的方法。现在我们就采用上述思想，基于向量距离对本章第一节中的问题用数学的语言描述：1-20号人工DNA序列含有A、T、C、G为DNA的四种碱基；表示第号DNA序列中所含碱基的个数；表示第号DNA序列中前个碱基含A的个数，；表示第号DNA序列中前个碱基含T的个数，；表示第号DNA序列中前个碱基含C的个数，；值得说明的是，不需要在用一个变量来表示第号DNA序列中前个碱基含G的个数了。这是因为DNA序列含有且仅含有A、T、