模煳聚類在DNA序列分類中應(yīng)用

1、模糊聚類在DNA分類中的應(yīng)用11易杯全國大學(xué)生數(shù)學(xué)建模競賽題：生物學(xué)家發(fā)現(xiàn)DNA序列是由四種堿基A,T,C,G按一定順序排列而成,其中既沒有“斷句”,也沒有標(biāo)點(diǎn)符號(hào),同時(shí)也發(fā)現(xiàn)DNA序列的某些片段具有一定的規(guī)律性和結(jié)構(gòu). 由此人工制造兩類序列(A類編號(hào)為110；B類編號(hào)為1120).現(xiàn)在的問題是如何找出比較滿意的方法來識(shí)別未知的序列(編號(hào)為2140), 并判斷它們那些屬于A類,那些屬于B類, 那些既不屬于A類又不屬于B類.問題：2問題數(shù)學(xué)模型為了表述的嚴(yán)格和方便 ,本文用數(shù)學(xué)的語言來重述這個(gè)問題: 已知字母序列 和字母序列集合A,B, ,其中 ,當(dāng) i 1, 10 時(shí)

2、, A;當(dāng) i 11, 2 時(shí), B,現(xiàn)要求當(dāng) 21i40時(shí),字母序列S 與集合 A及集合 B的關(guān)系。以下是計(jì)算出題中所給的序列1-20中的A , C，G, T的含量百分比如下表：34(1) 原始數(shù)據(jù)標(biāo)準(zhǔn)化首先對樣本數(shù)據(jù)進(jìn)行預(yù)處理，并將數(shù)據(jù)壓縮到0,1閉區(qū)間內(nèi)。其中： 表示第i個(gè)DNA序列的第j個(gè)指標(biāo)（1）（3） （2）（4）5(1) 原始數(shù)據(jù)標(biāo)準(zhǔn)化其中 ， ，分別表示 中的最小值和最大值。當(dāng) 時(shí)，則 ；當(dāng) 時(shí)，則 。將N個(gè)樣本的第j個(gè)指標(biāo)的平均值公式（1）及標(biāo)準(zhǔn)差公式（2）帶入原始數(shù)據(jù)標(biāo)準(zhǔn)化公式（3），即可得到標(biāo)準(zhǔn)化數(shù)據(jù)。然后再運(yùn)用如下極值標(biāo)準(zhǔn)化公式（4），將公式（3）得到標(biāo)準(zhǔn)化數(shù)據(jù)壓縮到0

3、，1內(nèi)，得到原始數(shù)據(jù)標(biāo)準(zhǔn)化并壓縮到0,1范圍后的輸出數(shù)見下表.6標(biāo)準(zhǔn)化后的第1-20組DNA序列樣本指標(biāo) 7(2) 模糊矩陣的確定及聚類過程分析引入模糊相似矩陣如下：其中， 表示樣本 與 之間的相似程度，當(dāng) 接近于1時(shí)，表明這兩個(gè)樣本相似程度較高。對應(yīng)于本文中 分別表示第i個(gè)和第j個(gè)DNA樣本序列。8(2) 模糊矩陣的確定及聚類過程分析由于模糊相似矩陣R的確定方法有很多，經(jīng)過對數(shù)量積法、相關(guān)系數(shù)法等11種常用方法的演算，本文從中選取了分類正確率較高的2種方法進(jìn)行詳細(xì)闡述并給出了分類結(jié)果。a. 相關(guān)系數(shù)法當(dāng) 時(shí)，得到模糊相似矩陣，然后用傳遞閉包法確定模糊等價(jià)矩陣。（其中為閾值，大于或等于取 1,

4、小于取 0,從而獲得一個(gè)新矩陣, 將矩陣中相同的行歸類,便可得到最后的分析結(jié)果。）9分類結(jié)果是： 1,2,3,5,6,7,8,9,10，11,12,13,14,15,16,18,19,20，4，17得到的模糊等價(jià)矩陣：10(2) 模糊矩陣的確定及聚類過程分析b. 夾角余弦法當(dāng) 時(shí)，分類結(jié)果為：1,2,3,5,6,7,8,9,10，11,12,13,14,15,16,18,19,20，4，17（具體步驟如相關(guān)系數(shù)法）11（3）結(jié)果分析綜合分析所有的模糊聚類分析結(jié)果發(fā)現(xiàn)，相關(guān)系數(shù)法、夾角余弦法、歐氏距離法得到的分類結(jié)果完全相同，均為1,2,3,5,6,7,8,9,10，11,12,13,14,15

5、,16,18,19,20，4，17正確率達(dá)90%，以此作為以堿基含量為特征下的模糊聚類分析方法的分類結(jié)果，并認(rèn)為采用如上三種模糊聚類分析方法對DNA序列分類具有可行性。12解決問題由此我們分別運(yùn)用如下3種方法對序列 DNA序列 21 - 40進(jìn)行模糊聚類分析 ,得到結(jié)果如下:相關(guān)系數(shù)法( = 0 . 85)分類結(jié)果: 21 24 26 28 31 33 38 40 , 22 23 25 27 29 30 34 35 36 37 39 , 32夾角余弦法( = 0 . 75)分類結(jié)果: 21 24 26 28 31 33 38 40 , 22 23 25 27 29 30 34 35 36 37

6、 39 , 32歐氏距離法 ( = 0 . 75)分類結(jié)果: 21 24 26 28 31 33 38 40 , 22 23 25 27 29 30 34 35 36 37 39 , 3213解決問題綜合上述的模糊聚類分析方法 ,將 21 - 40個(gè) DNA序列大致分為如下 3類 , 其分類結(jié)果為: 21 24 26 28 31 33 38 40 , 22 23 25 27 29 30 34 35 36 37 39 , 32其中編號(hào)為 32的 DNA序列無法準(zhǔn)確歸類.14結(jié)論和分析綜合以上所有的模糊聚類分析結(jié)果 ,我們得到序列 21 - 40的 DNA序列分類的最終結(jié)果:A類: 22 23 25 27 29 30 34 35 36 37 39 B類: 21 24 26 28 31 32 33 38 40 分析上述所有的 DNA序列分類結(jié)果 ,我們還可以發(fā)現(xiàn) ,模糊聚類分析中的相關(guān)系數(shù)法在對 DNA序列分類時(shí) ,它得到的分類結(jié)果在所有模糊聚類分析方法中表現(xiàn)最優(yōu)。DNA序列分類方法種類繁多 ,但它們都有一個(gè)共同特點(diǎn):分類結(jié)果精度不高;本文運(yùn)用模糊聚類分析的方法 ,忽略了 DNA序列內(nèi)部堿基排序規(guī)律 ,從宏觀角度對 DNA序列進(jìn)行分