第三章序列对比与数据库搜索(上)

1、第三章第三章序列对比和数据库搜索序列对比和数据库搜索(上)1 1 序列对比概述序列对比概述概念与背景概念与背景 通过知识的比较分析通过知识的比较分析, ,获取有用的信息是科学研究中一个获取有用的信息是科学研究中一个最常用和最经典的研究手段最常用和最经典的研究手段, ,它可以将研究对象相互比较它可以将研究对象相互比较来寻找对象可能具备的特性。来寻找对象可能具备的特性。 生物信息学中从核酸、氨基酸的一级结构分析序列的相生物信息学中从核酸、氨基酸的一级结构分析序列的相同点和不同点同点和不同点, , 能够推测它们的结构、功能以及进化上能够推测它们的结构、功能以及进化上的联系。的联系。 最常用的方法就是

2、序列对比最常用的方法就是序列对比, ,它为两个或更多个序列的残它为两个或更多个序列的残基之间的相互关系提供了一个非常明确的图谱。基之间的相互关系提供了一个非常明确的图谱。 通过比较两个序列之间的相似区域和保守位点通过比较两个序列之间的相似区域和保守位点, ,可寻找二可寻找二者之间可能的分子进化关系。者之间可能的分子进化关系。 进一步的对比是将多个蛋白质或核酸同时进行进一步的对比是将多个蛋白质或核酸同时进行比较比较, ,来寻找这些有进化关系的序列之间的共同来寻找这些有进化关系的序列之间的共同保守区域、位点和图谱保守区域、位点和图谱, ,分析产生共同功能的序分析产生共同功能的序列模式。列模式。 把

3、蛋白质序列与核酸序列相比较，来探索核酸把蛋白质序列与核酸序列相比较，来探索核酸序列可能的表达框架。序列可能的表达框架。 把蛋白质序列与具有三维结构信息的蛋白质相把蛋白质序列与具有三维结构信息的蛋白质相比比, ,从而获得蛋白质空间结构的信息，预测功能。从而获得蛋白质空间结构的信息，预测功能。概念与背景概念与背景 随着随着DNADNA测序方法的飞速发展测序方法的飞速发展, ,序列信息量急增序列信息量急增, , 使可使可供比较的序列数量呈现爆炸式增长。将未知序列同整供比较的序列数量呈现爆炸式增长。将未知序列同整个数据库中的已知序列进行比较分析已经成为一个强个数据库中的已知序列进行比较分析已经成为一个

4、强有力的研究手段。有力的研究手段。 序列比较的各种算法发展得也越来越快序列比较的各种算法发展得也越来越快, ,也越来越成熟。也越来越成熟。 序列比较可快速地获得有关序列的大量有价值的参考序列比较可快速地获得有关序列的大量有价值的参考信息信息, ,对于进一步分析其结构和功能有很大的帮助。对于进一步分析其结构和功能有很大的帮助。 对比是数据库搜索的基础，随着生物信息数据和生物对比是数据库搜索的基础，随着生物信息数据和生物学知识大量积累学知识大量积累, ,通过对比方法可以有效地分析和预测通过对比方法可以有效地分析和预测一些新发现的基因和蛋白质的功能。一些新发现的基因和蛋白质的功能。2 2 序列对比和

5、数据库技术序列对比和数据库技术序列对比原理与理论来源序列对比原理与理论来源： 序列比对的理论基础是进化学说，如果两个序列之间具序列比对的理论基础是进化学说，如果两个序列之间具有足够的相似性，就推测二者可能有共同的进化祖先。有足够的相似性，就推测二者可能有共同的进化祖先。它们是经过序列内残基的替换、残基或序列片段的缺失、它们是经过序列内残基的替换、残基或序列片段的缺失、以及序列重组等遗传变异过程分别演化而来。以及序列重组等遗传变异过程分别演化而来。 生物物种之间存在进化关系生物物种之间存在进化关系, , 对基因和蛋白质序列进行对基因和蛋白质序列进行比较比较, ,从本质上来讲从本质上来讲, ,是进

