BLOSUM矩阵-东南大学生物电子学国家重点实验室.ppt

第三章 序 列 比 较 序列比较的根本任务是： 发现序列之间的相似性 辨别序列之间的差异 目的： 相似序列 ? 相似的结构，相似的功能 判别序列之间的同源性 推测序列之间的进化关系 第一节 序列的相似性 同源（homology）- 具有共同的祖先 直向同源（Orthologous ） 共生同源（paralogous ） 相似（similarity） —同源序列一般是相似的 — 相似序列不一定是同源的 — 进化趋同（同功能） 序列的相似性描述 定性的描述 定量的数值 相似度 距离 序列比较的基本操作是比对（Alignment） 两个序列的比对是指这两个序列中各个字符的一种一一对应关系，或字符的对比排列 。 1、字母表和序列 字母表 4字符DNA字母表：{A, C, G, T} 扩展的遗传学字母表或IUPAC编码 单字母氨基酸编码 1、字母表和序列 特定的符号 ? ? — 代表字母表 A* — 代表由字母表A中字符所形成的一系列有限长度序列或字符串或序列的集合 ? a、b、c—代表单独的字符 ? s、t、u、v—代表A*中的序列 ? |s|—代表序列s的长度 为了说明序列s子序列和s中单个字符，在s中各字符之间用数字标明分割边界 例如，设s=ACCACGTA，则s可表示为 0A1C2C3A4C5G6T7A8 i:s:j 指明第i位或第j位之间的子序列, 当然，0 ? i ? j ? |s|。 子序列0:s: i 称为前缀，即prefix(s,i) 子序列 i:s:|s|称为后缀，即suffix(s, |s|-i+1) i:s: i — 为空序列 j-1:s:j —表示s 中的第j 个字符，简记为sj 子序列与子串 子序列：选取s中的某些字符（或删除s中的某些字符）而形成s的子序列 例如： TTT 是 ATATAT的子序列。 s的子串： 是由s中相继的字符所组成。 例如： TAC是AGTACA的子串， 但不是TTGAC的子串（是子序列）。 子串是子序列 子序列不一定是子串 字符串操作 字符串连接操作： 两个序列s和t的连接： s + + t 例如： ACC++CTA = ACCCTA 字符串k操作— 删除字符串两端的字符 其定义如下： prefix(s,l) = sk|s|-l suffix(s,l) = k|s|-ls i:s:j = ki-1sk|s|-j 序列比较可以分为四种基本情况：（1）两条长度相近的序列相似  ?找出序列的差别（2）判断一条序列的前缀与另一条序列的后缀相似（3）判断一条序列是否是另一条序列的子序列（4）判断两条序列中是否有非常相似的子序列 2、编辑距离（Edit Distance) 两条序列的相似程度的定量计算 相似度，它是两个序列的函数，其值越大，表示两个序列越相似 两个序列之间的距离。距离越大，则两个序列的相似度就越小 字符编辑操作（Edit Operation） 字符编辑操作可将一个序列转化为一个新序列 Match（a，a） Delete（a，-） Replace（a，b） Insert（-，b） 扩展的编辑操作 ACCGACAATATGCATA ? ? ? ? ? ATAGGTATAACAGTCA 4、 序列的两两比对 序列的两两比对 （Pairwise Sequence Alignment） 按字符位置重组两个序列，使得两个序列达到一样的长度 不同编辑操作的代价不同 为编辑操作定义函数w，它表示“代价（cost）”或“权重（weight）”。 对字母表?中的任意字符a、b，定义 w (a, a) = 0 w (a, b) = 1 a ? b w (a, -) = w ( -, b) = 1 也可以使用得分（score）函数来评价编辑操作 p (a, a) = 1 p (a, b) = 0 a ? b p (a, -) = w ( -, b) = -1