基于聚类分析法的DNA序列分类

陈静+李家兴

摘 要： 从DNA序列的碱基分布出发，以AGT作为标准，用8种坐标表示碱基组，根据每组DNA序列中各坐标的密度进行聚类分析，得到分类结果。此算法避免密码子密度繁琐的计算，算法更简便。

从DNA序列的碱基排列顺序出发，以（A，T，C）作为标准，将每组DNA序列用多个坐标点来表示，根据两组DNA序列对应碱基组坐标点的距離来分类。此算法考虑到DNA序列中碱基的排列顺序，算法科学性更强。

关键词： 聚类分析；密码子；坐标点

1 引言

DNA序列由碱基A、T、G、C排列而成，DNA序列的分类一直是基因工程研究的重要课题之一。本文将探讨运用聚类分析法对DNA序列进行分类，参考例题为2000全国大学生数学建模竞赛题。根据一定的规则准则提取数据，所给数据共有40组，其中前10组数据属于A类，11-20组数据属于B类，20-40为20组未知数据，需要将该20组数据进行分类，即判断未知的20组数据中哪些属于A类，哪些属于B类。

2 问题的分析与假设

查找相关文献可知，已有多种方法分析该类问题。主要的分类算法仍为聚类分析，但是存在不同的分析方法。岳晓宁、徐宝树、王竞波的基于聚类分析的DNA序列分类研究[1]，对密码子出现的概率进行分类；顾俊华、盛春楠、韩正忠的模糊聚类分析方法在DNA序列分类中的应用[2]，对单个碱基出现的概率进行分类，大量论文都对碱基或碱基组出现的概率为分类标准进行聚类分析处理，字母的聚类会使算法繁琐，同时单一的概率分析忽略了碱基或碱基组在DNA序列出现的顺序。

同样，本文用两种分层聚类分析方法来对DNA序列进行分类，但两种方法中的分类标准均用坐标点来表示DNA序列中的碱基，将字母数字化，既简化了算法，避免了上述算法所产生的缺点，又使得该算法对DNA序列的分类更加科学合理。

3 分层聚类分析法

3.1 模型建立

（1） 数据坐标化处理

理论上密码子的种类有64种，分别分析64种密码子出现的概率，容易使得算法过于繁琐，本文找出一种分类方法，简化了密码子的种类。以AGT作为标准，AGT对应坐标点表示（1， 1， 1），当坐标点中x轴对应密码子第一个碱基为A时，x轴对应数值为1，否则为0，y、z轴表示方法类似，具体表示如表1所示。

（2） 建立模糊相似矩阵

确定分类标准后，对每组DNA序列中对8种坐标点出现的概率进行统计分类，本文使用海明距离法建立模糊相似矩阵A=（xij）n×m。其中，第i组DNA序列和第j组DNA序列Xj的相似程度用相似系数rij=R（Xi，Xj）表示，Xik为第i组DNA序列中第k个坐标点的出现的概率，H的取值为使rij∈[0，1]（i=1，2，...，n）的常数，此处H=1。

（3） 聚类分析

运用数学软件MATLAB对数据进行统计分类，得到模糊相似矩阵A=（xij），再根据模糊相似矩阵来构造一个模糊等价矩阵A*，其方法就是用平方法求出A的传递包t（A），则t（A）= A*，然后由大到小取λ，最后确定一个的取值。

3.2 模型求解

针对例题，上述算法中取λ=0.81，得到一个大小为40x40的0、1矩阵，对所得矩阵进行分析得到分类结果如表2。题目给出的条件为1-10组为A类，11-20组为B类，所得结果未将1-10组与11-20组分在一类中，故分类结果科学合理性良好。最终得到结果，DNA序列22、23、25、27、29、30、32、34、35、36、37、39组属于A类，21、24、26、28、31、33、38、40组属于B类。

4 改进分层聚类分析法

4.1 模型建立

（1） 数据坐标化处理

以（A，T，C）对应初始坐标（0，0，0）作为数据坐标的标准，首先表示DNA序列中的第一个碱基，若第一个碱基为A，坐标的x轴对应数值加1，否则不变，y、z轴表示方法类似。按此方法从第一个碱基组开始依次向后移一个碱基单位，直至表示该DNA序列中的所有碱基，例子如下所示。

（2） 建立模糊相似矩阵

根据上述方法对DNA序列进行搜索，第i组DNA序列可以得到多个坐标点Xi（i=1，2，...n）（xi，yi，zi），整合n组DNA序列，可以得到由坐标点构成的模糊相似矩阵A=（xij）n×m。其中，第i组DNA序列和第j组DNA序列之间的相似程度用相似系数ri，j=R（Xi，Xj）表示。（xik，yik，zik）为第i组DNA序列中第k个碱基组的坐标表示，d（Xi，Xj）为第i组DNA序列和第j组DNA序列对应坐标点的距离。

（3） 聚类分析

同样，运用数学软件MATLAB进行直接聚类分析，待分类的DNA序列与已知的DNA序列进行比较分类。由例题可知0-10组为A类DNA序列，11-20组为B类DNA序列，待分类的DNA序列与分别于A、B类DNA序列计算相似度系数，比较平均相似系数riA、riB大小，相似系数值越小，则相似度越高。即若riA>riB，则第i组DNA序列属于B类，反之属于A类。

4.2 模型求解

根据例题条件，可知每组DNA序列均由117个碱基组成，三个碱基组成的碱基组依次向后移动碱基单位长度，每组DNA序列可以得到117个坐标点，于是得到一个由坐标点组成的40x117的模糊相似矩阵。按照上述算法求坐标点距离进行分类，最终得到结果如下表所示。

5 模型评价

本文对运用两种聚类分析法研究DNA序列的分类问题，在第一种分析方法中以AGT作为标准用坐标表示碱基组，共有8种坐标表示方式，计算每组DNA序列中各种类坐标的密度，然后运用海明距离法建立模糊相似矩阵，并用平方法求出传递包矩阵，确定系数，得到分类结果。此结果精度较高，并且减少了碱基组的种类，使算法更简便。

在改进的分层模糊分析算法中，以（A，T，C）作为标准用坐标表示碱基组，每组DNA序列有多个坐标点表示，根据两组DNA序列对应碱基组坐标点的距离来判断两组或两类DNA序列是否为同类。此结果不仅用碱基的分布进行分类，还考虑到了碱基的排列顺序，使算法科学性更强。

两种聚类分析算法各有的优势，将两算法的计算结果进行对比，也无太大出入，在误差范围之内，故两算法都合理可靠，均可用于DNA序列的分类研究中。

参考文献

[1] 岳晓宁，徐宝树，王竞波.基于聚类分析的DNA序列分类研究[J].沈阳大学学报，2008，20（6）：104-106.

[2] 顾俊华，盛春楠，韩正忠.模糊聚类分析方法在DNA序列分类中的应用[J].计算机仿真，2005，20（10）：108-111.endprint