1、第 31 卷第 1 期 2001 年 1 月 數(shù)學(xué)的實(shí)踐與認(rèn)識(shí) M A TH EMA T ICS IN PRA CT ICE AND TH EO R YV o l131 N o 11Jan. 2001emp loy the BP ( back p ropagat io n ) algo rithm to t rain NN by use of the N eural N etw o rk Too lbox in M A TLAB softw are package. In th is paper, tw o th ree2sto ry NN are created to input the e

2、xtracted DNA character vecto rs as samp les in to them. A fter the t rain ing, characters are extracted from the 20 unclassified artificial sequence samp les and 182 natural sequence samp les to fo rm the character vecto rs as input of the tw o NN fo r clustering. T he results show s: the clustering

3、 m ethod p resented in th is paper can classify the DNA sequences in quite h igh accuracyand p recisio n. It is quite feasible to app ly the artificial neural netw o rk to DNA sequence clustering.D NA分類模型楊 健,王 馳,楊 勇指導(dǎo)老師:王 鳴 (北京大學(xué), 北京 100871)編者按:本文將DNA 序列的堿基的組合看作“文章”的關(guān)鍵詞, 用逐步優(yōu)選法對(duì)關(guān)鍵詞進(jìn)行優(yōu)選并用分層分類的方法進(jìn)行分類.

4、 從理論上說, 這一方法可以提取較好的特征, 而且分類也較精細(xì). 這一模型有一定 創(chuàng)造性, 分析問題比較精細(xì)而貼近實(shí)際, 思路清楚, 敘述通順簡(jiǎn)練.摘要:本模型充分利用了所給數(shù)據(jù)的特點(diǎn), 運(yùn)用統(tǒng)計(jì)、最優(yōu)化等數(shù)學(xué)方法, 從已知樣本序列中提煉出能較好代表兩類特征的關(guān)鍵字符串, 據(jù)此提出量化的分類標(biāo)準(zhǔn), 能較好的對(duì)任給DNA 序列進(jìn)行分類. 首先, 從已知樣本序列中用廣度優(yōu)先法選出所有重復(fù)出現(xiàn)的字符串, 并計(jì)算其標(biāo)準(zhǔn)化頻率及分散度. 然后, 利用樣本數(shù)據(jù)結(jié)合最小二乘法確定兩類字符串各自的優(yōu)先級(jí)函數(shù), 并且逐步優(yōu)化其參數(shù)使之達(dá)到穩(wěn)定, 提高了可信度. 最后, 根據(jù)優(yōu)先級(jí)函數(shù)找出關(guān)鍵詞, 然后確定權(quán)數(shù),

5、 用層次分析法對(duì)未知樣本進(jìn)行分類, 并定出顯著水平, 從而得到了一個(gè)比較通用的分類方法. 經(jīng)過檢驗(yàn), 此方法對(duì) 2140 號(hào)待測(cè)樣本進(jìn)行了很好的分類, 對(duì)后面的182 個(gè)DNA 序列進(jìn)行同樣的操作, 也有較好的效果.1 問題的重述(略)2 模型假設(shè)(1) 假定待分類樣本 2140 中既不屬于A 類也不屬于B 類的樣本百分比不超過 5%.(2) 假設(shè)keyw o rd 的重要性與 t 和 s 有確定的關(guān)系, 且只與 t 和 s 有關(guān)( t, s 定義見下).(3) 假設(shè)不代表A 、B 類特征的字符串在DNA 序列中是均勻分布的.3 模型的分析從所給的DNA 序列觀察發(fā)現(xiàn), 很多字符串重復(fù)出現(xiàn)的頻

