【正文】 17 18 3 .42 19 6. 60 20 5 .17 其中 b1 =aaa+ata b2=aca+aga b3=cac+ctc b4=ccc+cgc b5 =gag+gtg b6=gcg+ggg b7=tat+ttt b8=tct+tgt b9 =aac+caa+atc+cta b10=aag+gaa+atg+gta b11=aat+taa+att+tta b12=acc+cca+agc+cga b13=acg+gac+ctg+gtc b14=act+tca+agt+tga b15=cag+gac+ctt+ttc b16=cat+tac+ctt+ttc b17=ccg+gcc+cgg+ggc b18=cct+tcc+cgt+tgc b19=gat+tag+gtt+ttg b20=gct+tcg+ggt+tgg 綜合起來(lái)，形成了有 41 個(gè)變量 的基本特征集。（不考慮字符串在序列片段中的起始位置，也采用“滾動(dòng)”算法。在參考文獻(xiàn) [1]的 Figur2 中，給出了這 20 種氨基酸的編碼（見(jiàn)圖 1）。（用“滾動(dòng)”算法，如 attcg 有 at,tt,tc,cg 共 4個(gè) 2字符串） (程序與附錄一類(lèi)似 ) 表 2 AA AC AT AG TA TC TG TT CA CT CC CG GA GT GC GG 1. .90 1 2. .90 3. .90 .90 .90 .90 .90 4. .90 5. .90 6. .00 .00 .90 7. .90 .90 .90 8. 9. .90 .00 2. 70 10. 11. .91 .91 .91 .91 .00 12. .91 .91 .91 .00 .91 .00 13. 2 14. .91 .00 .91 .9 1 .91 .00 .00 .00 .00 .00 .00 .00 .91 16. . .00 .91 .00 .91 .91 .913 .91 .91 20. .91 .91 .00 .00 .91 3． 3字符串的排列出現(xiàn)的頻率 A， T， C， G 這 4 個(gè)字符組成了 64 種不同的 3 字符串。 (程序見(jiàn)附錄一 ) 表 1 A C T G A+T 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. .00 16. 17. 18. 19. 20. 2． 2 字符串的排列出現(xiàn)的頻率 A， T， C， G 這 4 個(gè)字符組成了 16 種不同的 2 字符串。由于在不用于編碼蛋白質(zhì)的序列片段中， A和 T的含量特別多些，因此我們將 A和 T是否特別豐富作為一個(gè)特征。 （一）特征的形成 分別列舉一個(gè)字符， 2個(gè)字符， 3個(gè)字符的排列在序列中出現(xiàn)的頻率，構(gòu)成基本特征集。本問(wèn)題的學(xué)習(xí)樣本數(shù)為 20個(gè)，故特征參數(shù)的個(gè)數(shù)以 6— 8 個(gè)為宜。 ，而又不必要用太多的樣本，最好使特征參數(shù)的個(gè)數(shù)降至最少。在列舉了盡可能完備的特征參數(shù)集之后，就要借助于數(shù)學(xué) 的方法，使特征參數(shù)的數(shù)目（在保證分類(lèi)良好的前提下）減到最小。 一． 特征的形成和提取 為了有效地實(shí)現(xiàn)分類(lèi)識(shí)別，首先要根據(jù)被識(shí)別的對(duì)象產(chǎn)生一組基本特征，并對(duì)基本特征進(jìn)行變換，得到最能反映分類(lèi)本質(zhì)的特征。給出的已知類(lèi)別的樣本稱(chēng)為學(xué)習(xí)樣本。 題目給出了 20 個(gè)已知為兩個(gè)類(lèi)別的人工制造的 DNA 序列，要求我們從中提取特征，構(gòu)造分類(lèi)方法，從而對(duì) 20 個(gè)未標(biāo)明類(lèi)別的人工 DNA 序列和 182 個(gè)自然 DNA 序列進(jìn)行 分類(lèi)。 3． 較長(zhǎng)的 182 個(gè)自然序列與已知類(lèi)別的 20 個(gè)樣本序列具有共同的特征。 二 .模型的合理假設(shè) 1． 各序列中 DNA 堿基三聯(lián)組（即 3 字符串）的起始位置和基因表達(dá)不影 響分類(lèi)的結(jié)果。 作為研究 DNA序列的結(jié)構(gòu)的嘗試，提出以下對(duì)序列集 合進(jìn)行分類(lèi)的問(wèn)題： 1）請(qǐng)從 20 個(gè)已知類(lèi)別的人工制造的序列（其中序列標(biāo)號(hào) 1— 10 為 A 類(lèi)， 1120 為 B類(lèi)）中提取特征，構(gòu)造分類(lèi)方法，并用這些已知類(lèi)別的序列，衡量你的方法是否足夠好。這些發(fā)現(xiàn)讓人們相信， DNA序列中存在著局部的和全局性的結(jié)構(gòu)，充分發(fā)掘序列的結(jié)構(gòu)對(duì)理解 DNA全序列是十分有意義的。又例如，在不用于編碼蛋白質(zhì)的序列片段中， A和 T的含量特別多些，于是以某些堿基特別豐富作為特征去研究 DNA序列的結(jié)構(gòu)也取得了一些結(jié)果。雖然人類(lèi)對(duì)它知之甚少，但也發(fā)現(xiàn)了其中的一些規(guī)律性和結(jié)構(gòu)。 最后通過(guò)檢驗(yàn)證明所用的分類(lèi)數(shù)學(xué)模型效率較高。然后用 Fisher 線(xiàn)性判別法進(jìn)行分類(lèi)，得出了所求 20 個(gè)人工制造序列及 182 個(gè)自然序列的分類(lèi)結(jié)果如下： 1） 20 個(gè)人工序列： 22, 23， 25， 27， 29， 34， 35， 36， 37 為 A類(lèi)，其余為 B 類(lèi)。DNA 序列分類(lèi) 摘要 本問(wèn)題是一個(gè)“有人管理分類(lèi)問(wèn)題 ”。 首先分別列舉出 20 個(gè)學(xué)習(xí)樣本序列中 1字符串、 2 字符串、 3 字符串出現(xiàn)的頻率，構(gòu)成含 41 個(gè)變量的基本特征集，接著用主成分分析法從中提取出 4 個(gè)特征。 2） 182 個(gè)自然序列： 1， 4， 8， 10， 27， 29， 32， 41， 43， 48， 54， 63， 70， 72， 75， 76，81， 86， 90， 92， 102， 110， 116， 119， 126， 131， 144， 150， 157， 159， 160， 161，162， 163， 164， 165， 166， 169， 170， 182 為 B 類(lèi)，其余為 A 類(lèi)。 一 . 問(wèn) 題 重 述 人類(lèi)基因組計(jì)劃中 DNA全序列草圖是由 4個(gè)字符 A， T， C， G按一定順序排成的長(zhǎng)約 30億的序列，其中沒(méi)有“斷句”也沒(méi)有標(biāo)點(diǎn)符號(hào)。例如，在全序列中有一些是用于編碼蛋白質(zhì)的序列片段，即由這 4個(gè)字符組成的 64種不同的 3字符串，其中大多數(shù)用于編碼構(gòu)成蛋白質(zhì)的 20種氨基酸。此外，利用統(tǒng)計(jì)的方法還發(fā)現(xiàn)序列的某些片段之間具有相關(guān)性，等等。目前在這項(xiàng)研究中最普通的思想是省略序列的某些細(xì)節(jié)，突出特征，然后將其表示成適當(dāng)?shù)臄?shù)學(xué)對(duì)象。然后用你認(rèn)為滿(mǎn)意的方法，對(duì)另外 20個(gè)未標(biāo)明類(lèi)別的人工序列（標(biāo)號(hào) 21— 40）進(jìn)行分類(lèi)，把結(jié)果用序號(hào)（按從小到大的順序）標(biāo)明它們的類(lèi)別（無(wú)法分類(lèi)的不寫(xiě)入） 2） 同樣方法對(duì) 182個(gè)自然 DNA序列 (它們都較長(zhǎng) )進(jìn)行分類(lèi)，像 1）一樣地給出分類(lèi)結(jié)果。 2． 64 種 3 字符串壓縮為 20 組后不影響分類(lèi)的結(jié)果。 三 .模型建立與求解 研究 DNA 序列具有什么結(jié)構(gòu)，其 A， T， C， G4個(gè)堿基排成的看似隨機(jī)的序列中隱藏著什么規(guī)律，是解讀人類(lèi)基因組計(jì)劃中 DNA 全序列草圖的基礎(chǔ)，也是生物信息學(xué)（ Bioinformaties）最重要的課題之一。這是模式識(shí)別中的“有人管理分類(lèi)”問(wèn)題，即事先規(guī)定了分類(lèi)的標(biāo)準(zhǔn)和種類(lèi)的數(shù)目，通過(guò)大批已知樣本的信息處理找出規(guī)律，再用計(jì)算機(jī)預(yù)報(bào)未知。對(duì)于此類(lèi)問(wèn)題，我們通過(guò)建立分類(lèi)數(shù)學(xué)模型（這包括形成和提取特征以及制定分類(lèi)決策）、考查分類(lèi)模型的效率、預(yù)報(bào)未知這幾個(gè)步驟來(lái)進(jìn)行。這就是特征形成和提取的過(guò)程。這是因?yàn)椋?，而且會(huì)帶來(lái)噪音，干擾分類(lèi)和數(shù)學(xué)模型的建立。模式識(shí)別計(jì)算一般要求樣本數(shù)至少為變量數(shù)的3 倍，否則結(jié)果不夠可靠。 我們通過(guò)研究 4個(gè)字符 A,T,C,G 在 DNA 序列中的排列、組合特性，主要是研究字符和字符串的排列在序列中出現(xiàn)的頻率，從中提取 DNA 序列的結(jié)構(gòu) 特征參數(shù)。 i. 1 個(gè)字符的出現(xiàn)頻率 表 1列出了 20 個(gè)樣本中 A， T， C， G這 4個(gè)字符出現(xiàn)的頻率。在表一中，列出了 A 和 T 出現(xiàn)的頻率之和。表 2 列出了 20 個(gè)樣本中各 2字符串出現(xiàn)的頻率。這 64 種 3 字符串構(gòu)成生物蛋白質(zhì)的 20種氨基酸。因此，在計(jì)算 3字符串的出現(xiàn)頻率時(shí)，我們根據(jù)圖 1將代表同一種氨基酸的 3 字符串合成一類(lèi)，只統(tǒng)計(jì) 20類(lèi) 3字符串的出現(xiàn)頻率。如 acgtcc 中就有 acg,cgt,gtc,tcc 共 4 個(gè) 3 字符串）見(jiàn)表 3。 (二 )特征的提取 上述基本特征集中有 41 個(gè)變量，即樣本處于一個(gè)高維空間中。我們用主成分分析法進(jìn)行特征的提取，其步驟是： 1． 求 X的均方差矩陣 V 的特征根，記為： λ 1≥λ 2≥??≥λ k＞ 0 λ k+1=?? =λ P=0 2． 求λ 1,λ 2??λ K 對(duì)應(yīng)的標(biāo)準(zhǔn)正交的特征向量 r1， r2?? rK 得到第 i 個(gè)主成分為 yi=riX, i=1,2?? K 3． 求第 i個(gè)主成分的貢獻(xiàn)率 ui=λ i/ ??ki 1λ j, i=1,2?? K及前 m 個(gè)主成分的累計(jì)貢獻(xiàn)率 vm=??mi1ui. 4． 求得 q，使得 Vq≥ V0(V0一般在 到 1 之間 )，則取 W=(r1,r2,?? ,rq) Y=XW 第 3 步所求的貢獻(xiàn)率，代表主成分表達(dá) X 的能力，貢獻(xiàn)率越大，對(duì)應(yīng)的主成分表達(dá) X的能力越強(qiáng)。就可以用低維特征 Y=（ y1,y2, ?? yq）來(lái)反映高維特征（ x1,x