DNA序列的分類問題.doc

DNA序列的分類問題摘要本文給出了關(guān)于對DNA序列集合如何進行分類問題的解決方案。主要使用了Matlab軟件對問題進行建模及運算，運用了聚類分析及判別分析的方法對數(shù)據(jù)進行處理。在對原始數(shù)據(jù)的處理和轉(zhuǎn)換方面，使用了C#編寫了相關(guān)代碼，程序完成的主要任務是提取A、T、C、G在各個DNA序列集合中分別出現(xiàn)的頻率，然后將這四個頻率值作為每個DNA序列集合的特征向量，在Matlab中對其進行聚類分析，并利用分類結(jié)果，對未分類的DNA序列集合進行分類預測。1引言 隨著人類社會信息和知識總量的不斷膨脹，如何有效地管理和利用這些信息成為人們越來越關(guān)注的問題?？焖僭鲩L的海量數(shù)據(jù)，它們存放在大型和大量的數(shù)據(jù)存儲庫中。如果沒有強有力的工具，那么這些收集在大型數(shù)據(jù)存儲庫中的數(shù)據(jù)就會變成“數(shù)據(jù)墳墓”，從而出現(xiàn)數(shù)據(jù)豐富、信息貧乏的現(xiàn)象，而這些數(shù)據(jù)也難以被有效地利用并為人們的決策提供強有力的支持。數(shù)據(jù)挖掘技術(shù)正是在這種擴大的數(shù)據(jù)和貧乏的信息之間架起的一座橋梁，它的主要工作就是利用數(shù)據(jù)挖掘工具進行數(shù)據(jù)分析，發(fā)現(xiàn)重要的數(shù)據(jù)模式，對商務策略、知識庫、科學和醫(yī)學研究做出巨大貢獻。1 聚類分析是數(shù)據(jù)挖掘領(lǐng)域里經(jīng)常使用的基本方法之一，它是將數(shù)據(jù)對象分成類或簇的過程，使得同一個簇的對象之間具有很高的相似度，而不同簇中的對象高度相異。相異度根據(jù)描述對象的屬性值評估，通常使用距離變量。2在本文中，主要使用聚類分析對DNA序列進行分類。1. 1需要解決的問題2000年6月，人類基因組計劃中DNA全序列草圖完成，2002年完成精確地全序列圖。而DNA序列是由A、T、C、G四個字符按一定順序排成的長約30億的序列。但人們除了知道這四個字符表示四種堿基之外，對DNA序列所包含的其他信息卻幾乎一無所知。因此，充分發(fā)掘DNA序列的結(jié)構(gòu)對于理解DNA全序列有著十分重要的意義。該項目現(xiàn)有20個已知類別的人工制造DNA序列，其中序列標號110 為A類，11-20為B類?，F(xiàn)在需要從中提取特征，構(gòu)造分類方法，可以利用這些已知類別的序列，衡量所使用的分類方法是否足夠好。然后用該方法，對另外20個未標明類別的人工序列進行分類預測。2. 2數(shù)據(jù)集本項目所采用的數(shù)據(jù)集來自于2000年網(wǎng)易杯全國大學生數(shù)學建模競賽題目，題目中給出了20個已知類別的人工制造DNA序列，前10個為A類，后10個為B類。并且給出了20個未知分類的人工序列進行分類預測。數(shù)據(jù)文件見附錄art-model-data.txt3. 3 對數(shù)據(jù)的預處理由于原始數(shù)據(jù)均為一連串的A、T、C、G的字符組合，要對其進行數(shù)據(jù)挖掘，就需要對原始數(shù)據(jù)進行預處理，即查看其中是否存在異常值、錯誤值和空缺等情況，并對上述情況進行相應的處理。14數(shù)字特征的提取通過編寫C+程序，來得到每一條DNA中所包含的A、T、C、G的堿基數(shù)量以及該DNA總的堿基數(shù)，從而得到每條DNA中A、T、C、G在序列中出現(xiàn)的頻率及序列總長度，分別記為。程序代碼如下：將40條DNA序列應用該程序進行處理，最終得到如下結(jié)果：序號ATCG總數(shù)1331519441112301718461113307245011144732122011152612264711163914144411173921114011183121184111192317234811110201530451111139555111101236553161101328571114110143355913110153271071101640519101101739292715110183255131011019246216811020226219711021314122191132230232526105231819263910224224722221152526232432105262544242111427242421351042830521718117291519224510130312726231073127402025112321936252911033303721231113424172437102353521223510336242232271053722212634104382651202011739292530221064023502320116其中，用紅色標記出來的組，第22、32、37組均出現(xiàn)除A、T、C、G外的字符，這可能是由于數(shù)據(jù)錄入時的人工失誤造成。對于這三組數(shù)據(jù)，本文采用將錯誤字符忽略的辦法，即DNA序列總數(shù)使用A、T、C、G四個字符出現(xiàn)的總數(shù)和，將錯誤字符的個數(shù)忽略。將上述表格在EXCEL中進行計算，求出每條DNA中A、T、C、G出現(xiàn)的概率，即得到下表：序號PAPTPCPG10.29730.13510.17120.396420.27030.15320.16220.414430.27030.06310.21620.450540.42340.28830.10810.180250.23420.10810.23420.423460.35140.12610.12610.396470.35140.18920.09910.360480.27930.18920.16220.369490.20720.15320.20720.4324100.18020.13510.27030.4054110.35450.50000.04550.1000120.32730.50000.02730.1455130.25450.51820.10000.1273140.30000.50000.08180.1182150.29090.64550.00000.0636160.36360.46360.08180.0909170.35450.26360.24550.1364180.29090.50000.11820.0909190.21820.56360.14550.0727200.20000.56360.17270.0636210.27430.36280.19470.1681220.28570.21900.23810.2476230.17650.18630.25490.3824240.19130.40870.19130.1913250.24760.21900.22860.3048260.21930.38600.21050.1842270.23080.23080.20190.3365280.25640.44440.14530.1538290.14850.18810.21780.4455300.28970.25230.24300.2150310.24110.35710.17860.2232320.17270.32730.22730.2636330.27030.33330.18920.2072340.23530.16670.23530.3627350.33980.20390.21360.3398360.22860.20950.30480.2571370.21150.20190.25000.3269380.22220.43590.17090.1709390.27360.23580.28300.2075400.19830.43100.19830.17242相關(guān)工作對40條DNA序列提取了數(shù)字特征之后，首先對前20條進行聚類，依據(jù)已有分類和聚類結(jié)果進行比較，檢驗聚類的準確率。然后利用該聚類結(jié)果，再對后面20條進行判別分析，預測其類別。2.1基于距離聚類的方法聚類的方法有很多種，比如基于劃分的方法，基于層次的方法，基于密度的方法，基于網(wǎng)格的方法，基于模型的方法等等。本文采用基于距離聚類的方法對數(shù)據(jù)進行聚類分析。由于樣本點數(shù)據(jù)集中的變量（即每條DNA中A、T、C、G出現(xiàn)的概率）為定距變量，因此，在該樣本點的聚類分析中，本文采用定距變量之間的距離度量。分別使用歐式距離、標準化歐式距離、馬氏距離、曼哈頓距離等距離來得到20個樣本點之間的距離。而余弦距離和相似距離適合于定比變量，因此在這里不采用。2.2定義歐氏距離 假設(shè)有兩個n維樣本和，則它們的歐氏距離為： 歐氏距離是最常用的距離度量。2.3定義馬氏距離假設(shè)共有n個指標，第i個指標共測得m個數(shù)據(jù)（要求mn）：則可以得到階的數(shù)據(jù)矩陣，每一行是一個樣本數(shù)據(jù)。階數(shù)據(jù)矩陣X的階協(xié)方差矩陣記作。兩個n維樣本和的馬氏距離如下：馬氏距離考慮了各個指標量綱的標準化，是對其他幾種距離的改進。馬氏距離不僅排除了量綱的影響，而且合理考慮了指標的相關(guān)性。2.4定義標準化歐氏距離假設(shè)有兩個n維樣本和，則它們的標準化歐氏距離為：其中，D表示n個樣本的方差矩陣，,表示第j列的方差。2.5定義曼哈頓距離 假設(shè)有兩個n維樣本和，則它們的曼哈頓距離為： 曼哈頓距離也是一種常見的距離度量。2.6定義聚類方法常用的聚類方法主要有以下幾種：最短距離法、最長距離法、中間距離法、重心法等。在本文中，在用上述四種距離得到樣本點之間的距離后，采用最短距離法對樣本點進行聚類，并創(chuàng)建聚類樹。對用不同距離創(chuàng)建好的聚類，利用matlab中cophenet函數(shù)計算聚類樹信息與原始數(shù)據(jù)的距離之間的相關(guān)性，這個值越大越好。最終選擇該值最大的距離度量作為聚類的距離度量，并編寫程序?qū)颖具M行聚類。 3項目實施 在對樣本數(shù)據(jù)集進行預處理后，編寫matlab程序?qū)颖局械那?0個DNA序列進行聚類分析。同時，還可以使用向量內(nèi)積的方法以及神經(jīng)網(wǎng)絡的方法來對這20個樣本進行分類。本文將給出三種方法的分類結(jié)果，來進行比較。3.1使用聚類的方法 在Matlab中編寫如下代碼： 對20個樣本數(shù)據(jù)分別用四種距離進行聚類，得到四種距離的聚類樹信息與原始數(shù)據(jù)的距離之間的相關(guān)性如下： t1 = 0.8632 t2 = 0.8605t3 = 0.8922t4 = 0.8358由上可知，t3最大，所以，我們采用馬哈爾距離進行聚類。采用馬哈爾距離進行聚類，得到如下結(jié)果：b = 2 2 2 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2從結(jié)果來看，第一類只有一個，與實際相差太大，故采用歐式距離進行聚類。結(jié)果如下：b = 1 1 1 2 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2可見，用歐式距離進行聚類，與原始分類契合度較好。在Matlab中再對其進行判別分析，代碼如下：得第21-40序列分類如下：class = 2 1 1 2 1 2 1 2 1 2 2 1 2 1 2