DNA序列分類(2000年A題)2000年6月，人類基因組計(jì)劃中DNA全序列草圖完成，預(yù)計(jì)2001年可以完成精確的全序列圖，此后人類將擁有一本記錄著自身生老病死及遺傳進(jìn)化的全部信息的“天書”，這本大自然寫成的“天書”是由4個(gè)字符A,T,C,G按一定順序排列成的長約30億的序列，其中沒有“斷句”，也沒有標(biāo)點(diǎn)符號(hào)，除了這4種字符表示4種堿基因以外，人們對(duì)它包含的“內(nèi)容”知之甚少，難以讀懂。破譯這部世界上最巨量信息的“天書”時(shí)21世紀(jì)最重要的任務(wù)之一。在這個(gè)目標(biāo)中，研究DNA序列具有什么結(jié)構(gòu)，由這4個(gè)排成的看似隨機(jī)的序列中隱藏著什么規(guī)律，又是讀懂這部天書的基礎(chǔ)，是生物信息最重要的課題之一。雖然人類對(duì)這部“天書”知之甚少，但也發(fā)現(xiàn)了DNA序列中的一些規(guī)律和結(jié)構(gòu)。例如，在全序列中有一些是用于編碼蛋白質(zhì)的序列片斷，即由這4個(gè)字符組成64種不同的3字符串，其中大多數(shù)用于編碼構(gòu)成蛋白質(zhì)的24種氨基酸。又例如，在不用于編碼蛋白質(zhì)的序列片斷中A和T的含量特別多些，于是以某些堿基特別豐富作為特征去研究DNA系列的結(jié)構(gòu)，也取得一些結(jié)果。此外，利用統(tǒng)計(jì)的方法還發(fā)現(xiàn)序列的某些片斷之間具有相關(guān)性，等。這些發(fā)現(xiàn)讓人們相信，DNA序列中存在著局部或全局的結(jié)構(gòu)，充分發(fā)掘序列的結(jié)構(gòu)對(duì)理解DNA全序列是非常有意義的。目前在這項(xiàng)研究中，最普遍的思想是省略序列的某些細(xì)節(jié)，突出特征，然后將其表示成適當(dāng)?shù)臄?shù)學(xué)對(duì)象，這種被稱為粗?；湍Ｐ突姆椒ㄍ兄谘芯恳?guī)律性和結(jié)構(gòu)。作為研究DNA序列結(jié)構(gòu)的嘗試，提出下列對(duì)序列集合進(jìn)行分類的問題：1)下面有20個(gè)已知類別人工制造的序列(略)，其中1～10為A類，11～20為B類，請(qǐng)從中提取特征，構(gòu)造分類方法，并用這些已知類別的序列，衡量你的方法是否足夠好。然后用你認(rèn)為滿意的方法，對(duì)另外20個(gè)未表明類別的人工序列(序號(hào)21～40)進(jìn)行分類，把結(jié)果用序號(hào)(按從大到小順序)表明他們的類別(無法分類的不寫入)；提示：衡量分類方法的優(yōu)劣標(biāo)準(zhǔn)是分類的準(zhǔn)確率，構(gòu)造分類方法有許多途徑，例如提取序列的某些特征，給出它們的數(shù)學(xué)表示：幾何空間或向量空間的元素等，然后再選擇或構(gòu)造適合這種數(shù)學(xué)表示的分類方法；又例如構(gòu)造概率統(tǒng)計(jì)模型，然后用統(tǒng)計(jì)方法分類等。DNA序列的分類模型湯詩杰周亮王曉玲中國科技大學(xué)1.問題的提出(略)2.問題的分析為表述嚴(yán)格方便，先用數(shù)學(xué)方法重述問題。已知字母序列S1，S2，…，S40，Si＝x1x2…xni，其中xj{a,t,c,g}；A、B為兩個(gè)字符序列集合，滿足AB＝，且當(dāng)1i10時(shí)，SiA，當(dāng)11i20時(shí)，SiB。現(xiàn)要求考慮當(dāng)21i40時(shí)，Si屬于A、B那個(gè)集合。問題關(guān)鍵是從已知20個(gè)序列中提取分類特征。3.分類標(biāo)準(zhǔn)及評(píng)價(jià)所提取標(biāo)準(zhǔn)應(yīng)滿足以下兩條：(1).必須可標(biāo)志A組和B組。(2).必須有一定的實(shí)際意義。限制條件目標(biāo)函數(shù)4.模型建立與分析嘗試綜合使用3種設(shè)計(jì)思想不同方法處理。第1種：從字母出現(xiàn)的頻率出發(fā)。第2種：從字母出現(xiàn)的周期性出發(fā)。第3種：從序列所帶的某些方面信息量出發(fā)。最后從這3方面出發(fā)，得一綜合分類方法。方法1基于字母出現(xiàn)頻率不同段DNA中，每個(gè)堿基因出現(xiàn)頻率不同，從生物理論知，編碼蛋白質(zhì)的DNA中G、C含量偏高，非編碼蛋白質(zhì)的DNA中A、T含量偏。故A、G、T、C出現(xiàn)頻率有很多信息。表1，表2(略)分別給出A、B組字母頻率。由統(tǒng)計(jì)數(shù)字知：A組C基因含量高，B組T基因含量高。為定量化分析，引入四維向量(PA,PG,PT,PC),其中PA,PG,PT,PC,分別表示A，G，T，C的頻率。這樣我們得到了兩組向量Ai、Bi；i=1,2,…，10；然后將未知序列21～40作為一組新向量，要將它歸入A組或B組。將向量單位化，分別記為Ai、Bi、C；再計(jì)計(jì)算內(nèi)積：即：內(nèi)積＝(PA,PG,PT,PC)A?(PA,PG,PT,PC)未知|A|?|未知|認(rèn)為內(nèi)積小的兩個(gè)序列相關(guān)性小，內(nèi)積大的設(shè)某單個(gè)字母a在序列中第t1,t2,…,tk+1個(gè)位置出現(xiàn)，我們來找這些位置的關(guān)系。序列是大段DNA中的一個(gè)片斷，片斷起始點(diǎn)不同，會(huì)導(dǎo)致ti不同，考慮ti的分布及絕對(duì)值意義不大。為抵消的線性位移，考慮：si＝ti+1－ti；i=1,2,…,ks1，

