第五章多序列比对讲述.ppt

多序列比对 二、多序列比对的方法 手工比对方法（包括对结果进行修饰） 同步法 步进法 动态规划算法 优化计算方法 星形比对 其它多序列比对算法 二、步进法 动态规划算法 优化计算方法 1、多重比对的动态规划算法 Recall: 双序列比对 多序列比对：最优算法 动态规划算法：全空间 2、 优化计算方法 动态规划算法：优化算法 多序列比对的方法 手工比对方法（包括对结果进行修饰） 同步法 步进法 动态规划算法 优化计算方法 星形比对 其它多序列比对算法 星形比对 星形比对的基本思想是：在给定的若干序列中，选择一个核心序列，通过该序列与其它序列的两两比对形成所有序列的多重比对?，从而使得?在核心序列和任何一个其它序列方向的投影是最优的两两比对。 利用标准的动态规划方法求出所有si和sc的最优两两比对 时间为O（kn2） 将这些两两比对聚集起来 并采用“只要是空白， 则永远是空白”的原则。 sc s1 s2 … sk 如何选择核心序列？ 尝试将每一个序列分别作为核心序列，进行星形多重序列比对，取比对结果最好的一个。 另一种方法是计算所有的两两比对，取下式值最大的一个： ? sim( si, sc ) 例如，有5个序列： s1 = ATTGCCATT s2 = ATGGCCATT s3 = ATCCAATTTT s4 = ATCTTCTT s5 = ACTGACC 多序列比对的方法 手工比对方法（包括对结果进行修饰） 同步法 步进法 动态规划算法 优化计算方法 星形比对 其它多序列比对算法 五、MSA: 多序列比对的打分和评价 1、SP（Sum-of-Pairs）模型 利用保守序列或者特征统计图可以判断一个序列是否满足一定的特征 利用特征统计矩阵有哪些信誉好的足球投注网站数据库时，可以考察家族的成员关系。 * 第四章 多序列比对 Made by GENEDOC 一、多序列比对：简介 1. 不同物种中，许多基因的功能保守，序列相似性较高，通过多条序列的比较，发现保守与变异的部分； 2. 可构建统计学模型（如HMM） ，有哪些信誉好的足球投注网站更多的同源序列； 3. 构建进化树的必须步骤； 4. 比较基因组学研究；  多重序列比对的最终目标是通过处理得到一个得分最高（或代价最小）的序列对比排列，从而分析各序列之间的相似性和差异。 15 -3 -23 -38 -51 -66 Y 7 8 -12 -27 -40 -55 C -3 9 -1 -16 -29 -44 L -12 -1 10 -5 -18 -33 S -27 -16 -5 6 -7 -22 E -40 -29 -18 -7 4 -11 V -55 -44 -33 -22 -11 0 Gap Y C S D V Gap 4 2 时间复杂度：O(n2) 三条序列：时间复杂度：O(lmn) = O(n3) 四条序列：时间复杂度：O(n4)，非多项式时间！ 多项式时间复杂度：≤O(n3) m条序列：时间复杂度：O(nm)，指数时间！ … /CBBresearch/Schaffer/msa.html  前趋节点的个数等于2k - 1  假设以k维数组A存放超晶格，则计算过程如下： a[ 0, 0, … ,0 ] = 0 a[ i ] = max {a[ i - b ] + SP-score(Column(s, i, b))} (3-37) (3-38) if bj = 1 if bj = 0  图3.17 三维晶格节点计算依赖关系 问题： 计算量巨大 时间复杂度为O(2k?i=1,...,k ?si?) ↓ O(2kNk) 标准动态规划算法存在的问题： 有哪些信誉好的足球投注网站空间大 剪枝技术：将有哪些信誉好的足球投注网站空间限定在一个较小的区域范围内。 若问题是有哪些信誉好的足球投注网站一条得分最高（或代价最小）的路径，则在有哪些信誉好的足球投注网站时如果当前路径的得分低于某个下限（或累积代价已经超过某个上限），则对当前路径进行剪枝，即不再有哪些信誉好的足球投注网站当前路径的后续空间。 /CBBresearch/Schaffer/msa.html Sequence A Sequence B Sequence C 有哪些信誉好的足球投注网站有限空间，类似于BLAST算法 (sc, s1) (sc, s2) … (sc, sk) 两两比对 ? 多重比对 sc=s1 ATTGCCATT ATTGCCATT-- ATTGCCATT ATTGCCATT ATGGCCATT ATC-CAATTTT ATCTTC-TT