序列比对学习课件

课堂练习查找rectalcancer（直肠癌）在Homosapiens中相关的基因。TP53（Homosapiens）：mrna和蛋白质数目以及在染色体的位置。TP53（Homosapiens）

：unigene中的数据。TP53为基因名。1

/108作业CDSCodingsequence;regionofnucleotidesthatcorrespondswiththesequenceofaminoacidsinaprotein(locationincludesstartandstopcodons).

geneAregionofbiologicalinterestidentifiedasageneandforwhichanamehasbeenassigned.

自己翻译2

/108/Sitemap/samplerecord.html

帮助文档3

/108作业dbSNP-databaseofsinglenucleotidepolymorphisms,small-scaleinsertions/deletions,polymorphicrepetitiveelements,andmicrosatellitevariation.4

/108作业EntrezGeneisasearchabledatabaseofgenes,fromRefSeqgenomes,anddefinedbysequenceand/orlocatedintheNCBIMapViewer5

/108作业GenesandDisease-introductiontotherelationshipbetweengeneticfactorsandhumandisease.Summaryinformationfor~60geneticdiseaseswithlinkstorelateddatabasesandorganizations.6

/108作业TheGenomedatabaseprovidesviewsforavarietyofgenomes,completechromosomes,sequencemapswithcontigs,andintegratedgeneticandphysicalmaps.Thedatabaseisorganizedinsixmajororganismgroups:Archaea,Bacteria,Eukaryotae,Viruses,Viroids,andPlasmidsandincludescompletechromosomes,organellesandplasmidsaswellasdraftgenomeassemblies.7

/108以下哪个是RefSeq中mRNA【或蛋白质】条目的索引号码？（a）J01536；（b）NM_15392（c）NP_52280（d）AAB1345068

/108序列比对序列比对基本概念、打分矩阵与算法9主要内容一、概述1，序列比对（联配）的概念2，生物序列之间的关系二、序列比对的得分系统1，核酸的得分矩阵2，蛋白质的得分矩阵3，空位罚分体系三、点阵法与动态规划法比对两条序列四、工具软件BLAST210

/108“Biologistswillhavetobeadeptatleastinhandlingthetoolsofbioinformatics,and,fortrueinsight,theywillbebetterplacedlearningtheinformaticsneededtocreateatleastsometoolsforthemselves.”“生物学家们除了必须熟练掌握各种生物信息学的软件之外，最好他们还应当学会编写出一些适合自己需要的工具软件。”

—Nature

15Feb.2001，

—Science

16Feb.200111

/108Earlyexampleofsequencealignment:globins(1961)H.C.WatsonandJ.C.Kendrew,“ComparisonBetweentheAmino-AcidSequencesofSpermWhaleMyoglobinandofHumanHaemoglobin.”Nature190:670-672,1961.12

/1081，序列比对的概念：序列比对是生物信息学中最基本的操作序列比对可以用来预测两条序列（基因或者蛋白）是否具有相似的结构或者功能。通过分析许多DNA和蛋白质序列，我们有可能确定一群分子之间共享的结构域（domain）或模体（motif）。当更多的基因组被测序，寻找物种内和物种间蛋白质的相关性对于我们理解生命来说变得越来越重要。双序列比对是后面要介绍的BLAST（搜索数据库）的基础。其他很多基因组的分析都基于双序列比对。13

/108蛋白质序列比对包含更多的信息蛋白质包含更多的信息(20vs4characters);许多氨基酸有相近的理化性质。密码子具有简并性质（degenerate）密码子第三位改变而氨基酸不改变。蛋白序列可回溯更久远的祖先。DNA序列可以翻译成蛋白质序列再比对。14

/10815

/108Lipocalin蛋白质家族的两个蛋白retinol-bindingprotein4(NP_006735)b-lactoglobulin(P02754)两个相似的蛋白，它们有非常相似的三维结构，包括一配体的结合口袋和八个反平行的贝塔链组成的贝塔片层。但是，两个蛋白质氨基酸序列的双序列比对表明它们只有非常有限的氨基酸一致性。16

/108Pairwisesequencealignmentallowsus

tolookbackbillionsofyearsago(BYA)43210OriginoflifeOriginofeukaryotesinsectsFungi/animalPlant/animalEarliestfossilsEukaryote/archaea17

/10818

