图 1 蛋白质多序列比对 Fig.1 Amultiplealignmentofproteinsequences
3 双序列比对算法
序列比对根据同时进行比对序列的数目分为两 两比对和多序列比对 。序列比对从比对范围考虑可 分为全局比对和局部比对 。全局比对考虑序列的全 局相似性 , 局部比对考虑 序列片段之间 的相似性 。 Needleman和 Wunsch于 1970年提出了双序列全局 比对 Needleman -Wunsch动 态 规 划 比 对 算 法 [ 5] 。 1975年 , Smith和 Waterman在 Needleman-Wunsch算 法的基础上 , 提出了改进的两序列局部比对 SmithWaterman算 法[ 6] 。 目 前 BLAST算 法[ 7] 和 SmithWaterman算法是寻 找局部最优相似片段最为广泛 的算法 。
Smith-Waterman算法先用迭代方法计算出两个 序列的所有可能相似性比较的分值 , 然后通过动态 规划的方法回溯寻找最优相似性比对 。
BLAST算法是目 前使用最广泛的数据库搜索 算法 , 基本思想是通过产生数量较少 , 但质量更好的 匹配片段来提高搜索速度 , 并把数据库搜索建立在 严格的统计学基础之上 。 算法描述为 :在数据库中 找出与查询序列相同的匹配字串 (hit), 且这一局部 字串中不含空位 ;一个匹配字串选中后 , 以此作为内 核向两端延伸 , 以找出尽可能长的相似序列片段 , 也 即高分片段对 HSP(highsequencepairs);设定一个 统计显著性阀值 E, 统计显著性大于 E的 HSP将被 舍弃 , 剩下的 HSP即为高质量的匹配片段对 [ 3] 。
2006年 , Joseph.J.和 Sasikumar.R.提出一种可 以识别两条全基因序列中所有局部相似片断的快速 算法 , 他们利用了序列自身的性质 ——— CGR点 。在 此基础上 , 运用蛋白质混沌游走表示法 (PCGR)[ 8] 来比较两蛋白质序列 , 根据 PCGR点之间的距离就 可以找出两序列之间的相同部分 。
序列比对问题可以定义 为一个五元数组 MSA =(∑ ', S, A, F), 其中 :
(1)∑ '=∑ ∪ {-}为序列比对的符号集 。 “ ”表示缺失的核苷酸或氨 基酸 , ∑表示四 个核苷酸 或 20个氨基酸字符集 。
(2)S ={S1 , S2 , …, SN}为序列集 , 其中 Si= Si1 , Si2 … SiLi, Sij∈ ∑ , Li为第 i个序列的长度 , i=1, 2…, N, j=1, 2, … , Li。
(5)序列比对问题 MSA就是通过适当的空位 插入 , 构建一个使 F(A)达到最大的比对 A。
在序列比对中 , 需要将序列间残基的相似转换
收稿日期 :2008 -11 -05;修回日期 :2009 -03 -10. 资助项目 :华中农业大学学科研究交叉基金 (2008XKJC008)。 作者简介 :文凤春 , 女 , 湖北武汉人 , 副教授 , 硕士 。 研究方向 :生物信息学 ;Email:wfc@.
Studyonbiologicalsequencealignmentalgorithms
WENFeng-chun, WANGBang-ju, XIAOZhi-hong
(SchoolofscienceHuazhongAgriculturalUniversity, Wuhan 430073, China) Abstract:Sequencealignmentisanimportantmethodinbioinformatics.Itiswidelyusedinsequencesplicing, proteinstructureprediction, proteinstructurefunctionanalysis, phylogeneticanalysis, databaseretrievalandprimerdesign.Thispaperintroducescommonlysequencealignmentalgorithmsatpresent, comparethecomputationalcomplexityofthesealgorithms, advantage, disadvantage andapplicablefields.Finallywepointedoutproblemsofsequencealignmentandstudydirection. KeyWords:Bioinformatics;SequenceAlignment;Algorithm;PCGRPoint
3.1 Smith-Waterman算法 Smith-Waterman算法主要寻找生物进化过程中
的局部保守区域 , 比全局比对更有生物意义 。 算法
主要分计算得分矩阵和寻找最佳相似片段对 。
其串行算法如下 :
用 F(i, j)表示序列的前缀 S[ 1] S[ 2] … S[ i-
1] S[ i]和序列 T的前缀 T[ 1] T[ 2] … T[ j-1] T[ j]
之间的最佳相似性比较的得分 。 则 F(i, j)的递推
公式如下 :
F(i, j)=max{f(i-1, j-1)+σ(S[ i] , T[ j] ), F (i-1, j)+σ(-, j), F(j, j-1)+σ(i, -), 0} (1)
其中 , F(0, 0)=F(i, 0)=F(0, j)=0;σ(x, y)
对的计算复杂度为 O(max{m, n})。 因此 , 当序列
的长度增加时 , 计算庞大的记分矩阵成为 Smith-Wa-
terman算法的一个瓶颈 。
3.2 基于 PCGR点蛋白质序列比对算法
假设有 n类氨基酸 , 则边长为 1的正多边形的
第 n个顶点坐标为 :
(cos(2kπ/n), sin(2kπ /n)), (k=1, 2, …, n)。
是一对字符的打分函数 , 当 x与 y匹配时 , σ(x, y)
=d;当 x与 y错配时 , σ(x, y)=-t;当 x或 y有缺
省时 , σ(-, x)=σ(y, -)=-k。 d, t, k为正数 。
设序列 S和 T的长度分别是 m和 n, 得分矩阵
的计算复杂度是 O(m×n), 用回溯方法求得最佳比
出相应的 PCGR距离 , 就可以知道从某位置开始有
多少个相同的氨基酸 。 如此一来 , 就可以直接跳过
这么多的氨基酸 , 接着再进行比对 , 运用 PCGR可以
找到两蛋白质序列所有局部比对结果 。
对于氨基酸 , 可以根据氨基酸的 R基团的结构
和性质将氨基酸四大类 , 也可以根据侧链 R基团的
结构分为 七大类 , 再 根据分 类的 情况计 算相 应的
这是一种启发式算法 。目前使用最广泛的多序列比 对程序 CLUSTALW[ 11] 就是渐进比对算法 。 隐马尔 科夫模型 HMM[ 12] (HiddenMarkovModels)是目前
第 8卷 第 1期 2 0 10年 3月
生物信息学 ChinaJournalofBioinformatics
Vol.8 No.1 Mar., 2010
生物序列比对算法的研究现状
文凤春 1 , 王邦菊1 , 肖枝洪1
(华中农业大学理学院, 湖北 武汉 430073)
摘要 :序列比对是生物信息学研究的一个重要工具 , 它在序列拼接 、蛋白质 结构预测 、蛋白质 结构功能分 析 、系 统进化分析 、数 据库检索以及引物设 计等问题的研究中被广泛使用 。 本文详 细介绍 了在生 物信息 学中常用 的一些 序列比 对算法 , 比 较了这 些算法所需的计算复 杂度 , 优缺点 , 讨论了各自的使用范围 , 并指出今后序列比对研 究的发展方向 。 关键词 :生物信息学 ;序列比对 ;算法 ;PCGR点 中图分类号 :TP301 文献标识码 :A 文章编号 :1672 -5565(2010)-01 -064 -04
1 引言
2 序列比对
生物信息学是在生命科学的研究中以数学和计 算机科学为手段对生物信息进行存储 、检索和分析 的科学 , 是当今生命科学与自然科学的重大前沿领 域之一 , 也是 21世纪自然科学的核心领域之一 。在 生物信息学中得到生物序列仅仅是第一步 , 如何处 理 、存储和分析这些数据 , 从中获得生物结构 、功能 的相关信息乃是基因组研究取得成果 的决定性步 骤 [ 1 -2] 。序列分析是生物信息学研究的一项重要的 手段 , 是了解基因组结构和功能的基本途径 。在序 列分析中 , 比对是最常用和最经典的研究手段 。最 常见的比对是蛋白质序列之间或核酸序列之间的两 两比对 , 通过比较两个序列之间的相似区域和保守 性位点 , 寻求同源结构 , 揭示生物进化 、遗传和变异 等问题 。序列比对也是数据库搜索算法的基础 , 将 查询序列与整个数据库的所有序列进行比对 , 迅速 地获得有关查询序列的大量有价值的参考信息 , 对 于进一步分析其结构和功能都会有很大的帮助 [ 3] 。
第 1期
文凤春 , 等 :生物序列比对算法的研究现状
65
成数值后进行比较 , 为了评价一个比对质量的优劣 , 需要给定一个记分系统 。 常见的记分系统有氨基酸 置换矩阵 PAM和区块氨基酸置换矩阵 BLOSUM。
序列比对中用空位插入来模拟生物分子进化过 程中的突变现象 , 寻找保守区域 , 以反映它们之间的 进化关系[ 4] 。 图 1为蛋白质多序列比对实例 。
(3)矩阵 A=(aij)N×M表示比对 的结果 , 其中
N
aij∈ ∑', miax{Li}≤M≤i∑i=1 Li。 矩阵 A满足 :行数等于序列的数目 ;如果移去
每一行中的 “ -”字符 , 将得到原来序列 ;每列中不 允许同时为 “ -”。
(4)F是比对 A的记分函数 , 用来评估比对 A 的优劣 。