生物信息学概论数据库搜索与两两比对省公共课一等奖全国赛课获奖课件.pptx

第二章 数据搜索与两两比对 本章描述了 怎样比对两条或多条相关核苷酸或多肽序列，怎样比对两条或多条相关核苷酸或多肽序列，怎样搜索存放序列信息数据库。怎样搜索存放序列信息数据库。经过比对得到预测蛋白质、新基因结构和功效以及基因间、蛋白质间乃至物种之间进化关系主要信息。第1页2.1 点阵图 评定两条序列相同度最简单方法之一是利用点阵图点阵图。第一条被比较序列排列在点阵图空间横轴，第二条序列则排列在纵轴。点阵空间中两条序列中残基相同时，在对应位点上画上圆点，两条序列间连续相同区域在图中会形成由圆点组成上斜线。第2页含有连续相同区域两条含有连续相同区域两条DNA序列简单点阵图序列简单点阵图第3页滑动窗口技术滑动窗口技术 使用滑动窗口滑动窗口代替一次一个位点比较是处理这 个问题有效方法。假设窗口大小窗口大小为10，相同度阈值相同度阈值为8，则每次比较取10个连续字符，如相同字符超出8个，则标识 基于滑动窗口滑动窗口点矩阵点矩阵方法能够显著地降低点阵图噪声，而且明确无误指示出了两条序列间含有显著相同性区域。第4页（a）对人类（）对人类（Homo sapiens）与黑猩猩（）与黑猩猩（Pongo pygmaeus）球蛋白球蛋白基因序列进行比较完整点阵图。（基因序列进行比较完整点阵图。（b）利用滑动窗口对以上两种球蛋白基因）利用滑动窗口对以上两种球蛋白基因序列进行比较点阵图，其中窗口大小为序列进行比较点阵图，其中窗口大小为10个核苷酸，相同度阈值为个核苷酸，相同度阈值为8。(a)(b)第5页2.2 2.2 简单比对简单比对比对比对就是两条序列字符间简单两两匹配。比对能够反应出两条或多条同源序列间进化关系.最简单情况下即不考虑空位，当两条序列对比时，要做仅是为较短序列选择比正确起始点。第6页考虑这么两条核苷酸序列：AATCTATA和AAGATA 仅有三种比对方式不考虑空位简单比对，它打分函数是有对比奖励和罚分和来决定上例中三个比对从左至右分别是 4、1、3匹配得分：匹配得分：1失配得分：失配得分：0第7页2.3 空位空位两条或多条序列比对时，假如考虑到插入与删除时间发生地可能性，那么候选比对数量就会大大增加，也就造成了比正确复杂性。上节中两条核苷酸序列，在不考虑空位时仅有三种比对，而较短那条加入了两个空位后，变产生了28种不一样比对，比如：等等第8页2.3.1 简单空位罚分简单空位罚分对含有空位比对打分时，空位罚分空位罚分就必须包含到打分函数中，空位比正确简单打分公式以下：比如：假设匹配得分为1，失配得分为0，空位罚分为-1三种空位比对得分从左至右分别是1、3、3第9页2.3.2 起始罚分与长度罚分起始罚分与长度罚分使用简单空位罚分对两条序列进行比对时，经常能找到若干同格式最优比对。深入区分这些比正确方法是找出哪些比对包含较多不连续空位，哪些包含较少长度较长空位片段。第10页插入插入/删除事件删除事件假设两条序列长度分别是12和9假设这两条序列是真正同源序列，那么它们之间长度差异能够解释为(1)较长序列有核苷酸插入，或者(2)较短序列发生了核苷酸删除，或者(3)二者都发生了。在不知道原始父辈序列情况下，无法判断造成空位原因是因为一条序列插入事件还是另一条删除事件，通常把这类事件称为插入插入/删除事件删除事件。第11页多联核苷酸插入删除事件插入删除事件相对于单个核苷酸来说会较经常发生。统计结果表明，两条序列长度上差异更可能是单个三联核苷酸插入删除事件造成，而多个不连续核苷酸插入删除事件可能性比较小。空位罚分空位罚分由序列中产生新空位串引发起始罚分起始罚分和依据缺乏字符数而定长度罚分长度罚分。预设长度罚分小于起始罚分，以此建立打分函数便能奖励空位连在一起比对。第12页假设起始罚分为-2，长度罚分为-1，匹配得分为+1，失配得分为0，则对于这三个比对，从左至右比对得分分别是-3，-1，+1在后两种比对在使用简单空位罚分时，最终得分都是在后两种比对在使用简单空位罚分时，最终得分都是+3，现在却得到了不一样分数。，现在却得到了不一样分数。第13页2.4打分矩阵打分矩阵正如空位罚分空位罚分能够奖励与进化相关比对，失配罚分失配罚分也能够用来深入区分相同比对。统计结果表明，两条同源序列比对时，一些替换比其它替换常见多。例例：两条蛋白质序列，其中一条在某一个位置上是丙氨酸，假如该位点被替换成另一个较小且疏水氨基酸，比如缬氨酸对蛋白质影响很小，假如被替换成较大且带电残基，比如赖氨酸，那么对蛋白质影响可能就会非常大。直观讲，比较保守替换比随机替换更可能维持蛋白质功效，更不轻易被淘汰，所以在打分上更倾向于丙氨酸而不是赖氨酸。第14页打分矩阵（打分矩阵（Scoring Matrix）核酸打分矩阵设DNA序列所用字母表为 =A，C，G，T a.单位矩阵 b.BLAST矩阵 c.转换-颠换矩阵（transition，transversion）（嘌呤：腺嘌呤A，鸟嘌呤G；嘧啶：胞嘧啶C，胸腺嘧啶T）ATCGA1000T0100C0010G0001ATCGA5-4-4-4T-45-4-4C-4-45-4G-4-4-45ATCGA1-5-5-1T-51-1-5C-5-11-5G-1-5-51单位矩阵单位矩阵转换转换-颠换矩阵颠换矩阵BLAST矩阵矩阵第15页PAM矩阵（矩阵（Point Accepted Mutation）基于进化点突变模型基于进化点突变模型 一个一个PAM就是一个进化变异单位就是一个进化变异单位,即即1%氨基酸改变氨基酸改变相对突变率相对突变率仅仅是某种氨基酸仅仅是某种氨基酸 被其它任意氨基酸替换次数被其它任意氨基酸替换次数比如：ma是指丙氨酸与非丙氨酸残基比正确次数，是指丙氨酸与非丙氨酸残基比正确次数，Ma为概率为概率然而我们针对每个氨基酸对然而我们针对每个氨基酸对i 和和j，计算氨基酸，计算氨基酸j 被氨基酸被氨基酸i 替换次数替换次数 Aij比如：Acm 是被比对序列中，甲硫氨酸被半胱氨酸替换次数是被比对序列中，甲硫氨酸被半胱氨酸替换次数以以Aij除以除以ma 利用每个氨基酸出现频度对起进行标准化，得到利用每个氨基酸出现频度对起进行标准化，得到PAM-1矩阵矩阵中元素中元素Rij第16页式中Mab为任意氨基酸b替换a概率式中pa为氨基酸a未被替换概率第17页100个残基发生一次替换PAM-1矩阵第18页针对不一样进化距离采取针对不一样进化距离采取PAM 矩阵矩阵序列相同度序列相同度=40%50%60%|打分矩阵打分矩阵 =PAM120 PAM80 PAM 60PAM250 14%-27%第19页2.5 动态规划动态规划:Needleman 和和 Wunsch 算法算法一旦选定了序列比对打分方法，就可认为寻找最佳比对设计算法了。最显而易见方法就是对每个可能比对进行穷举搜索，但这一般是不可行。我们可以用动态规划解决这个问题，即把一个问题分解成计算量合理子问题，并使用这些子问题结果来计算最终答案。S.Needleman与C.Wunsch首次运用动态规划方法来进行序列分析。第20页假设两条序列：CACGA和CGA，使用统一空位空位和失失配罚分配罚分则：1、给第一条序列加一个空位 2、给第二条序列加一个空位 3、两条序列都不加空位第21页假如知道了ACGA与GA最正确比正确得分，就能够马上计算出表中第一行得分。一样地，假如知道了表中第二、第三行剩下序列最正确比正确得分，就能够计算出起始位点不一样三种比对得分。动态规划算法动态规划算法经过计算部分序列比对得分并填入一个表格，直到整个序列比对被计算出来，由此得到最优比对。第一位点 得分待对比剩下序列CC+1ACGAGA-C-1CACGAGAC-1ACGACGA（匹配得分为1，失配得分为0，空位罚分为-1）第22页动态规划动态规划比对ACAGTAG与ACTCG空位罚分为-1匹配奖励为+1失配得分为 00-1-2-3-4-5-1-2-3-4-5-6-7 A C T C GACAGTAG用空位罚分倍数对用空位罚分倍数对表格第一行与第一表格第一行与第一列进行初始化列进行初始化第23页填充表格填充表格0-1-2-3-4-5-1-2-3-4-5-6-7 A C T C GACAGTAG表格中表格中横向移动横向移动表示在表示在纵轴序列中加入一个空纵轴序列中加入一个空位位纵向移动纵向移动表示在横轴序表示在横轴序列中加入一个空位列中加入一个空位斜对角向移动斜对角向移动表示两序表示两序列各自对应核苷酸进行列各自对应核苷酸进行了比对了比对横向移动横向移动纵向移动纵向移动斜对角向移动斜对角向移动第24页0-1-2-3-4-5-1-2-3-4-5-6-7 A C T C GACAGTAG-1-1=-2，表示在横向序列中插，表示在横向序列中插入一个空位，然后与纵向序列入一个空位，然后与纵向序列中中A比较，空位罚分比较，空位罚分-1。-1-1=-2，表示在纵，表示在纵向序列中插入一个向序列中插入一个空位，然后与横向空位，然后与横向序列中序列中A比较，空比较，空位罚分位罚分-1。0+1=1，表示两序，表示两序列第一个列第一个A进行对进行对比，匹配奖励比，匹配奖励1。-2-2-2-21 11第25页0-1-2-3-4-5-1-2-3-4-5-6-7 A C T C GACAGTAG1-1=0，表示在横向序列中插入，表示在横向序列中插入一个空位，然后与纵向序列中一个空位，然后与纵向序列中C比较，空位罚分比较，空位罚分-1。-2-1=-3，表示在纵，表示在纵向序列中插入一个向序列中插入一个空位，然后与横向空位，然后与横向序列中序列中A比较，空比较，空位罚分位罚分-1。-1+0=-1，表示横向，表示横向序列序列A与纵向序列与纵向序列C进行比较，失配得进行比较，失配得分分0。-3-3-1-110 00第26页0-1-2-3-4-5-1-2-3-4-5-6-7 A C T C GACAGTAG-2-1=-3，表示在横向序列中插，表示在横向序列中插入一个空位，然后与纵向序列入一个空位，然后与纵向序列中中A比较，空位罚分比较，空位罚分-1。1-1=0，表示在纵，表示在纵向序列中插入一个向序列中插入一个空位，然后与横向空位，然后与横向序列中序列中C比较，空比较，空位罚分位罚分-1。-1+0=-1，表示横向，表示横向序列序列C与纵向序列与纵向序列A进行比较，失配得进行比较，失配得分分0。0 0-1-11-3-300第27页0-1-2-3-4-5-1-2-3-4-5-6-7 A C T C GACAGTAG0-1=-1，表示在横向序列中插入，表示在横向序列中插入一个空位，然后与纵向序列中一个空位，然后与纵向序列中C比较，空位罚分比较，空位罚分-1。0-1=-1，表示在纵，表示在纵向序列中插入一个向序列中插入一个空位，然后与横向空位，然后与横向序列中序列中C比较，空比较，空位罚分位罚分-1。1+1=2，表示横向，表示横向序列序列C与纵向序列与纵向序列C进行比较，匹配奖进行比较，匹配奖励励1。-1-1100-1-12 22 第28页0-1-2-3-4-5-110-1-2-3-20210-1-3-11210-4-20122-5-3-1112-6-4-2011-7-5-3-102A C T C GACAGTAG为了利用打分表重建比对重建比对，需要找出一条由表格中最右下角到最左上角路径！动态规划动态规划第29页途中箭头指示了部分打分表中正当路径，每条路径代表若干等价最优比对路径自右下至左上排列自来分别是 依据这条线路，能够重建比对，能够得到以下这个得分为2最优比对0-1-2-3-4-5-110-1-2-3-20210-1-3-11210-4-20122-5-3-1112-6-4-2011-7-5-3-102A C T C GACAGTAG第30页2.6 全局对比与局部比对全局对比与局部比对2.6.1 准全部比对准全部比对到当前为止，全部讨论基本比对算法仅是做了全局比全局比对对。而比对两序列时，这并不总是可取。假如从AAACACGTGTCT中搜寻段序列ACGT。在若干种两序列比对中，我们需要是区分对待末端空位与序列内部空位这种比对称为准全局比对准全局比对 (semiglobal alignment)第31页准全局比对准全局比对(1)经过初始化部分打分表，表格第一行与第一列为零；(2)允许表格最终一行与一列横向与纵向移动不被罚分；Needleman 和和 Wunsch 算法改进算法改进（准全局比对）（准全局比对）第32页2.6.2 Smith-Waterman算法算法准全局比对有时有点不能为序列搜索提供所需适应性需要进行局部比对局部比对比如：两条序列 AACCTATAGCT 和 GCGATATA，用准全局比对算法，空位罚分为-1，匹配奖励为+1，失配得分为-1，得：第33页局部比对时，表中小于零位置用零代替局部比对时，表中小于零位置用零代替AACCTATAGCT GCGATATA A A C C T A T A G C T第34页2.6.2 Smith-Waterman算法算法局部比对局部比对1981年，由F.Smith 和 M.Waterman首次提出；动态规划方法经过较少改动便能够用来识别匹配子序列，而且忽略匹配区域之前或之后失配和空位;局部比对时，表中小于零位置用零代替;得到局部比对代表了被比两条序列间最正确匹配子序列；局部比对方法能够识别子序列匹配，而这是全局与准全局比对不可能做到。第35页2.72.7数据库搜索数据库搜索尽管序列比对是比较两条已知序列极为主要工具，然而序列比正确更为常见用途是用来搜索大量序列数据库，以找到与特定序列相同那些序列。在数据库搜索过程中，因为被搜索序列很长，而且数量巨大，用简单而直接方法将数据库中每条序列与查询序列进行比对并返回得分最高序列难以奏效。作为替换方法，各种索引方法与启发方式被用来加紧搜索过程，即使不能确保与查询序列比正确最好，不过能返回大部分与查询序列比对很好，而且这些方法效率很高。第36页2.7.1 BLAST及其家族及其家族序列数据库搜索最著名且惯用工具之一是BLAST算法，原始BLAST算法是经过搜索序列数据库来找出最优空间局部比对。BLASTP是BLAST算法一个变种为了有效地搜索大型数据库，BLASTP首先将查询序列打坏成一个个单词，查询序中全部可能单词是经过查询序列上滑动与单词等长窗口来得到。除了BLASTP，还有BLASTN和BLASTX等等.第37页BLASTP搜索算法概述搜索算法概述第38页2.7.2 FASTA及其相关算法及其相关算法FASTA算法及家族组员能够进行序列间含空位局部比对。FASTA搜索非常细致，需要时间也长多。FASTA搜索也是将搜索序列打坏成单词。第39页对于氨基酸序列FAMLGFIKYLPGCM，假设单词长度为1，那么：目标序列TGFIKYLPGACT，那么对照表格发觉，甘氨酸（G）在第一个表中位置为5、12，在第二个表中为-4、3，再观察其它出现了很多距离为3情况，这一现象暗示了一个可能合理比对。经过两条序列偏移表，即可发觉相同区域。单词ACDEFGHIKLMNPQRSTVWY位置2131578431196121014123456789101112TGFIKYLPGACT3-2333-33-4-8210333第40页2.7.3 2.7.3 数据库搜索比对得分与统计显著性数据库搜索比对得分与统计显著性数据库搜索引擎普通都为每个搜索结果提供P得分和E得分加入搜索结果比对得分为S，那么P和和E得分得分指是用于随机找出一条或多条序列，比对得分大于等于S可能性。P与E值比较低说明该结果与查询序列含有进化上关系。第41页2.8 2.8 多重序列比对多重序列比对 (multiple sequence alignment)到当前为止，所讨论比对算法都是为进行序列两两比较而设计，然而同时比对多条序列也是很主要。当统计一组序列替换率时，多重序列比对通常比两两比对更适当，因为多重比对尽可能地多考虑到了序列中空位。多重比对对于打分矩阵建立也很主要，比如本章前面讨论PAM与BLOSUM矩阵。第42页不过因为伴随比对序列数量增大，多重比对算法复杂度呈指数级增加，就算是使用超级计算机或者工作站分布式网络，要对20条以上含有普通长度与复杂度序列进行比对，仍是非常棘手问题。所以，利用启发式比对方法启发式比对方法被提出来，这类方法不能确保产生一个最优比对，不过能找出一个近似最优比对。第43页本章总结本章总结两条或多条基因或氨基酸序列间比对序列间比对代表着一个相关这些序列从共同祖先开始进化路径假设。尽管真正进化路径无法被明确无误推断出，但序列比对算法能够识别随机发生率很低那些比对，各种技术能够用来左右打分函数，比如PAM与BLOSUM。Needleman与 Wunsch首先提出全局比对算法全局比对算法以及Smith与Waterman 提出局部比对算法局部比对算法已经成为了众多数据库搜索算法基础，包含 BLASTX 等工具。这些算法利用了索引、启发式和快速比较等技术，使得整个数据库中序列能与查询序列在很短时间内完成。第44页课堂练习课堂练习P47：2.2 在图纸上绘出以下两条序列简单点阵图。将序列沿各自坐标轴放置，为每个相同核苷酸对在图上画上圆点：GCTAGTCAGATCTGACGCTA GATGGTCACATCTGCCGC 标明点阵图上相同区域第45页课后作业课后作业P48：2.3 2.4 2.5 2.6第46页