【生物信息学第二版】序列比对

《【生物信息学第二版】序列比对》由会员分享，可在线阅读，更多相关《【生物信息学第二版】序列比对（61页珍藏版）》请在装配图网上搜索。

1、生物信息学生物信息学第二章第二章 序列比对序列比对南方医科大学南方医科大学 朱浩朱浩吉林大学吉林大学 李瑛李瑛生物信息学生物信息学第一节第一节 引引 言言 Section 1 Introduction （一）（一） 同源同源 两个序列享有一个共同的进化上的祖先，则这两两个序列享有一个共同的进化上的祖先，则这两个序列是同源的。个序列是同源的。 对于两个序列，他们或者同源或者不同源，不能对于两个序列，他们或者同源或者不同源，不能说他们说他们70%或或80%同源。同源。1 1、同源、相似与距离、同源、相似与距离 同源可分为垂直同源（同源可分为垂直同源（ortholog）和水平同源（）和水平同源（pa

2、ralog）垂直同源与水平同源垂直同源与水平同源（二）（二）相似相似性性与距离与距离 相似性、距离：是两个定量描述多个序列相似度相似性、距离：是两个定量描述多个序列相似度的度量。的度量。 相似性：被比对序列之间的相似程度。相似性：被比对序列之间的相似程度。 距离：被比对序列间的差异程度。距离：被比对序列间的差异程度。 相似性既可用于全局比对也可用于局部比对，而相似性既可用于全局比对也可用于局部比对，而距离一般仅用于全局比对，因为它反映了把一个距离一般仅用于全局比对，因为它反映了把一个序列转换成另一个序列所需字符替换的耗费。序列转换成另一个序列所需字符替换的耗费。二、二、相似与距离的定量描述相似

3、与距离的定量描述 相似性可定量地定义为两个序列的函数，即它可有相似性可定量地定义为两个序列的函数，即它可有多个值，值的大小取决于两个序列对应位置上相同多个值，值的大小取决于两个序列对应位置上相同字符的个数，值越大则表示两个序列越相似字符的个数，值越大则表示两个序列越相似。 编辑距离编辑距离（edit distance）也可定量地定义为两个也可定量地定义为两个序列的函数，其值取决于两个序列对应位置上差异序列的函数，其值取决于两个序列对应位置上差异字符的个数，值越小则表示两个序列越相似字符的个数，值越小则表示两个序列越相似。 对于一个比对，不论使用什么计分函数进行计分，对于一个比对，不论使用什么计

4、分函数进行计分，相似性被定义为总等值于最大的计分：相似性被定义为总等值于最大的计分： 对于对于k个序列，如果用一个函数个序列，如果用一个函数cost（）（）对每一列对每一列的所有替换操作进行计分，则多个序列之间的距的所有替换操作进行计分，则多个序列之间的距离等值于最小的计分：离等值于最小的计分：对相似性的计分对相似性的计分 编辑距离（编辑距离（edit distance）：一般用海明距离表示。）：一般用海明距离表示。三、算法实现的比对三、算法实现的比对 用计算机科学的术语来说，比对两个序列就是找出用计算机科学的术语来说，比对两个序列就是找出两个序列的最长公共子序列两个序列的最长公共子序列（lo

5、ngest common subsequence，LCS），它反映了两个序列的最高，它反映了两个序列的最高相似度。相似度。动态规划法示意动态规划法示意（A）使用动态规划法寻找两个序列的最长公共部分；使用动态规划法寻找两个序列的最长公共部分；（B）动态规划表的填写。动态规划表的填写。四、序列比对的作用四、序列比对的作用 获得共性序列获得共性序列 序列测序序列测序 突变分析突变分析 种系分析种系分析 保守区段分析保守区段分析 基因和蛋白质功能分析基因和蛋白质功能分析第二节第二节 比对算法概要比对算法概要Section 2 Alignment Algorithms（一一）通过点矩阵对序列比较进行计分

