基于聚類分析法的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