6、行进化论一样的比较分析是进行进化论一样的比较分析, ,只不只不过更加精细过更加精细, ,更加详尽。如果两个序列之间具有足够的更加详尽。如果两个序列之间具有足够的相似性相似性, ,就推测二者可能有共同的进化祖先就推测二者可能有共同的进化祖先, ,它们有可能它们有可能经过序列内残基的替换、残基或序列片段的缺失以及序经过序列内残基的替换、残基或序列片段的缺失以及序列重组等遗传变异过程演化而来。列重组等遗传变异过程演化而来。序列对比原理与理论来源：序列对比原理与理论来源： 序列相似和序列同源是不同的概念序列相似和序列同源是不同的概念, ,序列之间的相似程序列之间的相似程度是可以量化的参数度是可以量化的

7、参数, ,而序列是否同源需要有进化事实而序列是否同源需要有进化事实的验证。的验证。 目前大多数对比方法能够在某种程度上建立分子进化目前大多数对比方法能够在某种程度上建立分子进化的模型。通常假定同源序列是从某一共同祖先不断变的模型。通常假定同源序列是从某一共同祖先不断变化而来化而来, ,祖先序列在进化过程中分子发生取代、插入以祖先序列在进化过程中分子发生取代、插入以及缺失的变化。及缺失的变化。 在序列比较中在序列比较中, ,对同源基因或蛋白质序列相互比较时对同源基因或蛋白质序列相互比较时, ,残基之间相互对应残基之间相互对应, ,可使取代情况很明显地表现出来。可使取代情况很明显地表现出来。残基一

8、残基对比残基一残基对比 在残基一残基对比中,某些氨基酸残基相对于其他位置的残基具有较高的保守性,这些残基对于一个蛋白质的结构和功能是极为重要的。 处于活性位点的残基都是极为保守的,比如形成二硫键的半光氨酸,参与电子传递的氨基酸残基以及决定底物特异性的氨基酸残基。这些保守的残基对于保持蛋白的结构与功能非常重要。Alignment:GACGGATTAG GATCGGAATAG残基一残基对比残基一残基对比 要注意某些保守位置对蛋白功能无重要性，只是要注意某些保守位置对蛋白功能无重要性，只是进化史的反映进化史的反映 。 处理非常相近的物种时要必须十分小心处理非常相近的物种时要必须十分小心,因为相似因为

9、相似性在某些情况下更多地是历史的反映性在某些情况下更多地是历史的反映,而不是功能而不是功能的反映。的反映。 例如：例如：Mouse和和Rat的某些序列具有高度的相的某些序列具有高度的相似性似性,可能仅仅是因为没有足够的时间进行分化而可能仅仅是因为没有足够的时间进行分化而已。已。序列对比的误差与相似性标准序列对比的误差与相似性标准 序列对比是从已知获得未知的一个十分有效的序列对比是从已知获得未知的一个十分有效的方法。如通过将一个新的蛋白同其他已知结构方法。如通过将一个新的蛋白同其他已知结构功能的蛋白比较功能的蛋白比较,可推断新蛋白的结构与功能。可推断新蛋白的结构与功能。 例如，可得到酶的活性位点

10、残基例如，可得到酶的活性位点残基,形成二硫键形成二硫键的半脱氨酸残基的半脱氨酸残基,与配体结合部位的残基及与与配体结合部位的残基及与金属离子结合的残基金属离子结合的残基,形成特定结构形成特定结构motif的残的残基等。基等。序列对比的误差与相似性标准序列对比的误差与相似性标准 有些保守的残基不一定是结构功能重要的残基，有些保守的残基不一定是结构功能重要的残基，它们可能只是进化历史保留的结构。如果两个序它们可能只是进化历史保留的结构。如果两个序列有显著的保守性列有显著的保守性,要确定二者要确定二者具有共同的进化历具有共同的进化历史史,可认为二者有近似的结构和功能。除此之外，可认为二者有近似的结构

11、和功能。除此之外，还需要更多实验和信息的支持。还需要更多实验和信息的支持。 通过大量实验和序列对比的分析通过大量实验和序列对比的分析,一般认为蛋白质一般认为蛋白质的结构和功能比序列具有更大的保守性的结构和功能比序列具有更大的保守性,如果序列如果序列之间的之间的相似性超过相似性超过30%，认为它们很可能同源。，认为它们很可能同源。 序列对比的结果只提供了序列进化的理论可能性，序列对比的结果只提供了序列进化的理论可能性，还需要实验验证。还需要实验验证。 3 3 序列对比的方法学序列对比的方法学 早期的序列对比是全局的序列比较早期的序列对比是全局的序列比较,但由于蛋白质但由于蛋白质具有的模块性质具有