6、通过点矩阵对序列比较进行计分A.两条序列完全相同两条序列完全相同一、替换计分矩阵一、替换计分矩阵B.两条序列有一个共同的子序列两条序列有一个共同的子序列C.两条序列反向匹配两条序列反向匹配D.两条序列存在不连续的两条子序列两条序列存在不连续的两条子序列（二二）DNADNA序列比对的替换计分矩阵序列比对的替换计分矩阵 等价矩阵等价矩阵（unitary matrix） 转换转换-颠换矩阵颠换矩阵（transition-transversion matrix） BLAST矩阵矩阵核苷酸转换核苷酸转换矩阵矩阵（三三）蛋白质序列比对的替换计分矩阵蛋白质序列比对的替换计分矩阵 等价矩阵等价矩阵 遗传密码矩

7、阵（遗传密码矩阵（GCM） 疏水性矩阵（疏水性矩阵（hydrophobic matrix ） PAM矩阵矩阵 BLOSUM矩阵矩阵 PAM矩阵是从蛋白质序列的全局比对结果推导出来矩阵是从蛋白质序列的全局比对结果推导出来的，而的，而BLOSUM 矩阵则是从蛋白质序列块矩阵则是从蛋白质序列块（短序短序列列）比对推导出来的。比对推导出来的。PAM/BLOSUM矩阵编号与序列亲缘关系的比较矩阵编号与序列亲缘关系的比较二、双序列全局比对二、双序列全局比对动态规划算法动态规划算法的思想的思想 a, b是使用某一字符集是使用某一字符集的序列（的序列（DNA 或蛋白质或蛋白质序列）；序列）； m = a的长度

8、；的长度； n = b的长度；的长度； S（i,j） 是按照某替换计分矩阵得到的前缀是按照某替换计分矩阵得到的前缀a1.i与与b1.j最大相似性得分；最大相似性得分； w（c,d）是字符是字符c和和d按照替换计分矩阵计算的得分。按照替换计分矩阵计算的得分。 可按照规则建立得分矩阵：可按照规则建立得分矩阵：S（i,0） = 0, 0 i mS（0,j） = 0, 0 j n S（i-1,j-1）+ w（ai,bj） 匹配或错配匹配或错配S（i,j）=max S（i-1,j）+ w（ai,-） 插入插入 S（i,j-1） 缺失不罚分缺失不罚分 例如，对于序列例如，对于序列a=ACACACTA，序列

9、，序列b=AGCACACA，计分规则，计分规则w（匹配匹配）=+2；w（a,-）=w（-,b）=w（失配失配）=-1得分矩阵得分矩阵三、双序列局部比对三、双序列局部比对 处理子序列与完整序列处理子序列与完整序列（或短序列与长序列或短序列与长序列）比对比对的一般过程是：设短序列的一般过程是：设短序列a和长序列和长序列b，它们的长度，它们的长度分别为分别为La和和Lb，比对是在，比对是在b序列中寻找序列中寻找La长度的长度的a序序列的过程。列的过程。四、多序列全局比对四、多序列全局比对多序列比对主要涉及四个要素：多序列比对主要涉及四个要素：选择一组能进行比对的序列选择一组能进行比对的序列（要求是同

10、源序列要求是同源序列）；）；选择一个实现比对与计分的算法与软件选择一个实现比对与计分的算法与软件；确定软件的参数确定软件的参数；合理地解释比对的结果合理地解释比对的结果； 与双序列比对一样，多序列比对也有全局比对与双序列比对一样，多序列比对也有全局比对和局部比对和局部比对。（一一）动态规划法进行多序列比对动态规划法进行多序列比对（A）计算三个序列间的一个比对单元计算三个序列间的一个比对单元（i,j,k）依赖于其依赖于其7个前导项；个前导项；（B）计算计算u=ATGTTAT，v=ATCGTAC，w=ATGC三序列三序列比对的比对的三三维维得分矩阵得分矩阵。计算三序列比对计算三序列比对（二二）渐进

