microRNA计算识别中的模式识别技术.pdf

《microRNA计算识别中的模式识别技术.pdf》由会员分享，可在线阅读，更多相关《microRNA计算识别中的模式识别技术.pdf（4页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第22001 0 6期 年月 计 算 机 技 术 与 发 展 ER TECHNOl Y AND DEVELOPMENT Vo I 2 0 No 6 J u n 2 0 1 0 mi c r o R N A计算识别 中的模式识别技术 孙 秋 凤(南京师范大学 泰州学院 信息与科学技术 系，江苏 泰州 2 2 5 3 0 0)摘要：Mi c r o R N A s(r r a R N A s)是一种大小约 2 1-2 3个碱基的单链 R N A小分子，对多种生物学过程起调控作用，它们主要 参与基因转录后水平的调控，能有效地抑制相关蛋白质的合成，与生物体的生长发育和某些疾病的发生密切相关。对 n 1

2、 i c r o R N A s(r r a R N A s)的研究正在不断增加，计算识别为分子生物学实验寻找新 mi c r o R NA提供一组高质量的候选序列。文 中从模式识别的角度审视现有的计算识别技术，分析和比较各种方法的特点后发现基于支持向量机的识别方法已经能在 识别精度上得到很好的效果，这也是 m i e r o R N A识别技术将来发展的主要方向。关键词：m i c r o R N A；支持向量机；生物信息学；核函数 中图分类号：T P 3 9 1 4；Q 8 1 1 4 文献标识码：A 文章编号：1 6 7 3 6 2 9 X(2 0 1 0)0 6 0 o 9 7 0 4

3、 Pa t t e r n Re c o g n i t i o n Te c hn o l o g y f o r M i c r o RNA I d e nt i f i c a t i o n S UN Qi u f e n g (D e p a r t me n t o f I n f o r ma t i o n a n d Te c h n o l o g y，Ta i z h o u C o l l e g e，N a n j i n g N o rm a l U n i v e r s i t y，T a i z h o u 2 2 5 3 0 0，C h i n a)A b

4、s t r a c t：Mie r o R NAs(mi R NA s)a r e2 2 n t l o n g n o n c o d in g R g As t h a t a r e d e r i v e d f r o m la r g e r hai r p i n R NA p r e c u r s o r s a n d p la y im p o r t a n t r e g u lat o r y r o l e si n b o t h a nima l s a n d p l an t s Th e r e s e a r c ho fmi RNAsis c on

5、t i n u a l l yin c r e a s i n g a f t e rt h ef i r s tmi RNAswe r e d i s cov e r e d u s i ng e x p e rime n t a l me t h o d s S i n c e e xper i me n t a l mi RNA i d e n t if i c a t i o n r e ma in s t e c h nic a l l y c h a l l e ng i n g a n d in c o mp l e t e，t h i s cal ls f o r t h e

6、d e v e lo p me n t f o r c o mp u t a t i o n a l a p p r o a c h e s t o c o mp l e me n t e x per i men t a l a p p r o a c h e s t O mi RNA g e n e i d ent i f i c a t io n At t e mp t s t o l o o k b a c k t h e ex i s t in g c o mp u t a t i o n a l a p p r o a c h e s a nd comp a r e t h e i

7、r a d v a nt a g e s Fi n a l l y f ind t hat a mo n g a ll t h e po t e nt i a l me a n s t h e o n e b a s e d o nS VM h a s b e t t e r p r e c i s ion a n dt h a t Swh yt h i sme t h o d h a sb e o 3 n l et h ele a d i n gme L S L i l-ef o rmic r o RNA i d e n t i f ic a t io ni nt hef u t u r e

8、 Ke y wo r d s mi c mRNA；s u p p o r t v ect o r ma c h i n e；b io i n f o r ma t i e s；k e me l f u n c t io n O 引 言 mi R N A是一些长度约为 2 2 n t 的非编码调控 R N A 家族，它有 3 个显著 的特点：(1)广泛存在于真核生物 中，是一组不编码蛋 白 质的短序列 R N A，本身并不具有开放阅读框；(2)通常的长度为 2 0 2 4 n t，但在 3 端可以有 1 2 个碱基 的长 度变化；(3)成熟的 mi R NA 5 端有一磷酸基团，3 端为羟 基。