12、的模块性质,可能由于外显子的交换而产生新可能由于外显子的交换而产生新蛋白质蛋白质,因此局部对比会更加合理。因此局部对比会更加合理。 常用常用打分矩阵打分矩阵描述序列两两对比描述序列两两对比,两条序列分别作两条序列分别作为矩阵的两维为矩阵的两维,矩阵点是两维上对应两个残基的相矩阵点是两维上对应两个残基的相似性分数似性分数,分数越高则说明两个残基越相似。因此分数越高则说明两个残基越相似。因此,序列对比问题变成在矩阵里寻找最佳对比路径。序列对比问题变成在矩阵里寻找最佳对比路径。目前最有效的打分方法目前最有效的打分方法: Needleman-Wunsch动态规划算法动态规划算法 改良改良Smith-W

13、aterman算法算法 SIM算法算法 在在FASTA程序包中可以找到用动态规划算法程序包中可以找到用动态规划算法进行序列对比的工具进行序列对比的工具LALIGN,它能给出多个不它能给出多个不交叉的最佳对比结果。交叉的最佳对比结果。序列对比的任务与目的序列对比的任务与目的 序列比较的根本任务是：序列比较的根本任务是：发现序列之间的相似性发现序列之间的相似性辨别序列之间的差异辨别序列之间的差异 目的：目的：相似序列相似序列 相似的相似的结构，相似的功能结构，相似的功能 判别序列之间的同源性判别序列之间的同源性推测序列之间的进化关系推测序列之间的进化关系 序列的相似性比较序列的相似性比较 同源（同

14、源（homology）- 具有共同的祖先具有共同的祖先 直向同源（直向同源（Orthologous ） 共生同源（共生同源（paralogous ） 相似（相似（similarity）同源序列一般是相似的同源序列一般是相似的 相似序列不一定是同源的相似序列不一定是同源的 进化趋同（同功能）进化趋同（同功能）直向同源（直向同源（a1 in species I, a1 in species II)共生同源（共生同源（a1 and a2 in species I）进化趋同进化趋同水平转移水平转移基因复制基因复制序列的相似性描述序列的相似性描述 定性的描述定性的描述 定量的数值定量的数值 相似度相似度

15、 距离距离序列比较的基本操作序列比较的基本操作- -比对（比对（AlignmentAlignment） 两个序列的比对是指这两个序列中各个字符的一种对两个序列的比对是指这两个序列中各个字符的一种对应关系，或对比排列应关系，或对比排列 。设有两个序列：GACGGATTAG，GATCGGAATAGAlignment2: GA CGGATTAGGATCGGAATAGAlignment1:GACGGATTAG GATCGGAATAG序列表示与字母表序列表示与字母表 字母表字母表 4字符字符DNA字母表：字母表：A, C, G, TA, C, G, T 扩展的遗传学字母表或扩展的遗传学字母表或IUPAC

16、编码编码 单字母氨基酸编码单字母氨基酸编码扩展的遗传学字母表或扩展的遗传学字母表或IUPACIUPAC编码编码符符 号号含含 义义说说 明明GGGGGuanine Guanine 鸟嘌呤鸟嘌呤A AA AAdenine Adenine 腺嘌呤腺嘌呤T TT TThymine Thymine 胸腺嘧啶胸腺嘧啶CCCCCytosineCytosine胞嘧啶胞嘧啶R RG or AG or APurine Purine 嘌呤嘌呤Y YT or CT or CPyrimidine Pyrimidine 嘧啶嘧啶MMA or CA or CAmino Amino 氨基的氨基的K KG or TG or

17、TKeto Keto 酮基的酮基的S SG or CG or CStrong interaction (3 H bonds) Strong interaction (3 H bonds) 强的强的WWA or TA or TWeak interaction (2 H bonds) Weak interaction (2 H bonds) 弱的弱的H HA or C or TA or C or TNot-GNot-G非非鸟嘌呤鸟嘌呤B BG or T or CG or T or Cnot-Anot-A非非腺嘌呤腺嘌呤V VG or C or AG or C or Anot-T(not-U) no