/108DNA比对当然，有些场合需要进行DNA比对： ——分析克隆的cDNA片段的一致性的时候 ——分析基因的非编码区的时候 ——研究DNA的多态性的时候 ——检验输入DNA序列是否正确Query:181catcaactacaactccaaagacacccttacacccactaggatatcaacaaacctacccac240|||||||||||||||||||||||||||||||||||||||||||||||||||||||Sbjct:189catcaactgcaaccccaaagccacccct-cacccactaggatatcaacaaacctacccac24719

/1082，生物序列之间的关系双序列比对（Pairwisealignment）：两行排列两条序列，以获得最大的一致性（对于氨基酸而言是保守性），目的是可以评估两条序列的相似程度和同源性。Query:181catcaactacaactccaaagacacccttacacccactaggatatcaacaaacctacccac240|||||||||||||||||||||||||||||||||||||||||||||||||||||||Sbjct:189catcaactgcaaccccaaagccacccct-cacccactaggatatcaacaaacctacccac24720

/108定义：同源性（Homology）：如果两条序列有一个共同的进化祖先，那么它们是同源的。RBP:26RVKENFDKARFSGTWYAMAKKDPEGLFLQDNIVA59+K+++++GTW++MA+L+A

glycodelin:23QTKQDLELPKLAGTWHSMAMA-TNNISLMATLKA55

21

/108Definitions:twotypesofhomology直系同源（Ortholog）：不同物种间的具有共同进化祖先的同源序列，可以没有共同的功能。旁系同源（Paralog）：同一物种内通过基因复制产生的同源序列。22

/108Orthologs:membersofagene(protein)familyinvariousorganisms.ThistreeshowsRBPmoncarpzebrafishrainbowtroutteleostAfricanclawedfrogchickenmouseratrabbitcowpighorsehuman普通鲤鱼非洲爪蟾10changes23

/108Paralogs:membersofagene(protein)familywithinaspeciesapolipoproteinDretinol-bindingprotein4Complementcomponent8prostaglandinD2synthaseneutrophilgelatinase-associatedlipocalin10changesLipocalin1Odorant-bindingprotein2Aprogestagen-associatedendometrialproteinAlpha-1Microglobulin/bikunin24

/10825

/108Pairwisealignmentofretinol-bindingprotein4andb-lactoglobulin（乳球蛋白）26

/108定义相似度（Similarity）Theextenttowhichnucleotideorproteinsequencesarerelated.Itisbaseduponidentityplusconservation。一致性（Identity）Theextenttowhichtwosequencesareinvariant。保守性（Conservation）

Changesataspecificpositionofanaminoacidor(lesscommonly,DNA)sequencethatpreservethephysico-chemicalpropertiesoftheoriginalresidue.27

/108Identity(bar)Pairwisealignmentofretinol-bindingprotein4

andb-lactoglobulin（乳球蛋白）

28

/108Somewhatsimilar(onedot)Verysimilar(twodots)Pairwisealignmentofretinol-bindingprotein4

andb-lactoglobulin（乳球蛋白）29

/108InternalgapTerminalgapPairwisealignmentofretinol-bindingprotein4

andb-lactoglobulin（乳球蛋白）30

/108定义：空位（Gaps）如果某个位置是一个字符不匹配别的字符就叫一个Gap。

空位的得分一般是负分（罚分）。一次突变可能引发多个残基的插入或者删除，所以，空位的引入比空位的长度显得更加注目。31

/108比对的最基本概念字符串：由一些字母组成的一维数组。字母表（alphabet），核酸序列（DNA序列）的字母表为ATGC，再加一个gap（-）。字符串长度：AT-GGCC的长度为7。子串（substring）或【子序列subsequence（可以非连续）】：原序列中任意连续的一段序列，包括0长度和全长的序列。随机序列：每个位置出现ATGC中任何一个字符的概率都是1/4。也就没有什么生物学方面的意义。非随机序列也就是有生物学意义的序列。32

/108比对的最基本概念gap空位。距离：两序列之间差异程度的一个量化数字，如两个序列完全相同则距离为0。记分矩阵（scoringmatrix）。全局比对：序列全长进行比对，寻找一个最佳的配对。局部比对：子序列比对，只需要寻找局部的最佳匹配。比对的统计显著性E值。RawScore和Bitscore：比对得分。Algorithm算法。33

/108NCBI中的序列分析工具34

/108ORF识别一个ORF就是一个潜在的蛋白质编码区ORF识别35