9、在线虫、果 蝇、小 鼠和人等物种 中已经发现的数百 个 m i R N A s中的多数具有和其他参与调控基因表达的 分子一样的特征，提示 m i R N A s 在高级真核生物体内 对基因表达的调控作用可能和转录因子一样重要。收稿 日期：2 0 0 90 93 0；修回 日期：2 0 0 9一l 22 2 基金项 目：国家 自然科学基金(6 0 2 7 5 0 0 7)作者简介：孙秋风(1 9 7 9 一)，女，江苏泰州人，硕士，研究方向为模式 识别及生物信息技术。早期传统寻找 mi R NA的方法主要依赖于分子克 隆，此类方法一般都步骤烦琐、周期性长、工作量大，由 于目标不明确，效率较低且实

10、验费用昂贵。因此，研究 人员展开了计算方法的研究 以弥补实验方法的不足，基于机器学 习的计 算方法 已经 成为 发现 新 的 mi c r o R N A的一个重要手段，为实验发现提供候选 mi c mR N A 基 因。1 mi R N A计算识别方法 1 1 基于决策树的计算识别方法 这类识别方法中较为成功软件有：Mi R s c a n 1 和 mi R s e e k e r L 2 j。这类方法大致 的流程是从某一物种已 知 m i R N A 中提取相关特 征，建立 模 型，从 大量 的数据 集中筛选出候选 mi R N A，然后对其进行打分，若超过 某个阈值则认为此序列可归于这一

11、类。其中提取特征 并建立模型的操作从模式识别角度来看类似于建立一 棵决策树的过程(见图 1)。在文献 3 中考虑到在已识别的mi R N A周围可能 9 8-计算机技术与发展 第 2 O卷 存在新的 mi R N A，将待识别的序列长度增加 然后提 取其二级结构，使用 S VM对其进行分类。这个方法 的优点是使用了输入序列和二级结构，缺点在于忽略 了相关生物信息，可能导致在对哺乳类动物基因进行 测试时产生高的假阳性。图 1 一个二又 决策树的示例 文献 4 中的方法是基 于物种 间 的保 守性 而设 计 的，在特征方面除了使用了众所周知的前体二级结构 外，还提出 了三个可计算 的特征：(1)G

12、 C含 量为 3 8 7 0；(2)茎环长度在 2 0 7 0 n t 之间；(3)与物种 O s a t i v a 的序列相似性不低于 9 0。文献 5 中的 mi R A l i g n方法在序列信息的基础上 加人结构信息来对候选序列打分。在处理待识别序列 时，除了使用 自由能等常 规生物 属性来 预测 序列二 级 结构外，mi R A l i g n 增加 了一个在茎 环结构上检O n,4 mi R NA位置的操作，通过比较两个 mi R NA s 位置上的差别 确认二者是 否为 同源体。可以看 出，以上方法 的策 略大致 可 以分为 如下三 类：1)利用同源性搜索 已知 mi R N

13、 A基 因的直 系同源(o r t h o l o g)和旁系同源(p a r a l o g)。2)在 已知 mi I N A附近搜 索基 因簇。3)其他不依赖 于同源性 和 m i R N A基 因簇 的基 因 搜索法。该方法利用 近亲物 种 中 mi R N A基 因序列 的 保守性、非编码性，以及前体可形成潜在茎环结构等特 性来 给候选 mi R N A序列打分。1 2 基于支持 向量机的计算识别方法 1 2 1 支持 向量机 简介 支持 向量机(S u p p o r t V e c t o r Ma c h i n e，S V M)是基 于统计学习理 沦的学习方法。它通过构造最优超