s2，…，

sn的大小的信息是a的“稠密度”，和頻率有關(guān)，前面已經(jīng)處理過。下面考慮它的波動(dòng)幅度，幅度越小說明si的值越穩(wěn)定，即A出現(xiàn)的周期性越大。表征波動(dòng)幅度的兩是中心矩?，F(xiàn)求二階中心矩：同理可求Varg、Vart、Varc.由計(jì)算知Varg、Vart

對(duì)A、B組的區(qū)分率很高。為強(qiáng)調(diào)這種特性的顯著性，用F2＝Varg/Vart作這種方法的目標(biāo)函數(shù)。

圖1分別以Varg、Vart為橫坐標(biāo)、縱坐標(biāo)劃點(diǎn)，可看出點(diǎn)與原點(diǎn)的連線的斜率在A組和B組中有顯著的差別。從而很好地區(qū)別了A、B組。較好地彌補(bǔ)了方法1之缺點(diǎn)。方法2討論方法3基于序列熵值把DNA序列看成一個(gè)信息流，考慮其單位序列所含信息量(即熵)來分類。通過觀察A、B組特點(diǎn)，認(rèn)為重復(fù)越多信息量越少。設(shè)序列L＝(a1,a2,a3,…，an)；前m個(gè)字符所含信息量為fm()，記：gm()=fm()－fm-1()，加上第m個(gè)字符所增加的信息量fn()＝gi()，i=1n整個(gè)序列所含信息量F3()＝fn()/||；

單位長度序列所含信息量目標(biāo)函數(shù)關(guān)鍵尋找合適的gm()。gm()應(yīng)滿足以下條件：1).gm()>0因任加一字符都增加一定信息量。2).第m個(gè)字符與前面重復(fù)的越多，gm()=越小。3).第m個(gè)字符與靠得越近的重復(fù)的越多，gm()=越小。4).f0()=0對(duì)此，可構(gòu)造函數(shù)：gm()=bb+t11+t22+…+tpp.其中b是為防止分母為零而設(shè)的一個(gè)小正數(shù)；i=atit；i=1mit=1以第m-t個(gè)字符結(jié)尾的i字符串與第t個(gè)字符串結(jié)尾的第i字符串完全相同0否則a<1，體現(xiàn)越近位置重復(fù)，字符串信息量越少。t為兩字符串之間距離i為字符串長度長度不同的字符串重復(fù)對(duì)信息量影響不同，故必須在i前加上一個(gè)權(quán)ti.由概率統(tǒng)計(jì)知識(shí)知此影響呈指數(shù)上升，故可選適當(dāng)常數(shù)c>1，使得ti=ci-1，gm()定量給出了長度與信息之間的關(guān)系。字符串長度太大的重復(fù)很少見；好比較，先將它們標(biāo)準(zhǔn)化。將它們看成是L空間上的隨機(jī)變量，A、B為L的子集。令：i＝Fi();i－E(i)Var(i)gi＝根據(jù)現(xiàn)有樣本點(diǎn)：Fi(1),Fi(2),…,Fi(20);由矩估計(jì)方法得：代入(1)得gi?！?1)現(xiàn)尋求gi(A),gi(B)的分界點(diǎn)xi，其中：gi(A)={gi(a)|aA}；gi(B)={gi(b)|bB}；以g1為例，不能用一個(gè)分界點(diǎn)把A、B分開。根據(jù)極大似然估計(jì)的思想，分界點(diǎn)應(yīng)把盡可能多的點(diǎn)分開，即x1(－0.276758，0.482296)；因?yàn)間1分布未知，只能設(shè)其為均勻分布，則A、B最佳分界點(diǎn)x1為：恰屬于(－0.276758，0.482296)；類似可得：x2＝x3＝0為g2,g3

對(duì)應(yīng)的最佳分界點(diǎn)；E[gi(A)]+E[gi(B)]20矩估計(jì)x1=令：F＝a1g1＋a2g2＋a3g3；則其分界點(diǎn)：x=a10＋a20＋a30=0選取適當(dāng)?shù)腶1，a2，a3