/108六种翻译方式DNAcanbetranslatedintosixpotentialproteins5’CATCAA5’ATCAAC5’TCAACT5’GTGGGT5’TGGGTA5’GGGTAG5’CATCAACTACAACTCCAAAGACACCCTTACACATCAACAAACCTACCCAC3’3’GTAGTTGATGTTGAGGTTTCTGTGGGAATGTGTAGTTGTTTGGATGGGTG5’36

/108结果NM_008084

NM_00808437

/108NM_008084的信息38

/10839

/108同源性与相似性的异同相似度（Similarity）Theextenttowhichnucleotideorproteinsequencesarerelated.Itisbaseduponidentityplusconservation。同源性（Homology）：如果两条序列有一个共同的进化祖先，那么它们是同源的。40

/108人类与模式生物——小鼠

因为他们各自的kit基因都存在缺陷41

/108二、序列比对的得分系统：序列比对的一般方法

选择两条序列选择一个算法，通过该算法进行序列比对并对比对打分。允许空位（插入或者删除）得分反应两条序列的相似程度可以是全局比对，也可以是局部比对

估计比对是随机产生的概率。RBP:26RVKENFDKARFSGTWYAMAKKDPEGLFLQDNIVA59+K+++++GTW++MA+L+A

glycodelin:23QTKQDLELPKLAGTWHSMAMA-TNNISLMATLKA55

42

/108二、序列比对的得分系统1，核酸的得分矩阵（WeightMatrices）核酸打分矩阵设DNA序列所用的字母表为={A，C，G，T}Query:181catcaactacaactccaaagacacccttacacccactaggatatcaacaaacctacccac240|||||||||||||||||||||||||||||||||||||||||||||||||||||||Sbjct:189catcaactgcaaccccaaagccacccct-cacccactaggatatcaacaaacctacccac247比对需要一个量化的分数。43

/1081，核酸的得分矩阵（WeightMatrices）a.等价矩阵ATCGA1000T0100C0010G0001AGTCGAAATCGT444

/1081，核酸的得分矩阵（WeightMatrices）b.BLAST矩阵ATCGA5-4-4-4T-45-4-4C-4-45-4G-4-4-45AGTCGAAATCGT?45

/1081，核酸的得分矩阵（WeightMatrices）c.转换颠换矩阵（transition，transversion）（嘌呤：腺嘌呤A，鸟嘌呤G；嘧啶：胞嘧啶C，胸腺嘧啶T）ATCGA1-5-5-1T-51-1-5C-5-11-5G-1-5-51AGTCGAAATCGT?46

/1082，蛋白质打分矩阵（i）等价矩阵（ii）氨基酸突变代价矩阵GCM（iii）疏水矩阵（iv）PAM矩阵（PointAcceptedMutation）（v）BLOSUM矩阵（BlocksAminoAcidSubstitutionMatrices）其中Rij代表打分矩阵元素i、j分别代表字母表第i和第j个字符。47

/108遗传密码矩阵通过计算一个氨基酸残基转变到另外一个氨基酸残基所需的碱基变化的最小数目而得到。48

/108疏水矩阵是根据氨基酸残基替换前后疏水性的变化而得到的矩阵。若一次氨基酸替换，疏水性不发生太大的变化，则这种替换得分高，否则替换得分低。蛋白质疏水矩阵49

/108PAM矩阵PAM（PointAcceptedMatrix）矩阵叫做可接受点突变矩阵，基于氨基酸进化的点突变模型，即如果两种氨基酸替换频繁，说明自然界易接受这种替换，那么这对氨基酸替换得分就应该高。PAM矩阵是目前蛋白质序列比对中最广泛使用的计分方法之一，基础的PAM1矩阵反映的是进化产生的每百个氨基酸平均发生一个突变的量值。PAM1自乘n次得到PAMn，比较常用的是PAM70，PAM90。50

/108针对不同的进化距离采用PAM矩阵序列相似度=40%50%60%

|||打分矩阵=PAM120PAM80PAM60PAM250→14%-27%

51

