生物序列联配中的算法 - 中国科学院计算技术研究所前瞻研 ….pptVIP

生物序列联配中的算法;提 纲;DNA(1) 脱氧核糖核酸;DNA(2);DNA(3);DNA(4);RNA、转录和翻译;变异;蛋白质;基 因;基因组;DNA上的基因;基因的编码;带来的问题;生物序列相似性的比较;动机;序列联配问题的分类;两条序列联配问题的分类;全局联配(1)－定义;全局联配(2)－原始算法;全局联配(3);全局联配(4);全局联配(5); j i;三种可能的最优联配序列： S: a c g c t g - T: - c – a t g t S: a c g c t g - T: - c a – t g t S: - a c g c t g T: c a t g - t - ;局部联配(1);局部联配(2);局部联配(3);局部联配(4); j i;S = “ a b c x d e x ”，T= “ x x x c d e ” 局部最优联配是： c x d e c - d e 或 x - d e x c d e ;空位处罚(1);空位处罚(2);空位处罚(3);空位处罚(4);利用动态规划计算序列最优联配的算法的复杂度分析： 时间复杂度；O(nm) 空间复杂度：O(n+m);必威体育精装版的相关的研究;多序列联配(1);多序列联配(2);多序列联配(3);多序列联配(4);借助硬件来完成动态规划的算法 采用并行的固件，把问题有效地分配到多个处理器上运行，最后再把各处理器的运算结果收集起来 借助于一些比最初的动态规划算法更快的启发式算法。以降低运算结果的质量为代价来提高计算速度的。 ;启发式算法-FASTA;确定参数ktup，在两个序列中查找长度为ktup的、相匹配的片段(增强点)。连续的增强点在动态规划矩阵中主对角线附近。为了提高速度，可以通过查询表格或hash表来完成，然后在表格中有哪些信誉好的足球投注网站与另一条序列相匹配的、长度为ktup的片段。 在同一条对角线中临近的增强点成为一个增强段。每一个增强点都赋予一个正的分值，一个增强段中相邻的两个增强点之间的不匹配区域赋予一定的负值。一个增强段对应于一段相匹配的子序列，分值最高的段被标记为init1。 ;引入indel。把那些没有重叠(non-overlap)的增强段拼接起来(增强段的分值之和减去空位处罚)。分值最高的区域记为initn。 对最有可能的匹配序列进一步评分：以增强段init1所在的对角线为中心，划分出一个较狭窄的对角线带，利用S-W算法，来获得分值最高的局部联配，记作opt。 按照initn和opt的分值，对分值最高的序列再进行一次S-W联配。FASTA对每一个检索到的联配都提供一个统计学显著性的评估，以判断该联配的意义。;FASTA对DNA序列有哪些信誉好的足球投注网站的结果要比对蛋白质序列有哪些信誉好的足球投注网站的结果更敏感，因为它对数据库的每一次有哪些信誉好的足球投注网站都只有一个最佳的联配，这样对于蛋白质序列而言，一些有意义的联配可能被错过。 ;启发式算法-BLAST;首先确定一个终止值S、步长参数w和一个阀值t ，S值通常是基于统计学的原理指明一个预期的终止E值，然后软件会在考虑有哪些信誉好的足球投注网站背景性质的基础上计算出合适的S值。使要联配的序列中包含一个分值不小于S的HSP。 引入邻近字串的思想：不需要字串确切地匹配，当有一个字串的分值高于t时，BALST就宣称找到了一个选中的字串。为了提高速度，允许较长的字串长度W。W值很少变化，这样，t值就成为权衡速度和敏感度的参数。;一个字串选中后，程序会进行没有空位的局部寻优，联配的最低分值是S，当联配延伸时会遇到一些负的分值，使得联配的分值下降，当下降的分值小于S时，命中的延伸就会终止。这样系统会减少消耗于毫无指望的选中延伸的时间，使系统的性能得以改进。 ;PSI-BLAST;在利用动态规划矩阵进行联配时，以步长为2w来有哪些信誉好的足球投注网站每一条对角线，这样可以找到一些长度为2w的选中的字。 改进的算法中允许位于不同的对角线的两个片段拼接在一起。在拼接的过程中要涉及到indel操作，与FASTA算法只产生一个最佳联配不同，位于不同对角线的两个片段拼接在一起的前提条件是：拼接后片段的分值不小于某一个终止值。 ;执行通常的BLAST算法，使用一种不同的记分方式，根据高度显著联配(HSPs)的最高分值建立一个最初的profile。 根据该profile反复利用BLAST算法对数据库进行有哪些信誉好的足球投注网站，这一步实际上是根据表头文件的统计结果扩展局部联配。这一过程是反复进行的，直到再没有发现新的有意义的匹配