生物序列比对中的算法.ppt

生物序列比对中的算法 中科院计算所生物信息学实验室 华大—曙光联合实验室 张 法 提 纲 背景知识 序列相似性的比较 两条序列的比对问题 多序列的比对问题 一些启发式的算法 生物序列比对中的并行算法 DNA(1) 脱氧核糖核酸 DNA的分子组成 核甘(nucleotides) 磷酸盐(phosphate) 糖(sugar) 一种碱基 腺嘌呤(Adenine) 鸟嘌呤(Guanine) 胞嘧啶(Cytosine) 胸腺嘧啶(Thymine) DNA(2) 碱基的配对原则 A(腺嘌呤)—T(胸腺嘧啶) C(鸟嘌呤)—G(胞嘧啶) 一个嘌呤基与一个嘧啶基通 过氢键联结成一个碱基对。 DNA分子的方向性 5→3 DNA(3) DNA的双螺旋结构 碱基对之间的互补能力 DNA(4) DNA的复制 在DNA解旋酶的作用 下两条链分离开，分 别作为一个模板，在 聚合酶的作用下合成 一条新链。 RNA、转录和翻译 RNA(核糖核酸)：单链结构、尿嘧啶U代替胸腺嘧啶T、位于细胞核和细胞质中。 转录：DNA链 → RNA链 信使RNA(mRNA)，启动子。 翻译： mRNA上携带遗传信息在核糖体中合成蛋白质的过程。 变异 进化过程中由于不正确的复制，使DNA内容发生局部的改变。 变异的种类主要有以下三种： 替代(substitution) 插入或删除(insertion or deletion) indel 重排(rearrangement) 蛋白质 由氨基酸依次链接形成在生物体中总共有20种氨基酸。 蛋白有十分复杂的三维结构。其三维机构决定了蛋白质的功能。 基 因 什么是基因？ DNA上具有特定功能的一个片断，负责一种特定性状的表达。一般来讲，一个基因只编码一个蛋白质。 基因组 任何一条染色体上都带有许多基因，一条高等生物的染色体上可能带有成千上万个基因，一个细胞中的全部基因序列及其间隔序列统称为genomes（基因组）。 DNA上的基因 基因 基因的编码 基因编码是一个逻辑的映射，表明存储在DNA和mRNA中的基因信息决定什么样的蛋白质序列。 每个碱基三元组称为一个密码子(codon) 碱基组成的三元组的排列共有43＝64种，而氨基酸共有20种类型，所以不同的密码子可能表示同一种氨基酸。 带来的问题 序列排列问题 基因组的重排问题 蛋白质结构和功能的预测 基因(外显子、内含子)查找问题 序列装配(Sequence Assembly)问题 动机 在生物学的研究中，将未知序列同已知序列进行比较分析已经成为一种强有力的研究手段 ，生物序列相似性比较中绝大部分的问题在计算机科学领域中主要体现为字符串的匹配和查找 。 两条序列比对问题的分类 全局比对(Global Alignment) 局部比对(Local Alignment) 空位罚分(Gap Penalty) 全局比对(1)－定义 定义1：两个任意的字符 x和y，?(x,y)表示表x和y比较时的分值。 ?(x,x)=2, ?(x,y)= ?(x,-)= ?(-,y)=-1 定义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