/108人RBP4蛋白质序列：NP_006735牛β-乳球蛋白序列：P02754hsrbp,136CRLLNLDGTCbtlact,3CLLLALALTC******24.7%identityin81residuesoverlap;Score:77.0;Gapfrequency:3.7%rbp426RVKENFDKARFSGTWYAMAKKDPEGLFLQDNIVAEFSVDETGQMSATAKGRVRLLNNWDVbtlact21QTMKGLDIQKVAGTWYSLAMAASD-ISLLDAQSAPLRVYVEELKPTPEGDLEILLQKWEN************rbp486--CADMVGTFTDTEDPAKFKMbtlact80GECAQKKIIAEKTKIPAVFKI*******PAM40比对结果PAM250比对结果52

/108BLOSUM62模块氨基酸替换矩阵53

/108BLOSUM90PAM30低趋异度小鼠和大鼠RBPBLOSUM45PAM240高趋异度小鼠和细菌的lipocalinBLOSUM80PAM120BLOSUM62PAM180相似度越低的序列，在比对的时候，采用PAM矩阵时，后面的数字越大，采用BLOSUM矩阵时，后面的数字越小。54

/1083，空位罚分体系一般有两种罚分方法：1，线性罚分2，仿射罚分（affinepenalty）原理在于一个位置变异的影响小于多个位置同时变异的影响。从生物学角度看，一个位置发生变异是一个突变事件，而多个位置发生变异可能是发生了多个进化（突变）事件。AGTCGATAGTCGATAGT---TAGTCGATAGTCGATAGTCGATA-TCGAT-GTC-AT55

/108三、点阵法与动态规划法比对两条序列两条序列的比对常见有三种方法：点阵法，动态规划法，词或k串法（BLAST或FASTA中采用）。点阵法：如果两条序列相似度不是很高，因为点阵法能将所有可能的比对结果用该矩阵的（次）对角线表现出来。点阵法还能显示插入/缺失及序列内部正向和反向重复的存在，这是其它比对方法很难做到的。这种方法的局限在于大部分的点阵分析程序无法给出一个真正的比对结果。动态规划法：首先由计算机科学家提出来的一种算法，它从数学意义上保证结果是最优的。词或k串法：通过搜索序列间完全相同的一短串字符，然后通过动态规划法吧这些词语连接成比对结果。这类方法的优点是速度快，适合搜索整个数据库，寻找与待查序列比对结果最好的序列，得到比对结果在统计上是可靠的。56

/108点阵法点阵法是最基本的，也是很重要的一种可视化序列比对方法。“矩阵作图法”或“对角线作图”。首先建立一个矩阵，两条序列的长度分别为矩阵的行数和列数，一条序列置于矩阵的顶部，一条序列置于矩阵的左侧。把具有相同字符的单元做标记。ACCTGAGCTCGTTAACCAGCTAA57

/108滑动窗口技术由于序列可能很长，而字符只有4个（核酸），所以会有很多随机性的没有生物学意义的相似性，这些是比对中的噪声。使用滑动窗口代替一次一个位点的比较是解决噪声问题的有效方法。假设窗口大小为10，相似度阈值为8，则每次比较取10个连续的字符，如相同的字符超过8个，则标记。基于滑动窗口的点矩阵方法可以明显地降低点阵图的噪声，并且明确无误的指示出了两条序列间具有显著相似性的区域。58

/108→序列1→→序列2→59

/108滑动窗口的过滤不连续的匹配可能是噪声，需要用滑动窗口过滤，滑动窗口有两个参数，一是窗口大小，二是阈值，也就是不匹配的字符个数。例如我们这个例子由于字符个数很少，用（3，0）的参数。TGCTGCTCCG010010000C001001011T100100100A000000000G010010000A000000000T100100100A000000000A000000000滑动窗口是这样使用的：从（1，1）位置出发，将序列1的1～3个字符与序列2的1～3个字符比较，如果都相同，则在（1，1）位置处做标记，一直到完成整个表。例如如上表中的（1，5）位置做了标记，是因为序列1的1～3个元素和序列2的5～7个元素是相同的。60

/108（a）对人类（Homosapiens）与黑猩猩（Pongopygmaeus）的β球蛋白基因序列进行比较的完整点阵图。（b）利用滑动窗口对以上的两种球蛋白基因序列进行比较的点阵图，其中窗口大小为10个核苷酸，相似度阈值为8。(a)(b)61

/108对角线上的元素如果两个序列完全相同，则对角线上每个位置都会出现标记。62

/108其它位置的元素其它位置如果出现连续的相同字符，同样可以在表中体现出来。点阵图可以很直观的发现两条序列所有可能的匹配，这些匹配可能是某种功能域。也可用于寻找蛋白质或者DNA内部的重复或者反向重复区域63

