基因识别算法的研究进展.doc

湖南农业大学课程论文学 院：生物安全科学技术学院 班 级：2008级生信1班 姓 名：邓驰林 学 号: 200841634113课程论文题目：基因识别算法的研究进展课程名称：模式识别与预测评阅成绩：评阅意见：成绩评定教师签名：日期： 年 月 日基因识别算法的研究进展 学 生：邓驰林 (生物安全科学技术学院 生物信息 一 班级 学号：200841634113)摘 要：随着人类基因组计划的完成，生物基因数据呈指数形式增长，找出蛋白质编码基因，即基因识别，是进行基因组分析的基础，在生物信息处理中占有非常重要的地位。通常的基因识别方法大致可以分为如下三类：序列相似性方法、从头预测方法、序列相似性和从头预测方法相结合的第三类方法。由于物种的多样性，生物基因数据的指数型增长和人类对其有限的认识等原因，第一类方法的缺陷不仅速度较慢，而且准确率不高；相较第一类来说，第二类方法具有更坚实的数学基础，模型的物理意义也更加明显直观，而且，在实验当中对若干基因预测软件的测试表明，具有最高正确率的几种基因预测软件都属于这一种方法。谱分析是信号处理的常用方法，其中的统计相关分析、傅里叶变换、小波变换和数字滤波等手段已逐渐应用到DNA序列的分析中，属于第二类基因识别方法。 本文是对前人在生物信息学方面发表的数篇论文进行简单归纳，并发表一点自己的看法。关键词：基因识别、从头预测法、谱分析 一、 研究动机与意义随着人类基因组序列测序的最终完成，人类进入了后基因组时代，这是人来历史上一个伟大的成就，也是基因组研究的转折点和关键时刻，意味着人类基因组的研究将全面进入信息提取和数据分析阶段，即生物信息学发挥重要作用的阶段。生物信息学是再次背景下发展起来的综合运用生物学、数学、物理学、信息科学以及计算机科学等诸多科学的理论方法的崭新的交叉学科。生物信息学是内涵非常丰富的学科，其核心是基因组信息学，包括基因组信息的获取、处理、存储、分配和解释。基因组信息学的关键是读懂基因组的核苷酸顺序，即全部基因在染色体上的确切位置以及各DNA片段的功能；同时在发现了新基因信息之后进行蛋白质空间结构模拟和预测，然后依据特定蛋白质的功能进行药物设计。在上述研究中，编码区与非编码区的识别即基因识别，是进一步研究DNA和蛋白质序列的前提和基础。核苷酸全序列中一个个具有生物功能的片段成为基因，它是生物遗传信息的载体。非基因部分是不编码蛋白质，与生物性状无直接关系。给定一段DNA序列，一旦编码区确定，一级结构也就清楚了，这位预测它的结构与功能奠定了基础，因而基因识别也成为生物信息学的核心问题之一。随着基因组研究和信息技术的发展，现代生物学研究方法在生物研究中发生了深刻的变化。从生物学、细胞生物学到分子生物学，现代生物研究更多地依赖信息技术的分析结果提供进一步研究的线索和依据，强有力的数据处理分析工具成为现代生物科学研究发展的关键。生物信息的分析成为计算机研究人员的重要课题。在早期，基因识别的主要手段是基于获得细胞或生物的实验。通过对若干种不同基因的同源重组的速率和统计分析，我们能够获知它们在染色体上的顺序。若进行大量类似的分析，我们可以确定各个基因的大致位置。现在，由于人类已经获得了巨大数量的基因组信息，依靠较慢的实验分析已经不能满足基因识别的需要，而基于计算计算法的基因识别得到了长足的发展，成为了基因识别的准确率和性能，成为研究的关键。如果说数据是生物信息学处理的原材料，对它的理解是人们获得的最终产品，那么，算法就是实现这个生产工程的工具，采用更有效的工具是提高生产速率的必然途径。今天，当人们面临生物数据的黑洞的时候，有效地算法就更显出其重要性。可以说，生物信息学上的每一个飞跃，都伴随着一个经典的算法，而算法上的一个突破，也往往一位这生物信息学的一个进展。正因为如此，算法研究一直是人们研究的重点。二、国内外研究发展现状基因识别方面的程序在国外已较成熟，如广泛应用的Grail , Gene mark等，其识别率已经相当高。但是也存在明显的缺点：Grail程序尝尝丢失较短的外显子，而且其整合的同源比较算法完全依赖于已知的序列；Gene mark使用HMM算法，需要对一直的基因结构信号进行学习或训练，对那些与学习过的基因结构不大相似的基因，其预测效果不佳。国内在基因识别方面的研究比较之后，目前多为识别方法的研究和针对其方法的是研修程序，还未见较成熟的整合多种算法的基因识别程序。近年来，主要研究成果有张春霆原始的几何学方法，陈润生等的神经网络方法，孟捷等用加权距离判别法。三、 三种基因识别算法通常的计算机基因识别方法大致可以分为如下三类：序列相似性方法、从头预测方法、序列相似性和从头预测方法相结合的第三类方法。3.1序列相似性方法序列相似性方法给予序列保守性的特点，通过搜索已知的数据库中与待分析序列的相似性序列来进行比较和判定，并给出标注的结果。这一类方法的基本算法是局部比对算法，从最基本的Smith-Waterman动态规划算法到快速的启发式搜索算法FASTA和BLAST，都可以用来实现这种基因结构识别算法。这样的算法非常多，其利用的生物序列数据的类型也各不相同，比如Procrustes，ORF gene，ALN，ICE主要采用蛋白质序列作为已知序列进行比较，Gene Seger，SIM4采用cDNA数据，而Eb EST，TAP则采用EST数据进行比较。总体而言，这一类方法的识别正确率取决于是否存在已知的相似序列：如果存在，则能够达到较高的识别正确率，反之则正确率很低。虽然目前已知的生物序列的数据量很大，而且新产生的序列数据也与日俱增，但是目前的研究表明，只有大约一半新测序的基因能够找到已知的同源基因或蛋白质，剩余的基因只能采用其它的方法来识别。同时，由于方法本身的限制，这一类方法不能获得对基因结构规律的认识，这也限制了这一类方法的作用。3.2从头预测方法从头预测方法的基本思想是：由于基因比非编码区域部分更加保守，因而两者的统计特征明显不同。例如，在真核生物中的编码序列偏好使用S-W语言，而非编码区与序列偏好使用R-Y语言。这样，基因结构识别就类似于在噪声背景中进行信号识别，可以采用统计特征来区分这两者。利用这一特性对未知序列进行统计学分析可以发现编码区的粗略位置。这一类方法大致有如下两种实现方式：第一种实现方式是寻找序列中所有可能的编码区，并以这些可能的编码区作为节点，以节点之间的相容关系作为边，构造出一个五环图，然后使用动态规划算法从中寻找一条最优路径。这种算法分为两个阶段：在第一阶段，使用编码区的统计特征构造得分函数，并使用者得分函数为所有可能的编码区打分，挑选出其中满足一定条件的编码区片段作为无环图的节点，并利用编码区片段之间的相同性为这些节点建立连接。算法的第二阶段是一个标准的无环图优化问题。显然第一阶段中的的得分函数决定了算法的效果，第二阶段的优化算法则决定了这个算法的计算复杂度。采用这种实现方式的算法包括Geneld，FGENE，DAGGER等。从头预测方法的第二种实现方式则并不显式地构造出无环图，而是建立一个能够描述基因结构的Markov模型，其中具有最大出现概率的通路就是可能的基因结构。为了准确地描述基因的结构，这种Markov模型通常是隐Markov模型。这样的算法包括Gen Scan，DENIE，HMM Gene，GENEMARK，Gene Mark，Hmm以及EHMM等等。与前一种算法相比，这种算法具有更坚实的数学基础，模型的物理意义也更加明显直观，而且，对若干基因预测软件的测试表明，具有最高正确率的几种基因预测软件都属于这一种方法。事实上它们正是目前人们使用得最为广泛的几种基因预测软件。目前，从头预测方法对较简单的序列能够以较高的正确率识别出其中的完整基因结构，但是对复杂的序列，比如包含多个基因或者基因结构不规则的序列，其识别的准确率仍然是比较低的。3.3序列相似性和从头预测方法相结合由于序列相似性方法和从头预测方法具有明显的互补性，近年来，人们又开始研究把这两类方法结合起来的第三类方法。这类方法的思路是把序列相似性信息融合到从头预测的系统中，从而提高对基因结构识别的准确率。比如，Genome Scan就是在Gen Scan的基础上加入了蛋白质相似性信息得到的新的基因结构识别软件，在待识别的序列存在相似性序列的情况下，它能够获得高于后者的识别正确率。另外的例子包括FGENSH+、FGENSN_C和Twin scan等。然而，由于这一类方法涉及到多种来源的信息的融合问题，而信息融合目前还缺乏公认有效地度量指标和融合方法，因此，这一类方法在日前还处于研究的阶段。四、谱分析法谱分析作为信号处理的常用方法，今年来也被用于DNA序列的分析。谱分析用于DNA序列分析有自身的优势，可以将原始数据中局部的、潜在的周期性信息变得清晰和可观察。尽管DNA序列的谱分析已有很多重要结论，但还未成为主要研究手段。下面对目前统计相关谱、功率谱和傅里叶变换等谱分析方法在DNA序列分析中的应用情况作一简单介绍。4.1 DNA序列的统计相关分析信号理论中常用自相关函数来测量线性关系和周期性。1992年在DNA序列中发现了幂律相关后，自相关函数在DNA序列分子中逐渐流行起来。直接检测DNA序列逐渐流行起来。直接检测DNA序列中和尺度无关的相关性，可能对里金额基因组的组成和进化具有深刻意义。文献3定义了自相关函数C(L)，研究了它在DNA序列分析中的应用，并对应用效果和序列的尺寸限度作了讨论。计算自相关函数前先将DNA序列数值为S=X1,X2,Xn；将DNA序列的四种碱基(A、T、G、C)分成两类，一类赋值1，另一类赋值0.有几种可能的分类方法：SW赋值法(C或G赋值1，A或T赋值0)、RY赋值法(A或G赋值1，C或T赋值0)、KM赋值法(G或T赋值1，A或C赋值0)、T赋值法(T赋值1，其它赋值0)、C赋值法(C赋值1，其它赋值0)。其方法得到的结果是相互独立的，反映了DNA序列的不同方面，例如RY赋值法描述了A和G在序列中的分布，而A赋值法只描述A的分布。其中SW赋值法更适合基因范围的相关性研究。4.2 自相关函数在DNA序列中的应用自相关函数C(l)可作为度量DNA成分不均匀性的一个特征量，研究表明：DNA序列存在幂律相关。由于序列是有限长，计算结果受统计波动的影响，这是计算C(l)中的一个重要问题。 C(l)波动越大，这在序列相关性较弱时会严重影响计算结果。因此直接应用C(l)有一定困难，于是提出了C(l)的简介应用：碱基成分变化的分析、功率谱分析和小波分析等。碱基成分变化分析的过程为：在序列开始处取长度为l的窗，计算窗中的序列总和Si，然后将窗移动一格或l格计算S2，最后计算这些数组Si的方差 ；对不同窗长度l重复上述过程。若序列是稳态的，则可通过 来计算得到C(l)。功率谱也可用来间接计算自相关函数，但是要求序列是问题的，利用小波分析则可客服这个限制条件。4.3 自相关分析在基因组中的应用原核生物基因组的C(l)研究表明：在短序列中，相关性受三密码子组成中的碱基非均匀性控制。而对于序列，如分支结核杆菌的基因组，C(l)几乎为零。值得注意的是，在分支枯草杆菌基因组的很大范围内并不等于零。前者超过基因特征长度的行为和随机序列相似，也就是说基因组特征长度的行为和随机序列相似，也就是说基因组在大范围里是均匀的。但是后一类基因组表现相关性，说明了不均匀性的存在，用密码子三个位置处碱基的不均匀含量无法解释，可能和其它基因组中成分有差异的积阴德大量横向转移甚至自然选择有关。对人类基因组，用RY赋值法计算自相关函数，看到有超过四次的幂指数相关，这和短序列中的研究一直。用SW赋值法计算的C(l)在22条染色体的序列中找到超过5次系数的幂律相关，但这不是人类连续克隆分析中的普遍行为。这个染色体中出现的尺度不变的结构，说明这可能属于新基因组，是在进化过程中的更接近时候出现的。五、谱分析法研究的结论DNA序列具有高度的复杂性，通过谱分析方法可识别和描述序列的一些特征。统计相关分析指出了DNA序列的长程相关呈1/f特性，短程相关强度大，且存在不均匀性，氨基酸内部的碱基关联比氨基酸之间的强。分子进化必须在核酸序列才能最清楚显示出来，序列的相关性随着进化程度改变，因此统计相关分析将成为描述DNA序列的同源性的一种方法。由于传统的统计分析不可避免地带来随即涨落，这使得预测存在较大误差。采用光学小波分析方法可有效地去除涨落引起的高频“噪音”，是的预测更加直观。但是，小波分析只能预测编码区的大概位置，需要和其它方法结合以更加准确地进行预测。DNA序列的DFT变换分析中发现了真核生物中绝大多数外显子存在周期3行为，即在频率 处有一个峰，而内含子中没有。STFT可用来研究DNA序列的局部性质，结合彩色谱图可以更清楚地解释基因的周期特性。通过STFT的彩色谱图不但能预示外显子的位置，还能够识别