14、 乎 面，使得对未知样本的分类误差最小。对于两类线性 可分情形，可直接构造最优超平面，使得样本集中的所 有 向量满足如下条件：(1)能 被某一 超平 面正确划分：(2)距该超平 面最近 的异类 向量 与超平面 之间 的 距离最 大，即分类 间隔最 大。则该超 平面 为最优 超平 面。其 中，条件(1)是保证经验风险最小，条件(2)是使 V C置信度最小，从而使期望风险最小。这里，最优超平面的构造问题实质上是约束条件 下求解一个二次规划问题，以得到一个最优分类 函数 为：_ f(z)=s g n 5_ 2 y,a ik(，z)+b i=1 其 中 k(，)是一 核函数，s g n 是符号函数，L

15、为训 练样本数 目。在该分类 函数中，某些 z 对应的 不为零，由于 这些具有非零值 a 的对应的向量支撑了最优分类面，因此被称为支持 向量。对于线性 S V M，核函数 k(-，)就是两向量的点 积运算；对于非线性情形，可通过非线性映射把输入向 量映射到一个高维特征空间，来构造最优分类面，常用 的核 函数形式有多项式形式、径向基形式、二层感 知器 神经 网络形式。1 2 2 一 些将序列转化成向量的方法 在基于决策树的方法中已经有部分方法中使用 S VM来对结果进行分类，但使用仅限于将其作为一个 分类工具，并未有任何改进之处。随着研究 mi R N A的 人员越来越多，方法也开始呈现多样化，

16、对 于一些 边缘 学科而 言，如生物信 息学，人们 希望将 mi R N A不仅 仅 看成纯 生物 的序列，而是将其看 成大多 数人 能接 受 的 某种结构，且这种结构能有利于特征的提取。文献 6 中将发卡序列中碱基表示成相应的三联 组，然后统计 3 2个可 能的三联 组 出现 的次数，经 过归 一化后 作为 S V M 的输 入 向量进 行训 练 得到 决 策 面，进而对测试数据进行分类。这个方法的优点在于不需 要考虑相关的生物特征，而且测试结果也显示虽然没 有考虑那些 因素，但所 映射后 的特征还 是反映 了 m i R N A二级结构 的有关性质。文献 7 提出了一个依据遵循“特征生成、

17、选择、综 合”构造识别模式、基于 S V M 的 d e n o v o 方法来识 别前 体。为了捕获二级结构 中的信息，先通过 R NMo l d将 前体折叠，为了便于数据处理，再将碱基对进行编码。文献 8 的作者认为使用 S V M识别 mi R NA的方 法虽多，但那些方法都没有将一些特征很好地综合起 来，因此提 出 P S o L(P o s i t i v e S a m p l e O n l y L e a rni n g A l g o r i t h m)算法。算法的关键在于训练数据集的选择，算法的基本 第 6期 孙秋风：mi c r o R N A计算识别 中的模式识别技术

18、 9 9 思想是：(1)根据序列 统计 性，最 小 自 曲 能及相 关基 因间 的相似性度量将每个序列转换成特征 向量。其中序 列 统 计 性 包 括(A，C，G，T)，d i n e r(A A A C T T)及 t r i me r(A A A，A A C 1 v r r)的个 数；相 似 性度 量包括 T y p h i C T 1 8，T y p h i T y 2及 T y p h i L T 2。通常特征向量维数过 多会降低 识 别能力，因此对 转换 后得到的 8 8个向量 进行筛 选。(2)将 已有 的数 据 分 为 正类 样本 及 u n l a b e l e d d a

19、t a(即 其 中既 有 正 类 也 有 负 类)。P S o L的 目的是在 u n l a bel e d d a t a中预 测正类样 本，但问题是现有 的训练集 中没 有负类样本，如何产生负类样 本是本算法 的核心之一。由于序列 的保 守性通常 在二级结构，因此单单序列 比对将无法识别那些在其 初级序列上分化得很远但仍保持其碱基 配对结构 的 mi R NA s。基 于此，在 特征 提 取 生成时，与基于决策树类方法将特征 的提取重点放在序列信息不同的是，这类 方法的特征提取侧重于结构信息。1 2 3 一 些使 用特殊核 函数 的方 法 是所有(k i，mi)一mi s m a t c