6、率很高, 而且有些字符串在A類和B 類中出現(xiàn)的次數(shù)有很明顯的差距, 這暗示把某些字符串作為A , B 兩類的一個(gè)分類標(biāo)準(zhǔn). 所以應(yīng)對(duì)A 、B 兩類已知樣本做統(tǒng)計(jì)分析, 找出其中可能代表該類特征的字符串. 因?yàn)槊總€(gè)字符串重要性可能不一樣, 所以對(duì)這些字串的重要性排序, 選出最能代表該類特征的一部分字串. 然后用這些字串作為標(biāo)準(zhǔn)判斷驗(yàn)證A , B 兩類, 看所選的標(biāo)準(zhǔn)的準(zhǔn)確性, 最后用于任何一個(gè)DNA 序列的分類.32數(shù) 學(xué) 的 實(shí) 踐 與 認(rèn) 識(shí) 31 卷 4 定義與符號(hào)說明A 類樣本: 編號(hào)為 110 的DNA 序列.B 類樣本: 編號(hào)為 1120 的DNA 序列.詞(w o rd) : 由a

7、, c, t, g 組成的在樣本中重復(fù)至少兩次的字符串.關(guān)鍵詞(keyw o rd) : 能代表A 類或B 類的特征由a , c, t, g 組成的詞. 分散度( s ) : 指某一類中包含某個(gè)w o rd 的DNA 序列的個(gè)數(shù).出現(xiàn)次數(shù)( l ) : 某一字符串在DNA 序列中的出現(xiàn)次數(shù)序列長(zhǎng)度( n ) : DNA 序列的長(zhǎng)度 字符串長(zhǎng)( m ) : 字符串的長(zhǎng)度 4m標(biāo)準(zhǔn)化頻率( t ) : t = ln m 標(biāo)準(zhǔn)化了的詞的出現(xiàn)次數(shù) 優(yōu)先級(jí)函數(shù)( f ) : 衡量詞重要性的指標(biāo), 是 s 和 t 的函數(shù). 權(quán)值(D ) : 衡量DNA 序列類別特征的量化指標(biāo) 5 模型的建立與求解(1)

8、Keyw o rds 的選擇 選擇keyw o rd 是所有工作的基礎(chǔ), 能否對(duì)基因序列進(jìn)行有效的分類在很大程度上依賴keyw o rd 選擇的好壞, 所以我們的原則是所選的keyw o rd 一定要能代表A 類和B 類基因序列的盡量全面的特征, 并且所選的keyw o rd 應(yīng)對(duì)兩類基因有好的區(qū)分度, 以利于分類.第一步: 選擇word (廣度優(yōu)先法). 以A 類樣本為例: 計(jì)算字長(zhǎng)為 1 的w o rd 的出現(xiàn)次數(shù), 并置 i= 1; 分別以字長(zhǎng)為 i 的各結(jié)點(diǎn)為根結(jié)點(diǎn). 對(duì)每一個(gè)根結(jié)點(diǎn), 若其出現(xiàn)次數(shù)大于 1, 在其后分別加入a、c、g 、t, 組成長(zhǎng)度為 i + 1的新字符串, 計(jì)算其

9、出現(xiàn)次數(shù)及出現(xiàn)位置.例如: i= 1 時(shí), 字長(zhǎng)為 1 的w o rda、c、 g、t可做根結(jié)點(diǎn). 對(duì)于g , 在其后分別加 入a 、c、g 、t , 生成ga 、gc、gg 、 g t四個(gè)長(zhǎng)度為 2 的新串. 若中找到了新詞, 則置 i= i+ 1, 轉(zhuǎn)到 , 否則結(jié)束. 程序流程圖如圖 1:第二步: 選擇keywords (逐步優(yōu)選法)現(xiàn)在我們已經(jīng)有了 A 、B 類的所有的 w o rd, 下 面 要 在 這 些 w o rd 中 選 出 好 的 keywo rd.圖 1選擇典型代表.我們認(rèn)為, 對(duì)于每一個(gè)w o rd, 標(biāo)準(zhǔn)化頻率 t 和分散度 s 越大, 它越具有代表性, 所以我們先在

10、所有的w o rd 中人工粗選出一些明顯具有類別特征的w o rd 作為初選關(guān)鍵詞, 選擇時(shí),331 期 楊 健等: DNA 分類模型 不妨多選出一些, 盡量不要丟失信息, 也就是囫圇吞棗, 我們?cè)诰唧w操作時(shí), 對(duì)A 、B 類各選出了 30 個(gè)左右.進(jìn)行初步優(yōu)選:我們假定keyw o rd 的重要性只與 t 和 s 有關(guān), 而且這種關(guān)系在一定的范圍內(nèi)有確定的解析表達(dá)式, 我們想找出這個(gè)函數(shù)關(guān)系 f .顯然, f 是 s 的增函數(shù), 也是 t 的增函數(shù), 所以假設(shè) f 具有形式:f (s, t) = st(1)其中和 分別稱為 s 和 t 的影響力因子對(duì)于某個(gè)w o rd, 由(1) 式求出的值

