北郵生物信息大作業(yè)

1、工疾病自動(dòng)診斷問題1、題目分析根據(jù)題目要求，我們需要設(shè)計(jì)一套計(jì)算機(jī)自動(dòng)篩選方案，目的是通過患者檢測得到的20項(xiàng)指標(biāo)，分別判斷患者的腹瀉類型為病毒型腹瀉還是細(xì)菌型腹瀉。目前，我們已有的訓(xùn)練集是經(jīng)過專家篩選后的100例疑似患者的20項(xiàng)指標(biāo)。其中，20位為病毒型腹瀉，80位為細(xì)菌型腹瀉，即80位為細(xì)菌型腹瀉。因此，我認(rèn)為該問題為一個(gè)監(jiān)督下的模式分類問題，兩個(gè)分類指標(biāo)為腹瀉類型為病毒型”、腹瀉類型為細(xì)菌型”，觀測向量為得到的疑似患者的20項(xiàng)指標(biāo)：2、關(guān)鍵算法及分析信息獲取與預(yù)處理部分，在之前的檢查中已經(jīng)較為詳細(xì)的給出，這一步不再設(shè)計(jì)；特征選擇與提取部分，我計(jì)劃使用主成分分析方法，通過對20項(xiàng)標(biāo)準(zhǔn)進(jìn)行線

2、性組合，可以得到更能夠體現(xiàn)類間信息的新的一組觀測向量；分類器設(shè)計(jì)采用Fisher線性判別分析+最小錯(cuò)誤率貝葉斯決策的方法。主成分分析主成分分析的思想是從一組特征中計(jì)算出一組重要性按從大到小順序排列的的新特征，它們是原有特征的線性組合，并且之間是互不相關(guān)的。設(shè)為x的協(xié)方差矩陣，求解出矩陣的各個(gè)特征值與特征向量，則特征值最大的特征向量，為數(shù)據(jù)集的最佳投影方向。由此方向投影，可獲得最大的投影數(shù)據(jù)的方差。按照這個(gè)思路依次找到次大的，第三的特征值對應(yīng)的特征向量，它們就是次優(yōu)的，第三優(yōu)的投影方向。我們可以只提取重要性占前k%個(gè)主成分：k.h.我們把原始數(shù)據(jù)集按這些方向投影，得到的就是降維后的觀測向量。選擇

3、較少的主成分來表示數(shù)據(jù)，不但可以用作特征的降維，還可以用來消除特征中的噪聲。Fisher線性判別分析Fisher線性判別分析的基本思想是：將所有的樣本投影到一個(gè)方向上，然后在這個(gè)一維空間確定一個(gè)閾值。選擇最優(yōu)的投影方向應(yīng)該使得各個(gè)樣本點(diǎn)的類內(nèi)方差最小，類間方差最大。我們定義類內(nèi)離散度矩陣，類間離散度矩陣，投影向量，準(zhǔn)則的目標(biāo)函數(shù)為：加皿切=£=；7這是一個(gè)約束條件下的極值問題，我們可以利用拉格朗日乘子法求解。拉格朗日函數(shù)：L（卬/）=wTSbw-4科治w-c）上式在極值點(diǎn)處，應(yīng)該滿足對w的偏導(dǎo)數(shù)等于零。可以解得：W*=仁"工一明）式中，為Fisher線性判別準(zhǔn)則下的最優(yōu)投影

4、方向。為兩類的類均值向量。由于Fisher線性判別分析不對樣本的分布做任何假設(shè)，當(dāng)樣本維數(shù)較高樣本數(shù)也較多的時(shí)候，投影到一維空間后樣本接近正態(tài)分布。這時(shí)可以在一維空間中使用正態(tài)分布擬合樣本，再使用上面提到的最小錯(cuò)誤率貝葉斯決策，往往會有很好的效果。最小錯(cuò)誤率貝葉斯決策最小錯(cuò)誤率貝葉斯決策的決策規(guī)則為:如果P（他分，則x屬于w1,否則x屬于w2o其中，后驗(yàn)概率可以使用貝葉斯公式求得:口rq/SI/沖3）如'POT一年.一網(wǎng)）產(chǎn)（州）但是，將一個(gè)疑似患者判為病毒攜帶者和排除其患病可能性，其代價(jià)（損失）是不一樣的。對此，采用最小風(fēng)險(xiǎn)的貝葉斯決策。這種決策方法中，決策表是需要人為確定的，需要認(rèn)

5、真分析研究問題的內(nèi)在特點(diǎn)和分類目的，與疾病防控領(lǐng)域的專家共同決策，設(shè)計(jì)出適當(dāng)?shù)臎Q策表。具體的決策步驟：（1） 利用貝葉斯公式計(jì)算后驗(yàn)概率（2） 利用決策表，計(jì)算條件風(fēng)險(xiǎn)：C=24明叫P9W）;-1（3） 決策：在各種決策中選擇風(fēng)險(xiǎn)最小的決策，即病毒變異與否的判斷1、 問題分析針對病毒變異與否的判斷問題，我認(rèn)為應(yīng)該采樣合適數(shù)目的諾拉病毒DNA序列(可以是關(guān)鍵部分的基因)，然后使用多序列比對的方案，將多條序列對齊，就可以方便的定位出序列中堿基對的差異位置，從而評估病毒是否發(fā)生了變異。由于整條序列做多序列比對，可能時(shí)間復(fù)雜度較大，最后得到的變異位點(diǎn)信息也和我們想要的相差較大。我們可以選擇和病毒的致病

