模煳聚類在DNA序列分類中應用

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

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

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

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

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

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