DNA序列的聚类问题

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(43)维的向量表示。这样64维序列又有三种解读方式：对于一个给定的DNA序列，分别从开始的1、2、3号位置分别截取产生三种不同的表示。如序列aggcacggaaaa可分成(agg)(cac)(gga)(aaa)或(ggc)(acg)(gaa)或(gca)(cgg)(aaa)。这3种不同的截法所产生三种不同的密码信息，需要对其进行处理。周玉元等在《DNA序列分类的Fisher判别法》［切一文中，由生物学和生物化学知识，用碱基互补配对原则，将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；u表示人工制造DNA序列的第，号序列；ix表示按三种不同解读方式得到的第，号序列中含有第k个密柯子的个数；p表示按三种不同解读方式得到的第k个密码子在第,号序列中平均百分含量，即第k个密码子在第，号序列中出现i的频率；M表示按三种不同解读方式得到的第i号序列中含有密码子的总数。则有如下关系可以提取DNA序列的判别特征：Pik=M,其中M=£%kk=1由于数据的庞大，本文借用了计算机作为辅助工具，从而处理复杂的数据。文中以VisualC++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种密码，—^、侃U子的统计频率分布如下(以下数据按四舍五入法保留小数点后4位。为了显示清楚，现将20X64的矩阵以10个为一组，且纵横坐标相互交换，并不表示前10个DNA序列属于同一类，而后20个DNA序列属于另一类。)：表4-11-10号DNA序列中64种密码子的统计频率分布uiU2U3u4U5U6U7U8U9Uio10.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.0093

40.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.0093

380.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-211-20号DNAJ序列中64种密码毋子的统计频率分布u11U12u”13U14U15U16U17U18U19U2010.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.0000

60.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.0463

400.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，而且数据的取值

