动态规划法——双序列比对

格式：ppt
大小：1.56 MB
文档页数：55

下载文档原格式

(生物信息学)lecture04双序列比对

GATK软件具有准确度高、可扩展性强和易于使用等特点，广泛应用于全基因组关联分析、突变检测和基因组组装等领域。
SAMtools软件
1
SAMtools是一个用于处理和分析序列对齐映射（SAM）格式数据的生物信息学软件工具。
2
SAMtools软件提供了多种用于双序列比对的工具，如SAMtools sort、SAMtools index和 SAMtools view等。
BLAST软件具有高效、准确和灵活的特点，广泛应用于生物信息学领域的序列比对和相似性搜索。
GATK软件
GATK（Genome Analysis Toolkit）是一个用于分析高通量测序数据的生物信息学软件工具集。
GATK软件提供了多种用于双序列比对的工具，如Smith-Waterman算法和Burrows-Wheeler变换等。
药物作用机制研究
通过比对药物作用前后的基因或蛋白质序列，分析药物对生物分子的影响和作用机制，有助于深入理解药物的作用原理和潜在副作用。
05
双序列比对的挑战与未来发展
数据规模与计算复杂度
数据规模
随着测序技术的快速发展，产生的序列数据量呈指数级增长，给双序列比对带来了巨大的挑战。
计算复杂度
双序列比对的算法复杂度较高，尤其是在处理大规模数据时，需要消耗大量的计算资源和时间。
通过比对患者与健康人的基因序列，寻找与疾病相关的基因变异位点，有助于定位和阐明疾病发生的分子机制。
药物靶点发现
通过比对不同物种的基因或蛋白质序列，寻找与药物分布、活化等相关的靶点，有助于发现新的药物候选分子。
药物发现与设计
药物靶点筛选
通过比对已知药物靶点序列与数据库中的序列，筛选出潜在的药物靶点，有助于发现新的药物作用机制和候选药物。

动态规划算法及其在序列比对中应用分析

动态规划算法及其在序列比对中应用分析序列比对是生物信息学中一个重要的问题，用于比较两个或多个生物序列的相似性和差异性。

在序列比对过程中，动态规划算法是一种常用和有效的方法。

本文将介绍动态规划算法的基本原理和应用，并深入分析其在序列比对中的应用。

1. 动态规划算法基本原理动态规划算法是一种通过把问题分解为相互重叠的子问题，并通过将每个子问题的解存储起来来解决复杂问题的方法。

它通常用于处理具有重叠子问题和最优子结构特性的问题。

动态规划算法的核心思想是将原问题拆解成若干个子问题，通过计算每个子问题的最优解来得到原问题的最优解。

这个过程可以通过建立一个状态转移方程来实现，即找到子问题之间的关联关系。

2. 动态规划在序列比对中的应用序列比对是生物信息学研究中常见的任务之一，用于比较两个或多个生物序列的相似性和差异性。

动态规划算法在序列比对中被广泛应用，最为著名的例子是Smith-Waterman算法和Needleman-Wunsch算法。

2.1 Smith-Waterman算法Smith-Waterman算法是一种用于局部序列比对的动态规划算法。

它通过为每个可能的比对位置定义一个得分矩阵，并计算出从每个比对位置开始的最优比对路径来找到最优的局部比对。

Smith-Waterman算法的基本思路是从比对矩阵的右下角开始，根据得分矩阵中每个位置的得分值和其周围位置的得分值进行计算，并记录下最大得分值及其对应的路径。

最终，通过回溯从最大得分值开始的路径，得到最优的局部比对结果。

2.2 Needleman-Wunsch算法Needleman-Wunsch算法是一种用于全局序列比对的动态规划算法。

它通过为每个比对位置定义一个得分矩阵，并通过计算出从第一个比对位置到最后一个比对位置的最优比对路径来找到最优的全局比对。

Needleman-Wunsch算法的基本思路与Smith-Waterman算法类似，但不同之处在于需要考虑序列的开头和结尾对比对结果的影响。

利用动态规划算法进行两条序列比对

利用动态规划算法进行两条序列比对实验目的学会使用EMBOSS 软件包的NEEDLE 和WATER 进行两条序列比对。

