| 核酸的相似性分析 
|  |
 |  |
| 二、生物序列比对中的算法 提 纲 背景知识 n序列相似性的比较 u两条序列的比对问题 u多序列的比对问题 u一些启发式的算法 生物序列比对中的并行算法 | DNA(1) 脱氧核糖核酸 DNA的分子组成 核甘(nucleotides) 磷酸盐(phosphate) 糖(sugar) 一种碱基 嘌呤(Adenine) ? 嘌呤(Guanine) ? 嘧啶(Cytosine) ? 腺嘧啶(Thymine |
| DNA(2) n碱基的配对原则 A(腺嘌呤)—T(胸腺嘧啶) C(鸟嘌呤)—G(胞嘧啶) 一个嘌呤基与一个嘧啶基通 过氢键联结成一个碱基对。 DNA分子的方向性 5'→3' DNA(3) DNA的双螺旋结构 碱基对之间的互补能力 DNA(4) DNA的复制 在DNA解旋酶的作用 下两条链分离开，分 别作为一个模板，在 聚合酶的作用下合成 一条新链。 |
RNA、转录和翻译 RNA(核糖核酸)：单链结构、尿嘧啶U代替胸腺嘧啶T、位于细胞核和细胞质中。 转录：DNA链 → RNA链 RNA(mRNA)，启动子。 翻译： mRNA上携带遗传信息在核糖体中合成蛋白质的过程。 变异 过程中由于不正确的复制，使DNA内容发生局部的改变。 变异的种类主要有以下三种： u替代(substitution) u插入或删除(insertion or deletion) indel u重排(rearrangement) |
| 蛋白质 由氨基酸依次链接形成在生物体中总共有20种氨基酸。 蛋白有十分复杂的三维结构。其三维机构决定了蛋白质的功能。 基 因 DNA上具有特定功能的一个片断，负责一种特定性状的表达。一般来讲，一个基因只编码一个蛋白质。 基因组 任何一条染色体上都带有许多基因，一条高等生物的染色体上可能带有成千上万个基因，一个细胞中的全部基因序列及其间隔序列统称为genomes（基因组）。 |  |
| 基因的编码 基因编码是一个逻辑的映射，表明存储在DNA和mRNA中的基因信息决定什么样的蛋白质序列。 每个碱基三元组称为一个密码子(codon) 碱基组成的三元组的排列共有43＝64种，而氨基酸共有20种类型，所以不同的密码子可能表示同一种氨基酸。 带来的问题 n序列排列问题 n基因组的重排问题 n蛋白质结构和功能的预测 n基因(外显子、内含子)查找问题 n序列装配(Sequence Assembly)问题 | 动机 在生物学的研究中，将未知序列同已知序列进行比较分析已经成为一种强有力的研究手段 ，生物序列相似性比较中绝大部分的问题在计算机科学领域中主要体现为字符串的匹配和查找 。 两条序列比对问题的分类 u全局比对(Global Alignment) u局部比对(Local Alignment) u空位罚分(Gap Penalty) 全局比对(1)－定义 n定义1：两个任意的字符 x和y，s(x,y)表示表x和y比较时的分值。 s(x,x)=2, s(x,y)= s(x,-)= s(-,y)=-1 n定义2：S= s1…sn和T=t1…tm，其全局比对A可以用序列S?和T?来表示，其中： (1) | S? | = | T? |； (2) 将S?和T?中的空字符除去后所得到的序列分别为S和T； 比对A的分值Score为：
|
 | 全局比对(2)－原始算法 输入：序列S和T，其中 | S | = | T | = n 输出：S和T的最优比对 for i=0 to n do for (S的所有的子序列A，其中| A | = i ) do for (T的所有的子序列B，其中| B | = i ) do 全局比对(3) 动态规划(Dynamic Programming) Bellman在50年代提出的 理论基础－最优化原理 弱点：the curse of dimensionality Smith-Waterman Algorithm |
| 全局比对(4) Smith-Waterman 算法 计算出两个序列的相似分值，存于一个矩阵中。(edit matrix、DP矩阵) 根据此矩阵，按照回溯的方法寻找最优的比对序列。 全局比对(5)
 | 计算edit matrix： for i = 0 to n do for j = 0 to m do Calculate V (i, j) using V (i - 1, j - 1), V (i, j - 1), V (i - 1, j) end 全局比对(6) 计算完edit matrix后，得到序列比对的最优分值，通过回溯（Traceback）的方法可获得序列的最优比对序列 。 回溯的算法： for ( i = | S |，j = | T |; i > 0 && j > 0;) { if (V[i, j ] = V[ i –1, j –1] + σ ( S[ i ], T[ j ])) { i – –; j – –; } else if (V[i, j ] = V[ i –1, j] + σ ( S[ i ], – )) { i – –; insert( ‘–’, T, j ); } else if (V[i, j ] = V[ i, j–1] + σ (–, T[ i ] )) { j – –; insert( ‘–’, S, i ); } } |
| 例： S = “a c g c t g”和T = “c a t g t” s(x,x)=2, s(x,y)= s(x,-)= s(-,y)=-1  三种可能的最优比对序列： 1.S: a c g c t g - T: - c – a t g t 2.S: a c g c t g - T: - c a – t g t 3.S: - a c g c t g T: c a t g - t - | 局部比对(1) 两条序列在一些局部的区域内具有很高的相似度。 在生物学中局部比对比全局比对更具有实际的意义。 局部比对(2)  局部比对(3) 对全局比对策略稍作修改可得到局部最优比对算法。 比对的路径不需要到达搜索图的尽头 ,如果某种比对的分值不会因为增加比对的数量而增加时，这种比对就是最佳的。 依赖于记分系统的性质：因为某种路径的记分会在不匹配的序列段减少 ,当分值降为零时，路径的延展将会终止，一个新的路径就会产生。 |
| 局部比对(4) S = “ a b c x d e x ”，T= “ x x x c d e ” 记分函数s(x,y)： s(x,x)=2, s(x,y)= s(x,-)= s(-,y)=-1  S = “ a b c x d e x ”，T= “ x x x c d e ” 局部最优比对是： c x d e c - d e 或 x - d e x c d e | 空位罚分(1) 空位:序列中任意连续的尽可能长的空格。 空位的引入是为了补偿那些插入或缺失，但是在序列的比对中引入的空位不能太多，否则会使序列的排列变得面目全非。 每引入一个空位，比对的分值都会有所扣除，常见的罚分规则主要有两种： u权值恒定模型 u仿射罚分模型 空位罚分(2) 权值恒定模型： 在每个空位中的空格的分值为零， 即：s(x,-)= s(-,y) = 0 比对的分值为： 其中，Wg为开放一个空位的罚分 空位罚分(3) 仿射罚分模型(Affine Gap Model) 用一个附加的罚分比例去乘空位的长度 Wg+q×Ws 空位罚分(4) 初始条件： V(0, 0) = 0; V(i, 0) = E(i, 0) = Wg + iWs; V(0, j) = F(0, j) = Wg + jWs; 递归条件： V(i, j) = max { G(i, j), E(i, j), F(i, j)}; G(i, j) = V(i-1, j-1) +σ(S[i], T[j]); E(i, j) = max {E(i, j-1) + Ws, V(i, j-1) + Wg + Ws} F(i, j) = max {F(i-1, j) + Ws, V(i-1, j) + Wg + Ws}. |
| 利用动态规划计算序列最优比对的算法的复杂度分析： t时间复杂度；O(mn) 多序列比对(1) 两条序列比对问题的一般化推广 动机：携带更多的消息。 DNA或蛋白质数据库容量的指数级的增长，即使使用很简单的记分函数也很难找到一种在有效时间内的解决方法，而几乎所有的近似算法和许多的启发式算法，实际上都是在算法的计算速度和获得最佳比对结果的敏感性之间寻找一种权衡策略。 | 多序列比对(2) rigorous算法 两条序列 多条序列， NP hard tree_based算法和 iterative算法 首先从序列中找出两条相似度最大的比对，然后按照相似度递减的顺序连续添加一些序列到最优的比对序列中。 序列非常接近 原始算法基础上的近似算法，但是它们也是非常耗时的。 |
| 多序列比对(3) 记分方法：用函数δ(x, y)来计算字符x和y之间的距离，两个序列的比对的距离分值我们用V来表示 条序列比对的分值：为k条序列中任意两条序列(共有Ck2条)的分值(距离)V之和，用SP (Sum_of_Pairs)来表示 
| 中心星算法 输入：一组含有k条序列的集合? 找出序列St，St∈?，使得∑i≠tD( Si, St)的值最小，令A = { St } 逐次地添加Si∈?-{St}到A中，并使Si与St的比对的值最小；假设S1，S2，…Si-1已添加到A中，由于在分别和St进行比对的过程中需要加入一些空格，故此时A为：A = {S1’，S2’，…Si-1’，S’t}。添加Si到A中，按照两条序列比对的动态规划算法比较S’t和Si，分别产生新的序列St’’和Si’，再按照St’’中添加空格的位置调节序列S1’，S2’，…Si+1’为S1’’，S2’’，…Si-1’’，并用St’’替换St。 启发式算法-FASTA 基本思想是：一个能够揭示出真实的序列关系的比对至少包含一个两个序列都拥有的字(片断)，把查询序列中的所用字编成索引，然后在数据库搜索时查询这些索引，以检索出可能的匹配，这样那些命中的字很快被鉴定出来。 1.确定参数ktup，在两个序列中查找长度为ktup的、相匹配的片段(增强点)。为了提高速度，可以通过查询表格或hash表来完成，然后在表格中搜索与另一条序列相匹配的、长度为ktup的片段。 2.在同一条对角线中临近的增强点成为一个增强段。每一个增强点都赋予一个正的分值，一个增强段中相邻的两个增强点之间的不匹配区域赋予一定的负值。一个增强段对应于一段相匹配的子序列，分值最高的段被标记为init1。 |
| 3.引入indel。把那些没有重叠(non-overlap)的增强段拼接起来(增强段的分值之和减去空位处罚)。分值最高的区域记为initn。 4.对最有可能的匹配序列进一步评分：以增强段init1所在的对角线为中心，划分出一个较狭窄的对角线带，利用S-W算法，来获得分值最高的局部比对，记作opt。 5.决定采用initn或opt的分值，前者敏感度低但速度快。FASTA对每一个检索到的比对都提供一个统计学显著性的评估，以判断该比对的意义。
FASTA对DNA序列搜索的结果要比对蛋白质序列搜索的结果更敏感。它对数据库的每一次搜索都只有一个最佳的比对，一些有意义的比对可能被错过。 | 启发式算法-BLAST 基本思想是：通过产生数量更少的但质量更好的增强点来提高速度。 BALST算法是建立在严格的统计学的基础之上的。它集中于发现具有较高的相似性的局部比对，且局部比对中不能含有空位。 由于局部比对的限制条件，在大多数情况下比对会被分解为若干个明显的HSP(High-score Sequence Pairs)。 1.首先确定一个终止值S、步长参数w和一个阈值t ，S值通常是基于统计学的原理指明一个预期的终止E值，然后软件会在考虑搜索背景性质的基础上计算出合适的S值。使要比对的序列中包含一个分值不小于S的HSP。 2.引入邻近字串的思想：不需要字串确切地匹配，当有一个字串的分值高于t时，BALST就宣称找到了一个选中的字串。为了提高速度，允许较长的字串长度W。W值很少变化，这样，t值就成为权衡速度和敏感度的参数。 |
| 3.一个字串选中后，程序会进行没有空位的局部寻优，比对的最低分值是S，当比对延伸时会遇到一些负的分值，使得比对的分值下降，当下降的分值小于S时，命中的延伸就会终止。这样系统会减少消耗于毫无指望的选中延伸的时间，使系统的性能得以改进。 BLAST的改进 n在1997年提出了对BLAST程序的改进算法，提高了搜索速度、敏感度和实用性。 可处理间隔(gap)的gapped BLAST算法 PSI-BLAST算法 对一个选中字串长度标准的延伸 利用profile(表头文件)的数据结构来进行搜索 算法 扩大步长，以步长为2w来搜索。 允许位于不同的对角线的两个片段拼接在一起。位于不同对角线的两个片段拼接在一起的前提条件是：拼接后片段的分值不小于某一个终止值。 执行通常的BLAST算法，使用一种不同的记分方式，根据高度显著比对(HSPs)的最高分值建立一个最初的profile。 根据该profile反复利用BLAST算法对数据库进行搜索，这一步实际上是根据表头文件的统计结果扩展局部比对。这一过程是反复进行的，直到再没有发现新的有意义的匹配为止。由于在每一轮都会有新的片段加入，因此在操作过程中profile需要在每一个循环结束之后更新。 | 为适应同源比较的不通情况，BLAST得到了各种各样的补充和发展，形成了一个程序家族。 程序名 检索序列 数据库序列 BLASTP 蛋白质 蛋白质 BLASTN 核苷酸 核苷酸 BLASTX 核苷酸 蛋白质 TBLASTN 蛋白质 核苷酸 Substitution Matrix PAM 250 BLOSUM62 在SUN10000上进行BLAST的测试： 借助于一些比最初的动态规划算法更快的启发式算法。 借助硬件来完成动态规划的算法 采用高性能计算系统，把问题有效地分配到多个处理器上运行，最后再把各处理器的运算结果收集起来
|
生物序列比对中的并行算法
两条序列比对的并行算法 据序列的相似性比较，找出两者的最佳匹配 找出从一条序列转化到另一条序列的最佳路径 核心：动态规划 
 | 
动态规划的并行计算
基于流水线的动态规划算法 反对角线的动态规划算法 反对角线分块的动态规划算法 粗粒度分块策略 细粒度分块策略 H-V(Horizontal-Vertical )分块策略 多序列比对的并行算法 利用预测计算（Speculative computation）技术的并行算法 分而治之策略的并行算法 Berger_Munson算法 best_score=initial_score(); while(stop criteria is not met){ 1 current_score=calculate(seq,gap_positions); 2 flag=decide(current_score, best_score); 3 seq=modify(seq,flag,gap_positions);}
|
| 第一步：首先输入n条序列，任意分成两组。然后开始计算这两组序列之间的两条序列的比对分值，在这一步中新的空位的位置gap_positions被保存下来以备第三步调用 。 第二步：设置一个标记flag，如果一个新的比对的分值高于当前的最佳比对队列的分值，则flag标记为A( Accepted )，否则标记为R( Rejected )； 第三步：如果在第二步中flag标记为A，则根据第一步中的gap_positions来修改当前的比对队列，以作为下一次迭代的初始值，同时更新比对队列的分值，当连续遇到q个R时，算法结束。 | Berger_Munson算法的并行化 每一次迭代内的三个阶段是相互依赖；第i次迭代可能会用到第i-1次迭代的结果。 预测计算的基本思想是：利用当前状态的输入参数来推断未来状态的计算结果。 如果有连续的迭代被标记为R，那么这些迭代之间是相互独立的，可以并行处理。 |
| 三 、BLAST简介 
1、获取BLAST软件的途径 可以通过e-Mail、WWW或控制台命令操作BLAST程序，无论如何，一次数据库搜索包括四种基本元素：BLAST程序的名称，数据库名称，查询序列和大量的合适的参数，很显然，当以上元素发生变化时，搜索的细节就会随之改变。 | 要得到关于用e-Mail执行BLAST搜索的介绍，给blast@ncbi.nlm.nih.gov发一封含有“HELP”的邮件；在WWW工具中，帮助是在线的；如果使用Unix系统，使用man blast可以获得详细的帮助信息。 
|
| 2、 BLAST 算法 Blast使用预先索引的数据库 每个数据库的条目位置被记录 执行查询 —将查询序列分成“Words” —在数据库中查找这些“words” (对每个“words”也寻找类似的“words”) —当查询序列中两个间隔一定距离的非重叠的“Words”，可以与数据库的条目匹配，则这两个序列被称为segment pair —segment pair一直扩展直到分数下降到一定程度S —每个数据库的条目都这样依次计算 —按统计重要性输出数据库的条目 | 基本思想是：通过产生数量更少的但质量更好的增强点来提高速度。 BALST算法是建立在严格的统计学的基础之上的。它集中于发现具有较高的相似性的局部联配，且局部联配中不能含有空位。 由于局部联配的限制条件，在大多数情况下联配会被分解为若干个明显的HSP(High-score Sequence Pairs)。 §首先确定一个终止值S、步长参数w和一个阀值t(类似“Words”_） ，S值通常是基于统计学的原理指明一个预期的终止E值，然后软件会在考虑搜索背景性质的基础上计算出合适的S值。 §引入邻近字串的思想：不需要字串确切地匹配，当有一个字串的分值高于t时，BALST就宣称找到了一个选中的字串。为了提高速度，允许较长的字串长度W。W值很少变化，这样，t值就成为权衡速度和敏感度的参数。 §一个字串选中后，程序会进行没有空位的局部寻优，联配的最低分值是S，当联配延伸时会遇到一些负的分值，使得联配的分值下降，当下降的分值小于S时，命中的延伸就会终止。这样系统会减少消耗于毫无指望的选中延伸的时间，使系统的性能得以改进。 |
 | PSI-BLAST Position Specific Iterated BLAST 基于第一次Blast，构建PSSM(Position specific scoring matrix) 再循环进行多次的Blast搜索，并修改PSSM直到重要的匹配在PSSM中找到 加入了残基重要性判断，提高了敏感度和实用性。 只适合蛋白质序列 执行通常的BLAST算法，使用一种不同的记分方式，根据高度显著联配(HSPs)的最高分值建立一个最初的profile。 根据该profile反复利用BLAST算法对数据库进行搜索，这一步实际上是根据表头文件的统计结果扩展局部联配。这一过程是反复进行的，直到再没有发现新的有意义的匹配为止。由于在每一轮都会有新的片段加入，因此在操作过程中profile需要在每一个循环结束之后更新。 |
 |  |
| 使用BLAST的核苷酸序列数据库 描述 数据库情况 nr 极有价值的GenBank，排除了EST，STS和GSS部分 month nr 字集，每月（30天）更新，搜集了过去30天中的最新序列 est Genbank中的EST部分（expressed sequence tags, 表达序列标签） sts Genbank中的STS部分 (sequence tagged sites， 序列标签位点) htgs Genbank中的HTG部分 (high throughput genomic sequences， 高容量基因组序列) gss GSS(genome survey sequences，基因组测定序列)。
yeast 酵母的全基因组序列。
ecoli 大肠杆菌的全基因组序列。
mito 脊椎动物线粒体的全基因组序列。
Alu-repeats 搜集了灵长类动物的Alu重复序列。
vector 搜集了流行的带菌体的克隆。 |
使用BLAST的蛋白序列数据库 数据库 描述 nr 非冗余数据库（ non-redundant database）。All non-redundant GenBank CDS translations+RefSeq roteins+PDB+SwissProt+PIR+PRF month nr的子集，每月（30天）更新，搜集了过去30天中的最新序列。 Swissprot Swiss-Prot数据库。 pdb 拥有三维空间结构的原子坐标的氨基酸序列库。 yeast 由酵母基因组中基因编码的全套蛋白质。 ecoli 有大肠杆菌基因组中基因编码的全套蛋白质。 Drosophila genome |
| 一些对于BLAST很有用的参数值 参数名称 BLAST 2.0 数据库 (database) -d database 查询序列文件 (query sequence file) -I filename 期望阈值E (expectation cutoff) -e number HSP分值阈值S (HSP score cutoff) -s number 字串分值阈值T (word score cutoff) -f number 多命中窗口A (multihit window) -A number 打分矩阵 (score matrix) -M matrix 低复杂度过滤 (low-complexity filtering) -F 空位开放罚分 (gap opening penalty) -G number 空位拓展罚分 (gap extension penalty) -E number PSI-BLAST反复 (PSI-BLAST iterations) -j number | 因特网上的软件 CULSTALW ftp://ftp.ebi.ac.uk/pub/software/ DOTTER ftp://ftp.sanger.ac.uk/pub/dotter/ LALIGN，FASTA ftp://ftp.virginia.edu/pub/fasta/ BLAST ftp://ncbi.nlm.nih.gov/blast/ SEG ftp://ncbi.nlm.nih.gov/pub/seg/ 4、 以一条序列为例说明如何进行BLAST分析操作？  |
 |  |
 |  |
 |  |
 | 对2条序列的BLAST比较进行操作说明 BLAST比较结果中的3点说明： 蛋白质和核酸中都会包括低复杂度区域（LCR —low complexity regions），即这些区域的组成有某些偏好，比如DNA中的简单重复序列(ct)n等。在蛋白质中一些残基过多表现。在进行BLAST比较时，将会把LCR屏蔽掉，防止它们过高评价匹配的显著性。在核酸中用n、在蛋白质中用X代替。 在核酸比较结果中，上下相同的序列用竖线连接。在蛋白质序列比较结果中，上下相同的序列中间直接列出；如果比对的氨基酸不同，但结构类似则用 “+”号连接。 HSP Score （高分片段配对分值）越高， E Value（偶然选中这片段的可能性）越小，就越能提供进化同源的证据. |
 | >Protein IELFFILSSIWLGRFYYVFGFLLIVLVLLVIVCAEVSVVLTYMN LCVEDWRWWWKAFFASGSVAIYVFLLYSINYLVFDLRSLSGP VSAMLYLGYSFLMAFAIMLATGTIGFLTSFSFVHYLFSSKID
 |
 |  |
| 核酸的多序列比对 1、Clustwal W简介和使用—— 进行核酸或蛋白质的多序列的比较 网址： http://www.ebi.ac.uk/clustalw http://www.ddbj.nig.ac.jp/search/clustalw-e.html
| 对Clustal W比较结果的说明：http://www.ebi.ac.uk/clustalw/help.html “*” means that the residues or nucleotides in that column are identical in all sequences in the alignment. “:” means that conserved substitutions have been observed。 “.” means that semi-conserved substitutions are observed. |
| Show Colors A button labeled 'Show Colors' will be displayed in the Alignment section of results page. If you press this button the alignment will be show in color according to the table below. ?AVFPMILW RED Small (small+ hydrophobic (incl.aromatic -Y)) ?DE BLUE Acidic ?RHK MAGENTA Basic ?STYHCNGQ GREEN Hydroxyl + Amine + Basic - Q ?Others Gray 以蛋白质多条序列为例，说明操作过程 蛋白质： AAR19268 (rice)， 核酸： AY4456727(rice) A35162 (Hordeum ) C83374(Avena) A84592（rice） |
评论