20、 h k e rne l 的总 和：K(r，l 1，)(，)=(z)，O k i,m i()i =K (z，)G S K的基 本 思想 是 将 序 列 映射(见 图 4)成 l G S K，2一 G S K 和 3一G S K，通 过训 练 找 出权 值较 高 的 映射子串并把它们作为特征输入 S VM对数据进行测 试。S e q u e n c e =A B B A l I=(A jB，c)2-m e r s i A B，B B，B A ()C I)tM Ji sJl ()A A A B l A C 8 A 8 B B C C A C B C C ：A B B A AA 1 1 1 1 1

21、2 AB 1 t 1 1 1 2 AC 1 1 1 1 1 1 BA 1 1 1 1 1 2 p B B 1 1 1 1 3 BC 1 1 1 1 1 2 CA 1 1 1 1 1 1 CB 1 1 1 1 2 CC 1 1 1 1 1 0 尽 管 S V M 在生 物 学应 用 比较 成功，但 通 常都 要 涉及到将结构化 的生物数 据转化 成特征 向量。这导致 即使一个复杂 的结 构也会 被转化 成简 化的数 值，这 会 损失一些生物信息。为 了避 免这种 信息 的损 失，基 于 链 以及图的一些核 函数被应用到支持 向量机 中。文献 9 3 提出一种基于链的 S p e c t r u

22、m k e me l，所使 用的特征是 长度为 k的氨基酸的所有可能子序列的集 合(见 图 2)，若 两个 蛋 白序列含 有许 多相 同 的 志长 度 的子序列，则 ks p e c t r u m k e rne l 下 的内积 就会 越 大，即两个序列的相似度也会越大。AKQDY YYYE I AKQDY YY YE I 图 3(k，m)一 mi s ma t c h k e rne l 特征 映射示例 图 4 GS K映 射 示例 文献 1 2 又提出另一种类似的核 一s t e m k e me l。与上述核 的不同之处在于参与计算 的子 串不再是连续 的，而是允许不连续的子串参与映射

23、 向量。J I l (A K Q，K Q D，Q D Y,D Y Y,Y Y Y；Y Y Y,Y y E，Y E I)(o，0，1，i，2，1)图 2 k s p e c t r u m k e rne l 特征 映射 示例 文献 1 O 是在 s pec t r u m k e rne l 基础上提出一种新 的用于 S V M 的核 一mi s ma t c h k e rne l。n 1 i s m a t c h k e me J 的计算是基于(k，m)一p a t t e r n s 出现 的次数，而(k 1)一p a t t e r n s 是 由所有 与一个 k长度 子串最多有”个

24、不 匹配的七长度子 串的集合生成 的，特征映射 见图 3。文献 1 1 则 在 s pec t r u m k e rne l 和 mi s m a t c h k e me l 基础上提 出一 种 g e n e r a l i z e d s t r i n g k e rne l(G S K)。G S K 虽然 上 述 的 识 别 方 法 大 多 使 用 二级结构作 为输 人数 据，但在一 定程 度上忽略了其本身含有的拓扑信息，文献 1 3 提出将二级结构表示成 图 结构，这样 可 以直接 比较两 个图 之间 的相似性，避免训练数据、调整参数等。I bel e d D u a l Gr

25、a p h s(u)即是用来表示 二级结构 的图，两个 I I Xi s 之间的相似性则是用 Ma r g i n a l i z e d Ke rne l s 来进行计 算。2 结束语 目前，早期 mi I N A计 算识别方法面 临较低准 确率 计算机技术与发展 第 2 0卷 的问题，并且对 mi R N A基 因的从 头预 测(d e n o v o p r e d i c t i o n)大程度上 尚未解 决。如何 准确定位成 熟 mi R N A也尚待研究。且此类方法 的一大缺陷是没有 一个系统的方法把候选 mi R NA序列的初级结构和二 级结构的信息融合起来，用 以捕捉序列数据