实验内容1. Get the mRNA and protein sequence of Chlorocebus sabaeus and Colobus angolensispalliates from NCBI.2. Use Needle to do the sequence alignment in default parameters.*****Protein Sequence alignment result*****Program: needle# Rundate: Sat 28 Sep 2019 16:43:43 # Commandline: needle # -auto # -stdout# -datafile EBLOSUM62# -gapopen 10.0 # -gapextend 0.5 # -endopen 10.0 # -endextend 0.5# -aformat3 pair # -sprotein1 # -sprotein2 # Align_format: pair # Report_file: stdout # Aligned_sequences: 2# 1: XP_008000870.1 # 2: XP_011811726.1 # Matrix: EBLOSUM62 # Gap_penalty: 10.0 # Extend_penalty: 0.5 # Length: 586# Identity: 561/586 (95.7%) # Similarity: 572/586 (97.6%) # Gaps: 4/586 ( 0.7%) # Score: 2906.0***** mRNA Sequence alignment result *****# Program: needle# Rundate: Sat 28 Sep 2019 16:47:19 # Commandline: needle # -auto # -stdout# -datafile EDNAFULL# -gapopen 10.0 # -gapextend 0.5 # -endopen 10.0 # -endextend 0.5 # -aformat3 pair # -snucleotide1# -snucleotide2# Align_format: pair # Report_file: stdout # Aligned_sequences: 2# 1: XM_008002679.1 # 2: XM_011956336.1 # Matrix: EDNAFULL# Gap_penalty: 10.0 # Extend_penalty: 0.5 # Length: 2594# Identity: 2505/2594 (96.6%) # Similarity: 2505/2594 (96.6%) # Gaps: 27/2594 ( 1.0%) # Score: 12207.5a. After alignment, we have found that the identity and the gaps between two mRNAs were higher than protein, but the similarity of mRNA was lower than protein.b. The two sequences are closely related.3. Use Water to do the sequence alignment in default parameters.*****Protein Sequence alignment result*****# Program: water# Rundate: Sat 28 Sep 2019 16:52:02 # Commandline: water # -auto # -stdout# -datafile EBLOSUM62# -gapopen 10.0 # -gapextend 0.5 # -aformat3 pair# -sprotein1 # -sprotein2 # Align_format: pair # Report_file: stdout# Aligned_sequences: 2 # Matrix: EBLOSUM62# Gap_penalty: 10.0 # Extend_penalty: 0.5 ## Length: 582# Identity: 561/582 (96.4%) # Similarity: 572/582 (98.3%) # Gaps: 0/582 ( 0.0%) # Score: 2906.0*****mRNA Sequence alignment result*****# Program: water# Rundate: Sat 28 Sep 2019 16:53:55 # Commandline: water # -auto # -stdout# -datafile EDNAFULL# -gapopen 10.0 # -gapextend 0.5 # -aformat3 pair# -snucleotide1 # -snucleotide2 # Align_format: pair # Report_file: stdout## Aligned_sequences: 2 # Matrix: EDNAFULL# Gap_penalty: 10.0 # Extend_penalty: 0.5 ## Length: 2592# Identity: 2505/2592 (96.6%) # Similarity: 2505/2592 (96.6%) # Gaps: 25/2592 ( 1.0%) # Score: 12207.5a. After alignment, we have found that the identity and the gaps between two mRNAs were higher than protein, but the similarity of mRNA was lower than protein. ( THE SAME TO Needle )b. The two sequences are closely related.c. Higher identity and similarity than Needle.4. Do the protein sequence alignment and change the original parameters.Eg: We used the needle to do the protein sequence alignment and changed the GAP_OPEN from 10 to 1.# Program: needle# Rundate: Sat 28 Sep 2019 16:58:37 # Commandline: needle # -auto # -stdout# -datafile EBLOSUM62# -gapopen 1.0 # -gapextend 0.5 # -endopen 10.0 # -endextend 0.5# -aformat3 pair# -sprotein1 # -sprotein2 # Align_format: pair # Report_file: stdout ## Aligned_sequences: 2 # Matrix: EBLOSUM62# Gap_penalty: 1.0 # Extend_penalty: 0.5 ## Length: 588 # Identity: 561/588 (95.4%) # Similarity: 572/588 (97.3%) # Gaps: 8/588 ( 1.4%)# Score: 2908.0a. We can get a consequence that the identity, gaps and similarity between the protein sequences become lower, but the score become higher. ( Were more distinct but got higher score )b. Moreover, we have changed other 4 parameters, but not got any distinct result.5. Global and local pairwise sequence alignment between human myoglobin and hemoglobin protein sequences.***Global pairwise sequence alignment***Protein Sequence Alignment between hemoglobin subunit alpha(beta) and myoglobin(Homo sapiens)***Local pairwise sequence alignment***Protein Sequence Alignment between hemoglobin subunit alpha(beta) and myoglobin(Homo sapiens)实验总结1.此次实验，我们基本掌握了如何对两条序列进行全局&局部比对，以及根据不同情况对具体参数进行调整的能力。