6、能力密切相關(guān)的幾個(gè)基因，作為多序列分析的原材料。2、 求解算法即算法描述求解流程獲取病毒關(guān)鍵基因IJ多序列比對IJ遍鱉多序列比對下面簡要介紹多序列比對的實(shí)現(xiàn)方法。由于病毒的DNA序列較長，我們采取星形比對的方案。星形比對的基本思想是：在給定的若干序列中，選擇一個(gè)核心序列，通過該序列與其它序列的兩兩比對，形成所有序列的多重比對，從而使得該多重比對在核心序列和任何一個(gè)其它序列方向的投影是最優(yōu)的兩兩比對。下面給出星形比對的基本過程：1 .選擇核心序列2 .計(jì)算與核心序列的兩兩比對3 .逐對聚合兩兩比對的結(jié)果，獲得多重比對選定一個(gè)核心序列，把多重比對轉(zhuǎn)化為k個(gè)兩兩比對聚集過程。從某一個(gè)兩兩比對開始，比

7、如sc和si,然后逐步加上其他的兩兩比對。在這個(gè)過程中，逐步增加sc中的空位字符，以適應(yīng)其他的比對，但不刪除sc中已經(jīng)存在的空位字符。選擇核心序列的方法為：嘗試將每一個(gè)序列分別作為核心序列，進(jìn)行星形多重序列比對，取比對結(jié)果最好的一個(gè)。在上面提到的星形比對中，最基本的核心是兩兩比對，我們使用的兩兩比對的方法為：全局最優(yōu)序列比對的動(dòng)態(tài)規(guī)劃求解算法。給出求解過程：初始化DP輔助矩陣根據(jù)狀態(tài)轉(zhuǎn)移方程遞歸計(jì)算DP輔助矩陣A確定最優(yōu)路徑，即對應(yīng)于最優(yōu)比對矩陣更新策略:致力-1)+漢-閨的)MlD三內(nèi)。一1，j-D+百($團(tuán)淵口”人工-1J)+7串口D)尋找變異位點(diǎn)需要的序列經(jīng)過了比對，已經(jīng)對齊。我們可以定

8、義一個(gè)閾值，當(dāng)堿基序列中連續(xù)出現(xiàn)的變異堿基個(gè)數(shù)超過了這個(gè)閾值后，我們即可認(rèn)定這個(gè)序列是變異序列，與原序列的差異較大。閾值的選擇要與疾病防控領(lǐng)域的專家一起協(xié)定，這樣才能夠準(zhǔn)確的發(fā)現(xiàn)基因出現(xiàn)的變異情況。四:(1)若觀測序列為CCGC,試計(jì)算該觀測序列在所給定的HMM下的生成概率解：利用前向算法模型：隱狀態(tài)集合S=S1,S2,S3明字符集合V=C,G隱狀態(tài)轉(zhuǎn)移概率A=.0.30,20.3.040.402I0.10.203明字符生成概率矩陣B=10.40.6.0.30.7)0.60.4初始狀態(tài)概率向量兀=0.2,0.3,0.5若觀測序列為CCGC,O=C,C,G,C:1 .初始化：根據(jù)公式：a(l,i

9、)=tt購6)求得：a(1,1)=Tt(1)*b(1,o1)=0.08a(1,2)=兀(2)*b(2,o1)=0.09a(1,3)=兀(3)*b(3,o1)=0.3根據(jù)公式:£記土.加2方伉a+i)求得：a(2,1)=a(1,1)*a(1,1)+a(1,2)*a(2,1)+a(1,3)*a(3,1)*b(1,o2)=0.0252同理可得：a(2,2)=0.0336a(2,3)=0.0792a(3,1)=0.011304a(3,2)=0.024024a(3,2)=0.015216a(4,1)=0.00293a(4,2)=0.00447a(4,3)=0.007663.終結(jié)：根據(jù)公式:尸。

10、=!>()t=i求得P(O入)=a(4,1)*p(S1,)+a(4,2)*p(S2,)+a(4,3)*p(S3,)=0.00499(2)若觀測序列為CCGC,試計(jì)算生成該觀測序列的最佳路徑。解：利用Viterbi算法模型：1 .初始化：根據(jù)公式：儲(')=穴i刎。1)(2)=兀(3)=兀(1)(2)(3)*b1(o1)=0.08*b2(o1)=0.09*b3(o1)=0.32 .遞歸：根據(jù)公式:瓦(j)=maxbj(0f)l<i<N求得：82(1)=max81(1)*a11,S1(2)*a21,81(3)*a31*b1(O2)=0.03*0.4=0.012同理可得：82(2)=0.01882(3)=0.05483(1)=0.00324S3(2)=0.00756S3(3)=0.0064884(1)=0.0003984(2)=0.0009184(3)=0.001173.終結(jié)：根據(jù)公式:max!<?<Ar歷(訓(xùn)求得：P*=max84(1),84，84(3)=0.001174.回溯：根據(jù)公式:argmax1<?<N求得：q4*=3再由公式：仇