11、稱為它的f 值接下來我們用上面選出的 30 多個(gè)w o rd 結(jié)合最小二乘法來確定 和 . 以A 類為例,設(shè)A 類中粗選的w o rd 分別有值:t1 , t2, t39 和 s1 , s2 , s39為了運(yùn)用最小二乘法對(duì)(1) 式取對(duì)數(shù)有:logf = logs + lo g t(2)我們期望好的keyw o rd 的 f 值都較大, 而且穩(wěn)定在某個(gè)下限之上, 所以把A 類的 39 個(gè)w o rd 的 f 的期望值定為 5010 (這個(gè)值只具有相對(duì)意義, 具體定為多少對(duì)模型的優(yōu)劣沒有影響). 然后對(duì)這 39 個(gè)樣本運(yùn)用最小二乘法, 即: 求 和 , 使得 39達(dá)到最小 g (, ) =(lo

12、 gsi + log ti -log50) 2(3)i= 1利用M A TLAB 提供的優(yōu)化工具箱處理此最小二乘問題, 得到 A = 014625A = 018057同樣處理B 類的 26 個(gè)w o rd 同樣處理得到:B = 0. 2217B = 1. 3060這樣, 我們就得到了A 類B 類的優(yōu)先級(jí)函數(shù)的表達(dá)式:f A = sA tA(4)f B = sB tB(5)這個(gè)函數(shù)只是一個(gè)初步的函數(shù), 在下面的步驟中還會(huì)進(jìn)一步優(yōu)化函數(shù)的參數(shù)值.將A 類B 類的所有w o rd 的 s 和 t 值分別代入(4) (5) 式, 得到每個(gè)w o rd 對(duì)應(yīng)的 f 值, 即優(yōu)先級(jí), 將每類的w o rd

13、 按優(yōu)先級(jí)大小排序, 選擇優(yōu)先級(jí)最高的 16 個(gè)w o rd 作為每類初步優(yōu)化后的keyw o rds 對(duì)上面得到的keyw o rds 重復(fù)第步的方法, 用最小二乘法求出每類新的和 值, 這樣就得到了進(jìn)一步優(yōu)化之后的優(yōu)先級(jí)函數(shù), 用此函數(shù)算出每個(gè)w o rd 新的優(yōu)先級(jí), 再選擇優(yōu)先級(jí)最高的 16 個(gè)作為進(jìn)一步優(yōu)化之后的keyw o rd.重復(fù)幾遍第步, 直到和 的值達(dá)到穩(wěn)定. 此時(shí)的結(jié)果是:A = 0. 4585A = 0. 8851B = 0. 2347B = 1. 3769至此, 選擇keyw o rd 的工作結(jié)束, 而且得到的keyw o rd 是按優(yōu)先級(jí)大小排序的.由上面的工作步驟

14、可以看出, 這 32 個(gè)keyw o rd 基本上代表了A 類B 類的特征, 而且A 34數(shù) 學(xué) 的 實(shí) 踐 與 認(rèn) 識(shí) 31 卷 類B 類的keyw o rd 基本沒有重復(fù), 有很好的區(qū)分度. Keyw o rds 見表 1.圖 2 為每個(gè)w o rd 的優(yōu)先級(jí)對(duì)分散度、標(biāo)準(zhǔn)化頻率的圖象. 其中keyw o rd 用圈標(biāo)出. 從圖中看出, 用逐步優(yōu)選法求出的keyw o rd 確實(shí)分別代表了A 、B 類的重要特征. 表 1 選擇的關(guān)鍵字A 組 B 組 關(guān)鍵字 出現(xiàn)次數(shù) 分散度 關(guān)鍵字 出現(xiàn)次數(shù) 分散度 agga329taa5010ga10910t t ta5210ggcgg287aa1191