双序列比对算法综述

双序列比对算法综述作者：王沛来源：《学习与科普》2019年第12期摘要：在生物信息学中，基因序列比对是最基本、最重要的操作。

本文首先介绍了序列比对的划分方式，提出了双序列比对算法的研究意义；接着对典型的双序列比对算法的研究现状进行了较为详细的阐述，包括算法的原理、对比等；然后通过收集双序列比对算法的优化方案，总结出当前算法的发展趋势，得出结论。

关键词：生物信息，序列比对，双序列比对，动态规划，点阵图1 引言序列比对问题是指将基因序列进行比对，将其中相似性的部分标示出来，通过标示出的序列相似度来确定序列间的同源性关系。

在生物信息学中，基因序列的比对是最基本、最重要的操作，是进行基因识别、信息分析、结构预测等问题的前提。

本文将介绍一种最基础的比对方式——双序列比对。

2 背景与意义序列比对有多种划分方式。

根据比对数量的不同，可分为双序列比对和多序列比对。

双序列比对即通过两个基因序列的比对，找到相似的基因片段，从而推测目标基因可能具有的功能以及可能的分子进化关系。

而多序列比对通过多个基因序列的比对，寻找到它们相同的位点、区域，推测具有共同功能的序列模式。

就序列本身而言，对序列进行整体比对的方式称为全局比对，对序列进行部分比对的方式称为局部比对。

全局比对适用于总体相似度高的同源序列；局部比对适用于长度差别大、亲缘关系远的序列，可找出两条序列中相似度最高的片段。

由于双序列比对是基因序列比对最早采取的方式，也是生物信息学最基本的研究方法，所以我决定先从这种最基本的方式入手，了解双序列比对算法的研究现状及发展趋势，为进一步的学习做好铺垫。

3 双序列比对算法研究现状3.1 典型双序列比对算法介绍3.1.1 基于动态规划的双序列比对算法Needleman-Wunsch算法1970年，Needleman和Wunsch最早提出了一种基于动态规划思想的序列全局比对算法：使用迭代的方式求出两个基因序列之间的对比得分，并把结果存放在二维得分矩阵里面，然后运用动态规划方法在二维得分矩阵中进行回溯从而找到序列最佳比对路径，即序列比对的最优结果。

两序列比对算法

两序列比对算法摘要：序列比对是生物信息学研究的一个基本方法，对于发现生物序列中的功能、结构和进化信息具有重要的意义。

两序列比对中，典型的全局比对算法是Needleman—Wunsch算法；局部比对算法的基础是Smitll—Waterm an 算法，本文对典型的双序列比对算法进行描述。

关键词：生物信息学；两序列比对；算法引言：为了满足基因组中获得更多更有价值的信息，生物信息学迅速发展起来，生物信息学是一门多门科学交叉的学科，将数学、计算机科学应用于生物大分子信息的获取、加工、存储、分类、检索和分析等，以达到阐明和理解大量数据所蕴含的生物学意义的目的。

通过对DNA和蛋白质序列进行相似性比较，指明序列间的保守区域和不同之处，为进一步研究它们在结构、功能以及进化上的联系提供了重要的参考依据。

而序列比对就是运用某种特定的数学模型或算法，找出两个或多个序列之间的最大匹配碱基或残基数，比对的结果反映了算法在多大程度上反映了序列之间的相似性关系以及它们的生物学特征。

双序列比对算法双序列比对分为全局比对和局部比对，全局比对是考察两个序列之间的全局相似性，局部比对则比较序列片段之间的相似性。

Needleman—Wunsch算法是典型的全局比对算法，适用于全局水平上相似性程度较高的两个序列；Smitll—Waterman 算法适用于寻找局部相似序列对，该算法是目前被使用最广泛的序列相似性比较算法之一，由所熟悉的Needleman—Wunsch算法演变而来。

Needleman-Wunsch 算法使用迭代方法计算出两个序列的相似分值，存于一个得分矩阵中，然后根据这个得分矩阵，通过动态规划的方法回溯寻找最优的比对序列。