11、多序列比对渐进多序列比对三三个个序列序列的配对比对未必能组合成一个多序列比对的配对比对未必能组合成一个多序列比对 对于接近或超过对于接近或超过100个序列的多序列比对，渐进多序个序列的多序列比对，渐进多序列比对具有较高效率。最流行的渐进多序列比对软列比对具有较高效率。最流行的渐进多序列比对软件是件是Clustal家族家族。ClustalW有以下特点有以下特点： 首先，在比对中对每个序列赋予一个特殊的权值以首先，在比对中对每个序列赋予一个特殊的权值以降低高度近似序列的影响和提高相距遥远的序列的降低高度近似序列的影响和提高相距遥远的序列的影响影响（如下图（如下图）。）。ClustalW中对序列赋中

12、对序列赋权的方法权的方法 其次，根据序列间进化距离的离异度其次，根据序列间进化距离的离异度（divergence）在比对的不同阶段使用不同的氨基酸替换矩阵；在比对的不同阶段使用不同的氨基酸替换矩阵； 第三，采用了与特定氨基酸相关的空缺第三，采用了与特定氨基酸相关的空缺（gap）罚分罚分函数，对亲水性氨基酸区域中的空缺予以较低的罚分；函数，对亲水性氨基酸区域中的空缺予以较低的罚分； 第四，对在早期配对比对中产生空缺的位置进行较少第四，对在早期配对比对中产生空缺的位置进行较少的罚分，对引入空缺和扩展空缺进行不同的罚分。的罚分，对引入空缺和扩展空缺进行不同的罚分。 迭代法迭代法 基于一致性的方法基于

13、一致性的方法 遗传算法遗传算法其他多序列全局比对方法其他多序列全局比对方法五、多序列局部比对五、多序列局部比对 全局比对，其共同特征是序列中所有对应字符均假全局比对，其共同特征是序列中所有对应字符均假定可以匹配，所有字符具有同等的重要性，空格的定可以匹配，所有字符具有同等的重要性，空格的插入是为了使整个序列得到比对，包括使两端对齐。插入是为了使整个序列得到比对，包括使两端对齐。 局部比对不假定整个序列可以匹配，重在考虑序列局部比对不假定整个序列可以匹配，重在考虑序列中能够高度匹配的一个区段，可赋予该区段更大的中能够高度匹配的一个区段，可赋予该区段更大的计分权值，空格的插入是为了使高度匹配的区段

14、得计分权值，空格的插入是为了使高度匹配的区段得到更好的比对。到更好的比对。对对2个序列进行全局和局部比对可得到完全不同的结果个序列进行全局和局部比对可得到完全不同的结果 基于基于隐马尔可夫隐马尔可夫模型的多序列比对方法模型的多序列比对方法隐马尔可夫隐马尔可夫模型和模型和3个蛋白质序列个蛋白质序列PHSFTYVMT、PGSFTYW、RFTGFW的最小公共超图的最小公共超图六、比对的统计显著性六、比对的统计显著性确定比对得分确定比对得分score是否偶然是否偶然：1.将将球蛋白或肌球蛋白与大量非同源的蛋白质做比球蛋白或肌球蛋白与大量非同源的蛋白质做比对，然后将对，然后将score与这些比对的得分进

15、行比较。与这些比对的得分进行比较。2.把一个序列与一组随机产生的序列进行比对，然后把一个序列与一组随机产生的序列进行比对，然后同样将同样将score与这些比对的得分进行比较。与这些比对的得分进行比较。3.随机将两个序列中的一个打乱重组，比如说重组随机将两个序列中的一个打乱重组，比如说重组100次，并与另一个序列比对，同样得到一组比对次，并与另一个序列比对，同样得到一组比对的得分。的得分。第三节第三节 数据库搜索数据库搜索Section 3 Database Search一、经典一、经典BLASTBLAST 基本的基本的BLAST算法本身很简单，它的要点是片段算法本身很简单，它的要点是片段对对（