15、0ggc699tat14810ggaggc118at13110aa1158t taa3410agg654tatt3610ggaa3410ta6210ggcgga1710att8010a31810a32510cgg8010t tat4210cgga4210attt4410ggagg269t ta10510gga9310t t t t t t t5810gg19810t5527g42510t t t19310圖 2圖 3 為逐步優(yōu)選法的流程圖. 需要注意的是, w o rd 的 f 值不僅是提取keyw o rd 的標(biāo)準(zhǔn),而且也反映了每個(gè)keyw o rd 的重要程度, 這對(duì)于以后的基因分類標(biāo)準(zhǔn)也

16、具有重要的價(jià)值.(2) 加權(quán)系數(shù)的確定 現(xiàn)在來提取A 類和B 類基因序列的主要特征以便提出分類標(biāo)準(zhǔn).對(duì)于某條基因序列 P , 我們假定它相對(duì)于每一類的權(quán)值D 只與此類keyw o rd 在 P 中的出現(xiàn)次數(shù) l 和keyw o rd 的優(yōu)先級(jí)(即 f ) 有關(guān), 我們希望找到這個(gè)關(guān)系.351 期 楊 健等: DNA 分類模型 圖 3顯然, 一個(gè)合理的假定是: P 的權(quán)值D 是 l 和 f 值的某種組合. 設(shè)某條基因序列 P 的權(quán)值具有表達(dá)式:16 A , iD A (P ) =f A x A , i (P )(6)i= 116 B , iD B (P ) =f B x B , i (P )(7

17、)i= 1式(6) 中, f A , i 是A 類第 i 個(gè)keyw o rd 的優(yōu)先級(jí)函數(shù)值 xA , i是序列 P 中具有A 類第 i 個(gè)keyw o rd 的個(gè)數(shù) A 稱為A 類keyword 的影響力因子式(7) 中的變量、參數(shù)同理理解.稱D A (P ) 為基因序列P 的D A 值, D B (P ) 為P 的D B 值下面來確定 A 和 B , 以 A 為例.我們期望對(duì)于 10 個(gè)A 類樣本, 它們的D A 值都較大且穩(wěn)定在某個(gè)定值(設(shè)為 d ) 周圍, 另外, 為了提高分類效率我們把 A 推廣為 A , k , 表示只與前 k 個(gè)keyw o rd 有關(guān), 它的作用在第 3 點(diǎn)詳

18、細(xì)討論. 借用最小二乘法的思想, 令 h (A , k) = 10 i= 1kj = 1f A , k (P ) - d(8)2A , ji利用M A TLAB 的最優(yōu)化工具箱, 就可以確定 A , k 的值使 h (A , k ) 達(dá)到極小(與上面的分析相同, d 只具有相對(duì)意義, 它的選擇對(duì)模型好壞沒有影響).36數(shù) 學(xué) 的 實(shí) 踐 與 認(rèn) 識(shí) 31 卷 3 層次分類法現(xiàn)在要確定一個(gè)分類標(biāo)準(zhǔn)值 r , 當(dāng)待分類樣本 P 對(duì)某類的權(quán)值 r 時(shí)就將 P 分為該類. 但通過上面確定 A , k、B , k 的過程可以看出, 由A 、B 類的已知樣本確定 r 值會(huì)使標(biāo)準(zhǔn)過高, 所以用待分類的 20

19、 個(gè)樣本確定 r. 一個(gè)合理的假設(shè)是這 20 個(gè)樣本中既不屬于A 也不屬于B 的樣本數(shù)很少(5% ). 用下面的程序經(jīng)過幾次實(shí)驗(yàn)即可得出較合適的 r 值.另一個(gè)問題是選取多少個(gè)keyw o rd. 選擇越多的keyw o rd 標(biāo)準(zhǔn)越嚴(yán), 所以在算法中將 k 從 16 逐一遞減到 7 ( k 1 的定為高度顯著屬于 A (333 ) ;b) 層數(shù)為 1514 且 kA - kB 1 或 kA = kB 且D A- D B 1 的定為屬于顯著A (33 ) ;c) 層數(shù)為 137 且 kA - kB 1 的定為較顯著屬于A (3 ) ;d) 其余認(rèn)為不顯著;若 P 對(duì)A 、B 兩類均不顯著, 將