具有很高的灵敏度使用二维表格，一个序列沿顶部展开，一个序列沿左侧展开。

而且也能通过以下三个途径到达每个单元格：1.来自上面的单元格，代表将左侧的字符与空格比对。

2.来自左侧的单元格，代表将上面的字符与空格比对。

生物信息学中的基因组序列比对算法

生物信息学中的基因组序列比对算法1. 引言生物信息学是研究生物学信息的存储、分析和应用的学科，其中基因组序列比对算法是重要的研究方向之一。

基因组序列比对是将一个序列与一个或多个目标序列进行比较，以寻找相似性和差异性的过程。

本文将介绍生物信息学中常用的基因组序列比对算法，包括Smith-Waterman算法、Needleman-Wunsch算法和BLAST算法。

2. Smith-Waterman算法Smith-Waterman算法是一种动态规划算法，可以用于比对两个序列之间的相似性。

它的基本思想是通过构建一个得分矩阵，计算两条序列中各个位置之间的得分，然后根据得分确定最佳比对。

具体步骤如下：(1) 构建一个得分矩阵，矩阵的行和列分别表示两条序列的每个字符。

(2) 初始化得分矩阵，将第一行和第一列的得分设为0。

(3) 根据特定的得分规则，计算得分矩阵中每个位置的得分。

得分规则可以根据具体情况进行调整，常见的得分规则包括替换得分、插入得分和删除得分。

(4) 从得分矩阵中找出最高得分的位置，得到最佳比对的结束位置。

(5) 追溯最佳比对的路径，得到最佳比对的开始位置。

Smith-Waterman算法的优点是可以寻找到最佳比对的局部相似性，适用于比对包含插入或删除的序列。

3. Needleman-Wunsch算法Needleman-Wunsch算法是一种全局序列比对算法，通过构建一个得分矩阵和得分规则，计算两个序列的全局相似性。

具体步骤如下：(1) 构建一个得分矩阵，矩阵的行和列分别表示两条序列的每个字符。

(2) 初始化得分矩阵，将第一行和第一列的得分设为特定值。

(3) 根据特定的得分规则，计算得分矩阵中每个位置的得分。

(4) 从得分矩阵中找出最高得分的位置，得到最佳比对的结束位置。

(5) 追溯最佳比对的路径，得到最佳比对的开始位置。

Needleman-Wunsch算法的优点是可以寻找到全局最佳比对，适用于比对两个序列之间的整体相似性。

3-2,序列比对

Mii反映了氨基酸i的保守性 Mii = 1 – ΣMij PAM1矩阵： Mii = 1 – λΣMij = ~ 99%
PAM1矩阵，乘以10000
PAM2矩阵
基本假设：每个氨基酸的突变的概率独立于前次突变。因此，PAM2=PAM1*PAM1
PAM250矩阵
PAM250: 每100个氨基酸残基发生250次突变；蛋白质序列仍然有15-30%左右的相似性；
BLOSUM62矩阵构建步骤：
1. 提取Prosite数据库中504个家族的2万多蛋白质序列（含1961个Blocks），合并其中相似性≥62%的序列； 2. 统计各BLOCK的氨基酸对数量f； 3. 计算氨基酸对的出现频率q； 4. 计算每种氨基酸的期望频率p； 5. 计算氨基酸对出现的期望频率e； 6. 计算BLOSUM62矩阵分量rij
Step 1: 统计氨基酸的替代
1. 对于同一个group内的蛋白质序列，统计氨基酸出现的频率，以及替换的个数；
fFY = 6 fFH = 1 fYF = 9
对20种氨基酸做类似统计
fij不一定等于fji
Step2: 计算i->j的相对突变率
Pi = Fi / F : 氨基酸i出现的概率； fij = ij替代的总数; fi = 氨基酸i变为任一氨基酸的总数 = Σfij f = Σfi 氨基酸j的相对突变率： mj= fj / Fj
/CBBresearch/Schaff er/msa.html /general/software/packages/m sa/manual/manual.php
MSA：打分方式
多序列比对：方法改进
PAM矩阵
71个蛋白质家族的1572种变化；序列相似性 > 85%；功能同源的蛋白质通过中性进化，引入可接受的点突变；进化模型：

双序列比对算法

双序列比对算法
/// 双序列比对用于研究两个序列定义的DNA有多少相似之处，或者蛋白质序列有多少相似之处。

