生物信息学第二版序列比对ppt课件

生物信息学生物信息学第二章第二章 序列比对序列比对南方医科大学南方医科大学 朱浩朱浩吉林大学吉林大学 李瑛李瑛生物信息学生物信息学第一节第一节 引引 言言 Section 1 Introduction 3一一 同源同源两个序列享有一个共同的进化上的祖先，那么这两个序列是同源的。两个序列享有一个共同的进化上的祖先，那么这两个序列是同源的。对于两个序列，他们或者同源或者不同源，不能说他们对于两个序列，他们或者同源或者不同源，不能说他们70%或或80%同源。同源。、同源、类似与间隔、同源、类似与间隔4同源可分为垂直同源同源可分为垂直同源ortholog和程度同源和程度同源paralog垂直同源与程度同源垂直同源与程度同源5二类似性与间隔二类似性与间隔类似性、间隔：是两个定量描画多个序列类似度的度量。类似性、间隔：是两个定量描画多个序列类似度的度量。类似性：被比对序列之间的类似程度。类似性：被比对序列之间的类似程度。间隔：被比对序列间的差别程度。间隔：被比对序列间的差别程度。类似性既可用于全局比对也可用于部分比对，而间隔普通仅用于全局比对，类似性既可用于全局比对也可用于部分比对，而间隔普通仅用于全局比对，由于它反映了把一个序列转换成另一个序列所需字符交换的耗费。由于它反映了把一个序列转换成另一个序列所需字符交换的耗费。6二、类似与间隔的定量描画二、类似与间隔的定量描画类似性可定量地定义为两个序列的函数，即它可有多个值，值的大小取决于类似性可定量地定义为两个序列的函数，即它可有多个值，值的大小取决于两个序列对应位置上一样字符的个数，值越大那么表示两个序列越类似。两个序列对应位置上一样字符的个数，值越大那么表示两个序列越类似。编辑间隔编辑间隔edit distance也可定量地定义为两个序列的函数，其值取决于两也可定量地定义为两个序列的函数，其值取决于两个序列对应位置上差别字符的个数，值越小那么表示两个序列越类似。个序列对应位置上差别字符的个数，值越小那么表示两个序列越类似。7对于一个比对，不论运用什么计分函数进展计分，类似性被定义为总等值对于一个比对，不论运用什么计分函数进展计分，类似性被定义为总等值于最大的计分：于最大的计分：对于对于k个序列，假设用一个函数个序列，假设用一个函数cost对每一列的一切交换操作进展计分，对每一列的一切交换操作进展计分，那么多个序列之间的间隔等值于最小的计分：那么多个序列之间的间隔等值于最小的计分：8对类似性的计分对类似性的计分9编辑间隔编辑间隔edit distance：普通用海明间隔表示。：普通用海明间隔表示。10三、算法实现的比对三、算法实现的比对用计算机科学的术语来说，比对两个序列就是找出两个序列的最长公共子序用计算机科学的术语来说，比对两个序列就是找出两个序列的最长公共子序列列longest common subsequence，LCS，它反映了两个序列的最高类似，它反映了两个序列的最高类似度。度。11动态规划法表示动态规划法表示A运用动态规划法寻觅两个序列的最长公共部分；运用动态规划法寻觅两个序列的最长公共部分；B动态规划表的填写。动态规划表的填写。12四、序列比对的作用四、序列比对的作用获得共性序列获得共性序列序列测序序列测序突变分析突变分析种系分析种系分析保守区段分析保守区段分析基因和蛋白质功能分析基因和蛋白质功能分析13第二节第二节 比对算法概要比对算法概要Section 2 Alignment Algorithms14一经过点矩阵对序列比较进展计分一经过点矩阵对序列比较进展计分A.两条序列完全一样两条序列完全一样一、交换计分矩阵一、交换计分矩阵15B.两条序列有一个共同的子序列两条序列有一个共同的子序列16C.两条序列反向匹配两条序列反向匹配17D.两条序列存在不延续的两条子序列两条序列存在不延续的两条子序列18二二DNADNA序列比对的交换计分矩阵序列比对的交换计分矩阵等价矩阵等价矩阵unitary matrix转换转换-颠换矩阵颠换矩阵transition-transversion matrixBLAST矩阵矩阵19核苷酸转换矩阵核苷酸转换矩阵20三蛋白质序列比对的交换计分矩阵三蛋白质序列比对的交换计分矩阵等价矩阵等价矩阵遗传密码矩阵遗传密码矩阵GCM疏水性矩阵疏水性矩阵hydrophobic matrix PAM矩阵矩阵BLOSUM矩阵矩阵21PAM矩阵是从蛋白质序列的全局比对结果推导出来的，而矩阵是从蛋白质序列的全局比对结果推导出来的，而BLOSUM 矩阵那矩阵那么是从蛋白质序列块短序列比对推导出来的。么是从蛋白质序列块短序列比对推导出来的。PAM/BLOSUM矩阵编号与序列亲缘关系的比较矩阵编号与序列亲缘关系的比较22二、双序列全局比对二、双序列全局比对动态规划算法的思想动态规划算法的思想 a,b是运用某一字符集是运用某一字符集的序列的序列DNA 或蛋白质序列；或蛋白质序列；m=a的长度；的长度；n=b的长度；的长度；Si,j 是按照某交换计分矩阵得到的前缀是按照某交换计分矩阵得到的前缀a1.i与与b1.j最大类似性得分；最大类似性得分；23 wc,d是字符是字符c和和d按照交换计分矩阵计算的得分。按照交换计分矩阵计算的得分。可按照规那么建立得分矩阵：可按照规那么建立得分矩阵：Si,0=0,0 i mS0,j=0,0 j n Si-1,j-1+wai,bj 匹配或错配匹配或错配Si,j=max Si-1,j+wai,-插入插入 Si,j-1 缺失不罚分缺失不罚分24例如，对于序列例如，对于序列a=ACACACTA，序列，序列b=AGCACACA，计分规那么，计分规那么w匹配匹配=+2；wa,-=w-,b=w失配失配=-125得分矩阵得分矩阵26三、双序列部分比对三、双序列部分比对处置子序列与完好序列或短序列与长序列比对的普经过程是：设短序列处置子序列与完好序列或短序列与长序列比对的普经过程是：设短序列a和长序列和长序列b，它们的长度分别为，它们的长度分别为La和和Lb，比对是在，比对是在b序列中寻觅序列中寻觅La长度的长度的a序列的过程。序列的过程。27四、多序列全局比对四、多序列全局比对多序列比对主要涉及四个要素：多序列比对主要涉及四个要素：选择一组能进展比对的序列要求是同源序列；选择一组能进展比对的序列要求是同源序列；选择一个实现比对与计分的算法与软件；选择一个实现比对与计分的算法与软件；确定软件的参数；确定软件的参数；合理地解释比对的结果；合理地解释比对的结果；与双序列比对一样，多序列比对也有全局比对和部分比对。与双序列比对一样，多序列比对也有全局比对和部分比对。28一动态规划法进展多序列比对一动态规划法进展多序列比对A计算三个序列间的一个比对单元计算三个序列间的一个比对单元i,j,k依赖于其依赖于其7个前导项；个前导项；B计算计算u=ATGTTAT，v=ATCGTAC，w=ATGC三序列比对的三维得分矩阵三序列比对的三维得分矩阵。计算三序列比对计算三序列比对29二渐进多序列比对二渐进多序列比对三个序列的配对比对未必能组合成一个多序列比对三个序列的配对比对未必能组合成一个多序列比对30对于接近或超越对于接近或超越100个序列的多序列比对，渐进多序列比对具有较高效率。最个序列的多序列比对，渐进多序列比对具有较高效率。最流行的渐进多序列比对软件是流行的渐进多序列比对软件是Clustal家族。家族。31ClustalW有以下特点：有以下特点：首先，在比对中对每个序列赋予一个特殊的权值以降低高度近似序列的影响和提首先，在比对中对每个序列赋予一个特殊的权值以降低高度近似序列的影响和提高相距遥远的序列的影响如以下图。高相距遥远的序列的影响如以下图。ClustalW中对序列赋权的方法中对序列赋权的方法32其次，根据序列间进化间隔的离异度其次，根据序列间进化间隔的离异度divergence在比对的不同阶段运用不同在比对的不同阶段运用不同的氨基酸交换矩阵；的氨基酸交换矩阵；第三，采用了与特定氨基酸相关的空缺第三，采用了与特定氨基酸相关的空缺gap罚分函数，对亲水性氨基酸区域罚分函数，对亲水性氨基酸区域中的空缺予以较低的罚分；中的空缺予以较低的罚分；第四，对在早期配对比对中产生空缺的位置进展较少的罚分，对引入空缺和扩展第四，对在早期配对比对中产生空缺的位置进展较少的罚分，对引入空缺和扩展空缺进展不同的罚分。空缺进展不同的罚分。33迭代法迭代法基于一致性的方法基于一致性的方法遗传算法遗传算法其他多序列全局比对方法其他多序列全局比对方法34五、多序列部分比对五、多序列部分比对全局比对，其共同特征是序列中一切对应字符均假定可以匹配，一切字符具全局比对，其共同特征是序列中一切对应字符均假定可以匹配，一切字符具有同等的重要性，空格的插入是为了使整个序列得到比对，包括使两端对齐。有同等的重要性，空格的插入是为了使整个序列得到比对，包括使两端对齐。部分比对不假定整个序列可以匹配，重在思索序列中可以高度匹配的一个区部分比对不假定整个序列可以匹配，重在思索序列中可以高度匹配的一个区段，可赋予该区段更大的计分权值，空格的插入是为了使高度匹配的区段得段，可赋予该区段更大的计分权值，空格的插入是为了使高度匹配的区段得到更好的比对。到更好的比对。35对对2个序列进展全局和部分比对可得到完全不同的结果个序列进展全局和部分比对可得到完全不同的结果36 基于隐马尔可夫模型的多序列比对方法基于隐马尔可夫模型的多序列比对方法隐马尔可夫模型和隐马尔可夫模型和3个蛋白质序列个蛋白质序列PHSFTYVMT、PGSFTYW、RFTGFW的最小公共超图的最小公共超图37六、比对的统计显著性六、比对的统计显著性确定比对得分确定比对得分score能否偶尔：能否偶尔：1.将将球蛋白或肌球蛋白与大量非同源的蛋白质做比对，然后将球蛋白或肌球蛋白与大量非同源的蛋白质做比对，然后将score与这些比与这些比对的得分进展比较。对的得分进展比较。2.把一个序列与一组随机产生的序列进展比对，然后同样将把一个序列与一组随机产生的序列进展比对，然后同样将score与这些比对的与这些比对的得分进展比较。得分进展比较。3.随机将两个序列中的一个打乱重组，比如说重组随机将两个序列中的一个打乱重组，比如说重组100次，并与另一个序列比对，次，并与另一个序列比对，同样得到一组比对的得分。同样得到一组比对的得分。38第三节第三节 数据库搜索数据库搜索Section 3 Database Search39一、经典一、经典BLASTBLAST根本的根本的BLAST算法本身很简单，它的要点是片段对算法本身很简单，它的要点是片段对segment pair的概的概念，它是指两个给定序列中的一对子序列，它们的长度相等，且可以构成念，它是指两个给定序列中的一对子序列，它们的长度相等，且可以构成无空格的完全匹配。无空格的完全匹配。40程序名程序名查询序列查询序列数据库类型数据库类型方法方法blastp蛋白质蛋白质蛋白质蛋白质用蛋白质查询序列搜索蛋白质序列数据库用蛋白质查询序列搜索蛋白质序列数据库blastn核酸核酸核酸核酸用核酸查询序列搜索核酸序列数据库用核酸查询序列搜索核酸序列数据库blastx核酸核酸蛋白质蛋白质将核酸序列按将核酸序列按6条链翻译成蛋白质序列后搜索蛋白质条链翻译成蛋白质序列后搜索蛋白质序列数据库序列数据库tblastn蛋白质蛋白质核酸核酸用蛋白质查询序列搜索核酸序列数据库，核酸序列按用蛋白质查询序列搜索核酸序列数据库，核酸序列按6条链翻译成蛋白质条链翻译成蛋白质tblastx核酸核酸核酸核酸将核酸序列按将核酸序列按6条链翻译成蛋白质序列后搜索由核酸条链翻译成蛋白质序列后搜索由核酸序列数据库按序列数据库按6条链翻译成的蛋白质序列的数据库条链翻译成的蛋白质序列的数据库BLAST的查询序列和数据库的类型的查询序列和数据库的类型41BLAST算法图示算法图示42二、衍生二、衍生BLASTBLAST一一PSI-BLASTPSI-BLAST主要用于搜索与感兴趣的蛋白质关系较远的蛋白质。主要用于搜索与感兴趣的蛋白质关系较远的蛋白质。二二PHI-BLASTPHI-BLAST用来协助判别这个蛋白质属于哪个家族。用来协助判别这个蛋白质属于哪个家族。三三BLASTZBLASTZBLASTZBLASTZ是在比对人和鼠的基因组中开展起来的，它适宜于比对非常长的序列。是在比对人和鼠的基因组中开展起来的，它适宜于比对非常长的序列。43三、三、BLATBLATBLATThe BLAST-Like Alignment Tool与与BLAST搜索原理类似，但开展搜索原理类似，但开展了一些专门针对全基因组分析的技术。了一些专门针对全基因组分析的技术。BLAT的优点在于速度快，其比对速度要比的优点在于速度快，其比对速度要比BLAST快几百倍，其根本缘由在快几百倍，其根本缘由在于于:BLAST是将查询序列索引化，而是将查询序列索引化，而BLAT那么是将搜索数据库索引化，那么是将搜索数据库索引化，BLAT 把相关的呈共线性的比对结果衔接成为更大的比对结果。把相关的呈共线性的比对结果衔接成为更大的比对结果。44四、四、RNARNA序列搜索序列搜索RNA序列比对序列比对/搜索算法可大致分成两类：搜索算法可大致分成两类：查询序列查询序列query的构造未知，要找到数据库中和其构造相近的同源序列。的构造未知，要找到数据库中和其构造相近的同源序列。45 利用查询序列的构造信息，在构造信息的运用上又可以细分为：利用查询序列的构造信息，在构造信息的运用上又可以细分为：经过构建一个描画经过构建一个描画RNA序列共性构造的概率模型进展数据库检索；序列共性构造的概率模型进展数据库检索；基于索引基于索引index或者模体或者模体motif描画的方法定义描画的方法定义rna构造或共性构造，构造或共性构造，并进展数据库搜索。并进展数据库搜索。46五、数据库搜索的统计显著性五、数据库搜索的统计显著性一个典型的一个典型的BLAST搜索的输出包括搜索的输出包括E值和得分，后者又分原始得分值和得分，后者又分原始得分raw scores和比特得分和比特得分bit scores。P=1-e-EP值和值和E值是反映比对显著性的两种不同方式，大部分值是反映比对显著性的两种不同方式，大部分BLAST在线效在线效力运用力运用E值而非值而非P值来定义搜索的统计学显著性。值来定义搜索的统计学显著性。47第四节第四节 比对软件、参数与数据资源比对软件、参数与数据资源Section 4 Alignment Software，Parameter and Resource48一、参数选择的普通原那么一、参数选择的普通原那么空格罚分涉及几个问题：空格罚分涉及几个问题：空格罚分能否大于失配罚分；空格罚分能否大于失配罚分；不同大小空缺的罚分；不同大小空缺的罚分；空格的引入与延伸能否予以不同罚分。空格的引入与延伸能否予以不同罚分。49假设一次数据库搜索产生了太多的前往结果，可采取如下措施：假设一次数据库搜索产生了太多的前往结果，可采取如下措施：运用参考序列带运用参考序列带“refseq的数据库，这样可减少许多冗余结果；的数据库，这样可减少许多冗余结果；使查询序列只包含一个构造域，减少多构造域带来的多匹配；使查询序列只包含一个构造域，减少多构造域带来的多匹配；根据查询序列与数据库序列的关系运用更适宜的交换计分矩阵；根据查询序列与数据库序列的关系运用更适宜的交换计分矩阵；降低降低E值。值。50假设一次数据库搜索产生了太少的前往结果，可采取如下措施：假设一次数据库搜索产生了太少的前往结果，可采取如下措施：提高提高E值；值；运用更大的运用更大的PAM矩阵或更小的矩阵或更小的BLOSUM矩阵；矩阵；减小字长以及减小阈值。减小字长以及减小阈值。51二、主要比对软件二、主要比对软件52三、三、EBIEBI中的序列比对工具中的序列比对工具双序列比对双序列比对多序列比对多序列比对特性特性工具工具工具工具Global alignmentNeedleClustal OmegaGlobal alignmentStretcherClustalW2Local alignmentWaterDbClustalLocal alignmentLalignKalignLocal alignmentMatcherMAFFTGenomic alignmentPromoterWiseMUSCLEGenomic alignmentGeneWiseMViewGenomic alignmentWise2DBAPRANK53四、四、UCSCUCSC中的中的BLATBLAT比对工具比对工具BLAT在线工具在线工具输入界面输入界面54BLAT在线工具在线工具输出结果输出结果55第五节第五节 比对技术的开展比对技术的开展Section 5 Advances of Alignment Techniques56一、一、glocal glocal 比对比对两个序列的部分、全局和两个序列的部分、全局和glocal比对所对应的途径比对所对应的途径57二、全基因组比对二、全基因组比对全基因组比对主要提示多个序列中保守的和非保守的区段以及这些区段在基因全基因组比对主要提示多个序列中保守的和非保守的区段以及这些区段在基因组中的分布特征，这里主要引见组中的分布特征，这里主要引见UCSC基因组阅读器基因组阅读器The UCSC Genome Browser中的全基因组比对方法。中的全基因组比对方法。58UCSCUCSC基因组阅读器中所采用的多序列比对在多方面作了改良基因组阅读器中所采用的多序列比对在多方面作了改良首先，它采用了参照序列首先，它采用了参照序列reference sequence，运用，运用BLASTZ将每一个序将每一个序列与参照序列进展部分配对比对，参照序列中的一个碱基比对另一个序列中列与参照序列进展部分配对比对，参照序列中的一个碱基比对另一个序列中的至多一个碱基。的至多一个碱基。其次，根据计分矩阵和两序列的种系关系，对配对比对的结果进展所谓的其次，根据计分矩阵和两序列的种系关系，对配对比对的结果进展所谓的“串串连连chaining和和“连网连网netting。接着，接着，UCSC基因组阅读器运用基因组阅读器运用MULTIZ对多个对多个“串连的配对比对进展渐进串连的配对比对进展渐进多序列比对。多序列比对。59小小 结结序列比对是基因和序列比对是基因和DNA序列分析的根底，所根据的两个中心概念是同源和类似，序列分析的根底，所根据的两个中心概念是同源和类似，同源序列普通是类似的，类似序列不一定是同源的。多序列比对是双序列比对的同源序列普通是类似的，类似序列不一定是同源的。多序列比对是双序列比对的自然推行，采用更多物种的序列进展多序列比对经常能更准确和更可靠地提示序自然推行，采用更多物种的序列进展多序列比对经常能更准确和更可靠地提示序列的同源性和保守域。列的同源性和保守域。60