第2讲-序列比对课件.ppt

序列比对(alignment)，是根据特定的计分规则，将两个或多个符号序列按位置比较排列后，得到最具相似性的排列的过程。 计分规则：序列相似性的计算规则 规定匹配、不匹配、空位各自的得分 如： 匹配：1 不匹配：0 空格：0 ACGCTAGCGCTAGCTGCTAGCTAG ACGCTAGCGCAAGCTGCTAGCTG- 21 ACGCTAGCGCTAGCTGCTAGCTAG ACGCTAGCGCAAGCTGCTAGCT- G 22 三、序列比对的算法 点阵法 动态规划法 词或k串法（BLAST或FASTA中采用）。 点阵法 点阵法是最基本的，也是很重要的一种可视化序列比对方法。 “矩阵作图法” 或 “对角线作图” 。 首先建立一个矩阵，两条序列的长度分别为矩阵的行数和列数，一条序列置于矩阵的顶部，一条序列置于矩阵的左侧。 把具有相同字符的单元做标记。 A C C T G A G C T C G T T A A C C A G C T A A 对角线上的元素 如果两个序列完全相同，则对角线上每个位置都会出现标记。 其它位置的元素 其它位置如果出现连续的相同字符，同样可以在表中体现出来。 点阵图可以很直观的发现两条序列所有可能的匹配，这些匹配可能是某种功能域。也可用于寻找蛋白质或者DNA内部的重复或者反向重复区域 反向重复序列 序列1 →序列2 → 滑动窗口技术 由于序列可能很长，而字符只有4个（核酸），所以会有很多随机性的没有生物学意义的相似性，这些是比对中的噪声。 使用滑动窗口代替一次一个位点的比较是解决噪声问题的有效方法。 假设窗口大小为10，相似度阈值为8，则每次比较取10个连续的字符，如相同的字符超过8个，则标记。 基于滑动窗口的点矩阵方法可以明显地降低点阵图的噪声，并且明确无误的指示出了两条序列间具有显著相似性的区域。 滑动窗口的过滤 不连续的匹配可能是噪声，需要用滑动窗口过滤，滑动窗口有两个参数，一是窗口大小，二是阈值，也就是不匹配的字符个数。例如我们这个例子由于字符个数很少，用（3，0）的参数。 T G C T G C T C C G 0 1 0 0 1 0 0 0 0 C 0 0 0 0 0 0 0 0 0 T 0 0 0 0 0 0 0 0 0 A 0 0 0 0 0 0 0 0 0 G 0 0 0 0 0 0 0 0 0 A 0 0 0 0 0 0 0 0 0 T 0 0 0 0 0 0 0 0 0 A 0 0 0 0 0 0 0 0 0 A 0 0 0 0 0 0 0 0 0 滑动窗口是这样使用的：从（1，1）位置出发，将序列1的1～3个字符与序列2的1～3个字符比较，如果都相同，则在（1，1）位置处做标记，一直到完成整个表。例如如上表中的（1，5）位置做了标记，是因为序列1的1～3个元素和序列2的5～7个元素是相同的。 （a）对人类（Homo sapiens）与黑猩猩（Pongo pygmaeus）的β球蛋白基因序列进行比较的完整点阵图。（b）利用滑动窗口对以上的两种球蛋白基因序列进行比较的点阵图，其中窗口大小为10个核苷酸，相似度阈值为8。 (a) (b) 点阵图的一个例子 1 AAGGTCAGGAACAAAGAAACAGCTGAATACCAAACAGGATATCTGTGGTAAGCGGTTCCT 61 GCCCCGGCTCAGGGCCAAGAACAGATGAGACAGCTGAGTGATGGGCCAAACAGGATATCT 121 GTGGTAAGCAGTTCCTGCCCCGGCTCGGGGCCAAGAACAGATGGTCCCCAGATGCGGTCC /molkit/dnadot/ 两条相同序列的比对 课堂练习 GGGATCACGTATGCATTAGCATACATCACGCGG CCGCGTGATGTATGCTAATGCATACGTGATCCC 第二条序列是第一条序列的反向互补序列， 通过点阵图分析寻找序列可能的发夹状结构。 思考：点阵法为什么可以发现RNA序列的发夹状结构？ 发夹结构 双序列比对的动态规划算法 进行双序列比对最直接的方法是生成两序列的所有可能的比对，分别计算得分，然后挑选一个得分最高的比对作为最终结果。 但可能的比对是序列长度的指数函数。 AATCGT AGTCGA AATCGT- -ATCGTA AATCGT--- ---CGTCGA N-W算法是一种全局比对动态规划算法，于1970年被提出，得到了非常广泛的应用。 首先假设我们要对两条序列a和b进行比对，它们的长度分别为M和N，序列a