/// 这种比较在DNA鉴定和遗传暗示步骤中是非常重要的，在生物信息学应用中，两个序列之间比较也特别重要，特别是在研究顺序的进化关系和鉴定功能。

///
/// 双序列比对算法主要用于非完全比对，因为完全比对可以利用穷举法，把序列中的元素两两比对，以期发现所需的最近分数最高的所需的比对对。

/// 双序列比对算法可以利用动态规划算法，其中首先定义一个矩阵，表示序列i和序列j的最佳比对，在这个矩阵中，每个条目用于表示以矩阵中元素为末尾的两个序列段的相似度/距离，元素i和元素j越来越相似，这个度量值越大，距离越小。

///
/// 动态规划法大概有两个步骤：第一个步骤是填充一个矩阵，第二个步骤是从矩阵中搜索出最有可能产生最高得分的比对对。

第四章：双序列比对

Finding k-tups
position 1 2 3 4 5 6 7 8 9 10 11 protein 1 n c s p t a . . . . . protein 2 . . . . . a c s p r k position in offset amino acid protein A protein B pos A - posB ----------------------------------------------------a 6 6 0 c 2 7 -5 k 11 n 1 p 4 9 -5 r 10 s 3 8 -5 t 5 ----------------------------------------------------Note the common offset for the 3 amino acids c,s and p A possible alignment is thus quickly found protein 1 n c s p t a | | | protein 2 a c s p r k
比对的算法
Needleman-Wunsch Smith-Waterman算
算法适用于整体水平上相似性程度较高的 2个序列。是整体比对算法，其结果反映了两个序列中所有残基地整体相似性。
法在识别局部相似性时，具有很高的灵敏度，但只是寻找序列中一些小的、具有局部相似性的片断。
Basic Pairwise Alignment
列片断，称为k-tuple. 用于蛋白质序列比对时，k- tuple长度为1～2个残基，用于DNA序列比对时， k- tuple长度最多为6个碱基。通过比较2个序列中断片断及其相对位置可以构成一个动态规划矩阵地对角线方向上的一些匹配片断期望值E：E值越接近0，表明2序列第匹配不大可能是由随机因素造成的，即E值越低，置信度越高。

实验3两条序列比对与多序列比对

实验三：两条序列比对与多序列比对实验目的：学会使用MegAlign，ClustalX和MUSCLE进行两条序列和多条序列比对分析实验内容：双序列比对是使两条序列产生最高相似性得分的序列排列方式和空格插入方式。

两条序列比对是生物信息学最基础的研究手段。

第一次实验我们用dotplot方法直观地认识了两条序列比对。

但是dotplot仅仅是展示了两条序列中所有可能的配对，并不是真正意义上的序列比对。

这里介绍进行两条序列比对的软件-MegAlign。

多序列比对是将多条序列同时比对，使尽可能多的相同（或相似）字符出现在同一列中。

多序列比对的目标是发现多条序列的共性。

如果说序列两两比对主要用于建立两条序列的同源关系，从而推测它们的结构和功能，那么，同时比对多条序列对于研究分子结构、功能及进化关系更为有用。

多序列比对对于系统发育分析、蛋白质家族成员鉴定、蛋白质结构预测、保守模块的搜寻等具有非常重要的作用。

我们这节课主要学习多条序列比对的软件-ClustalX, MUSCLE。

一、MegAlignDNASTAR公司的Lasergene软件包是一个比较全面的生物信息学软件，它包含了7个模块。

其中MegAlign可进行两条或多条序列比对分析。

1. 两条序列比对1.1 安装程序解压DNASTAR Lasergene软件压缩包，双击Lasergene710WinInstall.exe文件，按照默认路径安装软件到自己电脑上。

1.2 载入序列a.点击开始－程序－Lasergene－MegAlign，打开软件。

我们首先用演示序列（demo sequence）学习软件的使用。

演示序列所在位置：C:\Program files\ DNASTAR\ Lasergene\ Demo Megalign\ Histone Sequences\。

b. 点击主菜单File—Enter sequence－选择序列所在文件夹，选择序列tethis21.seq和tethis22.seq，点击Add，这两条序列将出现在右侧selected sequences框中（Figure 3.1），选择完毕点击Done回到程序页面。

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

