两序列比对算法

两序列比对算法摘要：序列比对是生物信息学研究的一个基本方法，对于发现生物序列中的功能、结构和进化信息具有重要的意义。两序列比对中，典型的全局比对算法是Needleman—Wunsch算法；局部比对算法的基础是Smitll—Waterman算法，本文对典型的双序列比对算法进行描述。关键词：生物信息学；两序列比对；算法引言：为了满足基因组中获得更多更有价值的信息，生物信息学迅速发展起来，生物信息学是一门多门科学交叉的学科，将数学、计算机科学应用于生物大分子信息的获取、加工、存储、分类、检索和分析等，以达到阐明和理解大量数据所蕴含的生物学意义的目的。通过对DNA和蛋白质序列进行相似性比较，指明序列间的保守区域和不同之处，为进一步研究它们在结构、功能以及进化上的联系提供了重要的参考依据。而序列比对就是运用某种特定的数学模型或算法，找出两个或多个序列之间的最大匹配碱基或残基数，比对的结果反映了算法在多大程度上反映了序列之间的相似性关系以及它们的生物学特征。双序列比对算法双序列比对分为全局比对和局部比对，全局比对是考察两个序列之间的全局相似性，局部比对则比较序列片段之间的相似性。Needleman—Wunsch算法是典型的全局比对算法，适用于全局水平上相似性程度较高的两个序列；Smitll—Waterman算法适用于寻找局部相似序列对，该算法是目前被使用最广泛的序列相似性比较算法之一，由所熟悉的Needleman—Wunsch算法演变而来。Needleman-Wunsch算法使用迭代方法计算出两个序列的相似分值，存于一个得分矩阵中，然后根据这个得分矩阵，通过动态规划的方法回溯寻找最优的比对序列。具有很高的灵敏度使用二维表格，一个序列沿顶部展开，一个序列沿左侧展开。而且也能通过以下三个途径到达每个单元格：1.来自上面的单元格，代表将左侧的字符与空格比对。2.来自左侧的单元格，代表将上面的字符与空格比对。3.来自左上侧的单元格，代表与左侧和上面的字符比对（可能匹配也可能不匹配）。该单元格的值来自于一下3个中的最大值：（1）上方的值-2（2）左边的值-2（3）如果该单元格所在的行于所在的列对应的字符相等，则为左上值加1，否则为左上值-1。Smitll—aterman算法Smitll—Waterman算法主要分两步，计算得分矩阵和寻找最佳相似片段对。对于两个序列S和T，令/S/和/t/分别为序列S和T的长度，S[i]和T[j]（其中正整数ij满足0ViW/S/，0Vj小于等于/T/）都属于某个字符集Q，对Q中的任何元素和空符号，他们两两之间都有一个记分值，用记分函数0（x,y）表示。F（i,j）表示序歹US的前缀S[1]S[2]……S[i-1]S[i]和序列T[1]T[2]……T[j-1]T[j]"的前缀之间的最佳相似性比较的得分。那么就有以下公式：FLj)=mas(Ff-lJ—IMF£-1fj)+(75}、FGj-D+u1,-),()}其中：FLOUjLO*it当用i|=e‘i<r啊邛|)二-L当SH产7VIjr(-,j)=<rG-)—2通过公式，可得到得分矩阵，得到得分矩阵以后，用动态规划回溯的方法找到局部最大相似片段对。先找到得分矩阵中最大的元素，然后按照该元素原计算路径一步一步往前回溯，直到回溯到〃时停止。从得到的回溯路径可以得到其正向路径，就是两序列的最佳相似片段对。到目前为止，两序列比对问题已基本解决，标准方法是采用可以保证得到一个数学优化的比对结果的动态规划比对算法。两序列的动态规划比对算法是多序列比对的重要理论基础。两序列比对的一个主要目的是进行数据库相似性搜索，FASTA和BLAST是最常用的数据库搜索程序，均采用局域比对方法。FASTA：第一个广泛使用的数据库相似性搜索程序，其基本思想是：一个能够揭示出真实的序列关系的比对至少包含一个两个序列都拥有的字(由连续字符组成的子序列)，把查询序列中的所有字编成索引，然后在数据库中查询这些索引字。FASTA程序并不研究每一个选中的字，而是寻找包含若干个相邻的选中片段，将这些片段组合起来予以评价；然后，那些最有可能的匹配序列将会通过局域比对而被进一步评分，并对每一个检索到的比对提供一个统计学显著性的评估。算法过程简单描述为：1根据点阵图逻辑，从比对的所有结构中计算出最佳的对角线。2使用字符方法寻找查询字符和测试序列之间的精确匹配。3当所有的对角线发现之后，通过增加空位来连接对角线。4在最佳对角线区域中计算出比对结果。BLAST:是目前使用最广泛的数据库搜索算法，其基本思想是：通过产生数量较少，但质量更好的匹配片段来提高搜索速度，并把数据库搜索建立在严格的统计学基础之上。其算法描述如下：首先是在数据库中找出与查询序列相同的匹配字串(hit)，且这一局部字串中不含空位；一个匹配字串选中后，以此作为内核向两端延伸，以找出尽可能长的相似序列片段，也即高分片段对HSP(highsequencepairs)；设定一个统计显著性阀值E，统计显著性大于E的HSP将被舍弃，剩下的HSP即为高质量的匹配片段对，由此在数据库中搜索出具有一定可信度的同源序列。算法过程简单描述如下：1先将多个序列两两比对构建距离矩阵，反映序列之间两两关系；2然后根据距离矩阵计算产生系统进化指导树，3对关系密切的序列进行加权；然后从最紧密的两条序列开始，逐步引入临近的序列并不断重新构建比对，直到所有序列都被加入为止。现状与前景展望：序列比对是生物信息学的一个基础而又重要的问题，也是生物信息学中的一大难题。虽然人们已提出大量的比对方法，但是对于分歧较大的序列，比对的准确率以及算法的时间复杂度都有待于提高。目前，序列比对中存在的主要问题在于：如何给出一个合理的优化的相似性度量准则以及如何提高分歧多序列比对的准确率。序列比对问题未来的发展方向是基因组比较。参考文献IWison.Ondistributionofthepotentialdiferencesproduetedbytheheartbeatwithinthebodyandatitssurface[J].Ain.HeartJ，1930；5(3):599-6022MaizelJV，FitchWM.Testingehtcovalonhypothesisofwvolution[J].Mol.Biol.Evol.1995(12)：503—513.3TKAttwod,DJParry-Smith著.罗静初等译.生物信息学概论【M】.北京：北京大学出版社，2ool：141-1454蒋文蓉，王少华，赵文耘.计算机