20、其歸入另類.371 期 楊 健等: DNA 分類模型 5 模型的檢驗(yàn)及效果 對(duì)A 、B 類已知樣本: 最小二乘法保證A 類樣本的D A 值, B 類樣本的D B 值足夠大,這些樣本必能正確歸類; 對(duì) 20 組待測(cè)樣本可以看出,A 、B 類區(qū)分度很大.A 類 ( 11 個(gè) ) : 23 25 27 29 32 34 35 36 37 39; B 類 ( 9 個(gè) ) :21 24 26 28 30 31 33 38 40 對(duì) 182 組未知樣本: (略)可以看出有少部分樣本不能很好歸類. 原因一是已知樣本數(shù)量太少、長(zhǎng)度太短, 無法有效檢索到一些長(zhǎng)度較長(zhǎng)的keyw o rd; 二是模型有系統(tǒng)誤差;

21、還可能有部分樣本本來就不屬于A 和B.模型的穩(wěn)定性: 分別把A , B 兩組中的序列任意改變一些字符, 再利用本文的方法進(jìn)行分類, 經(jīng)過多次實(shí)驗(yàn), 新的分類結(jié)果均和原來相同, 說明本模型的算法有很高的穩(wěn)定性.6 模型的改進(jìn)在選擇keyw o rd 時(shí), 數(shù)量上可以增加(本模型對(duì)每組選了 16 個(gè)keyw o rd) , 這樣更全面的概括A , B 兩組的特點(diǎn), 使的分組更充分.本模型是利用算術(shù)加權(quán)的方法綜合個(gè)keyw o rd 的分類重要性, 可以探索其它的加權(quán)法, 如幾何加權(quán)法, 對(duì)加權(quán)數(shù)的選擇也可以進(jìn)一步改進(jìn).在分類的過程中采用學(xué)習(xí)法: 如果某個(gè)DNA 序列用本文的結(jié)果判斷, 發(fā)現(xiàn)對(duì)A 組

22、(或B 組) 的特點(diǎn)高度一致, 就可以把次序列列入A 組作為一個(gè)分類序列, 然后對(duì)新的A , B 組重復(fù)本文的過程, 這樣可以得到更好的分類法.7 模型的評(píng)價(jià)和推廣(1) 模型的優(yōu)點(diǎn) 本模型中有較多的新想法和新的標(biāo)準(zhǔn), 創(chuàng)建了一些比較獨(dú)特使用的函數(shù), 比如字符數(shù)字轉(zhuǎn)化函數(shù)y j. m (見附錄). 分類標(biāo)準(zhǔn)直觀明了, 容易用計(jì)算機(jī)完成. 本模型的算法容易推廣到實(shí)際的DNA 的序列分析中, 具有一定的實(shí)際應(yīng)用價(jià)值. 關(guān)鍵詞選擇時(shí)考慮較全面(涉及到出現(xiàn)次數(shù), 頻率, 理論概率各個(gè)方面). 對(duì)任何一個(gè)給定的DNA 序列采取多層分類法, 能夠保證一定的置信度. 靈活的利用掩碼m , 使得程序簡(jiǎn)潔, 編

23、程量大大減少.(2) 模型的不足之處 所給分類數(shù)據(jù)太有限, 導(dǎo)致采用keyw o rd 分類的方法, 判別與已知樣本長(zhǎng)度相差太大的未知序列時(shí)準(zhǔn)確率有所限制. 一些新的想法缺乏足夠的理論根據(jù), 所以有些問題的解決的帶有一定的主觀性. 本模型純粹從數(shù)學(xué)的角度來分類, 缺乏生物學(xué)背景.(3) 模型的推廣與應(yīng)用 由于本模型主要是根據(jù) 20 個(gè)長(zhǎng)度比較短的DNA 序列的特征歸納出的分類方法, 如果直接用本模型的結(jié)果用于實(shí)際的科研中, 可能會(huì)有很大的局限性, 但是本模型用keyw o rd 作為分類標(biāo)準(zhǔn)的思想是一個(gè)可以推廣的比較好的想法, 具體的推廣思路: 從自然DNA 序列 數(shù)學(xué)的實(shí)踐與認(rèn)識(shí) M A T