/108反向重复序列序列1→序列2→64

/108点阵图的一个例子

1AAGGTCAGGAACAAAGAAACAGCTGAATACCAAACAGGATATCTGTGGTAAGCGGTTCCT61GCCCCGGCTCAGGGCCAAGAACAGATGAGACAGCTGAGTGATGGGCCAAACAGGATATCT121GTGGTAAGCAGTTCCTGCCCCGGCTCGGGGCCAAGAACAGATGGTCCCCAGATGCGGTCC/molkit/dnadot/

两条相同序列的比对65

/108课堂练习GGGATCACGTATGCATTAGCATACATCACGCGGCCGCGTGATGTATGCTAATGCATACGTGATCCC第二条序列是第一条序列的反向互补序列，通过点阵图分析寻找序列可能的发夹状结构。思考：点阵法为什么可以发现RNA序列的发夹状结构？发夹结构66

/108作业点阵法中窗口过滤技术的方法和意义。海龟和鸟类中哪个与鳄鱼的相关性比较接近？首先，尝试用PubMed寻找答案，然后选择一个基因或者蛋白，使用BLAST2Sequences比对。河马与猪、鲸鱼中谁的相关性更近？为回答这个问题，首先从每种生物中寻找血红蛋白（hemoglobin）序列，然后进行双序列比对，记录氨基酸一致性百分比。假如你有两条远相关的蛋白，为了比较它们，最好使用下列哪个记分矩阵（）A.BLOSUM45或PAM250 B.BLOSUM45或PAM1C.BLOSUM80或PAM250 D.BLOSUM10或PAM167

/108PAM250意味着蛋白质序列上平均每100个氨基酸在进化历程上发生了250次替换，为什么与祖先序列如此远缘的蛋白质序列间仍然有14％——21％的相似性？点阵法如何分析RNA可能的发夹状结构？为什么罚分一般用仿射罚分而不是线性罚分？用图3——6和图3——7的计分矩阵计算比对得分，空位用68

/108双序列比对的动态规划算法进行双序列比对最直接的方法是生成两序列的所有可能的比对，分别计算得分，然后挑选一个得分最高的比对作为最终结果。但可能的比对是序列长度的指数函数。AATCGTAGTCGAAATCGT--ATCGTAAATCGT------CGTCGA69

/108一个简单的游戏两个人玩的游戏，有两堆石头，每堆十块石头，游戏规则为：每个人每一轮允许从一堆石头中拿走一块或是从两堆石头中各拿走一块，石头拿走了就不许再放回，谁拿走最后一块石头谁就赢得了比赛。问：每个人如何尽量保证自己是最后的赢家。70

/108玩石头游戏012345678910012345678910为了找出10＋10游戏的获胜策略，我们可以做一个表R，取代求解每堆10块石头的问题，我们将求解更一般的问题：一堆有n块石头，一堆有m块石头，称为n+m的游戏，如果玩家1总是有办法赢得R(5,6)的游戏，我们就记R(5,6)=W，否则就记R(5,6)=L。wwL71

/108玩石头游戏结果（从玩家1的角度）012345678910012345678910LWWWLWLLWWWWWLWLWLLWWWWWLWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWLWLWLWLWLWLLWLWLWLWLWLLWLWLWLWLWLWLWLWLWWWWWWWLWLWLWWWWWWWLWLWL从最简单的开始，利用前面的结果（子问题）72

/108Needleman-Wunsch算法N-W算法是一种全局比对动态规划算法，于1970年被提出，得到了非常广泛的应用。首先假设我们要对两条序列V和W进行比对，它们的长度分别为M和N，动态规划算法由3部分组成：1）最优化的递归计算方法；2）给出子问题最优解的矩阵填充过程和3）寻找最优化比对路径的回溯方法。序列W:AAGGTCAGGAA序列W前5个字符的前缀字串：AAGGT73

/108用来存储子问题的最优化动态规划矩阵存放子串TTCG和ATTC的最佳比对分数。该矩阵存放相应前缀字串的最佳比对得分。WV74

/1081）最优化的递归计算方法两条长i和j的序列V和W比对结束的方式有3种，两个字符vi和wj出现在同一列中；vi与一个空位出现在同一列中；或者wj与一个空位gap出现同一列中。。。。AAGT。。。。ACG。。。AAGT。ACG。。－两个字符vi和wj出现在同一列中vi和一个空位出现在同一列中。AAGT。－。。。。ACGwj和一个空位出现在同一列中75

