一个基于隐马尔可夫模型和生物知识修正.doc
《一个基于隐马尔可夫模型和生物知识修正.doc》由会员分享,可在线阅读,更多相关《一个基于隐马尔可夫模型和生物知识修正.doc(11页珍藏版)》请在三一文库上搜索。
1、精品论文一个基于隐马尔可夫模型和生物知识修正的 CpG 岛识别系统徐瑜,兰曼5(华东师范大学信息科学技术学院, 上海 200241)摘要: CpG 岛的存在能识别某些基因的启动子,而且 CpG 岛的异常甲基化多与人类肿瘤的 发生有关,因此 CpG 岛的识别在生物基因组测序中很重要。本文实现了一个基于隐马尔可夫模型(HMM)和后期生物知识修正的 CpG 岛识别系统,在 EMBL 的 DNA 序列数据集上10进行系统性能测试的结果显示,该系统对于 CpG 岛有较好的识别能力,同时又比较精确地 定位 CpG 岛的位置。与其它常用 CpG 岛识别工具的对比实验结果表明,该系统的识别准确性不亚于其它软件
2、。此外,该系统的优点是一经训练,可以用于自动识别。关键词:隐马尔可夫模型;机器学习;CpG 岛识别;知识修正中图分类号:请查阅中国图书馆分类法15A CpG Island Identification System Based on HMM andDomain Knowledge RevisionXU Yu, LAN Man(School of Information Science and Technology, East China Normal University, Shanghai20200241)Abstract: CpG Islands are often associated
3、with the promoters of most housekeeping genes and many tissue-specific genes. Finding candidate regions for aberrant DNA methylation contributesto the understanding of the epigenetic causes of cancer. Therefore, identification of CpG Islands isvery important in genome mapping projects. In this work,
4、 we implemented an automatic CpG25Islands identification system, i.e. CpG-Discover, based on Hidden Markov Model (HMM) and post-processing revision including biologic domain knowledge. The experimental results on the data set of human DNA sequences from EMNL showed that this system has good identifi
5、cation performance. Moreover, in comparison with other popular tools, CpG-Discover shows comparable effectiveness. In addition, the significant advantage is it can be applied to other data sets once built30on an annotated training data set.Key words: Hidden Markov model; machine learning; CpG Island
6、s identification; knowledge modification0引言生物学上,CpG岛(CpG islands)是指DNA上包含大量相邻的胞嘧啶(C)、鸟嘌呤(G),35以及使两者相连的磷酸酯键(p)的一个区域。通常,CpG岛的长度为几百到几千个碱基对(nucleotides,单位bp)。在人的基因组中,如果双碱基对CG出现,则C通常被甲基化。并 且,甲基化的C很快会突变成T,因此基因组中CpG岛非常少。然而,在基因的起始位置(启 动子),因为功能的保守性,其序列很少突变,在哺乳类基因中的启动子上含有约40%的CpG 岛,人类基因中含有约70%的CpG岛,因此,CpG岛的存在
7、能识别某些基因的启动子,并可40作为限制酶的辨识位置。从已知的DNA序列统计来看,几乎所有的管家基因(house-keeping genes)及约40%的组织特异性基因(tissue-specific genes)的附近(通常是在5上游区域)都含基金项目:教育部博士点基金(20090076120029)作者简介:徐瑜(1988-), 女,硕士研究生,自然语言处理,文本挖掘通信联系人:兰曼(1974-), 女,副教授,自然语言处理,数据挖掘,生物文本挖掘等. E-mail:- 2 -有非甲基化的CpG岛,其序列可能包括基因转录的启动子的第一外显子1。因此,CpG岛的 识别在生物基因组测序工作中是
8、非常重要的。此外,人类肿瘤的发生与多种肿瘤相关基因的CpG岛的甲基化水平有关,CpG岛甲基化可以调控基因转录的效率,使基因转录失活,是细45胞内DNA转录状态的重要表观遗传学标记,因此,启动子区域的CpG岛的异常甲基化也是识 别癌症的重要标志之一。针对CpG岛的定义,1987年,Gardiner-Garden和Formmer2认为长度在200bp以上,G+C 含量大于50,并且实际CpG含量与期望CpG含量的比值(ObsCpGExpc G)大于0.6的区域 即为CpG岛。2002年,Daiya Takai 和 Peter A. Jones3的研究认为,长度在500bp以上,G+C50含量大于5
9、5,并且实际CpG含量与期望CpG含量的比值(ObsCpGExpc G)大于0.65的区域 更可能和基因的5区域有关。因此,根据研究的不同的目的,生物学研究人员可以采用不同 的参数进行CpG岛预测。DNA序列中的CpG岛既可以通过生物学实验的方法识别,也可以通过计算机来识别可能 的CpG岛。由于DNA序列的多样性,如果借助于生物信息和计算机工具首先识别出潜在的55CpG岛,就可以大大减少生物实验的成本和盲目性,极大地提高生物实验的时间效率和针对 性。近年来,利用计算机开发CpG岛识别工具,吸引了许多生物学领域和传统计算机领域研 究人员的兴趣,他们已经开发出许多有用的工具来帮助生物学家提高工作效
10、率。根据这些工 具所采用的方法,我们将它们大致分为两类。第一类方法是采用传统的滑动窗口(sliding window),这些工具包括CpGIS3,CpGProD4和CpGIE5等。滑动窗口法从头至尾对DNA60序列进行扫描(每次移动1n位),分别计算窗口内序列是CpG岛 (用“+”表示) 和不是CpG 岛 (用“-”表示) 的概率值(通常采用log-odds ratio),如果高于设定的域值,则认为窗口内 的序列是CpG岛,否则认为不是。采用滑动窗口法的不足之处在于:(1)窗口的大小很难 确定,通常窗口的大小直接影响CpG岛的长度和数量,如果窗口过大,一些长度较短的CpG 岛会被合并在一起,从
11、而被预测成一个大的CpG岛,降低识别的准确率;(2)窗口只能向65一个方向移动,对于之前错误的判断结果,不能在后面得到发现和修改,从而影响识别的精 度;(3)系统运行时间较长。第二类方法是采用聚集(clustering)的技术,这些工具包括 CpGCluster6和CpGIF7等。这类工具的基本思想是基于CpG岛定义中的密度或物理距离等生 物学属性,不断迭代地扫描序列,并将符合这些属性的相邻CpG岛合并为大的CpG岛簇。聚 集方法的提出是为了解决滑动窗口方法的不足,然而它带有如下的缺陷:(1)识别的结果70依赖于扫描序列的顺序,而不同的扫描顺序则会识别出不同的CpG岛,因此系统稳定性不足;(2
12、)识别的敏感度较低,倾向于识别长度较长的CpG岛序列。 与上述两类方法不同,在本文,我们尝试使用隐马尔可夫模型(HMM)建立一个自动识别CpG岛的系统,并结合生物知识对预测结果进行后期修正,从而达到较为理想的识别预 测结果。隐马尔可夫模型是一种机器学习的方法,它广泛应用于序列分析和模式识别的研究75中,例如语音识别、手写识别,命名实体识别等。这类应用的一个重要特点是,数据的序列 性。这种序列可以被认为是后一状态依赖于前一状态的时间序列,即具有马尔可夫性。正是 因为考虑到DNA序列(碱基对)也可以被看做是具有马尔可夫性的有序数据,我们在本文 中利用HMM模型实现了一个自动从人类DNA序列中识别C
13、pG岛的系统,即CpG-Discover系 统。80本文中,我们首先介绍结合HMM模型和生物知识修正的CpG-Discover系统的框架结构。 然后在欧洲分子生物学实验室(EMBL)发布的人类基因中CpG岛的数据集上测试本系统的 性能,并与其它常用的CpG岛识别工具(基于滑动窗口和聚集技术)进行对比实验,深入分析和讨论实验结果。最后我们总结这一工作和未来的方向。1CpG-Discover 系统框架85CpG-Discover 系统的框架结构主要包括三个子系统:(1)建立 HMM 模型的参数系统;(2)基于 HMM 模型建立 CpG 岛识别系统;(2)基于生物知识的后期识别修正系统。下 面我们分
14、别详细介绍这三个子系统的工作。1.1建立 HMM 模型的参数系统这个子系统完成对 HMM 模型的求解过程,即实现参数初始化、参数逼近和参数投票这90三个步骤,建立起 HMM 模型的参数系统。在参数初始化阶段,针对 4 种碱基(A,C,T, G)分别在 CpG 岛内外的状态,我们标记此 HMM 模型包括 8 个状态,分别是 A+, C+, G+, T+, A, C, G,T,标号中“+”和“”分别表示此核苷酸在和不在 CpG 岛上。这 8 个状态之间的 转移方式如图 1 所示。这 8 个状态间的状态转移概率可以从有标识的训练序列中得到,后面 会详细叙述。本文中,我们基于欧洲分子生物学实验室(EM
15、BL)核苷序列数据库进行实验95建立 HMM 模型,因此,在以下三个参数求解的过程中,我们以 ID 为 BC008880 的人类 DNA序列为例来进行说明。C+G+A+T+A-T- C-G- 11 -1001.1.1参数初始化图 1HMM 模型中 8 个状态之间的转移图示Fig. 1 The transform of 8 states in HMM105110这个步骤完成 HMM 模型中状态转移概率矩阵(A)、发射概率矩阵(B)和状态概率 矩阵()的初始化,作为下一步参数逼近的输入种子。三个概率矩阵的初始化步骤如下:(1)初始化状态转移概率矩阵 A:对于每个训练样本序列,我们采用基于长度为 2
16、 的 滑动窗口的方法来初始化参数,即通过计算从第一个状态转移到第二个状态的出现频数,来 计算转移概率。(2)初始化发射概率矩阵 B:假设一个状态到一个符号的发射概率都为 0 或 1。(3)初始化状态概率矩阵 :每个状态的初始化概率由序列中各个状态的出现频数计 算。参数完成初始化后,我们得到初始化后的各个概率矩阵。表 1 显示了人类 DNA 序列BC008880 经过初始化之后的三个概率矩阵的分布结果。1.1.2参数逼近在第二步中,我们采用 Baum-Welch 算法来重新估计基于训练序列的概率矩阵。上一步 的三个初始化概率矩阵作为 Baum-Welch 算法的输入,输出期望的转移和发射概率矩阵
17、,再115将得到的期望概率代替旧的参数,这个过程不断迭代进行直至达到收敛。在每次迭代过程中,模型概率的准确度都得到提高,直到一个极限概率,整个迭代过程最终收敛于一个局部最优 解。参数估计后,对每个训练序列,我们都得到三个逼近后的概率矩阵。表 2 显示了人类 DNA 序列 BC008880 经过 Baum-Welch 近似之后的三个概率矩阵的分布结果。120A+C+T+G+A-C-T-G-0.19150.23450.51060.063800000.18520.23460.34570.22220.01230000.12930.32760.33620.206900000.13730.23530.50
18、980.1176000000000.39360.13650.23290.236900000.40830.1750.10.3167000.005400.32970.15680.25950.248600000.19180.16440.29680.347A:A+ C+ T+ G+ A- C- T- G-:表 1 人类 DNA 序列 BC008880 经过初始化之后的三个概率矩阵的结果Tab. 1 The result of initialization of DNA sequence (BC008880)ACTG10000100001000011000010000100001B: A+ C+ T+
19、G+ A-C- T- G-0.04388 0.0756 0.0476 0.1092 0.2334 0.1120 0.2045 0.1718125A+C+T+G+A-C-T-G-0.00610.04830.00580.94060.00120.00160.00170.00200.56020.02560.12330.29120.00110.00150.00160.00230.00570.48620.16540.33490.00170.00460.00570.00280.01780.23530.50980.11760.00120.00140.00210.00350.00110.00110.00110.
20、00110.87760.11810.00360.00330.00120.00110.00110.00110.01670.26820.70460.01300.00110.00120.00110.00120.01660.28190.01690.68710.00110.00110.00110.00110.00280.22230.29170.4856A: A+ C+ T+ G+ A-C- T-G-表 2 人类 DNA 序列 BC008880 经过 Baum-Welch 逼近之后的三个概率矩阵的结果Tab. 2 The result of initialization of DNA sequence (
21、BC008880)B:ACTGA+0.43010.04100.31770.2140C+0.05590.59650.00800.3426T+0.00530.24020.71210.0454G+0.13010.14830.00830.7163A-0.92480.03080.0040.0450C-0.35340.54340.02170.0845T-0.55900.00970.42400.0103G-0.06590.01960.40140.5162:0.001113 0.999155 0.001543 0.001164 0.001001 0.001019 0.001002 0.0010031301.1
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 一个 基于 隐马尔可夫 模型 生物 知识 修正
链接地址:https://www.31doc.com/p-3621795.html