范围在m］之间。下面就将DNA序列所提取的聚类要素作为标准化后的数据进行处理。现在要基于DNA序列聚类要素（提取的判别特征）来计算分类对象之间的相似系数，，从而得到相似系数的矩阵.，它是自反且对称的。 iJRGil，Pi2,Gil，Pi2,…，Pi64),£乙勺k=1们：'pj同样，用计算机以VisualC++6.0软件为平台进行数据处理。代码见附录。得到的模糊相似矩阵为图4-1：输天源交件名：cede,txt输入密码子标'谜上:件名：'standar.t-xt模糊相似矩阵如下:1.00010,8221.0000.8510.8581.0000.4500.5070.2921.0000.S&70.8740.0980;3580,8190.88®'0-.7990.5250.7620.7@3.0；8040.6290.7800.7930 0.4811.0000.獭0,7150；8071.0000.8900.8650,6800.7610.6050.4440.8340.7860.7470.7340.7150,3610,0330.7750；2460.3090.1290.J6970.1970.3470.2^0.2940.1010.5900.1700.3191.0000.8070,765L酬0.4020.350说腮0,2790.1110；5540.1840.2840.2960.2190.2580.1240;£430.1900.3110.S530.11g0.159口.照40/&280.1050.2400,247。.戏10.3080.1网0.7^0.199。.渤0.4470.4490.4110.2980.7490；3@40.47.70.57?0.2430.3050.1760,5890.2290.^2璀脂0.1830/2120.0940.5060.1580.2290^2570.1890潮50.0370.4980.1700.-2170：.2^81.0000.7361.0000.7480,0541.0000/359 摭赣 0.202 1.0000.406 0.215 0.207 0押32 1.0000.348 0.185 0.195 0.82,^ 0.906 1.0000：362 0.219 0.216 0^304 0.876 0.914 1.0000/204 0.164 O.r^O 0.870 0.802 0.905。.獭 1.0000.360 0.261 0.219 0^08 0.856 0.807 0：871 0.754 1.0000/361 0.451 0.418 0,535 0.408 0.9,89 0.471 0海 0.618 1.0000.^2? 0.196 0.^27 D312 0.658 0.9^1 0.881 0.806 0.850 0.441 1.0000/345 0.161 0.194 0.858 0.-819 0.9U 0.916 0.821 0..796 0.350 0.8761.0000,271 0.184 0.194 0.764 0.745 0.849 D.E聘用,83E 0.744 0.387 0.7680.8521.000图4-1基于密码子的DNA序列分类的模糊相似矩阵三、聚类分析模糊聚类的方法有很多种，如第三章第二节介绍的聚类编网法和最大树法，但为了方便计算机的实现，现采用传递闭包法求DNA序列的模糊等价矩阵，即传递闭包。为了简化计算，本文采用平方法求其传递闭包。由上面求得的模糊相似矩阵R，至多经过hogn]+1步便可求得模糊等价矩阵R。 2R—R2T^2）f一R22k=R计算机编程代码见附录。求得的模糊等价矩阵（数据保留小数点后3位）为图4-2：o'*D:\Progra*Files\MicrosoftVisualStudio\ByProjects\FTTZZYCLUSTERYDebug\Cut_set.exe模糊等价矩阵如下：1.0000.8511.0000.8510.9741.0000.6290.&290.6251.0000.8510.^74O.'&980.^291.000Q.曲肿脱铀80.^3\0.6^0：W1.000TOC\o"1-5"\h\z0.8H;0^^O.'&n. 0.629 Oj'On 0.898 1.0000.^3^0^330.^^. 0.6^ 0-865 0：i865 1.0000.8340•.砒40：B34 0.629 O;'034 0.83S 1.0000.^340i^340.^34 0.629 Q：爵4 0.883 0.354 1.0000.8290.^90.829 0.739 0/829 0.629。:牍9 0.^9 0.629。.皎91.0000.623 0.BM 0.629 0.7^9 0.629 0.623 0.625 0.B29 0.623 L脸 0.9J2 1.0000.623 0.6^9 0/623 0.739 0/629 0.629 0：;'62B 0.6^9 0.62B 0.6^9 0.928 O.aZS 1.0000.625 0.BM 0.625 0.739 0.629 0.623 0.625 0.B29 0.623 0.B2S 0.914 0.914 0.914 1.0000.623 0.6^9 0/623 0.739 0/629 0.629 0：;'62B 0.6^9 0.62B 0.6^9 0.905 0.905 0.905 0.305 1.0000.625 0.BM 0.625 0.7^ 0.629 0.6M 0.625 0.B29 0.625 0.B2S 0.908 0.908 0.908 0.B08 0.905 1.0000.623 0.6^9 0/623 0.749 0/629 0.629 0：;'62B 0.6^9 0.62B 0.6^9 0/739 0.7B9 0：;739 0.739 0.739。.商9 1.0000.625 0.BM 0.625 0.739 0.629 0.623 0.625 0.B29 0.623 0.B2S 0.921 Q.雅1 0.921 0.914 0.905 0.B08 0.^33 1.0000.623 0.6^9 0/623 0.739 0/629 0.629 0：;'62B 0.629 0.62B 0.6£9 0.914 0.914 0.914 0.916 0.905 0.308 0.-759 0.914 1.0000.629 0.B29 0.629 0.7^ 0.629 0.629 0.629 0.B29 0.629 0.B29 0/882 0.W 0/832 0.B82 0.882：0iB82 0.733 0.882 0/8821.000图4-2基于密码子的DNA序列分类的模糊等价矩阵最后，聚类分析：人取不同的值，得到各截矩阵为：当…1.00时，截矩阵为单位阵，〃分为20类；当M=0.85时，截矩阵如图4-3，U分为6类：｛u,u,u,u｝，r2’3’5匕4｝，*6,u7,u8｝， *9，"10｝'*11，"12,u13,u14,U15,"16,"18,"19,U20｝'。土*D:\Progra>Files\Micrasoft菊五阈值:0.85陶1直为G.35Q的截矩阵如下：1111110001111010001111010 0 0 0 0 10 0 0 0 0 1 10 0 0 0 0 1 1 10 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 00101101110111101111101111110000000101111110101111110111,U2,笠'U5,U6,U1,U2,笠'U5,U6,U7当X=0.70u,u,u,u,u当…0.600ui3,ui4,ui5,ui6,ui7ui8ui9201u｝；00000000001111110111图4-3基:于密码子的DNA序列分类蚪0.85的截矩阵后面的分析省略截矩阵的图，分析方法相同。当…0.75时，根据截矩阵的分析方法，U分为4类:{u ,u,u,u,u,u,u,u,u}'{u }'阵2345678910111213141516171819201.000.85—— \ I—p-l 4 2345678910111213141516171819201.000.85—— \ I—p-l 4 0.75 | |0.70 \ 0.60 0.00图4-4基于密码子的DNA序列分类聚类图四、结果分析当"085时，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序列分别具有较好的相似性，相似程度高。当"070时，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一正确率。本文选用正确率来衡量聚类方法的优劣，正确率的构造如下：对已知类别的1-20号人工DNA序列聚类。属于A类的对象成功地被判定为A类，或者属于B类的对象成功地被判定为B类，称为判定正确。设判定正确的个数为m，总共的个数为M（本文中M——20），正确率为〃，则：mmP——————M20由上面的聚类分析结果可知：当洋075时，4号DNA序.列自成一类；当"070时，4号DNA序列被判定归为B类——.DNA序列。而已知的4号DNA序列属于A类DNA序列，所以4号DNA序列无法通过上述方法进行聚类，则”——19，〃——95%，即正确率为95%。P——上述方法是考虑到碱基在生物学上的特殊意义，基于密码子的概念解决DNA序列分类问题的，但是它没有考虑到DNA序列的序列排序性，遗漏了DNA序列的某些组合意义上的信息。下面将提出另一种提取DNA序列特征的方法，弥补上述方法在排列性上的不足。第二节基于向量距离的DNA序列模糊聚类分析一、基于向量距离的DNA序列模糊聚类基本思想除了第三章第二节介绍的模糊聚类一般方法以外，常见的聚类分析方法还有系统聚类法、动态聚类法等。我们可以参考它们的做法，对模糊聚类法中模糊相似关系的建立提供其他的方法。在系统聚类法中用到了距离的概念来进行聚类。系统聚类法的基本思想是首先定义待分类对象之间的距离和类与类之间的距离。初始将各个待分类对象各自看成一类（每一类只包含一个对象），这时类与类之间的距离与待分类对象间的距离是等价的，然后将距离最近的两类合并成新类，并计算新类与其他类之间的距离，再按最小距离准则合并类，这样每次缩小一类，直到所有的样品都并成一类为止。对于这里的距离，我们可以理解如下：把每一个分类对象的皿个聚类要素看成m维空间的m个坐标轴，则每一个分类对象的皿个要素所构成的m维数据向量就是m维空间中的一个点。这样，各分类对象之间的差异性就可以由它们所对应的m维空间中点之间的距离度量。上述距离是事物之间差异性的测度，而相似系数则是其相似性的测度，所以距离和相似系数都是聚类分析的依据和基础。我们可以借用距离的概念，并做一下修改，将其应用到模糊聚类分析当中，从而标定u与u的相似程度r，得到相似矩阵，再用模糊聚类法进行聚类分析。修改如下：令*•为第,个分类对象与第;个分类对象之间的距离，则1勺_1m日j其中M为一适当选择的正数，使得0<r.,<1计算d的方法，我们可以参考常用的距离公式:1） 绝对值距离（海明距离）

