生物信息学序列比对ppt学习课件.ppt

,第二章序列比对,生物信息学,第一节引言,Section1Introduction,（一）同源,两个序列享有一个共同的进化上的祖先，则这两个序列是同源的。对于两个序列，他们或者同源或者不同源，不能说他们70%或80%同源。,、同源、相似与距离,同源可分为垂直同源（ortholog）和水平同源（paralog）,垂直同源与水平同源,（二）相似性与距离,相似性、距离：是两个定量描述多个序列相似度的度量。相似性：被比对序列之间的相似程度。距离：被比对序列间的差异程度。相似性既可用于全局比对也可用于局部比对，而距离一般仅用于全局比对，因为它反映了把一个序列转换成另一个序列所需字符替换的耗费。,二、相似与距离的定量描述,相似性可定量地定义为两个序列的函数，即它可有多个值，值的大小取决于两个序列对应位置上相同字符的个数，值越大则表示两个序列越相似。编辑距离（editdistance）也可定量地定义为两个序列的函数，其值取决于两个序列对应位置上差异字符的个数，值越小则表示两个序列越相似。,对于一个比对，不论使用什么计分函数进行计分，相似性被定义为总等值于最大的计分：,对于k个序列，如果用一个函数cost（）对每一列的所有替换操作进行计分，则多个序列之间的距离等值于最小的计分：,对相似性的计分,编辑距离（editdistance）：一般用海明距离表示。,三、算法实现的比对,用计算机科学的术语来说，比对两个序列就是找出两个序列的最长公共子序列（longestcommonsubsequence，LCS），它反映了两个序列的最高相似度。,动态规划法示意,（A）使用动态规划法寻找两个序列的最长公共部分；（B）动态规划表的填写。,四、序列比对的作用,获得共性序列序列测序突变分析种系分析保守区段分析基因和蛋白质功能分析,第二节比对算法概要,Section2AlignmentAlgorithms,（一）通过点矩阵对序列比较进行计分,A.两条序列完全相同,一、替换计分矩阵,B.两条序列有一个共同的子序列,C.两条序列反向匹配,D.两条序列存在不连续的两条子序列,（二）DNA序列比对的替换计分矩阵,等价矩阵（unitarymatrix）,转换-颠换矩阵（transition-transversionmatrix）,BLAST矩阵,核苷酸转换矩阵,（三）蛋白质序列比对的替换计分矩阵,等价矩阵遗传密码矩阵（GCM）疏水性矩阵（hydrophobicmatrix）PAM矩阵BLOSUM矩阵,PAM矩阵是从蛋白质序列的全局比对结果推导出来的，而BLOSUM矩阵则是从蛋白质序列块（短序列）比对推导出来的。,PAM/BLOSUM矩阵编号与序列亲缘关系的比较,二、双序列全局比对,动态规划算法的思想,a,b是使用某一字符集的序列（DNA或蛋白质序列）；m=a的长度；n=b的长度；S（i,j）是按照某替换计分矩阵得到的前缀a1.i与b1.j最大相似性得分；,w（c,d）是字符c和d按照替换计分矩阵计算的得分。可按照规则建立得分矩阵：S（i,0）=0,0imS（0,j）=0,0jn,S（i-1,j-1）+w（ai,bj）匹配或错配S（i,j）=maxS（i-1,j）+w（ai,-）插入S（i,j-1）缺失不罚分,例如，对于序列a=ACACACTA，序列b=AGCACACA，计分规则w（匹配）=+2；w（a,-）=w（-,b）=w（失配）=-1,得分矩阵,三、双序列局部比对,处理子序列与完整序列（或短序列与长序列）比对的一般过程是：设短序列a和长序列b，它们的长度分别为La和Lb，比对是在b序列中寻找La长度的a序列的过程。,四、多序列全局比对,多序列比对主要涉及四个要素：选择一组能进行比对的序列（要求是同源序列）；选择一个实现比对与计分的算法与软件；确定软件的参数；合理地解释比对的结果；,与双序列比对一样，多序列比对也有全局比对和局部比对。,（一）动态规划法进行多序列比对,（A）计算三个序列间的一个比对单元（i,j,k）依赖于其7个前导项；（B）计算u=ATGTTAT，v=ATCGTAC，w=ATGC三序列比对的三维得分矩阵。,计算三序列比对,（二）渐进多序列比对,三个序列的配对比对未必能组合成一个多序列比对,对于接近或超过100个序列的多序列比对，渐进多序列比对具有较高效率。最流行的渐进多序列比对软件是Clustal家族。,ClustalW有以下特点：首先，在比对中对每个序列赋予一个特殊的权值以降低高度近似序列的影响和提高相距遥远的序列的影响（如下图）。,ClustalW中对序列赋权的方法,其次，根据序列间进化距离的离异度（divergence）在比对的不同阶段使用不同的氨基酸替换矩阵；第三，采用了与特定氨基酸相关的空缺（gap）罚分函数，对亲水性氨基酸区域中的空缺予以较低的罚分；第四，对在早期配对比对中产生空缺的位置进行较少的罚分，对引入空缺和扩展空缺进行不同的罚分。,迭代法基于一致性的方法遗传算法,其他多序列全局比对方法,五、多序列局部比对,全局比对，其共同特征是序列中所有对应字符均假定可以匹配，所有字符具有同等的重要性，空格的插入是为了使整个序列得到比对，包括使两端对齐。局部比对不假定整个序列可以匹配，重在考虑序列中能够高度匹配的一个区段，可赋予该区段更大的计分权值，空格的插入是为了使高度匹配的区段得到更好的比对。,对2个序列进行全局和局部比对可得到完全不同的结果,基于隐马尔可夫模型的多序列比对方法,隐马尔可夫模型和3个蛋白质序列PHSFTYVMT、PGSFTYW、RFTGFW的最小公共超图,六、比对的统计显著性,确定比对得分score是否偶然：1.将球蛋白或肌球蛋白与大量非同源的蛋白质做比对，然后将score与这些比对的得分进行比较。2.把一个序列与一组随机产生的序列进行比对，然后同样将score与这些比对的得分进行比较。3.随机将两个序列中的一个打乱重组，比如说重组100次，并与另一个序列比对，同样得到一组比对的得分。,第三节数据库搜索,Section3DatabaseSearch,一、经典BLAST,基本的BLAST算法本身很简单，它的要点是片段对（segmentpair）的概念，它是指两个给定序列中的一对子序列，它们的长度相等，且可以形成无空格的完全匹配。,BLAST的查询序列和数据库的类型,BLAST算法图示,二、衍生BLAST,（一）PSI-BLAST主要用于搜索与感兴趣的蛋白质关系较远的蛋白质。,（二）PHI-BLAST用来帮助判断这个蛋白质属于哪个家族。,（三）BLASTZBLASTZ是在比对人和鼠的基因组中发展起来的，它适合于比对非常长的序列。,三、BLAT,BLAT（TheBLAST-LikeAlignmentTool）与BLAST搜索原理相似，但发展了一些专门针对全基因组分析的技术。BLAT的优点在于速度快，其比对速度要比BLAST快几百倍，其根本原因在于:BLAST是将查询序列索引化，而BLAT则是将搜索数据库索引化，BLAT把相关的呈共线性的比对结果连接成为更大的比对结果。,四、RNA序列搜索,RNA序列比对/搜索算法可大致分成两类：,查询序列（query）的结构未知，要找到数据库中和其结构相近的同源序列。,利用查询序列的结构信息，在结构信息的使用上又可以细分为：通过构建一个描述RNA序列共性结构的概率模型进行数据库检索；基于索引（index）或者模体（motif）描述的方法定义rna结构或共性结构，并进行数据库搜索。,五、数据库搜索的统计显著性,一个典型的BLAST搜索的输出包括E值和得分，后者又分原始得分（rawscores）和比特得分（bitscores）。,P=1-e-E,P值和E值是反映比对显著性的两种不同方式，大部分BLAST在线服务使用E值而非P值来定义搜索的统计学显著性。,第四节比对软件、参数与数据资源,Section4AlignmentSoftware，ParameterandResource,一、参数选择的一般原则,空格罚分涉及几个问题：空格罚分是否大于失配罚分；不同大小空缺的罚分；空格的引入与延伸是否予以不同罚分。,如果一次数据库搜索产生了太多的返回结果，可采取如下措施：使用参考序列（带“refseq”的）数据库，这样可减少许多冗余结果；使查询序列只包含一个结构域，减少多结构域带来的多匹配；根据查询序列与数据库序列的关系使用更合适的替换计分矩阵；降低E值。,如果一次数据库搜索产生了太少的返回结果，可采取如下措施：提高E值；使用更大的PAM矩阵或更小的BLOSUM矩阵；减小字长以及减小阈值。,二、主要比对软件,三、EBI中的序列比对工具,四、UCSC中的BLAT比对工具,BLAT在线工具输入界面,BLAT在线工具输出结果,第五节比对技术的发展,Section5AdvancesofAlignmentTechniques,一、glocal比对,两个序列的局部、全局和glocal比对所对应的路径,二、全基因组比对,全基因组比对主要揭示多个序列中保守的和非保守的区段以及这些区段在基因组中的分布特征，这里主要介绍UCSC基因组浏览器（TheUCSCGenomeBrowser）中的全基因组比对方法。,UCSC基因组浏览器中所采用的多序列比对在多方面作了改进,首先，它采用了参照序列（referencesequence），使用BLASTZ将每一个序列与参照序列进行局部配对比对，参照序列中的一个碱基比对另一个序列中的至多一个碱基。其次，依据计分矩阵和两序列的种系关系，对配对比对的结果