生物序列联配中的算法

《生物序列联配中的算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、生物序列联配中的算法张法提纲背景知识序列相似性的比较两条序列的联配问题多序列的联配问题一些启发式的算法生物序列联配中的并行算法DNA(1)脱氧核糖核酸DNA的分子组成核甘(nucleotides)磷酸盐(phosphate)糖(sugar)一种碱基腺嘌呤(Adenine)鸟嘌呤(Guanine)胞嘧啶(Cytosine)胸腺嘧啶(Thymine)DNA(2)碱基的配对原则A(腺嘌呤)—T(胸腺嘧啶)C(鸟嘌呤)—G(胞嘧啶)一个嘌呤基与一个嘧啶基通过氢键联结成一个碱基对。DNA分子的方向性5'→3'DNA(3)D

2、NA的双螺旋结构碱基对之间的互补能力DNA(4)DNA的复制在DNA解旋酶的作用下两条链分离开，分别作为一个模板，在聚合酶的作用下合成一条新链。RNA、转录和翻译RNA(核糖核酸)：单链结构、尿嘧啶U代替胸腺嘧啶T、位于细胞核和细胞质中。转录：DNA链→RNA链信使RNA(mRNA)，启动子。翻译：mRNA上携带遗传信息在核糖体中合成蛋白质的过程。变异进化过程中由于不正确的复制，使DNA内容发生局部的改变。变异的种类主要有以下三种：替代(substitution)插入或删除(insertionordeletion

3、)indel重排(rearrangement)蛋白质由氨基酸依次链接形成在生物体中总共有20种氨基酸。蛋白有十分复杂的三维结构。其三维机构决定了蛋白质的功能。基因什么是基因？DNA上具有特定功能的一个片断，负责一种特定性状的表达。一般来讲，一个基因只编码一个蛋白质。基因组任何一条染色体上都带有许多基因，一条高等生物的染色体上可能带有成千上万个基因，一个细胞中的全部基因序列及其间隔序列统称为genomes（基因组）。DNA上的基因基因基因的编码基因编码是一个逻辑的映射，表明存储在DNA和mRNA中的基因信息决定什么

4、样的蛋白质序列。每个碱基三元组称为一个密码子(codon)碱基组成的三元组的排列共有43＝64种，而氨基酸共有20种类型，所以不同的密码子可能表示同一种氨基酸。带来的问题序列排列问题基因组的重排问题蛋白质结构和功能的预测基因(外显子、内含子)查找问题序列装配(SequenceAssembly)问题生物序列相似性的比较动机在生物学的研究中，将未知序列同已知序列进行比较分析已经成为一种强有力的研究手段，生物学领域中绝大部分的问题在计算机科学领域中主要体现为序列或字符串的问题。序列联配问题的分类如果两个序列具有足够的相

5、似性，则认为两者具有同源性。－序列相似性的比较(两条序列的联配)序列的分类序列的排列多序列的联配两条序列联配问题的分类全局联配(GlobalAlignment)局部联配(LocalAlignment)空位处罚(GapPenalty)全局联配(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)

6、S’

7、=

8、T’

9、；(2)将S’和T’中的

10、空字符除去后所得到的序列分别为S和T;联配A的分值Score为：全局联配(2)－原始算法输入：序列S和T，其中

11、S

12、=

13、T

14、=n输出：S和T的最优联配fori=0tondofor(S的所有的子序列A，其中

15、A

16、=i)dofor(T的所有的子序列B，其中

17、B

18、=i)do……全局联配(3)动态规划DP(DynamicProgramming)Smith-Waterman算法计算出两个序列的相似分值，存于一个矩阵中。(相似度矩阵、DP矩阵)根据此矩阵，按照动态规划的方法寻找最优的联配序列。全局联配(4)前提条件递归关系全

19、局联配(5)在得到相似度矩阵后，通过动态规划回溯（Traceback）的方法可获得序列的最优联配序列。例：S=“acgctg”和T=“catgt”(x,x)=2,(x,y)=(x,-)=(-,y)=-1ji01c2a3t4g5t00-1-2-3-4-51a-1-110-1-22c-2100-1-23g-300-1214c-4-1-1-1115t-5-2-21036g-6-3-3032三种可能的最优联配序列：S:acgctg-T:-c–atgtS:acgctg-T:-ca–tgtS:-acgctgT:cat

20、g-t-局部联配(1)两条序列在一些局部的区域内具有很高的相似度。在生物学中局部联配比全局联配更具有实际的意义。两条DNA长序列，可能只在很小的区域内(密码区)存在关系。不同家族的蛋白质往往具有功能和结构上的相同的一些区域。局部联配(2)前提条件：V(i,0)=0;V(0,j)=0;递归关系：找出i*和j*，使得：局部联配(3)对全局联配策略稍作修改可得到局部最优联配算法