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

陳靜+李家興

摘 要： 從DNA序列的堿基分布出發(fā)，以AGT作為標(biāo)準(zhǔn)，用8種坐標(biāo)表示堿基組，根據(jù)每組DNA序列中各坐標(biāo)的密度進(jìn)行聚類分析，得到分類結(jié)果。此算法避免密碼子密度繁瑣的計(jì)算，算法更簡(jiǎn)便。

從DNA序列的堿基排列順序出發(fā)，以（A，T，C）作為標(biāo)準(zhǔn)，將每組DNA序列用多個(gè)坐標(biāo)點(diǎn)來(lái)表示，根據(jù)兩組DNA序列對(duì)應(yīng)堿基組坐標(biāo)點(diǎn)的距離來(lái)分類。此算法考慮到DNA序列中堿基的排列順序，算法科學(xué)性更強(qiáng)。

關(guān)鍵詞： 聚類分析；密碼子；坐標(biāo)點(diǎn)

1 引言

DNA序列由堿基A、T、G、C排列而成，DNA序列的分類一直是基因工程研究的重要課題之一。本文將探討運(yùn)用聚類分析法對(duì)DNA序列進(jìn)行分類，參考例題為2000全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽題。根據(jù)一定的規(guī)則準(zhǔn)則提取數(shù)據(jù)，所給數(shù)據(jù)共有40組，其中前10組數(shù)據(jù)屬于A類，11-20組數(shù)據(jù)屬于B類，20-40為20組未知數(shù)據(jù)，需要將該20組數(shù)據(jù)進(jìn)行分類，即判斷未知的20組數(shù)據(jù)中哪些屬于A類，哪些屬于B類。

2 問題的分析與假設(shè)

查找相關(guān)文獻(xiàn)可知，已有多種方法分析該類問題。主要的分類算法仍為聚類分析，但是存在不同的分析方法。岳曉寧、徐寶樹、王競(jìng)波的基于聚類分析的DNA序列分類研究[1]，對(duì)密碼子出現(xiàn)的概率進(jìn)行分類；顧俊華、盛春楠、韓正忠的模糊聚類分析方法在DNA序列分類中的應(yīng)用[2]，對(duì)單個(gè)堿基出現(xiàn)的概率進(jìn)行分類，大量論文都對(duì)堿基或堿基組出現(xiàn)的概率為分類標(biāo)準(zhǔn)進(jìn)行聚類分析處理，字母的聚類會(huì)使算法繁瑣，同時(shí)單一的概率分析忽略了堿基或堿基組在DNA序列出現(xiàn)的順序。

同樣，本文用兩種分層聚類分析方法來(lái)對(duì)DNA序列進(jìn)行分類，但兩種方法中的分類標(biāo)準(zhǔn)均用坐標(biāo)點(diǎn)來(lái)表示DNA序列中的堿基，將字母數(shù)字化，既簡(jiǎn)化了算法，避免了上述算法所產(chǎn)生的缺點(diǎn)，又使得該算法對(duì)DNA序列的分類更加科學(xué)合理。

3 分層聚類分析法

3.1 模型建立

（1） 數(shù)據(jù)坐標(biāo)化處理

理論上密碼子的種類有64種，分別分析64種密碼子出現(xiàn)的概率，容易使得算法過(guò)于繁瑣，本文找出一種分類方法，簡(jiǎn)化了密碼子的種類。以AGT作為標(biāo)準(zhǔn)，AGT對(duì)應(yīng)坐標(biāo)點(diǎn)表示（1， 1， 1），當(dāng)坐標(biāo)點(diǎn)中x軸對(duì)應(yīng)密碼子第一個(gè)堿基為A時(shí)，x軸對(duì)應(yīng)數(shù)值為1，否則為0，y、z軸表示方法類似，具體表示如表1所示。

（2） 建立模糊相似矩陣

確定分類標(biāo)準(zhǔn)后，對(duì)每組DNA序列中對(duì)8種坐標(biāo)點(diǎn)出現(xiàn)的概率進(jìn)行統(tǒng)計(jì)分類，本文使用海明距離法建立模糊相似矩陣A=（xij）n×m。其中，第i組DNA序列和第j組DNA序列Xj的相似程度用相似系數(shù)rij=R（Xi，Xj）表示，Xik為第i組DNA序列中第k個(gè)坐標(biāo)點(diǎn)的出現(xiàn)的概率，H的取值為使rij∈[0，1]（i=1，2，...，n）的常數(shù)，此處H=1。

（3） 聚類分析

運(yùn)用數(shù)學(xué)軟件MATLAB對(duì)數(shù)據(jù)進(jìn)行統(tǒng)計(jì)分類，得到模糊相似矩陣A=（xij），再根據(jù)模糊相似矩陣來(lái)構(gòu)造一個(gè)模糊等價(jià)矩陣A*，其方法就是用平方法求出A的傳遞包t（A），則t（A）= A*，然后由大到小取λ，最后確定一個(gè)的取值。

3.2 模型求解

