两序列比对算法.docx

两序列比对算法摘要: 序列比对是生物信息学研究的一个基本方法, 对于发现生物序列中的功能、结构和进化信息具有重要的意义。两序列比对中,典型的全局比对算法是 Needleman — Wunsch 算法; 局部比对算法的基础是 Smitll — Waterm an 算法,本文对典型的双序列比对算法进行描述。关键词:生物信息学;两序列比对;算法引言: 为了满足基因组中获得更多更有价值的信息, 生物信息学迅速发展起来, 生物信息学是一门多门科学交叉的学科,将数学、计算机科学应用于生物大分子信息的获取、加工、存储、分类、检索和分析等,以达到阐明和理解大量数据所蕴含的生物学意义的目的。通过对 DNA 和蛋白质序列进行相似性比较, 指明序列间的保守区域和不同之处, 为进一步研究它们在结构、功能以及进化上的联系提供了重要的参考依据。而序列比对就是运用某种特定的数学模型或算法, 找出两个或多个序列之间的最大匹配碱基或残基数, 比对的结果反映了算法在多大程度上反映了序列之间的相似性关系以及它们的生物学特征。双序列比对算法双序列比对分为全局比对和局部比对, 全局比对是考察两个序列之间的全局相似性, 局部比对则比较序列片段之间的相似性。 Needleman — Wunsch 算法是典型的全局比对算法,适用于全局水平上相似性程度较高的两个序列; Smitll — Waterman 算法适用于寻找局部相似序列对, 该算法是目前被使用最广泛的序列相似性比较算法之一,由所熟悉的 Needleman — Wunsch 算法演变而来。 Needleman-Wunsch 算法使用迭代方法计算出两个序列的相似分值,存于一个得分矩阵中,然后根据这个得分矩阵, 通过动态规划的方法回溯寻找最优的比对序列。具有很高的灵敏度使用二维表格, 一个序列沿顶部展开, 一个序列沿左侧展开。而且也能通过以下三个途径到达每个单元格: 1. 来自上面的单元格, 代表将左侧的字符与空格比对。 2. 来自左侧的单元格, 代表将上面的字符与空格比对。 3. 来自左上侧的单元格, 代表与左侧和上面的字符比对( 可能匹配也可能不匹配)。该单元格的值来自于一下 3 个中的最大值:(1 )上方的值-2(2 )左边的值-2(3 )如果该单元格所在的行于所在的列对应的字符相等,则为左上值加 1 ,否则为左上值-1。 Smitll — Waterman 算法 Smitll — Waterm an 算法主要分两步,计算得分矩阵和寻找最佳相似片段对。对于两个序列 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] " 的前缀之间的最佳相似性比较的得分。那么就有以下公式: 通过公式, 可得到得分矩阵, 得到得分矩阵以后, 用动态规划回溯的方法找到局部最大相似片段对。先找到得分矩阵中最大的元素,然后按照该元素原计算路径一步一步往前回溯,直到回溯到" 时停止。从得到的回溯路径可以得到其正向路径, 就是