24、H EM A T ICS IN PRA CT ICE AND TH EO R Y第 31 卷第 1 期 2001 年 1 月 V o l131 N o 11Jan. 2001任意選出比較多的(為了保證較高的準(zhǔn)確性) , 利用keyw o rd 作為分類標(biāo)準(zhǔn), 然后利用本文提供的加權(quán)系數(shù)的確定方法就可以定出一個(gè)具體的定量標(biāo)準(zhǔn). 具有一定實(shí)用價(jià)值.參考文獻(xiàn): 1 李 濤, 賀勇軍等. M A TLAB 工具箱應(yīng)用指南應(yīng)用數(shù)學(xué)篇. 電子工業(yè) 1 2 袁亞湘. 最優(yōu)化方法. 科學(xué) 1 3 張乃孝, 裘宗燕. 數(shù)據(jù)結(jié)構(gòu)c+ + 與面向?qū)ο蟮耐緩? 高教 1 4 汪仁官. 概率論引論. 北京大學(xué) 1 5

25、陳家鼎, 孫山澤等. 數(shù)理統(tǒng)計(jì)學(xué)講義. 高教 1The Group ing of D NA Sequences M odelYAN G J ian,W AN G Ch i,YAN G Yong(Pek ing U n iversity, Beijing 100871)Abstract: In th is paper, a m ethod to classify the DNA sequences is p ropo sed. M athem atical m ethods such as statistics and op t im izat io n are used to build th

26、e mode l. T he data is analysed sufficien t ly and the “critical w o rds”is go t, w h ich can rep resent the characteristics of each group. A cco rding to th is, a quantitative standard fo r group ing is brough t fo rw ard. T h is model can p roperly classify the given data th rough testing. F irst,

27、 the strings w h ich appear repeatedly (called w o rds) in the given data are scanned ou t. T he standard frequency and dispersio n fo r each w o rd are calculated. Second, using the L east Squares m ethod, the p rio rity funct io n is fixed. T h rough stepw ise op t im izat io n, the coefficients a

28、re m ade stable. T h ird, the key w o rds are selected out and calculate the w eigh t acco rding to the p rio rity funct io n. A t last, using the “ana lyse h ierarchy p rocess”, the undete rm ined data is classified. T h is m ethod can classify theundete rm ined data (N o. 21N o. 40) fairly w ell,

29、it can also give good result fo r the last 182sequence s.D NA 序 列 的 分 類韓軼平,余 杭,劉 威指導(dǎo)老師:楊啟帆 (浙江大學(xué), 杭州 310027)編者按:本文借助于計(jì)算機(jī)符號(hào)處理的能力來把握序列中不同堿基的豐度特征, 從而進(jìn)行了利用數(shù)理統(tǒng)計(jì)方法的分類研究. 而后引入相關(guān)度分類判別算法及反饋機(jī)制來比較堿基的相對(duì)位置, 在既定方向上頗具新意地把工作推向深入. 不足之處在于, 未能使用相關(guān)度工具對(duì)各類樣本分別進(jìn)行分析; 此外,“純數(shù)學(xué)”必須與其他學(xué)科緊密結(jié)合才會(huì)有優(yōu)秀的建模工作, 本文雖然對(duì)編碼氨基酸的三聯(lián)體進(jìn)行初步探討, 著墨處

30、自是輕淡許多.sequence s. T he second is the perio dic p roperty of the DNA sequence s. T he th ird is that amount of info rm at io n of the sequence s. By using th is m ethod, w e classify the nature sequences and artifical sequence s. A t last, w e analyze the characteristic in th is model and consider the generalizat ion of th is mode l.關(guān)于D NA 序列分類問題的模型馮 濤,康吉吉雯,韓小軍指導(dǎo)老師:賀明峰 (大連理工大學(xué), 大