类别不平衡的分类方法及在生物信息学中的应用_图文

1、 1412 计算机研究与发展 2010, 47( 8 2. 2 识别 snoRNA 核仁小分子 RNA ( snoRN A 是一 种重要的非 编码 RNA, 它可以指导核 糖体 RNA ( rRNA 的甲 基化和假尿嘧啶化 , 进而影响其生物合成. 另外它还 可以指导小核 RNA ( snRNA 、 转运 RNA ( tRNA 和信使 RNA ( mRNA 的转录后 修饰. 根据 结构特 点 , snoRN A 主要可以分为 C D box snoRN A 和 H ACA box snoRNA 两大类. Jana 等人的研究表明 : 2 种不同的 sno RNA 在 二级结构、 自由能、 GC

2、 含量、 配对碱基个数等特征 上相对于随机的基因组序列均具有显著性 , 因此可 以用分类的方法从众多的非编码 RNA 中找出 C D box snoRNA 和 H ACA box snoRNA 17 究者试图通过机器学习的方法来对其分类. 由于 m icroRNA 的成熟 体较短, 不 容易判别 , 因此一般对其前体 ( pr ecur sor 提取二级结构特征 , 从而进行判别. 然而目前用实验确定的 micr oRNA 只有几千个, 在一个物种上的则更少, 而类似于前体 的发夹环则可以在基因组中找到很多, 对于人的基 因组至少可以找到上百万条. 因此这是一个明显的 类别 不 平 衡 的 分

3、 类 问 题. Xue 等 人 16 对 人 类 的 micro RNA 前体进行了研究 , 他们提供的数 据集中 存在 193 个正例、 8 494 个反例 , 而 在使用 LibSV M 时通过随机降采样 , 提取了 163 个正例和 168 个反 例作为训练集, 用 30 个正例和 1 000 个反例作为测 试集 . 我们选用了和他们相同的测试集 , 而训练集则 使用了除测试集以外的所有样本( 163 个正例、 7 494 个反例 , 表 3 是实验结果对比 , 其中 T riplet SV M 是 Xue 等人 Table 3 16 . 对于 C D bo x sno RNA, Jan

4、a 等选取了 306 个 正例和 45209 个反例作为训练集 ; 对于 H ACA box snoRNA, Jana 的训练集中有 65 个正例和 8 445 个 反例. 他们使用 L ibSVM 作为分类器. 在这 2 个训 练集上 , 我们使用与文献 17 中同样的特征 , 表 2 是 L ibSVM 和本文算法在 5 重交叉验证上的实验结果 对比. 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 高于本 文算法的结果, 是由于其训练集的正例远高于测试 集, 因此存 在 , 过拟 合 的 现象 . 这 一 点在 Xue 等 人 的论文中也被提及, 当他们用同样的训练集去 预测其他 物种 时, sn 有所 下降 . 另 外, 同 C D bo x snoRNA 的分类结果一样, 本文提出的分类器在保 证 sn 的情况下提高了 sp , 这对于分子生物学研究人 员是非常重要的. Xue 等人的主要贡献在于特征提取 , 通过选择 合适的特征使得其分类器成为强分类器. 而本文的 工作是基于集成学习和 A daBo ost 思 想, 因此 更适 合处理弱分类的问题 , 比如在

7、EST 序列中判别真实 的 SNP 位点 . 2. 4 EST 序列中挖掘 SNP 位点 SN P 位点是 重要 分子 标记手 段, 许多 研究 表 明 SNP 同人群分类、 遗传疾病都有着紧密的联系 . 在 EST 序列中挖掘 SN P 位点, 进而进行分子标记 , 是一项可以节省大量实验成本 却又富有挑战 性的 任务 . 首先在人类的部分 EST 序列 ( 22 994 条 中, 利 16 由表 2 可以看出, 对于弱分类问题 H ACA box snoRNA, 我们的方法无论是敏感性 sn 还是特异性 sp 都 有 显 著 的 提 高. 对 于 强 分 类 问 题 C D box sno

8、RNA, 我们的方法在保证较高的敏感性的同时, 提高了特异性 . 这对于分子生物学研究者是非常重 要的, 因为生物学实验验证的成本非常高, 因此一般 对生物信息预测软件的特异性要求高于敏感性 . 2. 3 判别 microRNA 前体真伪 microRNA 是生物体内另外一种重要的非编码 RN A 分子 , 在调解遗传基因表达、 控制细胞生长等 方面有着重 要的 作用. 在各 种生物 基因 组中 寻找 m icroRN A 是诠释基因组工作的一个重要的部分, 其思路是在基 因组序列中找出可疑的 片段然后鉴 别 . 目前鉴别的方法主要是生物芯片 ( micro Array 或北桥实验 ( No

9、rthern Blot , 它们 都具有花 费高、 操作困难和不完全准确的缺点. 因此生物信息学研 邹 权等 : 类别不平衡的分类方法及在生物信息学中的应用 1413 ( 徐燕 , 李锦涛 , 王斌 , 等 . 不均衡数据集上文本分类的特征 选择研究 J . 计 算机 研究 与 发展 , 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 数据库比较 , 确定了其 中有 183 个真实的 SNP 位点. 由于反例样本 ( 2 891 个 远远大于正例样本( 183 个 , 无法直接用 LibSVM 进行 处 理 . 第 1 次 实 验 用 降 采 样 的 方 法 结 合 L ibSVM , 第 2 次实验用类似于本文的分割反例集 然后投票的方法, 基分类器使用 L ibSVM . 表 4 是 2 次实验与本文算法

11、的效果对比. 由表 4 可以看出, 投票机制优于降采样机制 . 在 投票机制下, 利用多种分类器且重复训练错分样本 的本文方法的效果好于仅使用 L ibSVM. 因此本实 验证明了本文使用的 3 个主要策略的优越性: 1. 分 割投票策略; 2. 使用原理不同的基分类器策略; 3. 循 环训练错分样本策略. 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、模型无关的基 因选择方法 J . 软件学报 , 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 结束语 为了处理生物信息学中的样本类别不平衡问题 , 本文提出了一种基于分割反例集并投票的决策方法 . 在处理强分类问题时, 能够在保证敏感性的同时, 提 高特异性, 这对于生物信息研究者十分重要 . 在生物 信息学研究中, 特异性往往比敏感性重要, 因为高特 异性可以降低实验验证成本. 不平衡数据的分类问题是一个很重要的课题. 本文的方法仅应用于生物信息学中常见的几个挖掘 问题, 对基因芯片这种高维极度不平衡数据的分析 尚需要进一步的研究. 另外 , 分类器的效果主要受数 据分布的影响 , 在考虑数据分布特点

19、的同时 , 研究不 平衡程度对该方法的影响将是未来的工作 . 本文数 据、 软件 的 下 载地 址 为 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 ( 刘胥影 , 吴建鑫 , 周志华 . 一种基于级联模型的类别不平衡 数据分类方法 J . 南京大学学报 : 自然科学 , 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 计算机研究与发展 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 年 生 , 博 士 , 教 授 , 博 士生 导 师 , 主要研究方 向 为 生 物 信 息 学与 机 器 学 习 ( 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 ( 李鹏 , 王晓龙 , 刘远超 , 等 . 一种基于混合策略的失衡 数据 集分类方法 J . 电子学报 , 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、 方向为机器学习和计算机视觉 . 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. 邹 权 , 1982 年 生 , 博 士 , 主 要研究方向 为 非编码 R NA 的结构预 测与挖掘算法 . analysis of disease asso ciatio ns. 王 峻 , 1983 年生 , 博士研究 生 , 主 要研究 方向为 SN P 分析算法与应用、 疾病关联性分析 . Research Background T w o class classifi