• 腺嘌呤(Adenine)
• 鸟嘌呤(Guanine)
• 胞嘧啶(Cytosine)
• 胸腺嘧啶(Thymine)
ppt课件
3
•DNA(2)
碱基的配对原则 A(腺嘌呤)—T(胸腺嘧啶) C(鸟嘌呤)—G(胞嘧啶)
一个嘌呤基与一个嘧啶基通 过氢键联结成一个碱基对。
DNA分子的方向性 5'→3'
转录：DNA链 → RNA链 信使RNA(mRNA)，启动子。
翻译： mRNA上携带遗传信息在核糖体 中合成蛋白质的过程。
ppt课件
7
•变异
进化过程中由于不正确的复制，使DNA 内容发生局部的改变。
变异的种类主要有以下三种： 替代(substitution) 插入或删除(insertion or deletion) indel 重排(rearrangement)
(2) 将S’和T’中的空字符除去后所得到的序
列分别为S和T;
联配A的分值Score为：S
l
core (S'[i],T'[i])
i1
ppt课件
19
•全局联配(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
ppt课件
11
•DNA上的基因
基因
ppt课件
12
•基因的编码
基因编码是一个逻辑的映射，表明存储 在DNA和mRNA中的基因信息决定什么 样的蛋白质序列。
每个碱基三元组称为一个密码子(codon) 碱基组成的三元组的排列共有43＝64种，
而氨基酸共有20种类型，所以不同的密 码子可能表示同一种氨基酸。
ppt课件
16
•序列联配问题的分类
如果两个序列具有足够的相似性， 则认为两者具有同源性。
－
序列相似性的比较 (两条序列的联配) 序列的分类 序列的排列 多序列的联配
ppt课件
17
•两条序列联配问题的分类
全局联配(Global Alignment) 局部联配(Local Alignment) 空位处罚(Gap Penalty)
ppt课件
4
•DNA(3)
DNA的双螺旋结构
碱基对之间的互补能力
ppt课件
5
•DNA(4)
DNA的复制 在DNA解旋酶的作用 下两条链分离开，分 别作为一个模板，在 聚合酶的作用下合成 一条新链。
ppt课件
6
•RNA、转录和翻译
RNA(核糖核酸)：单链结构、尿嘧啶U代 替胸腺嘧啶T、位于细胞核和细胞质中。
ppt课件
13
•带来的问题
序列排列问题 基因组的重排问题 蛋白质结构和功能的预测 基因(外显子、内含子)查找问题 序列装配(Sequence Assembly)问题
ppt课件
14
生物序列相似性的比较
ppt课件
15
•动机
在生物学的研究中，将未知序列同已知 序列进行比较分析已经成为一种强有力 的研究手段 ，生物学领域中绝大部分的 问题在计算机科学领域中主要体现为序 列或字符串的问题 。
ppt课件
18
•全局联配(1)－定义
定义1：两个任意的字符 x和y，(x,y)表示
表x和y比较时的分值。
(x,x)=2, (x,y)= (x,-)= (-,y)=-1
定可义以2用：序S列= sS1’…和sTn和’来T表=t示1…，tm其，中其：全局联配A
(1) | S’ | = | T’ |；
……
ppt课件
20
•全局联配(3)
动态规划DP(Dynamic Programming) Smith-Waterman 算法
计算出两个序列的相似分值，存于一 个矩阵中。(相似度矩阵、DP矩阵)
根据此矩阵，按照动态规划的方法寻 找最优的联配序列。
ppt课件
21
•全局联配(4)
前提条件
V(0,0)0
例： S = “a c g c t g”和T = “c a t g t”
(x,x)=2, (x,y)= (x,-)= (-,y)=-1
ppt课件
23
j0 1 2 3 4 5
i
ca t g t
0
0 -1 -2 -3 -4 -5
1 a -1 -1 1 0 -1 -2
2 c -2 1 0 0 -1 -2
T: - c a – t g t 3. S: - a c g c t g
T: c a t g - t -
ppt课件
25
•局部联配(1)
两条序列在一些局部的区域内具有 很高的相似度。
在生物学中局部联配比全局联配更 具有实际的意义。
V(i,0)V(i1,0)(S[i],) V(0, j)V(0, j1)(,T[i])
递归关系
V(i1,j1)(S[i]T,[j])
V(i,j)max V(i1,j)(S[i],)

V(i,
ppt课件
j1)(,T[j]
)
22
•全局联配(5)
在得到相似度矩阵后，通过动态规划回 溯（Traceback）的方法可获得序列的最 优联配序列 。
生物序列联配中的算法
张法
ppt课件
1
•提 纲
背景知识 序列相似性的比较
两条序列的联配问题 多序列的联配问题 一些启发式的算法 生物序列联配中的并行算法
ppt课件
2
•DNA(1) 脱氧核糖核酸
DNA的分子组成
核甘(nucleotides)
磷酸盐(phosphate)
糖(sugar)
一种碱基
3 g -3 0 0 -1 2 1
4 c -4 -1 -1 -1 1 1
5 t -5 -2 -2 1 0 3
6 g -6 -3 -3 0 3 2
ppt课件
24
三种可能的最优联配序列：
1. S: a c g c t g 2. T: - c – a t g t 2. S: a c g c t g -
ppt课件
8
•蛋白质
由氨基酸依次链接形成在生物体中总共 有20种氨基酸。
蛋白有十分复杂的三维结构。其三维机 构决定了蛋白质的功能。
ppt课件
9
•基 因
什么是基因？
DNA上具有特定功能的一个片断，负 责一种特定性状的表达。一般来讲， 一个基因只编码一个蛋白质。
ppt课件
10
•基因组
任何一条染色体上都带有许多基因，一 条高等生物的染色体上可能带有成千上 万个基因，一个细胞中的全部基因序列 及其间隔序列统称为genomes（基因组）。