16、segment pair）的概念，它是指两个给定序列的概念，它是指两个给定序列中的一对子序列，它们的长度相等，且可以形成中的一对子序列，它们的长度相等，且可以形成无空格的完全匹配。无空格的完全匹配。程序名程序名 查询序列查询序列 数据库类型数据库类型方法方法blastp蛋白质蛋白质蛋白质蛋白质用蛋白质查询序列搜索蛋白质序列数据库用蛋白质查询序列搜索蛋白质序列数据库blastn核酸核酸核酸核酸用核酸查询序列搜索核酸序列数据库用核酸查询序列搜索核酸序列数据库blastx核酸核酸蛋白质蛋白质将核酸序列按将核酸序列按6条链翻译成蛋白质序列后搜条链翻译成蛋白质序列后搜索蛋白质序列数据库索蛋白质序列数据库

17、tblastn蛋白质蛋白质核酸核酸用蛋白质查询序列搜索核酸序列数据库，用蛋白质查询序列搜索核酸序列数据库，核酸序列按核酸序列按6条链翻译成蛋白质条链翻译成蛋白质tblastx核酸核酸核酸核酸将核酸序列按将核酸序列按6条链翻译成蛋白质序列后搜条链翻译成蛋白质序列后搜索由核酸序列数据库按索由核酸序列数据库按6条链翻译成的蛋白条链翻译成的蛋白质序列的数据库质序列的数据库BLAST的查询序列和数据库的类型的查询序列和数据库的类型BLAST算法图示算法图示二、衍生二、衍生BLASTBLAST（一一）PSI-BLASTPSI-BLAST 主要用于搜索与感兴趣的蛋白质关系较远的蛋白质主要用于搜索与感兴趣的蛋

18、白质关系较远的蛋白质。（二二）PHI-BLASTPHI-BLAST 用来帮助判断这个蛋白质属于哪个家族用来帮助判断这个蛋白质属于哪个家族。（三三）BLASTZBLASTZ BLASTZ是在比对人和鼠的基因组中发展起来的，是在比对人和鼠的基因组中发展起来的，它适合于比对非常长的序列它适合于比对非常长的序列。三、三、BLATBLAT BLAT（The BLAST-Like Alignment Tool）与与BLAST搜索原理相似，但发展了一些专门针对全搜索原理相似，但发展了一些专门针对全基因组分析的技术。基因组分析的技术。 BLAT的优点在于速度快，其比对速度要比的优点在于速度快，其比对速度要比B

19、LAST快几百倍，其根本原因在于快几百倍，其根本原因在于: BLAST是将查询序列是将查询序列索引化，而索引化，而BLAT则是将搜索数据库索引化，则是将搜索数据库索引化，BLAT 把相关的呈共线性的比对结果连接成为更大把相关的呈共线性的比对结果连接成为更大的比对结果。的比对结果。四、四、RNARNA序列搜索序列搜索RNA序列比对序列比对/搜索算法可大致分成两类：搜索算法可大致分成两类： 查询序列查询序列（query）的结构未知，要找到数据库中的结构未知，要找到数据库中和其结构相近的同源序列。和其结构相近的同源序列。 利用查询序列的结构信息，在结构信息的使用上利用查询序列的结构信息，在结构信息的

20、使用上又可以细分为：又可以细分为：(a)通过构建一个描述通过构建一个描述RNA序列共性结构的概率模序列共性结构的概率模型进行数据库检索型进行数据库检索； (b)基于索引基于索引（index）或者模体或者模体（motif）描述的描述的方法定义方法定义rna结构或共性结构，并进行数据库结构或共性结构，并进行数据库搜索搜索。五、数据库搜索的统计显著性五、数据库搜索的统计显著性 一个典型的一个典型的BLAST搜索的输出包括搜索的输出包括E值和得分，值和得分，后者又分原始得分后者又分原始得分（raw scores）和比特得分和比特得分（bit scores）。 P=1-e-E P值和值和E值是反映比对显

21、著性的两种不同方式值是反映比对显著性的两种不同方式，大部分大部分BLAST在线服务使用在线服务使用E值而非值而非P值来定值来定义搜索的统计学显著性。义搜索的统计学显著性。第四节第四节 比对软件、参数与数据资源比对软件、参数与数据资源Section 4 Alignment Software， Parameter and Resource一、参数选择的一般原则一、参数选择的一般原则空格罚分涉及几个问题：空格罚分涉及几个问题：空格罚分是否大于失配罚分；空格罚分是否大于失配罚分；不同大小空缺的罚分；不同大小空缺的罚分；空格的引入与延伸是否予以不同罚分。空格的引入与延伸是否予以不同罚分。如果一次数据库搜