26、中可能存 在的微弱“信号”。在已有方法中所采用的一些启发式参数也有待进 一步研究。如：Mi R s c a n方法 中，候选 m i R N A前体经 d 折叠后 的最小折叠 自由能量阈值下限设为 2 5(即 G I。I d i呕 一2 5 k c a l m o l e)，但 经 过 对 已 知 的 mi R N A前体进行折叠后发现，许多最小折叠 自由能量 小于该阈值，如线虫 m i R NA前体 e e l mi r 一2 6 1经折 叠后其 (=一7 0 8 k c a l mo l e。因此，如何避免设 立这些人 为参数成 为识别算法 的一个 重要方 面。基于以上各方面的考虑，机器学

27、习方法成为识别 算法 的一 个很好选择。目前研究的热点在于如何将序列和结构信息综合 起来，以达到更好的分类效果。已经提出的基于 s t ri n g k e r n e l 和 g r a p h k e me l 的算法是个很好的尝试。参考文献：1 L i m L P，L a u N C，We i n s t e in E G，e t a1 T h e m i e r o R N A s o f C a e n o r h a b d i t i s e le g a n s J G e n e s D e v ，2 0 0 3，1 7：9 9 1 1 o o 8 2 L a i E C，T

28、 o m a n e a k P，Wi l l i a ms R W，e t a 1 C o mp u t a t i o n a l i d e n t i f i c a t i o n o f D r o s o p h i l am i c r o R N A g e n e s J G e n o me B i-o l，2 0 0 3(4)：1 2 O 3 S e w e r A，P a u l M，L a n d g r a f P，e t a 1 I d e n t i f i c a t io n o f c l u s t e r e d m i e r o R N A s

29、u s i n g a n a b i n i t io p r e d i c t i o n m e t h o d J B i o i r ff o r m a t ie s，2 0 0 5(6)：2 6 7 2 8 1 4 Wa n gX J，R e y esJL，C h u a Na mI-h i，e t a 1 P r e d i c ti o n a n di d e n t i fi e a t i o n o f Ar a b i d o l i s t h a l i a n a mi e r o R NA s a n d t h e i r mR N At a r g e

30、 t s J G od l o n l e B i 0 1 ，2 0 0 4(5)：1 1 5 5 Wa n g X W，Z h a n g J，L i F，e t a 1 Mi c r o R N A I d e n t i f i c a ti o n B a s e d o nSeq u eno e a n d S t r u c t u r e A l ig n ment J B i o i r d o r r nat i e s 2 0 0 5，2 1(1 8)：3 6 1 0 3 6 1 4 【6 X u e C h e n g h a i，U F e i，H e T a o，e

31、t a1 C l a s s i fi c a t i o n o f r e a l a n d p s e u d omi e r o R NA p r e c u r s o r s u s i I 1g l o c a l s t r u c t u r e s e q u e n c e f e a t u r e s and s u p p o r t v o l m a c h l n e J B i o i r d o r r n a t i c s 2 0 0 5 (6)：3 1 0 3 1 7 7 Y a n gL i a n gHu a i，H s u Wy une，L

32、e eMo ng L i，e t a 1 I d e n t i fi e a-t i o n o f Mi e mR N AP r e d i c t i o n v i a S V M c P r o e e e d l ng of t h e 4 t hAs i a P a c i f icB i o i n f o r ma t ie sC。n f e 姗 c e Ta i p e i Ta i wa n：s n ，2 0 0 6：2 6 7 2 7 6 8 K i mS u n g K y u，N a m J mWu，R h e e J e K e u n，e t a 1 mi Ta

33、 r g e t：mi e r o RNA t a r g e t g e n e p r e d i c t i o n u s i ng a s u pp o r t v e c-t o r m a e h i n e J B io i n f o r ma t i e s，2 0 0 6(7)：4 1 1 4 2 2 9 ks l ie CS，E s k i n E，N o b l e W S T h e s p e c t r u mk e r n e l：a s t r i n g k e md f o r S V M p r o t e i n c l a s s i f i c

34、a t io n C P r o e P a e B i o c t n p u t S y mp s 1 ：s n ，2 0 0 2：1 4 4 1 1 4 4 8 1 0 s I ie CS，E s k i nE，C o h e nA，e t a 1 Mis ma t c h s t r i n g k e me ls f o r d i s c r i m i n a t i v e p r o t e i n e l s s s i fi e a t i o n【J B i o in f o r ma t i es 2 0 0 4，2 0(4)：4 6 7 4 7 6 1 1 T e

35、r a mo t o R，A o k i M，K i m u r a T，e t a1 P r e d i i o n o f s i R N A f u n c t i o n a l it y u s ing g e n e r a l i z e d s t r i n g k e md a n d s u p p o r t v e c t o r m a e h i n e J F 1 B S L e t t，2 0 0 5，5 7 9(1 3)：2 8 7 8 2 8 8 2 1 2 Y a s u b u mi，S a k a k i b a r a K e r n e l F

36、unc t i o n s f o r R N A -q u eno e a n a l y s e s C 2 n d T a i w an J a p a n B i la t er a l S y mp o d u m o n B i o i n f o r m a t i e s s 1 ：s n ，2 0 0 6 1 3 K a r k l i nY，Me r a zRF，H o l b r o o k SR C A a a s i f i e a t io n o f N o n C n c li n g I A Us i n g Gr a p h R e p r ese n t

37、a t io n s 0 f n d a r y S t r u c t u r e C P a c i fi c S y m p o s i u m o i l B i o o o m p u t i ng a I ：s n ，2 0 0 5 (上接第 9 6页)参考文献：1 P a w l a k Z R o u g h Set s J I n t e r n a t io n a l J o u r n a l o f C o m p u t e r and I n f o r ma t i o n S c i e n c e s，1 9 8 2，1 1(5)：3 4 1 3 5 6 2

38、 Z HA N G w叽 一 x i u，MI J u s h e n g，wU We i z h i Ap p r o a c h es t o k n o wle d g e r e d u c t i o n s i n i n c o n s i s t e n t s y s t e ms J I n t e r n a t i o n a l J o u r n a l o f I n t e l l i g e n t S y s t e m s，2 0 0 3。1 8(9)：9 8 9 1 0 o0 3 赵荣利，崔志明，陈建明 一种改进的基于差别矩阵的属性 约简方法 J 计算机

39、技术与发展，2 0 0 6，1 6(1 1)：3 2 3 3 4 汪小燕，杨思春 一种基于分辨矩阵的新 的属性约简算法 J 计算机技术与发展，2 0 0 8，1 8(2)：7 7 7 8 【5 陈鑫影，邱占芝 基于可分辨重要度 的属性约简算法 J 大连交通大学学报，2 o 0 8，2 9(4)：8 3 8 4 6 张文修，吴伟志，梁吉业，等 粗糙集理论与方法 M 北 京：科学出版社，2 0 0 1 7 田卫东，周创德，胡学刚，等 基于简化分辨矩阵的粗糙集 属性约简算法 J 计算机科学，2 0 0 8，3 5(3)：2 1 0 2 1 1 8 葛浩，杨传健，李龙澍 一种改进的基于二进制可分辨矩

40、阵属性约简算法 J 计算机技术与发展，2 0 0 8，1 8(8)：1 3 一 l 4 9 HU X H，C e r e o n e N L e a r n i ng i n r e l a t i o n a l d a t a b a s e s：A r o ngh s e t a p p r o a c h J C o mp u t a t i o n a l I n t d l ig e n c e，1 9 9 5，1 1(2)：3 2 3 3 3 7 1 0 胡可云 基于概念格核粗糙集的数据挖掘方法研究 D 北 京：清华大学，2 0 0 1 1 1 李侃，刘玉树 一种粗糙集属性约简算法 J 计算机工 程与应用，2 0 o 2，3 8(5)：1 5 1 9