两序列比对算法

两序列比对算法摘要：序列比对是生物信息学讨论的一个基本方法，对于发觉生物序列中的功能、结构和进化信息具有重要的意义。两序列比对中，典型的全局比对算法是Needleman一Wunsch算法;局部比对算法的基础是Smitll—Waterman算法，本文对典型的双序列比对算法进行描述。关键词：生物信息学；两序列比对；算法引言：为了满意基因组中获得更多更有价值的信息，生物信息学快速进展起来，生物信息学是一门多门科学交叉的学科，将数学、计算机科学应用于生物大分子信息的猎取、加工、存储、分类、检索和分析等，以达到阐明和理解大量数据所蕴含的生物学意义的目的。通过对DNA和蛋白质序列进行相像性比较，指明序列间的保守区域和不同之处，为进一步讨论它们在结构、功能以及进化上的联系供应了重要的参考依据。而序列比对就是运用某种特定的数学模型或算法，找出两个或多个序列之间的最大匹配碱基或残基数，比对的结果反映了算法在多大程度上反映了序列之间的相像性关系以及它们的生物学特征。双序列比对算法双序列比对分为全局比对和局部比对，全局比对是考察两个序列之间的全局相像性，局部比对贝此较序列片段之间的相像性。Needleman—Wunsch算法是典型的全局比对算法，适用于全局水平上相像性程度较高的两个序列；Smitll—Waterman算法适用于查找局部相像序列对，该算法是目前被使用最广泛的序列相像性比较算法之一，由所熟识的Needleman—Wunsch算法演化而来。Needleman-Wunsch算法使用迭代方法计算出两个序列的相像分值，存于一个得分矩阵中，然后依据这个得分矩阵，通过动态规划的方法回溯查找最优的比对序列。具有很高的灵敏度使用二维表格，一个序列沿顶部绽开，一个序列沿左侧绽开。而且也能通过以下三个途径到达每个单元格：1.来自上面的单元格，代表将左侧的字符与空格比对。2.来自左侧的单元格，代表将上面的字符与空格比对。3.来自左上侧的单元格，代表与左侧和上面的字符比对(可能匹配也可能不匹配\该单元格的值来自于一下3个中的最大值:(1)上方的值-2(2)左边的值-2(3)假如该单元格所在的行于所在的列对应的字符相等，则为左上值加1,否则为左上值-1。SmitH—Waterman算法Smitll—Waterman算法主要分两步，计算得分矩阵和查找最佳相像片段对。对于两个序列S和T,令/S/和/t/分别为序列S和T的长度，S[i]和T[j](其中正整数ij满意0<3/S/,0<j小于等于/T/)都属于某个字符集。，对。中的任何元素和空符号，他们两两之间都有一个记分值，用记分函数6(x,y)表示。F(i,j)表示序列S的前缀S⑴S[2]……S[i-l]S[i]和序列T[1]T[2]……T[j-l]T[j]"的前缀之间的最佳相像性比较的得分。那么就有以下公式：Ff,；)=max{F£-1,；-1)+(r6|/|,7]/|),F£-1,j)+(r3j),F£,；-!)+(r(,-),())其中：/0,())=F£,())=F0,y)=0(iMi|,7]/|)=2,当S|i|=7l/|(r6]小71/|)二一1,当5“，71/|(r(",,)=(『£,一)二2通过公式，可得到得分矩阵，得到得分矩阵以后，用动态规划回溯的方法找到局部最大相像片段对。先找到得分矩阵中最大的元素，然后依据该元素原计算路径一步一步往前回溯，直到回溯到"时停止。从得到的回溯路径可以得到其正向路径，就是两序列的最佳相像片段对。到目前为止，两序列比对问题已基本解决，标准方法是采纳可以保证得到一个数学优化的比对结果的动态规划比对算法。两序列的动态规划比对算法是多序列比对的重要理论基础。两序列比对的一个主要目的是进行数据库相像性搜寻，FASTA和BLAST是最常用的数据库搜寻程序，均采纳局域比对方法。FASTA:第一个广泛使用的数据库相像性搜寻程序，其基本思想是：一个能够揭示出真实的序列关系的比对至少包含一个两个序列都拥有的字（由连续字符组成的子序列），把查询序列中的全部字编成索引，然后在数据库中查询这些索引字。FASTA程序并不讨论每一个选中的字，而是查找包含若干个相邻的选中片段，将这些片段组合起来予以评价；然后，那些最有可能的匹配序列将会通过局域比对而被进一步评分，并对每一个检索到的比对供应一个统计学显著性的评估。算法过程简洁描述为：1依据点阵图规律，从比对的全部结构中计算出最佳的对角线。2使用字符方法查找查询字符和测试序列之间的精确匹配。3当全部的对角线发觉之后，通过增加空位来连接对角线。4在最佳对角线区域中计算出比对结果。BLAST:是目前使用最广泛的数据库搜寻算法，其基本思想是：通过产生数量较少，但质量更好的匹配片段来提高搜寻速度，并把数据库搜寻建立在严格的统计学基础之上。其算法描述如下：首先是在数据库中找出与查询序列相同的匹配字串(hit),且这一局部字串中不含空位；一个匹配字串选中后，以此作为内核向两端延长，以找出尽可能长的相像序列片段，也即高分片段对HSP(highsequencepairs);设定一个统计显著性阀值E，统计显著性大于E的HSP将被舍弃，剩下的HSP即为高质量的匹配片段对，由此在数据库中搜寻出具有肯定可信度的同源序列。算法过程简洁描述如下：1先将多个序列两两比对构建距离矩阵，反映序列之间两两关系；2然后依据距离矩阵计算产生系统进化指导树,3对关系亲密的序列进行加权；然后从最紧密的两条序列开头，逐步引入接近的序列并不断重新构建比对，直到全部序列都被加入为止。现状与前景展望：序列比对是生物信息学的一个基础而又重要的问题，也是生物信息学中的一大难题。虽然人们已提出大量的比对方法，但是对于分歧较大的序列，比对的精确率以及算法的时间简单度都有待于提高。目前，序列比对中存在的主要问题在于：如何给出一个合理的优化的相像性度量准则以及如何提高分歧多序列比对的精确率。序列比对问题将来的进展方向是基因组比较。参考文献lWison.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蒋文蓉，王少华，赵文耘.计算机帮助考试系统数据结构的开发f