22、索产生了太多的返回结果，可采取如果一次数据库搜索产生了太多的返回结果，可采取如下措施：如下措施： 使用参考序列使用参考序列（带带“refseq”的的）数据库，这样可减数据库，这样可减少许多冗余结果；少许多冗余结果； 使查询序列只包含一个结构域，减少多结构域带使查询序列只包含一个结构域，减少多结构域带来的多匹配；来的多匹配； 根据查询序列与数据库序列的关系使用更合适的根据查询序列与数据库序列的关系使用更合适的替换计分矩阵；替换计分矩阵； 降低降低E值。值。 如果一次数据库搜索产生了太少的返回结果，可如果一次数据库搜索产生了太少的返回结果，可采取如下措施：采取如下措施： 提高提高E值；值； 使用更

23、大的使用更大的PAM矩阵或更小的矩阵或更小的BLOSUM矩阵；矩阵； 减小字长以及减小阈值。减小字长以及减小阈值。二、主要比对软件二、主要比对软件三、三、EBIEBI中的序列比对工具中的序列比对工具双序列比对双序列比对多序列比对多序列比对特性特性工具工具工具工具Global alignmentNeedleClustal OmegaGlobal alignmentStretcherClustalW2Local alignmentWaterDbClustalLocal alignmentLalignKalignLocal alignmentMatcherMAFFTGenomic alignment

24、PromoterWiseMUSCLEGenomic alignmentGeneWiseMViewGenomic alignmentWise2DBAPRANK四、四、UCSCUCSC中的中的BLATBLAT比对工具比对工具BLAT在线工具在线工具输入界面输入界面BLAT在线工具在线工具输出结果输出结果第五节第五节 比比对技术的对技术的发展发展Section 5 Advances of Alignment Techniques一、一、glocal glocal 比对比对两个序列的局部、全局和两个序列的局部、全局和glocal比对所对应的路径比对所对应的路径二、全基因组比对二、全基因组比对 全基因组

25、比对主要揭示多个序列中保守的和非保守全基因组比对主要揭示多个序列中保守的和非保守的区段以及这些区段在基因组中的分布特征，这里的区段以及这些区段在基因组中的分布特征，这里主要介绍主要介绍UCSC基因组浏览器基因组浏览器（The UCSC Genome Browser）中的全基因组比对方法。中的全基因组比对方法。UCSCUCSC基因组浏览器中所采用的多序列比对在多方面作基因组浏览器中所采用的多序列比对在多方面作了改进了改进 首先，它采用了参照序列首先，它采用了参照序列（reference sequence），使用使用BLASTZ将每一个序列与参照序列进行局部配将每一个序列与参照序列进行局部配对比对

26、对比对，参照序列中的一个碱基比对另一个序列中参照序列中的一个碱基比对另一个序列中的至多一个碱基。的至多一个碱基。 其次，依据计分矩阵和两序列的种系关系，对配对其次，依据计分矩阵和两序列的种系关系，对配对比对的结果进行所谓的比对的结果进行所谓的“串连串连”（chaining）和和“连网连网”（netting）。）。 接着，接着，UCSC基因组浏览器使用基因组浏览器使用MULTIZ对多个对多个“串串连连”的配对比对进行渐进多序列比对的配对比对进行渐进多序列比对。小小 结结 序列比对是基因和序列比对是基因和DNA序列分析的基础，所依据的两序列分析的基础，所依据的两个核心概念是同源和相似，同源序列一般是相似的，个核心概念是同源和相似，同源序列一般是相似的，相似序列不一定是同源的。多序列比对是双序列比对相似序列不一定是同源的。多序列比对是双序列比对的自然推广，采用更多物种的序列进行多序列比对常的自然推广，采用更多物种的序列进行多序列比对常常能更准确和更可靠地揭示序列的同源性和保守域。常能更准确和更可靠地揭示序列的同源性和保守域。