18、t-T(not-U) 非胸腺嘧啶非胸腺嘧啶D DG or A or TG or A or Tnot-C not-C 非胞嘧啶非胞嘧啶N NG or A or T or CG or A or T or CAny Any 任何任何序列描述特定的表示符号序列描述特定的表示符号 代表字母代表字母 A* 代表由字母表代表由字母表A中字符所形成的一系中字符所形成的一系列有限长度序列或字符串或序列的集合列有限长度序列或字符串或序列的集合 a、b、c代表单独的字符代表单独的字符 s、t、u、v代表代表A*中的序列中的序列 |s|代表序列代表序列s的长度的长度序列表示法序列表示法 为了说明一个序列的为了说明一个

19、序列的s s子序列和该子序列中的单个字子序列和该子序列中的单个字符，在符，在s s子序列中各字符之间用数字标明分割边界。子序列中各字符之间用数字标明分割边界。n例如，设例如，设s=ACCACGTAs=ACCACGTA，则，则s s可表示为可表示为 0 0A A1 1CC2 2CC3 3A A4 4CC5 5GG6 6T T7 7A A8 8 ni i:s:s:j j 指明第指明第i i位或第位或第j j位之间的子序列位之间的子序列, ,n当然，当然，0 0 i i j j |s| |s|。n子序列子序列0 0:s: :s: i i 称为前缀，即称为前缀，即prefix(s,prefix(s,i

20、i) )n子序列子序列 i i:s:|s|:s:|s|称为后缀，即称为后缀，即suffix(s, |s|-suffix(s, |s|-ii+1) +1) ni:s: i 为空序列为空序列nj-1:s:j 表示表示s 中的第中的第j 个字符，简记为个字符，简记为sj子序列与子串表示法子序列与子串表示法n子序列：子序列：选取选取s中的某些字符或删除中的某些字符或删除s中的某些字符而形成的中的某些字符而形成的子序列子序列 例如：例如： TTT 是是 ATATAT的子序列。的子序列。n s的子串：的子串：是由是由s中相继的字符所组成。中相继的字符所组成。 例如：例如： TAC是是AGTACA的子串的子

21、串但不是但不是TTGAC的子串（是子序列）。的子串（是子序列）。 n注意：注意：子串是子序列；子序列不一定是子串子串是子序列；子序列不一定是子串序列比较的四种基本情况序列比较的四种基本情况（1 1）两条长度相近的序列相似，找出序列的差别）两条长度相近的序列相似，找出序列的差别（2 2）判断一条序列的前缀与另一条序列的后缀相似）判断一条序列的前缀与另一条序列的后缀相似（3 3）判断一条序列是不是另一条序列的子序列）判断一条序列是不是另一条序列的子序列（4 4）判断两条序列中是否有非常相似的子序列）判断两条序列中是否有非常相似的子序列相似性定量计算相似性定量计算-编辑距离（编辑距离（Edit Di

22、stance)Edit Distance)GCATGACGAATCAG TATGACAAACAGC GCATGACGAATCAG TATGAC-AAACAGC 说明两条序列的相似程度说明两条序列的相似程度 两条序列的相似程度计算两条序列的相似程度计算n相似度：相似度： 它是两个序列的函数，其值越大，表示两个序列越相似它是两个序列的函数，其值越大，表示两个序列越相似 。n距离：距离： 两个序列之间的距离越大，则两个序列的相似度就越小。两个序列之间的距离越大，则两个序列的相似度就越小。 序列转化与字符编辑操作序列转化与字符编辑操作（Edit OperationEdit Operation） 字符编

23、辑操作可将一个序列转化为一个新序字符编辑操作可将一个序列转化为一个新序列列 n匹配匹配 Match（a，a）n删除删除 Delete（a，-） n替代替代 Replace（a，b）n插入插入 Insert（-，b）其他扩展的编辑操作其他扩展的编辑操作ACCGACAATATGCATA ATAGGTATAACAGTCAACCGACAATATGCATA ACTGACAATATGGATA 首尾颠倒原理首尾颠倒原理-反向互补序列反向互补序列RNA发夹式二级结构发夹式二级结构矩阵序列比较矩阵序列比较 矩阵序列比较也叫矩阵序列比较也叫“矩阵作图法矩阵作图法” 或或 “对角线作对角线作图图”。子序列矩阵标记子

