生物信息学第二版序列比对名师优质课获奖市赛课一等奖课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,人民卫生出版社,8,年制及,7,年制临床医学等专业用,生物信息学,*,本幻灯片资料仅供参考，不能作为科学依据，如有不当之处，请参考专业资料。,*,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Click to edit Master title style,本幻灯片资料仅供参考，不能作为科学依据，如有不当之处，请参考专业资料。,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Click to edit Master title style,本幻灯片资料仅供参考，不能作为科学依据，如有不当之处，请参考专业资料。,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Click to edit Master title style,本幻灯片资料仅供参考，不能作为科学依据，如有不当之处，请参考专业资料。,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Click to edit Master title style,本幻灯片资料仅供参考，不能作为科学依据，如有不当之处，请参考专业资料。,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Click to edit Master title style,本幻灯片资料仅供参考，不能作为科学依据，如有不当之处，请参考专业资料。,生物信息学,第1页,第二章 序列比对,南方医科大学 朱浩,吉林大学 李瑛,生物信息学,第2页,第一节 引 言,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 Algorithms,第14页,（,一,）,经过点矩阵对序列比较进行计分,A.,两条序列完全相同,一、替换计分矩阵,第15页,B.,两条序列有一个共同子序列,第16页,C.,两条序列反向匹配,第17页,D.,两条序列存在不连续两条子序列,第18页,（,二,）,DNA,序列比正确替换计分矩阵,等价矩阵,（,unitary matrix,）,转换,-,颠换矩阵,（,transition-transversion matrix,）,BLAST,矩阵,第19页,核苷酸转换,矩阵,第20页,（,三,）,蛋白质序列比正确替换计分矩阵,等价矩阵,遗传密码矩阵（,GCM,）,疏水性矩阵（,hydrophobic matrix,）,PAM,矩阵,BLOSUM,矩阵,第21页,PAM,矩阵是从蛋白质序列全局比对结果推导出来，而,BLOSUM,矩阵则是从蛋白质序列块,（,短序列,）,比对推导出来。,PAM/BLOSUM,矩阵编号与序列亲缘关系比较,第22页,二、双序列全局比对,动态规划算法,思想,a,b,是使用某一字符集序列,（,DNA,或蛋白质序列,）；,m,=,a,长度；,n,=,b,长度；,S,（,i,j,）,是按照某替换计分矩阵得到前缀,a,1.i与,b,1.j最大相同性得分；,第23页,w,（,c,d,）,是字符c和d按照替换计分矩阵计算得分。,可按照规则建立得分矩阵：,S,（,i,0,）,=0,0 i m,S,（,0,j,）,=0,0 j n,S,（,i-1,j-1,）,+w,（,a,i,b,j,）,匹配或错配,S,（,i,j,）,=max S,（,i-1,j,）,+w,（,a,i,-,）,插入,S,（,i,j-1,）,缺失不罚分,第24页,比如，对于序列,a,=ACACACTA，序列,b,=AGCACACA，计分规则,w,（,匹配,）,=+2；,w,（,a,-,）,=,w,（,-,b,）,=,w,（,失配,）,=-1,第25页,得分矩阵,第26页,三、双序列局部比对,处理子序列与完整序列,（,或短序列与长序列,）,比正确普通过程是：设短序列,a,和长序列,b,，它们长度分别为,L,a,和,L,b,，比对是在,b,序列中寻找,L,a,长度,a,序列过程。,第27页,四、多序列全局比对,多序列比对主要包括四个要素：,选择一组能进行比正确序列,（,要求是同源序列,）；,选择一个实现比对与计分算法与软件,；,确定软件参数,；,合理地解释比正确结果,；,与双序列比对一样，多序列比对也有全局比对和局部比对,。,第28页,（,一,）,动态规划法进行多序列比对,（,A,）,计算三个序列间一个比对单元,（,i,j,k,）,依赖于其,7,个前导项；,（,B,）,计算,u,=ATGTTAT,，,v,=ATCGTAC,，,w,=ATGC,三序列,比正确,三维,得分矩阵,。,计算三序列比对,第29页,（,二,）,渐进多序列比对,三,个,序列,配对比对未必能组合成一个多序列比对,第30页,对于靠近或超出,100,个序列多序列比对，渐进多序列比对含有较高效率。最流行渐进多序列比对软件是,Clustal,家族,。,第31页,ClustalW,有以下特点,：,首先，在比对中对每个序列赋予一个特殊权值以降低高度近似序列影响和提升相距遥远序列影响,（以下列图）。,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 Search,第39页,一、经典,BLAST,基本,BLAST,算法本身很简单，它关键点是片段对,（,segment pair,）,概念，它是指两个给定序列中一对子序列，它们长度相等，且能够形成无空格完全匹配。,第40页,程序名,查询序列,数据库类型,方法,blastp,蛋白质,蛋白质,用蛋白质查询序列搜索蛋白质序列数据库,blastn,核酸,核酸,用核酸查询序列搜索核酸序列数据库,blastx,核酸,蛋白质,将核酸序列按,6条链翻译成蛋白质序列后搜索蛋白质序列数据库,tblastn,蛋白质,核酸,用蛋白质查询序列搜索核酸序列数据库，核酸序列按,6条链翻译成蛋白质,tblastx,核酸,核酸,将核酸序列按6条链翻译成蛋白质序列后搜索由核酸序列数据库按6条链翻译成蛋白质序列数据库,BLAST,查询序列和数据库类型,第41页,BLAST,算法图示,第42页,二、衍生,BLAST,（,一,）,PSI-BLAST,主要用于搜索与感兴趣蛋白质关系较远蛋白质,。,（,二,）,PHI-BLAST,用来帮助判断这个蛋白质属于哪个家族,。,（,三,）,BLASTZ,BLASTZ,是在比对人和鼠基因组中发展起来，它适合于比对非常长序列,。,第43页,三、,BLAT,BLAT,（,The BLAST-Like Alignment Tool,）,与,BLAST,搜索原理相同，但发展了一些专门针对全基因组分析技术。,BLAT,优点在于速度快，其比对速度要比,BLAST,快几百倍，其根本原因在于,:BLAST,是将查询序列索引化，而,BLAT,则是将搜索数据库索引化，,BLAT,把相关呈共线性比对结果连接成为更大比对结果。,第44页,四、,RNA,序列搜索,RNA,序列比对,/,搜索算法可大致分成两类：,查询序列,（,query,）,结构未知，要找到数据库中和其结构相近同源序列。,第45页,利用查询序列结构信息，在结构信息使用上又能够细分为：,经过构建一个描述,RNA,序列共性结构概率模型进行数据库检索,；,基于索引,（,index,）,或者模体,（,motif,）,描述方法定义,rna,结构或共性结构，并进行数据库搜索,。,第46页,五、数据库搜索统计显著性,一个经典,BLAST,搜索输出包含,E,值和得分，后者又分原始得分,（,raw scores,）,和比特得分,（,bit scores,）,。,P=1-e,-E,P,值和,E,值是反应比对显著性两种不一样方式,，,大部分,BLAST,在线服务使用,E,值而非,P,值来定义搜索统计学显著性。,第47页,第四节,比对软件、参数与数据资源,Section 4,Alignment Software,，,Parameter and Resource,第48页,一、参数选择普通标准,空格罚分包括几个问题：,空格罚分是否大于失配罚分；,不一样大小空缺罚分；,空格引入与延伸是否给予不一样罚分。,第49页,假如一次数据库搜索产生了太多返回结果，可采取以下办法：,使用参考序列,（,带,“refseq”,）,数据库，这么可降低许多冗余结果；,使查询序列只包含一个结构域，降低多结构域带来多匹配；,依据查询序列与数据库序列关系使用更适当替换计分矩阵；,降低,E,值。,第50页,假如一次数据库搜索产生了太少返回结果，可采取以下办法：,提升,E,值；,使用更大,PAM,矩阵或更小,BLOSUM,矩阵；,减小字长以及减小阈值。,第51页,二、主要比对软件,第52页,三、,EBI,中序列比对工具,双序列比对,多序列比对,特征,工具,工具,Global alignment,Needle,Clustal Omega,Global alignment,Stretcher,ClustalW2,Local alignment,Water,DbClustal,Local alignment,Lalign,Kalign,Local alignment,Matcher,MAFFT,Genomic alignment,PromoterWise,MUSCLE,Genomic alignment,GeneWise,MView,Genomic alignment,Wise2DBA,PRANK,第53页,四、,UCSC,中,BLAT,比对工具,BLAT,在线工具,输入界面,第54页,BLAT,在线工具,输出结果,第55页,第五节,比对技术发展,Section 5,Advances of Alignment Techniques,第56页,一、,glocal,比对,两个序列局部、全局和,glocal,比对所对应路径,第57页,二、全基因组比对,全基因组比对主要揭示多个序列中保守和非保守区段以及这些区段在基因组中分布特征，这里主要介绍,UCSC,基因组浏览器,（,The UCSC Genome Browser,）,中全基因组比对方法。,第58页,UCSC,基因组浏览器中所采取多序列比对在多方面作了改进,首先，它采取了参考序列,（,reference sequence,）,，使用,BLASTZ,将每一个序列与参考序列进行局部配对比对,，,参考序列中一个碱基比对另一个序列中至多一个碱基。,其次，依据计分矩阵和两序列种系关系，对配对比正确结果进行所谓,“,串连,”,（,chaining,）,和,“,连网,”,（,netting,）。,接着，,UCSC,基因组浏览器使用,MULTIZ,对多个,“,串连,”,配对比对进行渐进多序列比对,。,第59页,小 结,序列比对是基因和,DNA,序列分析基础，所依据两个关键概念是同源和相同，同源序列普通是相同，相同序列不一定是同源。多序列比对是双序列比正确自然推广，采取更多物种序列进行多序列比对经常能更准确和更可靠地揭示序列同源性和保守域。,第60页,Thank You!,第61页,