莈两序列比对算法
蚇摘要：序列比对是生物信息学研究的一个基本方法，对于发现生物序列中的功能、结构和
进化信息具有重要的意义。两序列比对中，典型的全局比对算法是Needleman—Wunsch算法；
局部比对算法的基础是Smitll—Waterman 算法，本文对典型的双序列比对算法进行描述。
膃
袄关键词：生物信息学；两序列比对；算法
莀引言：
聿为了满足基因组中获得更多更有价值的信息，生物信息学迅速发展起来，生物信息学是一
门多门科学交叉的学科，将数学、计算机科学应用于生物大分子信息的获取、加工、存储、
分类、检索和分析等，以达到阐明和理解大量数据所蕴含的生物学意义的目的。通过对DNA
和蛋白质序列进行相似性比较，指明序列间的保守区域和不同之处，为进一步研究它们在结
构、功能以及进化上的联系提供了重要的参考依据。而序列比对就是运用某种特定的数学模
大程度上反映了序列之间的相似性关系以及它们的生物学特征。
型或算法，找出两个或多个序列之间的最大匹配碱基或残基数，比对的结果反映了算法在多
于全局水平上相似性程度较高的两个序列；Smitll—Waterman算法适用于寻找局部相似序
列对，该算法是目前被使用最广泛的序列相似性比较算法之一，由所熟悉的
Needleman—Wunsch算法演变而来。
蒁Needleman-Wunsch算法
膇使用迭代方法计算出两个序列的相似分值，存于一个得分矩阵中，然后根据这个得分矩阵，
通过动态规划的方法回溯寻找最优的比对序列。具有很高的灵敏度使用二维表格，一个序列
沿顶部展开，一个序列沿左侧展开。而且也能通过以下三个途径到达每个单元格：1.来自上
面的单元格，代表将左侧的字符与空格比对。2.来自左侧的单元格，代表将上面的字符与空
格比对。3.来自左上侧的单元格，代表与左侧和上面的字符比对（可能匹配也可能不匹配）。
该单元格的值来自于一下3个中的最大值：（1）上方的值-2（2）左边的值-2（3）如果该
单元格所在的行于所在的列对应的字符相等，则为左上值加1，否则为左上值-1。
芆Smitll—Waterman 算法 |
|
肁Smitll—Waterman算法主要分两步，计算得分矩阵和寻找最佳相似片段对。对于两个序列 | |
S和T，令/S/和/t/分别为序列S和T的长
芈度，S[i]和T[j]（其中正整数ij满足0＜i≤/S/，0＜j小于等于/T/）都属于某
芆个字符集Ω，对Ω中的任何元素和空符号，他们两两之间都有一个记分值，用记分函数δ（x,y）表示。F(i,j)表示序列S的前缀S[1]S[2]……S[i-1]S[i]和序列T[1]T[2]……T[j-1]T[j]"的前缀之间的最佳相似性比较的得分。那么就有以下公式：
螅通过公式，可得到得分矩阵，得到得分矩阵以后，用动态规划回溯的方法找到局部最大相似片段对。先找到得分矩阵中最大的元素，然后按照该元素原计算路径一步一步往前回溯，
对。
直到回溯到"时停止。从得到的回溯路径可以得到其正向路径，就是两序列的最佳相似片段
芀FASTA：第一个广泛使用的数据库相似性搜索程序，其基本思想是：一个能够揭示出真实的序列关系的比对至少包含一个两个序列都拥有的字(由连续字符组成的子序列)，把查询序列中的所有字编成索引，然后在数据库中查询这些索引字。FASTA程序并不研究每一个选中的字，而是寻找包含若干个相邻的选中片段，将这些片段组合起来予以评价；然后，那些最有可能的匹配序列将会通过局域比对而被进一步评分，
并对每一个检索到的比对提供一个统计学显著性的评估。
蚈算法过程简单描述为：
膅1根据点阵图逻辑，从比对的所有结构中计算出最佳的对角线。
薂2使用字符方法寻找查询字符和测试序列之间的精确
莁匹配。
螇3 当所有的对角线发现之后，通过增加空位来连接对角线。
薄4在最佳对角线区域中计算出比对结果。
节BLAST：是目前使用最广泛的数据库搜索算法，其基本思想是：通过产生数量较少，但质
量更好的匹配片段来提高搜索速度，并把数据库搜索建立在严格的统计学基础之上。其算法
描述如下：首先是在数据库中找出与查询序列相同的匹配字串(hit)，且这一局部字串中不
含空位；一个匹配字串选中后，以此作为内核向两端延伸，以找出尽可能长的相似序列片段，
也即高分片段对HSP(highsequence pairs)；设定一个统计显著性阀值E，统计显著性大于E
的HSP将被舍弃，剩下的HSP即为高质量的匹配片段对，由此在数据库中搜索出具有一定可信
度的同源序列。
膈算法过程简单描述如下：
腿1先将多个序列两两比对构建距离矩阵，反映序列之间两
肄两关系；
肃2然后根据距离矩阵计算产生系统进化指导树，
芇开始，逐步引入临近的序列并不断重新构建比对，直到所有序膀3对关系密切的序列进行加权；然后从最紧密的两条序列
螃
芁现状与前景展望：
肂序列比对是生物信息学的一个基础而又重要的问题，也是生物信息学中的一大难题。虽
然人们已提出大量的比对方法，但是对于分歧较大的序列，比对的准确率以及算法的时间复
杂度都有待于提高。目前，序列比对中存在的主要问题在于：如何给出一个合理的优化的相
似性度量准则以及如何提高分歧多序列比对的准确率。序列比对问题未来的发展方向是基因
组比较。
袂参考文献
艿1Wison．Ondistribution of the potential diferences produeted by the heart beat
withinthe body and at its surface[J]．AIn．HeartJ，1930；5(3)：599-602
螄2MaizelJ V，FitchW M．Testingeht covalon hypothesis of
wvolution[J]．Mo1．Bio1．Evo1．1995(12)：503—513．
蒄3 T K Attwod，D J Parry-Smith著．罗静初等译．生物信息学概论【M】．北京：北京大
学出版社，2ool：141-145
节4蒋文蓉，王少华，赵文耘．计算机辅试系统数据结构的开发fJ1微计算机信息，
2006，7-2：248—250
羀5．TSmith．MWaterman．Identificationof common moleculag sequence[J]．
Journalof Moleeular Biology，198l；147：195～l97
以下无正文
仅供个人用于学习、研究；不得用于商业用途。
Forpersonal use only in study and research; not for commercial use.
仅供个人用于学习、研究；不得用于商业用途。
Nurfür den pers?nlichen für Studien, Forschung, zu kommerziellenZwecken verwendet werden.
Pourl 'étude et la recherche uniquement à des fins personnelles; pas àdes fins commerciales.
仅供个人用于学习、研究；不得用于商业用途。использоватьсяв коммерческих целях.
то л ь к о для людей, которые используются дляобучения, исследований и не должны