24、序列矩阵标记序列1 序列序列2 两序列比较两序列比较 序列序列1 序列序列1 自我比较滑动窗口技术滑动窗口技术两条序列中有很多匹配的两条序列中有很多匹配的字符对，因而在矩阵中会字符对，因而在矩阵中会形成很多点标记。使用滑形成很多点标记。使用滑动窗口代替一次一个位点动窗口代替一次一个位点的比较是解决这个问题的的比较是解决这个问题的有效方法。有效方法。 假设窗口大小假设窗口大小为为1010，相似阈值为，相似阈值为8 8，则，则每次比较取每次比较取1010个连续的字个连续的字符，如相同的字符超过符，如相同的字符超过8 8个，则标记。个，则标记。 基于滑动窗基于滑动窗口的矩阵方法可以明显地口的矩阵方法

25、可以明显地降低点阵图的噪声，并能降低点阵图的噪声，并能明确无误地标出了两条序明确无误地标出了两条序列间具有显著相似性的区列间具有显著相似性的区域。域。滑动窗口技术与完整点矩阵图结果比较滑动窗口技术与完整点矩阵图结果比较(a) (b) (1) (2) （2）利用滑动窗口对以上的）利用滑动窗口对以上的两种球蛋白基因序列进行比较两种球蛋白基因序列进行比较的点阵图，其中窗口大小为的点阵图，其中窗口大小为10个核苷酸，相似度阈值为个核苷酸，相似度阈值为8。 （1）对人类（）对人类（Homo sapiens）与黑猩猩（与黑猩猩（Pongo pygmaeus）的的球蛋白基因序列进行比较的球蛋白基因序列进行比

26、较的完整点阵图。完整点阵图。相似区域连续的两条相似区域连续的两条DNADNA序列的点阵图序列的点阵图序列的两两比对方法序列的两两比对方法序列的两两比对序列的两两比对（Pairwise Sequence Alignment），），按字符位置重按字符位置重组两个序列，使得两个序列达到一样的长度。然后进行对比。组两个序列，使得两个序列达到一样的长度。然后进行对比。 s:AGCACAC AAG CACACA t:A CACACTAACACACT A Match(A, A)Match(A, A)Delete(G, - )Replace(G, C)Match(C, C)Insert( -, A)Match

27、(A, A)Match(C, C)Match(C, C)Match(A, A)Match(A, A)Match(C, C)Match(C, C)Replace(A, T)Insert( -, T)Delete(C, -)Match(A, A)Match(A, A)序列序列AGCACACA和和ACACACTA的两种比对结果的两种比对结果Alignment-1 Alignment-2编辑操作的代价与得分编辑操作的代价与得分代价代价: : 不同编辑操作方法代价不同不同编辑操作方法代价不同 若代价（若代价（cost）或权重（）或权重（weight）为编辑操作的函数）为编辑操作的函数,并以并以W表示。表

28、示。 对字母表对字母表 中的任意字符中的任意字符a、b，可以定义，可以定义: w (a, a) = 0 w (a, b) = 1 ( a b) w (a, -) = w ( -, b) = 1得分得分: : 序列比对也可以使用得分（序列比对也可以使用得分（scorescore）函数来）函数来评价编辑操作评价编辑操作 p (a, a) = 1 p (a, b) = 0 a b p (a, -) = w ( -, b) = -1 得分与代价的评介原则得分与代价的评介原则 两条序列两条序列s s 和和 t 的比对的得分（或代价）等于将的比对的得分（或代价）等于将s s 转化为转化为t 所用的所用的所