回顾
• Dynamic Programming
• Edit Distance（编辑距离）
• Alignment（比对） • Directed Acyclic Graph
• Edit Graph
• Backtracking
- T G C A T - A - C AT - C - TGA TC
1 /55
5
3 /55
Sequence Alignment
4
Outline
• Global Alignment • Scoring Matrices • Local Alignment
• Alignment with Affine Gap Penalties
5 /55
From LCS to Alignment: Change up the Scoring
16 /55
PAM
• Point Accepted Mutation (Dayhoff et al.) • 1 PAM = PAM1 = 1% average change of all amino acid positions • After 100 PAMs of evolution, not every residue will have changed • some residues may have mutated several times • some residues may have returned to their original state • some residues may not changed at all
11 /55
Percent Sequence Identity
• The extent to which two nucleotide or amino acid sequences are invariant
AC C TG A G – AG AC G TG – G C AG
mismatch indel
18 /55
Ala Arg Asn Asp Cys Gln ... Trp Tyr Val
A R N D C Q W Y V
BLOSUM
• Blocks Substitution Matrix • Scores derived from observations of the frequencies of substitutions in blocks of local alignments in
9 /55
The Blosum62 Scoring Matrix
10 /55
Measuring Similarity
• Measuring the extent of similarity between two sequences • Based on percent sequence identity • Based on conservation
22 /55
Local vs. Global Alignment
• The Global Alignment Problem tries to find the longest path between vertices (0,0) and (n,m) in the edit graph.
• The Local Alignment Problem tries to find the longest path among paths between arbitrary vertices (i,j) and (i’, j’) in the edit graph. • In the edit graph with negatively-scored edges, Local Alignmet may score higher than Global Alignment
13 /55
Scoring Matrix: Example
A A 5 R -2 N -1 K -1
R
N K
-
7
-
-1
7 -
3
0 6
• Notice that although R and K are different amino acids, they have a positive score.
si, j
s i 1 , j 1 1 if V i W j s i 1 , j 1 - m if V i W j max s i 1 , j s i , j 1
m : mismatch penalty
σ : indel penalty
8 /55
Scoring Matrices
• To generalize scoring, consider a (4+1) x(4+1) scoring matrix δ. • In the case of an amino acid sequence alignment, the scoring matrix would be a (20+1)x(20+1) size. The addition of 1 is to include the score for comparison of a gap character “-”.
• Why? They are both positively charged amino acids will not greatly change function of protein.
14 /55
Conservation
• Amino acid changes that tend to preserve the physicochemical properties of the original residue • Polar to polar • aspartate glutamate • Nonpolar to nonpolar • alanine valine • Similarly behaving residues • leucine to isoleucine
15 /55
Scoring matrices
• Amino acid substitution matrices • PAM • BLOSUM
• DNA substitution matrices • DNA is less conserved than protein sequences • Less effective to compare coding regions at nucleotide level
related proteins
• Matrix name indicates evolutionary distance • BLOSUM62 was created using sequences sharing no more than 62% identity
19 /55
The Blosum62 Scoring Matrix
BLOSUM 62
20 /55
BLOSUM90
BLOSUM80
BLOSUM62
BLOSUM45
PAM30
PAM120
PAM180
PAM240
低趋异度
高趋异度
小鼠和大鼠RBP
小鼠和细菌的lipocalin
相似度越低的序列，在比对的时候，采用PAM矩阵时，后面的数字越大，采用BLOSUM矩阵时，后面的数字越小。
• The Longest Common Subsequence (LCS) problem—the simplest form of sequence alignment – allows only insertions and deletions (no mismatches). • In the LCS Problem, we scored 1 for matches and 0 for indels • Consider penalizing indels and mismatches with negative scores • Simplest scoring schema: - T G C A T - A - C +1 : match premium AT - C - TGA TC -μ : mismatch penalty -σ : indel penalty
6 /55
Simple Scoring
• When mismatches are penalized by –μ, indels are penalized by –σ, and matches are rewarded with +1, the resulting score is: #matches – μ(#mismatches) – σ (#indels)
70% identical
12 /55
Making a Scoring Matrix
• Scoring matrices are created based on biological evidence. • Alignments can be thought of as two sequences that differ due to mutations. • Some of these mutations have little effect on the protein’s function, therefore some penalties, δ(vi , wj), will be less harsh than others.
习题
• 4，求两条序列的最长共同子序列。【作业】
v = TACGGGTAT w = GGACGTACG
2 /55
G
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0Leabharlann G2 0A