類別不平衡的分類方法及在生物信息學(xué)中的應(yīng)用

1、 1412 計算機研究與發(fā)展 2010, 47( 8 2. 2 識別 snoRNA 核仁小分子 RNA ( snoRN A 是一 種重要的非 編碼 RNA, 它可以指導(dǎo)核 糖體 RNA ( rRNA 的甲 基化和假尿嘧啶化 , 進而影響其生物合成. 另外它還 可以指導(dǎo)小核 RNA ( snRNA 、 轉(zhuǎn)運 RNA ( tRNA 和信使 RNA ( mRNA 的轉(zhuǎn)錄后 修飾. 根據(jù) 結(jié)構(gòu)特 點 , snoRN A 主要可以分為 C D box snoRN A 和 H ACA box snoRNA 兩大類. Jana 等人的研究表明 : 2 種不同的 sno RNA 在 二級結(jié)構(gòu)、 自由能、 GC

2、 含量、 配對堿基個數(shù)等特征 上相對于隨機的基因組序列均具有顯著性 , 因此可 以用分類的方法從眾多的非編碼 RNA 中找出 C D box snoRNA 和 H ACA box snoRNA 17 究者試圖通過機器學(xué)習(xí)的方法來對其分類. 由于 m icroRNA 的成熟 體較短, 不 容易判別 , 因此一般對其前體 ( pr ecur sor 提取二級結(jié)構(gòu)特征 , 從而進行判別. 然而目前用實驗確定的 micr oRNA 只有幾千個, 在一個物種上的則更少, 而類似于前體 的發(fā)夾環(huán)則可以在基因組中找到很多, 對于人的基 因組至少可以找到上百萬條. 因此這是一個明顯的 類別 不 平 衡 的 分

3、 類 問 題. Xue 等 人 16 對 人 類 的 micro RNA 前體進行了研究 , 他們提供的數(shù) 據(jù)集中 存在 193 個正例、 8 494 個反例 , 而 在使用 LibSV M 時通過隨機降采樣 , 提取了 163 個正例和 168 個反 例作為訓(xùn)練集, 用 30 個正例和 1 000 個反例作為測 試集 . 我們選用了和他們相同的測試集 , 而訓(xùn)練集則 使用了除測試集以外的所有樣本( 163 個正例、 7 494 個反例 , 表 3 是實驗結(jié)果對比 , 其中 T riplet SV M 是 Xue 等人 Table 3 16 . 對于 C D bo x sno RNA, Jan

4、a 等選取了 306 個 正例和 45209 個反例作為訓(xùn)練集 ; 對于 H ACA box snoRNA, Jana 的訓(xùn)練集中有 65 個正例和 8 445 個 反例. 他們使用 L ibSVM 作為分類器. 在這 2 個訓(xùn) 練集上 , 我們使用與文獻 17 中同樣的特征 , 表 2 是 L ibSVM 和本文算法在 5 重交叉驗證上的實驗結(jié)果 對比. T able 2 Performance of LibSVM and Our Method on snoRNA 表2 本文方法和 LibSVM 在 snoRNA 上的效果比較 RN A H A CA b ox sn oR N A M eas

5、u rement sn sp C D box snoRN A sn sp LibSV M 0. 78 0. 89 0. 96 0. 91 LibID 0. 86 0. 90 0. 90 0. 94 提供的軟件 . Performance of Our Method and Triplet SVM on miRNA 表3 與 Triplet SVM 的效果比較 T riplet SV M 0. 93 0. 88 LibID 0. 83 0. 91 M easur ement sn sp 本文的方法更多地考慮了反例信息 , 因此 sp 要 高于 T riplet SVM . 而 T riplet

6、SVM 中的 sn 高于本 文算法的結(jié)果, 是由于其訓(xùn)練集的正例遠高于測試 集, 因此存 在 , 過擬 合 的 現(xiàn)象 . 這 一 點在 Xue 等 人 的論文中也被提及, 當(dāng)他們用同樣的訓(xùn)練集去 預(yù)測其他 物種 時, sn 有所 下降 . 另 外, 同 C D bo x snoRNA 的分類結(jié)果一樣, 本文提出的分類器在保 證 sn 的情況下提高了 sp , 這對于分子生物學(xué)研究人 員是非常重要的. Xue 等人的主要貢獻在于特征提取 , 通過選擇 合適的特征使得其分類器成為強分類器. 而本文的 工作是基于集成學(xué)習(xí)和 A daBo ost 思 想, 因此 更適 合處理弱分類的問題 , 比如在

7、EST 序列中判別真實 的 SNP 位點 . 2. 4 EST 序列中挖掘 SNP 位點 SN P 位點是 重要 分子 標記手 段, 許多 研究 表 明 SNP 同人群分類、 遺傳疾病都有著緊密的聯(lián)系 . 在 EST 序列中挖掘 SN P 位點, 進而進行分子標記 , 是一項可以節(jié)省大量實驗成本 卻又富有挑戰(zhàn) 性的 任務(wù) . 首先在人類的部分 EST 序列 ( 22 994 條 中, 利 16 由表 2 可以看出, 對于弱分類問題 H ACA box snoRNA, 我們的方法無論是敏感性 sn 還是特異性 sp 都 有 顯 著 的 提 高. 對 于 強 分 類 問 題 C D box sno

8、RNA, 我們的方法在保證較高的敏感性的同時, 提高了特異性 . 這對于分子生物學(xué)研究者是非常重 要的, 因為生物學(xué)實驗驗證的成本非常高, 因此一般 對生物信息預(yù)測軟件的特異性要求高于敏感性 . 2. 3 判別 microRNA 前體真?zhèn)?microRNA 是生物體內(nèi)另外一種重要的非編碼 RN A 分子 , 在調(diào)解遺傳基因表達、 控制細胞生長等 方面有著重 要的 作用. 在各 種生物 基因 組中 尋找 m icroRN A 是詮釋基因組工作的一個重要的部分, 其思路是在基 因組序列中找出可疑的 片段然后鑒 別 . 目前鑒別的方法主要是生物芯片 ( micro Array 或北橋?qū)嶒?( No

9、rthern Blot , 它們 都具有花 費高、 操作困難和不完全準確的缺點. 因此生物信息學(xué)研 鄒 權(quán)等 : 類別不平衡的分類方法及在生物信息學(xué)中的應(yīng)用 1413 ( 徐燕 , 李錦濤 , 王斌 , 等 . 不均衡數(shù)據(jù)集上文本分類的特征 選擇研究 J . 計 算機 研究 與 發(fā)展 , 2006, 43( 增刊 : 5862 2 S t ol fo S, Fan W, Lee W , et al . Cost based modeli ng for f raud and int rusion det ect ion: R es ult s from t he jam project C 3

10、Proc of t he 5t h A CM SIG KD D Int C onf on K n ow l edge 用多序列比對的辦法 , 找到了 3 074 個候選的 SNP 位點. 通過與 N CBI dbSNP 數(shù)據(jù)庫比較 , 確定了其 中有 183 個真實的 SNP 位點. 由于反例樣本 ( 2 891 個 遠遠大于正例樣本( 183 個 , 無法直接用 LibSVM 進行 處 理 . 第 1 次 實 驗 用 降 采 樣 的 方 法 結(jié) 合 L ibSVM , 第 2 次實驗用類似于本文的分割反例集 然后投票的方法, 基分類器使用 L ibSVM . 表 4 是 2 次實驗與本文算法

11、的效果對比. 由表 4 可以看出, 投票機制優(yōu)于降采樣機制 . 在 投票機制下, 利用多種分類器且重復(fù)訓(xùn)練錯分樣本 的本文方法的效果好于僅使用 L ibSVM. 因此本實 驗證明了本文使用的 3 個主要策略的優(yōu)越性: 1. 分 割投票策略; 2. 使用原理不同的基分類器策略; 3. 循 環(huán)訓(xùn)練錯分樣本策略. T able 4 Performance of LibSVM and Our Method on SNP Data 表 4 與 LibSVM 的效果比較 M easurement LibSV M ( U nder Sampling sn sp 0. 50 0. 69 LibS VM ( V

12、 ot ing 0. 66 0. 70 LibID 0. 81 0. 82 8 7 D iscovery and Dat a M ining. N ew Y ork: A CM , 1999 K ub at M S , H olt e R C S, M at w in S S . M achin e l earning for t h e det ect ion of oil spill s in sat ellit e radar images J . M achine Learnin g, 1998, 30( 2 : 195- 215 4 Faw cet t T. , In vi vo s

13、 pam fil t ering: A challenge p rob lem for dat a minin g J . AC M SIGK D D Ex plorat ions , 2003, 5 ( 2 : 140- 148 5 W an g Chun lin, D ing C hris, M eraz R F, et al. PS ol: A p os iti ve sam ple only learn ing algorit hm f or f inding non coding R N A genes J . Bioinform at ics , 2006, 22( 21 : 25

14、90- 2596 6 J iang P, Wu H , W an g W, et al . M iPred: Classif icati on of r eal an d pseud o microRN A precurs ors using random f orest p redict ion model w it h com bined feat u res J . N ucl eic A cids R es earch, 2007, 35: W 339- W 344 M art h G T , et al. A general approach t o singl e nucl eot

15、 ide p ol ymorphism discovery J . N at ure G eneti cs, 1999, 23( 4 : 452- 456 Li Jianzh ong, Y ang K u n, G ao H ong, et al. M odel f ree gene s elect ion m et hod by con siderin g unbalan ced sam ples J . J ournal of Soft w are, 2006, 17( 7 : 1485- 1493 ( in Ch ines e ( 李建中 , 楊昆 , 高宏 , 等 . 考慮樣本不平衡的

16、模型無關(guān)的基 因選擇方法 J . 軟件學(xué)報 , 2006, 17( 7 : 1485- 1493 9 C haw la N V , Bow yer K W, H all L O, et al. S M O TE: S ynt het ic minorit y over samplin g t echni qu e J . J ournal of A rt if icial Int ell igence Research, 2002, 16( 6 : 321- 357 10 Bat ist a G E, Prat i R C, M onard M C . A st udy of t he b e

17、havior of several met h od s f or bal an cing machine l earning t raining data J . A CM SIG K DD Ex plorat ions , 2004, 6( 1 : 20- 29 11 G uo H , V ikt or H L. Learning f rom imbalan ced dat a s et s w it h boost ing an d dat a generat ion: Th e D ataBoost IM Not e: D at a in this t able are average

18、 value of 10 t imes 5 cross validation. 3 結(jié)束語 為了處理生物信息學(xué)中的樣本類別不平衡問題 , 本文提出了一種基于分割反例集并投票的決策方法 . 在處理強分類問題時, 能夠在保證敏感性的同時, 提 高特異性, 這對于生物信息研究者十分重要 . 在生物 信息學(xué)研究中, 特異性往往比敏感性重要, 因為高特 異性可以降低實驗驗證成本. 不平衡數(shù)據(jù)的分類問題是一個很重要的課題. 本文的方法僅應(yīng)用于生物信息學(xué)中常見的幾個挖掘 問題, 對基因芯片這種高維極度不平衡數(shù)據(jù)的分析 尚需要進一步的研究. 另外 , 分類器的效果主要受數(shù) 據(jù)分布的影響 , 在考慮數(shù)據(jù)分布特點

19、的同時 , 研究不 平衡程度對該方法的影響將是未來的工作 . 本文數(shù) 據(jù)、 軟件 的 下 載地 址 為 ht t p: nclab. hit. edu. cn zo uquan libid . 14 approach J . A CM SIG K DD Ex plorat ions , 2004, 6( 1 : 30 - 39 12 Zadroz ny B, Langf ord J, A be N . Cost sen sit ive learning by cost pr op ort ionat e exampl e w eight ing C 435- 442 13 M anevit z

20、 L M , Yous ef M . On e class S VM S for docu ment classif icati on J . Journal of M achine Learnin g R es earch, 2001, 2( 2 : 139- 154 Liu Xuying, W u Jian xin, Zhou Zhihua. A cascade based classif icati on met hod f or cl as s im bal an ced dat a J . Journal of Nanjin g U nivers it y: N at ural Sc

21、iences, 2006, 42 ( 2 : 148 - 155 ( in Chinese ( 劉胥影 , 吳建鑫 , 周志華 . 一種基于級聯(lián)模型的類別不平衡 數(shù)據(jù)分類方法 J . 南京大學(xué)學(xué)報 : 自然科學(xué) , 2006, 42( 2 : 148- 155 Pr oc of t he 3rd Int Con f on Dat a M ining. Piscat aw ay, N J : IEEE, 2003: 參 1 考 文 獻 Xu Y an, Li Jin tao, Wang Bin, et al. A st udy of f eat ure selecti on f or text

22、cat egorizat ion on imb alanced data J . Journal of C om put er R esear ch an d D evel opmen t, 2006, 43 ( Suppl : 58- 62 ( in Chinese 1414 15 Li Pen g, Wang Xiaolong, Liu Yu anchao, et al . A 計算機研究與發(fā)展 2010, 47( 8 Guo Maozu, bo rn in 1966. PhD. Pro fesso r since 2002. P hD superv isor . H is main re

23、search inter ests include bioinfo rmatics and machine learning. 郭茂祖 , 1966 年 生 , 博 士 , 教 授 , 博 士生 導(dǎo) 師 , 主要研究方 向 為 生 物 信 息 學(xué)與 機 器 學(xué) 習(xí) ( maozuguo hit. edu. cn . Liu Yang, bor n in 1976. P hD and lectur er class ificat ion met h od f or imb alance dat a s et based on hyb rid st rat egy J . A ct a Elect

24、 ronica Sin ica, 2007, 35( 11 : 21612165 ( in Ch ines e ( 李鵬 , 王曉龍 , 劉遠超 , 等 . 一種基于混合策略的失衡 數(shù)據(jù) 集分類方法 J . 電子學(xué)報 , 2007, 35( 11 : 2161- 2165 16 Xu e C, Li F, H e T, et al. Class ificat ion of real and pseudo micr oR N A precursors usi ng l ocal st ru ct ure sequen ce f eat ures an d s upport vect or mac

25、h ine J . BM C Bi oin format ics, 2005, 6: 310 17 H ert el J , H ofacker I L, St adler P F. snoR eport : Comput ati on al ident if icat ion of snoR N A s w it h un know n t arget s J . Bioinform at ics , 2008, 24( 2 : 158- 164 18 K rogh A , et al. N eural netw ork ens embl es, cross validat ion, an

26、d act ive learnin g G 238 19 Fran k E, et al. Dat a min ing in bioinf orm at ics u sing Weka J . Bioi nformat ics , 2004, 20( 15 : 2479- 2481 A dvances in N eural Inf ormat ion since 2006. H is main research inter ests include machine learning and computer visio n 劉 揚 , 1976 年 生 , 博 士 , 講 師 , 主 要研 究

27、 方向為機器學(xué)習(xí)和計算機視覺 . Wang Jun, born in 1983. PhD candidate. Her main r esea rch and interests on include SNP , alg or ithms application Proces sing Syst ems 7. Cambri dg e: M IT Pres s, 1995: 231- Zou Quan, bo rn in 1982. P hD. H is main r esear ch inter ests include the pr edict ion o f ncRN A str ucture and mining ncR N A. 鄒 權(quán) , 1982 年 生 , 博 士 , 主 要研究方向 為 非編碼 R NA 的結(jié)構(gòu)預(yù) 測與挖掘算法 . analysis of disease asso ciatio ns. 王 峻 , 1983 年生 , 博士研究 生 , 主 要研究 方向為 SN P 分析算法與應(yīng)用、 疾病關(guān)聯(lián)性分析 . Research Background T w o class classifi