針對(duì)例題，上述算法中取λ=0.81，得到一個(gè)大小為40x40的0、1矩陣，對(duì)所得矩陣進(jìn)行分析得到分類結(jié)果如表2。題目給出的條件為1-10組為A類，11-20組為B類，所得結(jié)果未將1-10組與11-20組分在一類中，故分類結(jié)果科學(xué)合理性良好。最終得到結(jié)果，DNA序列22、23、25、27、29、30、32、34、35、36、37、39組屬于A類，21、24、26、28、31、33、38、40組屬于B類。

4 改進(jìn)分層聚類分析法

4.1 模型建立

（1） 數(shù)據(jù)坐標(biāo)化處理

以（A，T，C）對(duì)應(yīng)初始坐標(biāo)（0，0，0）作為數(shù)據(jù)坐標(biāo)的標(biāo)準(zhǔn)，首先表示DNA序列中的第一個(gè)堿基，若第一個(gè)堿基為A，坐標(biāo)的x軸對(duì)應(yīng)數(shù)值加1，否則不變，y、z軸表示方法類似。按此方法從第一個(gè)堿基組開始依次向后移一個(gè)堿基單位，直至表示該DNA序列中的所有堿基，例子如下所示。

（2） 建立模糊相似矩陣

根據(jù)上述方法對(duì)DNA序列進(jìn)行搜索，第i組DNA序列可以得到多個(gè)坐標(biāo)點(diǎn)Xi（i=1，2，...n）（xi，yi，zi），整合n組DNA序列，可以得到由坐標(biāo)點(diǎn)構(gòu)成的模糊相似矩陣A=（xij）n×m。其中，第i組DNA序列和第j組DNA序列之間的相似程度用相似系數(shù)ri，j=R（Xi，Xj）表示。（xik，yik，zik）為第i組DNA序列中第k個(gè)堿基組的坐標(biāo)表示，d（Xi，Xj）為第i組DNA序列和第j組DNA序列對(duì)應(yīng)坐標(biāo)點(diǎn)的距離。

（3） 聚類分析

同樣，運(yùn)用數(shù)學(xué)軟件MATLAB進(jìn)行直接聚類分析，待分類的DNA序列與已知的DNA序列進(jìn)行比較分類。由例題可知0-10組為A類DNA序列，11-20組為B類DNA序列，待分類的DNA序列與分別于A、B類DNA序列計(jì)算相似度系數(shù)，比較平均相似系數(shù)riA、riB大小，相似系數(shù)值越小，則相似度越高。即若riA>riB，則第i組DNA序列屬于B類，反之屬于A類。

4.2 模型求解

根據(jù)例題條件，可知每組DNA序列均由117個(gè)堿基組成，三個(gè)堿基組成的堿基組依次向后移動(dòng)堿基單位長(zhǎng)度，每組DNA序列可以得到117個(gè)坐標(biāo)點(diǎn)，于是得到一個(gè)由坐標(biāo)點(diǎn)組成的40x117的模糊相似矩陣。按照上述算法求坐標(biāo)點(diǎn)距離進(jìn)行分類，最終得到結(jié)果如下表所示。

5 模型評(píng)價(jià)

本文對(duì)運(yùn)用兩種聚類分析法研究DNA序列的分類問題，在第一種分析方法中以AGT作為標(biāo)準(zhǔn)用坐標(biāo)表示堿基組，共有8種坐標(biāo)表示方式，計(jì)算每組DNA序列中各種類坐標(biāo)的密度，然后運(yùn)用海明距離法建立模糊相似矩陣，并用平方法求出傳遞包矩陣，確定系數(shù)，得到分類結(jié)果。此結(jié)果精度較高，并且減少了堿基組的種類，使算法更簡(jiǎn)便。

在改進(jìn)的分層模糊分析算法中，以（A，T，C）作為標(biāo)準(zhǔn)用坐標(biāo)表示堿基組，每組DNA序列有多個(gè)坐標(biāo)點(diǎn)表示，根據(jù)兩組DNA序列對(duì)應(yīng)堿基組坐標(biāo)點(diǎn)的距離來(lái)判斷兩組或兩類DNA序列是否為同類。此結(jié)果不僅用堿基的分布進(jìn)行分類，還考慮到了堿基的排列順序，使算法科學(xué)性更強(qiáng)。

兩種聚類分析算法各有的優(yōu)勢(shì)，將兩算法的計(jì)算結(jié)果進(jìn)行對(duì)比，也無(wú)太大出入，在誤差范圍之內(nèi)，故兩算法都合理可靠，均可用于DNA序列的分類研究中。

參考文獻(xiàn)

[1] 岳曉寧，徐寶樹，王競(jìng)波.基于聚類分析的DNA序列分類研究[J].沈陽(yáng)大學(xué)學(xué)報(bào)，2008，20（6）：104-106.

[2] 顧俊華，盛春楠，韓正忠.模糊聚類分析方法在DNA序列分類中的應(yīng)用[J].計(jì)算機(jī)仿真，2005，20（10）：108-111.endprint