mmj£xik-xjkk=1欧氏距离1m( )dij=\;£*k-xjk»Lk=1闵科夫斯基距离其中

离。m£X其中

离。m£XIk=1当p=1时，即为海明距离；当p=2时，即为欧氏距djik—Xjk切比雪夫距离dj,=max乂诙-x*k这是闵科夫斯基距离时的特殊情况。 、p二选择不同的距离，聚类结果会有所差异。在实际的应用中，我们可以也选取其他计算d的方法。现在我们就采用上述思想，ij基于向量距离对本章第一节中的问题用数学的语言描述：1-20号人工DNA序列含有A、T、C、G为DNA的四种碱基;L表示第,号DNA序列中所含碱基的个数；；表示第,号DNA序列中前k个碱基含A的个数，ik11<k<L；星表示第i号DNA序列中前k个碱基含T的个数，1<k<L；x］表示第i号DNA序列中前k个碱基含C的个数，1<k<L；值得说明的是，不需要在用一个变量来表示第，号DNA序列中前k个碱基含G的个数了。这是因为DNA序列含有且仅含有A、T、C、G四种碱基，即有x=kxxx成立，其中x表示第i号DNA序列中前k牛碱基含Gik的个数。由x弋x、x可以构成一组3维向量，记为x=(xxk1xh其中"k<L。对于第,号DNA序列有L个x x,x 1—k<L '--L遗样的向童，'舞,号DNA序列有乙个这样的向量。本文将以这L个向量和这L个向量构造模糊相似系数。具体方法如下:（一）Z’distanceC,x,ikjkk=0 Lij使得wrv1，本文取c=0.02；离诚电羸绝矗距着藩和箫嘴蹈这里瞿切比雪夫距离，本文选用欧氏距离，即：其中r=1一为一常数（disdistancel*,x.)=i,j=1,2,^,20,k<minQ,L)ij按上述方式定义可以确保0<r<1，r=1，且r=r，也就是说可以确保既是自反的又是对称•的，艮此是模糊相似矩阵。但，这要求x和x这两个向量的个数相同，这样就存在k<min。L），即较长的那一组DNA序列将丢失一部分数据,。对于本文先前给出的数据，vi,正札2,...,20｝都有］L_L|<1，说明任意两个DNA序列的长度差都不超过1，这样丢失的数据将是很少的，所以适用于上述模糊聚类方法。与基于密码子的DNA序列模糊聚类分析方法相同地，由平方法求得其传递闭包，从而得到模糊等价矩阵.。最后R再取不同的阈值人，得到截矩阵，以等价类的概念进行聚类分析。二、基于向量距离的DNA序列模糊聚类分析根据上述思想，用计算机以VisualC++6.0软件为平台进行数据处理（代码见附录四），得到的模糊相似矩阵如下图4-5:"*D:\Progra>FilesXIicrosoftVisualStudioMyProjects\DNA_Clusler\Debugi\Ertractinn-eze*模糊相似矩阵如下：1.0000.8591.0000.8800.8400.7950.7460.8400.8400,9030.§42模糊相似矩阵如下：1.0000.8591.0000.8800.8400.7950.7460.8400.8400,9030.§420.8220.8310.8750.9190.8590.9110.7^0..&020；5S70.6070.4730.5600：5000.5970.5140.5990.4480<5350.5970/7550.7920.52(0.6100.4560.5540.4660.5651.0000.6991.0000.9280.68?-0.S2S0J180：7580.^490.3570.7840.064L秘0.7900.5980.4910.6780.4380.6080.4710.8030.4780.6520：3240.4920.4070.8820?72'60,^160.4畦L嗽'0.4&70；5460.4580.5511.0000.7870：:7290.8560.8790.8470.4870.4400.4810.4840：3290.4850*0.5010.4550.4791.000口差腭0.865。船0.6790.594。.就L5300,^600.4160.5870.7730,^640.4800.4941.000顷50.7990.6580.6910.82'80.6190.6530：5110.68^0.8370.6510.5680,5671.0000：9051.0000.7930.8&11.0000.620 0.575 0.491 1.0000.568 0<529 0.461 0；91^ 1.0000.598 0.568 0.520 0.836 0.87? 1.0000.609 0.572 0.509。涕12 0.929 0.896 1.0000.455 0.420 0.361 0.809 0^75 0.810 0.834 1.0000.616 0<571 0.486 0>924 0..^87 0.811 0.897 0.792 1.0000：m 0.780 0.692 0/724 0.671 0.685 0.713 0；558 0.734 1.0000*21 0<585 0.533' 0.873 0.890 0.3暨:。脂技L.刊1 0.^67 0.72'6 1.0000.561 0.540 0.513 0/701 0滋B 0.885 0^53 0.790 0.776 0.655 0^871.0000,575 0.551 0.54&： 0；754 0.790 0.844 0.W；0J50 0.756 0.669 0.^550.9221.000图4-5基于向量距离的DNA序列分类的模糊相似矩阵用平方法对上述模糊相似矩阵求传递闭包，得到的模糊等价矩阵如下图：*D:\Progra*Files\MicrosoftVisualStudio\ByProjects\DITA__CliLster\Debug\Extractiaii.exe*但湖等价矩阵如下:1.0000.8790.8800.8480.8800.•满0.89^0.8790.8790.847540.7340,7540.7340,7540.?340.8370J34L珈0.7341.0000.8790.8490.-8790.8790.-8790.9191.0000.8790.8800.8480.8800.•满0.89^0.8790.8790.847540.7340,7540.7340,7540.?340.8370J34L珈0.7341.0000.8790.8490.-8790.8790.-8790.9190；9110.8470.?340.7340.7340.7340.7340.7340.0370.7340.7340.7341.0000.8480.82H0.8800.8800.8790.8790.847L伽0.734L诳0.734L诳0.?340.8370J340,7540.7341.0000.8490.8490.8490.8490.8490.8470.?340.7340.7340.7340.7340.7340.037