/108采用简单打分系统匹配得4分，不匹配得－3分，空隙得－4分，或者用前面讲过的计分矩阵。为了量化，我们必须对各种配对情况给一个分数。76

/1081）最优化的递归计算方法假设我们已经得到了几个子问题的最优比对，分别是①V序列长i-1的前缀和W序列长j-1的前缀的最优比对，②V序列长i的前缀和W序列长j-1的前缀的最优比对，③V序列长i-1的前缀和W序列长j的前缀的最优比对，那么对于V序列长i的前缀和W序列长j的前缀的最优比对能否简单的（例如线性关系式）得到呢？。。。。。。。。。。。。。。。。。。。。。。。ji序列W？j-1i-13个红色圈的最佳值已知。序列V77

/1081）最优化的递归计算方法两个字符vi

和wj

出现在同一列中。。。AAG。T。。。。AC。G这种情况下比对得分情况是怎么样的呢？表示两条序列各去掉最后一个字符的最佳得分表示两个字符配对的分值，见前面的打分系统。这段比对得分已知78

/1081）最优化的递归计算方法这种情况下比对得分情况是怎么样的呢？与一个空位出现在同一列中。。。AAGT。ACG。。－d表示空位罚分值。与一个空位出现在同一列中的时候得分是79

/1081）最优化的递归计算方法据此，我们可以写出一个概括性的公式。。。AAGT。。。。ACG。。。AAGT。。ACG。－80

/108。。。。。。。。。。。。。。。。。。。。。。。ji序列W？j-1i-1序列V81

/1082）给出子问题最优解的矩阵填充过程－ATTCCAAG－0－4－8－12－16－20－24－28－32T－4T－8C－12G－16A－20G－24T－28后面例子再详细讲填充过程。82

/1083）矩阵回溯以寻找最有比对路径一旦整个矩阵填充完毕，就可以得到最优比对得分，即矩阵中最后一个得分，要找出最优比对方式，我们还需要对整个矩阵进行回溯。从矩阵的最后一个单元（M,N）开始，根据填充记录的路径，直到回溯到第一个单元（0，0）。根据回溯路径，就得到了两条序列的最优比对结果。83

/108例题讲解利用Needleman-Wunsch算法对两条DNA序列进行全局比对。a＝ATTCCAAG，b＝TTCGAGT，得分系统是（4，－3，－4）求解这个问题分3步。（1）给动态规划矩阵赋初值（2）按照最优分的递归算法填充动态规划矩阵（3）从最后一个单元格开始，回溯最优化比对路径84

/108（1）给动态规划矩阵赋初值－ATTCCAAG－0－4－8－12－16－20－24－28－32T－4T－8C－12G－16A－20G－24T－28012345678

0123456785

/108（2）按照最优分的递归算法填充动态规划矩阵－ATTCCAAG－0－4－8－12－16－20－24－28－32T－4T－8C－12G－16A－20G－24T－28－30－7－4得分系统是（4，－3，－4）－8－12－16－20－241486

/10887

/108（3）从最后一个单元格开始，回溯最优化比对路径－TTCGA－GTATTCCAAG－VWWV88

/10889

/108作业找出例题中其它的最佳比对结果（总共4个比对，还有2个）。用动态规划法找出两序列的所有最佳比对，要求写出详细过程。打分矩阵采用{（4，－3，－4}，即匹配得4分，不匹配得－3分，空位得－4分。序列1：AAAG，序列2：ACG。90

/108总结动态规划算法是一种高效的给出最优比对的算法。它的基本思想就是将待解决问题分成若干个子问题，先求解子问题，并存储子问题的解而避免重复计算，然后从这些子问题的解得到原问题的解。动态规划算法能保证在给定得分系统下产生最优的比对结果（optimalalignment）。但是这种方法对参数非常敏感，记分系统参数的选择在很大程度上决定着比对的结果。最优比对结果往往不止一个，次优结果也有可能更具有生物学意义，最优只是数学上的概念，而且是跟记分系统参数相关的。91

/108Algorithm:Similarityinput:

sandt;output:similaritybetweensandt92

/108AlgorithmAligninput:indicesi,j,arrayagivenbyalgorithmSimilarityoutput:al