29、有编辑操作的得分（或代价）所有编辑操作的得分（或代价）的总和。的总和。 s s 和和t 的最优比对是所有可能的比对中的最优比对是所有可能的比对中得分最高得分最高（或代价最小）的一个比对。（或代价最小）的一个比对。 s s 和和t 的真实距离应该是在得分函数的真实距离应该是在得分函数p p值（或代值（或代价函数价函数ww值）值）最优时的距离最优时的距离。 例：例：s: AGCACAC At: A CACACTA costcost=2=2 s: AGCACAC A t: A CACACTA score (s，t）= 5序列比对的目的是寻找一个得分最大（或代价最序列比对的目的是寻找一个得分最大（或代

30、价最小）的比对。小）的比对。得分与代价的评介原则得分与代价的评介原则3 3 打分矩阵（打分矩阵（Weight MatricesWeight Matrices） （1 1）核酸打分矩阵所用）核酸打分矩阵所用DNADNA序列字母表如前所述为：序列字母表如前所述为： = A = A，CC，GG，T T 嘌呤：腺嘌呤嘌呤：腺嘌呤A A，鸟嘌呤，鸟嘌呤GG；嘧啶：胞嘧啶；嘧啶：胞嘧啶CC，胸腺嘧啶，胸腺嘧啶T T a. a. 等价矩阵等价矩阵 b. BLASTb. BLAST矩阵矩阵 c. c. 转移矩阵（转移矩阵（transitiontransition，transversiontransversio

31、n）ATCGA1000T0100C0010G0001ATCGA5-4-4-4T-45-4-4C-4-45-4G-4-4-45ATCGA1-5-5-1T-51-1-5C-5-11-5G-1-5-51a 等价矩阵表等价矩阵表c 转移矩阵转移矩阵b BLAST矩阵矩阵空位罚分空位罚分 空位罚分是为了补偿插入和缺失对序列相似性比空位罚分是为了补偿插入和缺失对序列相似性比较的影响较的影响, ,由于没有什么合适的理论模型能很好地由于没有什么合适的理论模型能很好地描述空位问题描述空位问题, ,因此空位罚分缺乏理论依据，更多因此空位罚分缺乏理论依据，更多的带有主观特色。的带有主观特色。 一般的处理方法是用两个

32、罚分值一般的处理方法是用两个罚分值, ,一个对插入的第一个对插入的第一个空位罚分一个空位罚分, ,另一个对空位的延伸罚分。另一个对空位的延伸罚分。 具体的对比问题具体的对比问题, ,采用不同的罚分方法会取得不同采用不同的罚分方法会取得不同的效果。的效果。 对比计算产生的分值多大才能说明两个序列是同对比计算产生的分值多大才能说明两个序列是同源的源的, , 主要是把具有相同长度的随机序列进行对主要是把具有相同长度的随机序列进行对比比, ,把分值与最初的对比分值相比把分值与最初的对比分值相比, ,看对比结果是看对比结果是否具有显著性。否具有显著性。蛋白质打分矩阵蛋白质打分矩阵 缴氨酸对异亮氨酸的取代

33、与谷氨酸对异亮氨酸的取代对缴氨酸对异亮氨酸的取代与谷氨酸对异亮氨酸的取代对结构和功能的不同影响结构和功能的不同影响, ,应该给予不同的打分。如果用应该给予不同的打分。如果用一个取代矩阵来描述氨基酸残基两两取代的分值一个取代矩阵来描述氨基酸残基两两取代的分值, ,会提会提高对比的敏感性和生物学意义。高对比的敏感性和生物学意义。 对不同的研究对象应该构建适宜的取代矩阵对不同的研究对象应该构建适宜的取代矩阵, ,但国际上但国际上常用的取代矩阵有常用的取代矩阵有等价矩阵、等价矩阵、PAM和和BLOSUM等等,它它们来源于不同的构建方法和不同的参数选择们来源于不同的构建方法和不同的参数选择,包括包括PA

34、M250、BLOSUM62、BLOSLIM90、BLOStJM30等。等。 对于不同的对象可以采用不同的取代矩阵以获得更多信对于不同的对象可以采用不同的取代矩阵以获得更多信息。例如，对同源性较高的序列可以采用息。例如，对同源性较高的序列可以采用BLOSUM90矩阵矩阵,而对同源性较低的序列可采用而对同源性较低的序列可采用BLOSUM30矩阵矩阵。蛋白质打分矩阵蛋白质打分矩阵 等价矩阵等价矩阵 氨基酸突变代价矩阵氨基酸突变代价矩阵GCM GCM 疏水矩阵疏水矩阵 PAMPAM矩阵（矩阵（Point Accepted MutationPoint Accepted Mutation） BLOSUMB

35、LOSUM矩阵矩阵( (Blocks Amino Acid Substitution MatricesBlocks Amino Acid Substitution Matrices）jijiRij01其中其中Rij代表打分矩阵元素代表打分矩阵元素i、j分别代表字母表第分别代表字母表第i和第和第j个字符。个字符。氨基酸突变代价矩阵氨基酸突变代价矩阵GCMGCM疏水矩阵疏水矩阵PAMPAM矩阵（矩阵（Point Accepted MutationPoint Accepted Mutation） 基于进化的点突变模型基于进化的点突变模型 一个一个PAMPAM就是一个进化的变异单位就是一个进化的变异单

36、位, , 即即1%1%的的氨基酸改变氨基酸改变 这类矩阵里列出同源蛋白质在进化过程中氨基这类矩阵里列出同源蛋白质在进化过程中氨基酸变化的可能性。酸变化的可能性。 这类矩阵是基于进化原理的，编码相同蛋白质这类矩阵是基于进化原理的，编码相同蛋白质的基因随着进化发生分歧，相似度降低。的基因随着进化发生分歧，相似度降低。矩阵集合矩阵集合- PAM-N- PAM-N如，如，PAM120矩阵用于比较相距矩阵用于比较相距120个个PAM单位的序单位的序列。列。一个一个PAM-N矩阵矩阵元素（元素（i，j）的值：的值： 反应两个相距反应两个相距N个个PAM单位的序列中，第单位的序列中，第i种氨基酸替种氨基酸替

37、换第换第j种氨基酸的频率。种氨基酸的频率。可根据针对不同的进化距离采用可根据针对不同的进化距离采用PAM 矩阵：矩阵：序列相似度序列相似度 = 40% 50% 60% | | |打分矩阵打分矩阵 = PAM120 PAM80 PAM 60PAM250 14% - 27% 归一化打分归一化打分BLOSUM 62BLOSUM 62序列两两比对基本算法序列两两比对基本算法直接方法直接方法 生成两个序列所有可能的比对，分生成两个序列所有可能的比对，分别计算代价函数，然后挑选一个代价最小的比对别计算代价函数，然后挑选一个代价最小的比对作为最终结果。作为最终结果。本质问题：优化本质问题：优化动态规划寻优策

38、略动态规划寻优策略动态规划算法（动态规划算法（Dynamic Programming）最短路经问题最短路经问题起点起点终点终点C1 C2 W1 W2路径路径1：C1 + w1 ？路径路径2：C2 + w2 ？ 取最小值！取最小值！算法求解算法求解: 从起点到终点逐层计算从起点到终点逐层计算动态规划法序列的两两比对动态规划法序列的两两比对起点起点终点终点ATTCCGAAGA AGTCGAAGGTATTCCGAAG AGTCGAAGGAT+（1）ATTCCGAAGA AGTCGAAGG-T+（2）ATTCCGAAG AGTCGAAGGTA-+（3）比对过程比对过程起点起点终点终点ATTCCGAAG

39、A AGTCGAAGGT 从两个序列前端开始从两个序列前端开始 逐步推进逐步推进 直到两个序列的末端。直到两个序列的末端。序列序列S: i-1 i i+1序列序列t: j-1 j j+1序列序列S: i-1 i i+1序列序列t: j-1 j j+1Case1:匹配（匹配（si，tj )中间过程：比对中间过程：比对0:S:i 与与 0:T:j 序列序列S: i-1 i i+1序列序列t: j-1 j j+1序列序列S: i-1 i i+1序列序列t: j-1 j j+1Case2:删除（删除（si， -） 序列序列S: i-1 i i+1序列序列t: j-1 j j+1序列S: i-1 i i

40、+1序列序列t: j-1 j j+1Case3:插入（ -，tj ） 设序列设序列s、t的长度分别为的长度分别为m和和n。考虑两个前缀：考虑两个前缀： 0:s:i 0:t:j 如已知序列如已知序列0:s:i 和和0:t:j 所有较短子列的最优比对，即已知：所有较短子列的最优比对，即已知：（1）0:s:(i-1) 和和 0:t:(j-1) 的最优比对的最优比对（2） 0:s:(i-1) 和和 0:t:j 的最优比对的最优比对（3） 0:s:i 和和 0:t:(j-1) 的最优比对的最优比对则则0:s:i和和 0:t:j 的最优比对一定是上述三种情况之一的扩展：的最优比对一定是上述三种情况之一的扩

41、展：1）替换（）替换（si，tj）或匹配（）或匹配（si，tj ) ，这取决于，这取决于si 是否等于是否等于tj2）删除（）删除（si， -）3）插入（）插入（ -，tj ）):,:(00jitsS如序列比对关系为：如序列比对关系为：为序列为序列0 0:s:s:i i和与序列和与序列 0 0:t:t:j j 比对的得分比对的得分按下述方法操作：按下述方法操作： 其初值为：其初值为：for i=1 , 2 ,., mfor j=1 , 2 ,., n),():, :(),():,:(),():,:(max):, :()1(000)1(0)1(0)1(000jjiijijijijitptsSsp

42、tsStsptsStsS),():,:():,:(),():,:():, :(0):,:() 1(00000000) 1(00000000jjjiiitptsStsSsptsStsStsS距离矩阵距离矩阵按照上述方法，对于给定的得分函数按照上述方法，对于给定的得分函数p，两，两个序列所有前缀的得分定义了一个个序列所有前缀的得分定义了一个(m+1) (n+1)的距离矩阵的距离矩阵D = ( d i , j )其中其中d i , j = S (0:s:i , 0:t:j ) d i , j的计算公式如下：的计算公式如下：),(),(),(max1, 11, 1,jjiijijijijitpdspd

43、tspddd i , j 最小值的三种选择决定了各矩阵元素之间的关系，最小值的三种选择决定了各矩阵元素之间的关系，用下图表示：用下图表示：di,jdi,j-1di-1,jdi-1,j-1 距离矩阵元素距离矩阵元素d i , j 的计算的计算S (0:s:i , 0:t:j )S (0:s:i-1 , 0:t:j )S (0:s:i-1 , 0:t:j-1 )S (0:s:i , 0:t:j-1 )-AGCT-ATGCAGCTGCTT子序列与完整序列的比对子序列与完整序列的比对 目标目标：使使S(s, i:t:j ) 最大最大序列序列S:序列序列t: i j不计前缀不计前缀0:t:i 的得分的得

44、分, 也不计删除后缀的也不计删除后缀的j+1:t:|t|得分得分目标：目标：使使dw (i:s :j, i:t:j ) 最大最大序列序列S:序列序列t: i ji j寻找最大的相似子序列寻找最大的相似子序列寻找最佳比对的子序列方法寻找最佳比对的子序列方法 在矩阵中找最大值在矩阵中找最大值 该值就是最优的局部比对得分该值就是最优的局部比对得分 该值对应的点为序列局部比对的末点该值对应的点为序列局部比对的末点 然后反向推演前面的最优路径，直到局部比对的然后反向推演前面的最优路径，直到局部比对的起点。起点。 寻找最佳比对的子序列寻找最佳比对的子序列TATA|TATA寻找最佳比对的子序列寻找最佳比对的

45、子序列 所谓准全局比较就是在评价序列比对时不计终端所谓准全局比较就是在评价序列比对时不计终端“空空缺缺”（end spaceend space，或空位）的得分或代价，或空位）的得分或代价 序列序列1 长度为长度为8序列序列2 长度为长度为18（a）6个匹配，个匹配，1个失个失 配，配，1个空位个空位 （b）8个匹配个匹配准全局比较准全局比较情况情况1 1 ：不记：不记s s后面的空位与后面的空位与 t t 后缀比对的得分后缀比对的得分在矩阵在矩阵d di,ji,j中取最后一行的最大值，即：中取最后一行的最大值，即：序列序列S:序列序列t: i ji j空位空位后缀后缀准全局比较准全局比较情况情

46、况2 2 ：不记：不记s s前面的空位与前面的空位与 t t 前缀比对的得分前缀比对的得分将矩阵将矩阵d di,ji,j中的第一行各元素值置为中的第一行各元素值置为“0”序列序列S:序列序列t: i ji j空位空位前缀前缀准全局比较准全局比较半全局比较算法与基本算法在计算半全局比较算法与基本算法在计算d di,ji,j时的区别归纳为下时的区别归纳为下列四个方面：列四个方面：（1 1）第一行初始值为）第一行初始值为“0”0”，表示不计第一个序列的前端空位；，表示不计第一个序列的前端空位；（2 2）寻找最后一行的最大值，表示不计第一个序列的末端空位；）寻找最后一行的最大值，表示不计第一个序列的末端空位；（3 3）第一列初始值为）第一列初始值为“0”0”，表示不计第二个序列的前端空位；，表示不计第二个序列的前端空位；（4 4）寻找最后一列的最大值，表示不计第二个序列的末端空位。）寻找最后一列的最大值，表示不计第二个序列的末端空位。准全局比较准全局比较对于最