５Ｙ’９３５３９１分类号研究生学位论文生物信息学中的序列相似性比对算法研究生姓名睦佳指导教师姓名魏壶强熬授申请学位级别工程煎±专业领域让簋扭拄苤论文答辩日期垒２鳗垒§且２２且学位授予日期２Ｑ塑生§且中国海洋大学生物信息学中的序列相似性比对算法摘要序列相似性比对是生物信息学中基本的信息处理方法，它对于发现生物序列中的功能、结构和进化的信息具有非常重要的意义。主要思想就是运用某种特定的数学模型或算法，找出两个或多个序列之间的最大匹配碱基或残基数，比对的结果反映了算法在多大程度上反映了序列之间的相似性关系以及它们的生物学特征。因此，生物信息学中分析的序列相似性比对的简单有效算法一直是生物学家关，心的问题，序列比对也是讲’算生物学中解决象序列装配，进化树重构及基因组分析等众多问题的第一步。进行序列相似性比对的算法很多，而这些算法大多数都是基于动态规划算法，只是在其基础上进行了不同程度的改进而已。根据同ｕ．１‘比对的序列数目的不同，将序列相似性比对算法分成双序列相似性比对算法和多序列相似性比对算法。本文在第二章前三节详细地介绍了这些基于动态规划算法的序列相似性比对算法。所有这些算法有个共同的特点：算法是字符串比较算法，序列的比较是字符上的比较，它们的差异性体现在彼此间存在不同的子序列或子结构，而相似性体现在它们有共同的子序列或子结构，因此我们很自然的会想到寻找生物序列的最长公共子序列，这就是所谓的ＬＣＳ问题。近两年国内外一些学者给出了ＤＮＡ序列的图形表示．用几何的方法比较生物序列，这些理论已经基本成熟。我们在第四节介绍了ＤＮＡ序列图形表示的相关理论并给出了－－ｉ，ｆ，基于二维图形表示的寻找生物序列和生物结构的最长公共子序列的算法，该算法简单并可视化。很适合用于生物序列的比较和分析。在第三章给出了用于寻找ｍＲＮＡ序列和蛋白序列的最优局部对ＬＶ．矛ｉＪ全局对比的对比算法。关键词：算法：ＤＮＡ；序列比对；图形表示；ＬＯＳＴｈｅＡＩｇｏｒｉｔｈｍｓｏｆＳｅｑｕｅｎｃｅＡＩｉｇｎｍｅｎｔｉＡｂｓｔｒａｃｔＳｅｑｕｅｎｃｅａｌｉｇｎｍｅｎｔｉｓａｎＢｉｏｉｎｆｏｒｍａｔｉｃｓｂａｓｉｃｉｎｆｏｒｍａｔｉｏｎｐｒｏｃｅｓｓｉｎｇｍｅｔｈｏｄｆｏｒｄｉｓｃｏｖｅｒｉｎｇｆｕｎｃｔｉｏｎａｌ，ｉｎｂｉｏｉｎｆｏｒｍａｔｉｃｓａｎｄｕｓｅｆｕｌｅｖｏｌｕｔｉｏｎａｒｙｆｉｎｄａｓｔｒｕｃｔｕｒａｌ，ａｎｄｔｏｉｎｆｏｒｍａｔｉｏｎｉｎｂｉｏｌｏｇｉｃａｌｓｅｑｕｅｎｃｅｓ．ＴｈｅｍａｉｎｉｄｅａｉＳａｍｏｎｇｍａｘｉｍｕｍｂａｓｅｍａｔｃｈｉｎｇｂｉｏｌｏｇｉｃａｌｓｅｑｕｅｎｃｅｓ．ＴｈｅｒｅｓｕｌｔｏｆｓｅｑｕｅｎｃｅｓｓｅｑｕｅｎｃｅｃｏｍｐａｒｉｓｏｎｓｈｏｗｔｈｅＳｉｍｉｌａｒｉｔｙ／ｄｉｓｓｉｍｉｌａｒｉｔｙｂｅｔｗｅｅｎｓｅｑｕｅｎｃｅｓ．ａｎｄｔｈｅｂｉｏｌｏｇｉｃａｌｃｈａｒａｃｔｅｒｉｓｔｉＣｏｆｔｈｅＩｔｉＳｖｅｒｙｉｍｐｏｒｔａｎｔｔｏｌｏｏｋｆｏｒａｓｉｍｐｌｅａｎｄｅｆｆｅｃｔｉｖｅａｌｇｏｒｉｔｈｍｓｏｆｓｅｑｕｅｎｃｅｓａｌｉｇｎｍｅｎｔｆｏｒｂｉｏｌｏｇｉｓｔ．ＳｅｑｕｅｎｃｅａｌｉｇｎｍｅｎｔｉＳｓｔｅｐａｌＳＯｔｈｅｆｉｒｓｔｆｏｒｍａｎｙｐｒｏｂｌｅｍｓｉｎｃｏｍｐｕｔａｔｉｏｎａｌｂｉｏｌｏｇｙ，ｔｒｅｅｉｎｃｌｕｄｉｎｇｆｒａｇｍｅｎｔａｓｓｅｍｂｌｙ，ｅｖｏｌｕｔｉｏｎａｒｙＴｈｅｒｅａｒｅｒｅｃｏｎｓｔｒｕｃｔｉｏｎａｎｄｇｅｎｏｍｅａｎａｌｙｓｉＳ．ｔｈｅａｎａｌｙｓｉＳｂａｓｅｄｏｎｍａｎｙｍｅｔｈｏｄｓｆｏｒｏｆｓｉｍｉｌａｒｉｔｙｏｆＤＮＡｓｅｑｕｅｎｃｅｓ，ｂｕｔｍｏｓｔｏｆｔｈｅｍａｒｅｔｈｅｔｈｅｄｙｎａｍｉｃｐｒｏｇｒａｍｍｉｎｇｃａｎａｌｇｏｒｉｔｈｍ．Ｔｈｅｓｅｑｕｅｎｃｅａｌｉｇｎｍｅｎｔａｌｇｏｒｉｔｈｍｂｅｄｉｖｉｄｅｄｉｎｔｏｐａｉｌｌ＿ｗｉｓｅｓｅｑｕｅｎｃｅａｌｉｇｎｍｅｎｔａｌｇｏｒｉｔｈｍｓａｎｄ眦ｌ】ｔｉｐｌｅｓｅｑｕｅｎｃｅａｌｉｇｎｍｅｎｔａｉｇｏｒｉｔｈｍ．Ｉｎｃｈａｐｔｅｒ２，ｗｅｏｎｉｎｔｒｏｄｕｃｅｔｈｅｔｒａｄｉｔｉｏｎａｌａｌｇｏｒｉｔｈｍｓｔｈｅｄｙｎａｍＪｏｎｅＣｏｆｓｅｑｕｅｎｃｅａｌｉｇｎｍｅｎｔｂａｓｅｄｐｒｏｇｒａｍｍｉｎｇａｌｇｏｒｉｔｈｍ．ＷｅｗｉｌｌｆｉｎｄｔｈａｔａＩｌａｌｇｏｒｉｔｈｍｓｓｈａｒｅｄｏｎｃｈａｒａｃｔｅｒｉｓｔｉＣ：Ｔｈｅｔｒａｄｉｔｉｏｎａｌｍｅ·ｔｈｏｄｉＳｂａｓｅｄｓｈｏｗｔｈｅｓｅｓｔｒｉｎｇｈａｖｅａｃｏｍｍｏｎｃｏｍｐａｒｉｓｏｎｏｆｓｔｒｉｎｇ．Ｔｈｅｓｉｍｉｌａｒｉｔｙｓｕｂｓｔｒｉｎｇ．ＬＣＳｉＳｔｈｅｐｒｏｂｌｅｍｆｏｒｆｉｎｄｉｎｇｍａｘｉｍｕｍｃｏｍｍｏｎｓｕｂｓｅｑｕｅｎｃｅ（ＬｏｎｇｅｓｔＢａｓｅｏｎＣｏｍｍｏｎＳｕｂｓｅｑｕｅｎｃｅ）ｉｎｂｉｏｌｏｇｉｃａｌｐｒｏｖｉｄｅａｎｅｗｓｅｑｕｅｎｃｅ．Ｒｅｃｅｎｔｌｙ，ｍａｎｙａｕｔｈｏｒｓｈａｖｅｐｒｏｖｉｄｅｄｇｒａｐｈｉｃａｌｒｅｐｒｅｓｅｎｔａｔｉｏｎｓｏｆｂｉｏｌｏｇｉｃａｌｓｅｑｕｅｎｃｅｓ．ｔｈｉＳｉｄｅａ，ｗｅｍｅｔｈｏｄｔｏＳＯｌｖｅｔｈｅＬＣＳｂｅｔｗｅｅｎｂａｓｅｄｏｎｂｉｏｌｏｇｉｃａｌｓｅｑｕｅｃｎｅａｎｄｂｉｏｌｏｇｉｃａｌｓｔｒｕｃｔｕｒｅｔｈｅｇｒａｐｈｉｃａｌｆｏｒｔｈｅｒｅｐｒｅｓｅｎｔａｔｉｏｎ．ＴｈｅａｌｇｏｒｉｔｈｍｄｅｍｏｎｓｔｒａｔｅｓｓｅｑｕｅｎｃｅｔｈｅｅｆｆｅｃｔｉｖｅｎｅｓｓｗｅＶｉｓｕａ］ｉｚａｔｉｏｎａｎｄｃｏｍｐａｒｉｓｏｎ．ＡｎｄａｌＳＯｃｏｎｓｉｄｅｒａｌｇｏｒｉｔｈｍｔｏｓｅａｒｃｈｔｈｅｌｏｃａｌａｌｉｇｎｍｅｎｔａｎｄｇｌｏｂａｌａｌｉｇｎｍｅｎｔｂｅｔｗｅｅｎｍＲＮＡｓｅｑｕｅｎｃｅｓａｎｄｐｒｏｔｅｉｎｓｅｑｕｅｎｃｅｓｉｎｃｈａｐｔｅｒ３．Ｋｅｙｗｏｒｄｓ：ＡＩｇｏｒｉｔｈｍ。ＤＮＡｓｅｑｕｅｎｃｅ，ＳｅｑｕｅｎｃｅＧｒａｐｈｉｃａａＩｉｇｎｍｅｎｔＩｒｅｐｒｅｓｅｎｔａｔｉｏｎ。ＬＯＳ．独创声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含未获得（蕉！塑毽直墓丝益塞挂型童盟的！查拦丑窒２或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文作者签名：７惦签字日期：娜６年月２－７Ｈ学位论文版权使用授权书本学位论文作者完全了勰学校有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权学校可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。（保密的学位论文在解密后适用本授权书）学位论文作者签名：ｆ聋—弗签字日期：Ｍ６年Ｓ月２．）日学位论文作者毕业后去向：工作单位：山东大学威海分校通讯地址：山东大学威海分校数学系导师签字礁训飞年月日签字日期：电话：５６８８５２３邮编：２６４２０９生物信息学中的序列相似性比对算法１绪论１．１生物学基础知识１．１．１ＤＮＡ．ＲＮＡ和蛋白质ＤＮＡ（ｄｅｏｘｙｒｉｂｏｎｕｃｌｅｉｃａｃｉｄ）是遗传特征的基础，它是由核苷酸小分子生成的聚合物。核苷酸有四种，可以用四种基来区分他们。四个基分别是（Ａ）腺嘌呤、（Ｃ）胞嘧啶、（Ｇ）鸟嘌呤和（Ｔ）胸腺嘧啶。ＤＮＡ分子可以看成是四个字母字符集舴＝ｆＡ，Ｃ，Ｇ，Ｔ｝上的词。ＤＮＡ分子是有方向性的，左端通常记为５’，另一端记为３’。ＤＮＡ蕴涵的复制机制的关键特征是碱基互补。既Ａ与Ｔ配对，Ｇ与Ｃ配对。这种配对是由于氢键作用。原理是ＤＮＡ单个链（按５’到３’次序）５’ＡＣＴＧＡＣＴＧＣ３’与相反方向写的相补的链配对。ＤＮＡ分子是双链结构。两条链缠绕在一起形成双螺旋，此著名的双螺旋。（ｄｏｕｂｌｅｈｅｌｉｘ）结构是ｄｊＪａｍｅｓＷａｔｓｏｎ和ＦｒａｎｃｉｓＣｒｉｃｋ在１９５３年发现的。这种碱基互补配对的机制使得ＤＮＡ在细胞中得以复制。ＲＮＡｆｒｉｂｏｎｕｃｌｅｉｃａｃｉｄ）分子与ＤＮＡ分子很相似，但在组成和结构上也有一些重要的不同。在ＲＮＡ分子中，核糖取代了ＤＮＡ分子中的２’．脱氧核糖。另外，胸腺嘧啶Ｔ被尿嘧啶Ｕ取代了，Ｕ与Ｔ一样能够与Ａ配对。ＲＮＡ分子并不形成双螺旋。有时我们可以看到ＲＮＡ．ＤＮＡ杂交双螺旋。此外，ＲＮＡ能够通过碱基互补与同一分子的其它部分结合。ＲＮＡ的三维结构远较ＤＮＡ复杂。ＤＮＡ与ＲＮＡ的另一个不同是，ＤＮＡ本质上仅有一个功能，即编码信息，而在细胞中有不同的ＲＮＡ，各自行使不同的功能。生物体的大部分物质是各种各样的蛋白质，他们既是工作部件，又是组成原料。蛋白质包括很多种，结构蛋白是组织的构成单元，酶是化学反应的催化剂。蛋白质的其他功能还包括氧气输送和抗体防御等。这种非常重要的大分子是由氨基酸（ａｍｉｎｏａｃｉｄ）的分子序列组成的。自然界中之发现了２０种不同的氨基酸，表１．１列出了这些氨基酸，这是蛋白质中最常见的２０种，另外还有几种非标准的氨基酸。表１．１蛋白质中发现的２０中常见氨基酸单字母缩写ｌＡＣＤ三字母缩写ＡｌａＣｙｓＡｓｐ名称丙氨酸（ａｌａｎｉｎｅ）半膀氨酸（ｃｙｓｔｅｉｎｅ）天冬氨酸（ａｓｐａｒｔｉｃａｃｉｄ）谷氨酸（ｇｌｕｔａｍｉｃａｃｉｄ）苯丙氨酸（ｐｈｅｎｙｌａＩａｎｉｎｅ）甘氨酸（ｇｌｙｃｉｎｅ）；２３４５６ＥＦＧＧ１ｕＰｈｅＧｌｙ生物信息学中的序列相似性比对算法７８９ｌＯ１１１２１３１４１５１６１７１８１９２０ＨＩＫＬＨｉｓＩｌｅＬｙｓＬｅｕ组氨酸（ｈｉｓｔｉｄｉｎｅ）异亮氨酸（ｉｓｏｌｅｕｃｉｎｅ）赖氨酸（１ｙｓｉｎｅ）亮氨酸（１ｅｕｃｉｎｅ）甲硫氨酸（ｍｅｔｈｉｏｎｉｎｅ）天冬酰胺（ａｓｐａｒａｇｉｎｅ）脯氨酸（ｐｒｏｌｉｎｅ）谷氨酰胺（ｇｌｕｔａｍｉｎｅ）精氨酸（ａｒｇｉｎｉｎｅ）幺幺氨酸（ｓｅｒｉｎｅ）苏氨酸（ｔｈｒｅｏｎｉｎｅ）缬氨酸（ｖａｌｉｎｅ）色氨酸（ｔｒｙｐｔｏｐｈａｎ）酪氨酸（ｔｙｒｏｓｉｎｅ）ＭＮＰＭｅｔＡｓｎＰｒｏＧｌｎＡｒｇＳｅｒＴｈｒＶａｌＴｒｐＱＲＳＴＶＷＹＴｙｒ在蛋白质中，氨基酸通过肽键相连。因此，蛋白质是多肽链。肽键使得每个蛋白质都有一个骨架（ｂａｃｋｂｏｎｅ），在骨架的一端是一个氨基，另～端是一个羧基。我们因此可以区别多肽链的两端并给它定一个方向，习惯上多肽始于氨基（Ｎ端），止于羧基（Ｃ端）。蛋白质并不仅仅是氨基酸残基的线性序列，这种序列称为一级结构（ｐｒｉｍａｒｙｓｔｒｕｃｔｕｒｅ）。。蛋白质实际上在三维空间中折叠，形成二级（ｓｅｃｏｎｄａｒｙ）、三级（ｔｅｒｔｉａｒｙ）和四级（ｑｕａｔｅｒｎａｒｙ）结构。因为蛋白质的三维结构非常复杂，而且，蛋白质的三维结构与其功能相关，因此确定蛋白质的折叠或三维结构是分子生物学的一个重要领域。１．１．２分子遗传学机制ＤＮＡ分子的重要性在于，机体中合成ＲＮＡ和蛋白质的信息编码于ＤＮＡ分子中。基于此，ＤＮＡ有时被称为“生命蓝图”。每一个细胞都有几个非常长的ＤＮＡ分子，每一个这样的分子称为染色体（ｃｈｒｏｍｏｓｏｍｅ）。ＤＮＡ中仅有一部分连续的片段编码构建蛋白质的信息，而其它部分并不编码蛋白质信息。每一种不同的蛋白质仅对应一段ＤＮＡ序列，该段序列称为基因（ｇｅｎｅ）。如前所述，蛋白质是氨基酸链。因此，确定蛋白质仅需确定其所含的每一个氨基酸，这正是基因所要做的，他用三联核苷酸编码每一个氨基酸。每个三联核苷酸称为密码子（ｃｏｄｏｎ）。三联核苷酸与氨基酸之间的对应关系称为遗传密码（ｇｅｎｅｔｉｃｃｏｄｅ），见表１．２。表１．２氨基酸的遗传密码１’ａｂｌｅｌ－２Ｇｅｎｅｔｉｃｃｏｄｅ第一位５’端第二位核苷酸ＵＦＣＧＹ酪氨酸Ｙ酪氪酸ＡＣ半膀氨酸Ｃ半膀氨酸第三位３’端核苷酸Ｕ核苷酸ＵＳ丝氨酸苯丙氨酸Ｆ苯丙氨酸Ｓ丝氨酸Ｃ生物信息学中的序列相似性比对算法Ｌ亮氨酸Ｓ丝氮酸ｓｔｏｐｓｔｏｐ终止终止ＡＬ亮氨酸Ｓ丝氩酸ｓｔｏｐＷ色氨酸Ｇ终止ＬＣ亮氨酸Ｐ脯氨酸Ｈ组氨酸Ｒ精氮酸ＵＬ亮氨陵Ｐ脯氨酸ｌ｛组氮酸Ｒ楷氨艘ＣＬ亮氩酸Ｐ脯氮瞳Ｑ符氩酰胺Ｒ捎氮酸ＡＬ亮氨酸Ｐ脯氮酸０谷氨酰胺Ｒ精氯幢ＧＩＡＴＮ天冬酰胺Ｓ丝氮酸Ｕ异亮氨酸苏氨酸ＩＴＮ灭冬啦胺Ｓ丝氮陵Ｃ异亮氯睦封、氮酸ＩＴＫ赖氢酸Ｒ精氮酸Ａ异亮氯般粥，氮敞ＭＴＫ赖氩酸Ｒ精氯陵Ｇ甲硫氨酸苏氨酸ＶＧ缬氮陂Ａ埘氮酸Ｄ天冬氮酸ＧＨ氮酸ＵＶ缬氨酸Ａ丙氪酸Ｄ天冬氨酸Ｇ甘氨酸ＣＶ蝴氩酸Ａ丙氮艘Ｅ谷氨酸Ｇ｝＝『氨艘ＡＶ缬氮酸Ａ丙氨酸Ｅ谷氨酸Ｇ甘氨酸Ｇ生物信息学中的序列相似性比对算法表１．２中的三联核苷酸是用ＲＮＡ碱基而非ＤＮＡ碱基表示，因为ＲＮＡ分子提供了ＤＮＡ和蛋白质之间的关联。另外，有三个密码子并不编码任何氨基酸而是用于表示基因的终止，这三个特殊的终止密码在表中用ｓｔｏｐ表示。下面我们介绍ＤＮＡ信息是如何指导蛋白质合成的。一个识别基因或基因簇起始的机制是启动子（ｐｒｏｍｏｔｅｒ）。启动子是基因前面的一段ＤＮＡ序列，密码子ＡＵＧ则是基因开始的信号。识别出基因的起始点后，基因到ＲＮＡ的拷贝就开始了，合成的ＲＮＡ称为信使ＲＮＡ（ｍＲＮＡ），其序列与ＤＮＡ的一条链相同，但是Ｕ代替了Ｔ，该过程称为转录（ｔｒａｎｓｃｒｉｐｔｉｏｎ）。因ＲＮＡ是单链而ＤＮＡ是双链的，ｍＲＮＡ在序列上与一条ＤＮＡ链相同（只不过是ｕ取代了Ｔ），与另一条链互补。ＤＮＡ中，与ｍＲＮＡ序列一致的链称为反义链（ａｎｔｉｓｅｎｓｅｓｔｒａｎｄ）或编码链（ｃｏｄｉｎｇｓｔｒａｎｄ），而另一条链称为有意义链（ｓｅｎｓｅｓｔｒａｎｄ）、反密码链（ａｎｔｉｃｏｄｉｎｇｓｔｒａｎｄ）或模板链（ｔｅｍｐｌａｔｅｓｔｒａｎｄ）。实际上被转录的是模板链，因为ｍＲＮＡ是由与该链互补的核糖核酸组成的，合成过程是从５’端向３’端，因此模板链是从３’端向５’端阅读的。上述的转录在原核生物（ｐｒｏｋａｒｙｏｔｅ）中是正确的。在这些生物中，由于缺乏核膜，ＤＮＡ是自由悬浮于细胞中的。但在真核生物（ｅｕｋａｒｙｏｔｅ）的细胞中有细胞核，ＤＮＡ位于细胞核中，其转录模式更为复杂。许多真核细胞基因具有不同的组成部分，即内含子（ｉｎｔｒｏｎ）和外显子（ｅｘｏｎ）。转录后内含子必须从ｍＲＮＡ中切除，这意味着内含予不参与蛋白质的合成。在内含子被剪切后，离开细胞核的剪短的ｍＲＮＡ仅含有外显子与起始和终止的序列。因为有内含子和外显子，我们用不同的名字命名染色体上的全基因和剪切后仅含外显子的基因，前者称为基因组ＤＮＡ（ｇｅｎｏｍｉｃＤＮＡ），后者称互补ＤＮＡ（ｃｏｍｐｌｅｍｅｎｔａｒｙＤＮＡ）或ｃＤＮＡ。通过细胞核外的ｍＲＮＡ，然后使用一个称为反转录（ｒｅｖｅｒｓｅｔｒａｎｓｃｒｉｐｔｉｏｎ）的过程以ｍＲＮＡ为模板合成ｃＤＮＡ。这样，人们可以不经染色体而获得ｃＤＮＡ。在某些生物的中也存在反转录现象，例如，反病毒通过反转录的机制能将它们的ＲＮＡ基因组复制成ＤＮＡ。现在让我们重新回到ｍＲＮＡ和蛋白质合成。在这个过程中另外两种ＲＮＡ分子起到重要的作用。蛋白质的合成是在细胞内的核糖体中进行的。核糖体由蛋白质和被称为核糖体ＲＮＡ（ｒｉｂｏｓｏｍａｌＲＮＡ，ｒＲＮＡ）的大分子组成。遗传信息从ＲＮＡ传到蛋白质的过程称为翻译（ｔｒａｎｌａｔｉｏｎ）。实际上，遗传密码的翻译是由ｔＲＮＡ实现的，它连接密码子和其所编码的氨基酸。当ｍＲＮＡ穿过核糖体内部时，ｔＲＮＡ匹配当前的密码子，即当前位于核糖体内部的ｍＲＮＡ密码子，与它结合，并带进对应的氨基酸（细胞中总是悬浮着大量的氨基酸）。这些分子此时所处的空间位置使他们可以完成下列操作，即随着ｔＲＮＡ与密码子结合，新结合的氨基酸紧靠先前己形成的氨基酸链，一个合适的酶则催化该氨基酸加入肽链，然后释放ｔＲＮＡ。蛋白质按这种一个氨基酸接一个氨基酸的方式合成起来。当出现终止密码子时，没有ｔＲＮＡ与之对应，合成便终止，ｍＲＮＡ被释放，并被降解成核糖核苷酸。总结上面描述的过程，细胞内遗传信息的流动通常用中心法则（ｃｅｎｔｒａｌｄｏｇｍａ）来说明。生物信息学中的序列相似性比对算法复制图１．１分子生物学的中心法则１．２生物信息学生物信息学（Ｂｉｏｊｎｆｏｒｍａｔｉｃｓ）这个名词有许多不同的定义。从字面上来看，生物信息学是将信息科学和技术应用于生物学。生物信息学广义的概念是指应用信息科学的方法和技术，研究生物体系和生物过程中信息的存贮、信息的内涵和信息的传递，研究和分析生物体细胞、组织、器官的生理、病理、药理过程中的各种生物信息，或者也可以说成是生命科学中的信息科学。生物信息学狭义的概念是指应用信息科学的理论、方法和技术，管理、分析和利用生物分子数据。通过收集、组织、管理生物分子数据，使研究人员能够迅速地获得和方便地使用相关信息；通过处理、分析、挖掘生物分子数据，得到深层次的生物学知ｉ：！＝｛，加深对生物世界的认识：在生物学、医学的研究和应用中，利用生物分子数据及其分析结果，可以大大提高研究和开发的科学性及效率，如根据基因功能分析结果来检测与疾病相关的基因，根据蛋白质分析结果进行新药设计。一般提到的”生物信息学”是就指这个狭义的概念，更准确地说，应该是分子生物信息学（ＭｏｌｅｃｕｆａｒＢｉｏｉｎｆｏｒｍａｔｊＣＳ）。生物信息学以计算机、网络为工具，采用数学和信息科学的理论、方法和技术去研究生物大分子，其研究重点主要落实在核酸和蛋白质两个方面，包括它们的序列、结构和功能。生物信息学以基因组ＤＮＡ序列信息分析作为出发点，破译遗传语言，认识遗传信息的组织规律，辨别隐藏在ＤＮＡ序列中的基因，掌握基因信息，对蛋白质空间结构进行模拟和预测，依据蛋白质结构和功能的关系进行药物分子设计。与生物信息学相关的概念还有计算分子生物学（ＣｏｍｐｕｔａｃｉｏｎａｌＭｏｌｅＣｋｌｆａｒＢｉｏｌｏｇｙ），计算分子生物学主要研究分析方法，开发分析工具，促进生物分子数据的分析。与生物信息学相关的另一个名词是生物计算（Ｂｉｏｃｏｍｐｕ％ｉｎｇ），生物计算特指用计算机技术分析和处理生物分子数据。生物系统通过存贮、修改、解读遗传信息和执行遗传指令形成特定的生命活动，促使生物体生长发育，产生生物进化。从信息学的角度来看，生物分子是生物信息的载体，生物信息学主要研究两种载体，即ＤＮＡ分子和蛋白质分子。生物分子至少携带着三种信息，即遗传信息、与功能相关的结构信息、进化信息。ＤＮＡ是遗传信息的载体。ＤＮＡ的核菅酸序列上存储着蛋白质的氨基酸序列编码信息，存储着基因表达凋控的信息，存储着遗传信息。遗传信息存储在ＤＮＡ四种字符组成的序列中，生物体生长发育的本质就是遗传信息的传递和表达。因此，可以说ＤＮＡ序列包含着最基本的生命信息。存储在ＤＮＡ中的信息使无活生物信息学中的序列相似性比对算法力的分子组织成有功能的活细胞，进而构成能进行新陈代谢、生长和繁殖的生物体。人们已经认识到遗传信息的载体主要是ＤＮＡ［在少数情况下核糖核酸（ＲＮＡ）也充当遗传信息的载体］，控制生物体性状的基因是一系列ＤＮＡ片段。一方面，ＤＮＡ通过自我复制，在生物体的繁衍过程中传递遗传信息。另一方面，基因通过转录和翻译，使遗传信息在生物个体中得以表达，并使后代表现出与亲代相似的生物性状。在基因表达过程中，基因上的遗传信息首先通过转录从ＤＮＡ传到ＲＮＡ，然后再通过翻译从ＲＮＡ传递到蛋白质。基因控制着蛋白质的合成，从基因的ＤＮＡ序列到蛋白质序列存在着一种明确的对应关系，而这种对应关系就是我们所知道的第一遗传密码。蛋白质分子在生物体内执行着各项重要任务，如生化反应的催化、营养物质的输运、信号的识别与传递等。蛋白质的功能多种多样，但是必须注意一点，即蛋白质功能取决于蛋白质的空间结构。要了解和掌握蛋白质的功能必须首先分析蛋白质的结构，对于其它生物大分子也一样。因此，蛋白质结构是一种重要的生物分子信息。然而，蛋白质结构决定于蛋白质的序列（这是目前基本共认的假设），蛋白质结构的信息隐含在蛋白质序列之中。作为信息的载体，ＤＮＡ分子和蛋白质分子都打上了进化的烙印。通过比较相似的蛋白质序列，如肌红蛋白和血红蛋白，可以发现由于基因复制而产生的分子进化证据。比较来自于不同种属的同源蛋白质，即直系同源蛋白质，可以分析蛋白质甚至种属之间的系统发生关系，推测它们共同的祖先蛋白质。生物分子信息具体表现为ＤＮＡ序列数据、蛋白质序列数据、生物分子结构数据、生物分子功能数据等。序列数据、结构数据是非常直观的，但是功能数据却是多变复杂的，如关于蛋白质功能的定性描述、蛋白质之间的相互作用描述、基因表达数据、代谢路径、网络等。在所有类型的数据中，序列是最基本的数据，而且也是目前最多的数据。生物分子数据是宝藏，生物信息数据库是金矿，等待我们去挖掘和利用。与一般信息相比，生物分子信息具有明显的特征。首先，生物分子信息数据量大，例如ＤＮＡ序列以千兆碱基（Ｇｉｇａｂａｓｅ，Ｇｂ）为单位。随着信息处理技术进入现代生物学研究领域，随着互联网在全球的贯通，各种生物信息学数据库迅速发展，生物分子数据积累速度成倍增长。其次，生物分子信息复杂，既有生物分子序列的信息，又有结构和功能的信息，既有生命本质信息，如基因，又有生命表象信息，如基因表达信息。生物分子信息另一个重要的特征是，生物分子信息之间存在着密切的联系，例如，基因序列与蛋白质序列之间的关系，生物分子序列与结构之间的关系，结构与功能之间的关系，基因变异与疾病之间的关系。对于生物分子信息，靠人工难以完成数据处理和分析的任务，更谈不上发现隐藏在这些信息之中的内在规律。同时，对于生物分子信息，仅靠某一学科的专家，也无法进行分析研究，因此，在生物信息学研究领域中，要求生物学家、数学家和计算机科学工作者协力合作，发展新的分子生物学计算理论和方法，运用先进的计算机技术收集、集成和分析处理生物信息。可参考文献［１］［２］。１．２．１生物信息学研究内容第一，收集和管理生物分子数据，使得生物学研究人员能够方便地使用这些数据，并为信息分析和数据挖掘打下基础。生物分子数据来自于生物学实验，应用信息学技术收集和管理这些数据，将各种数据以一定的表示形式存放在计生物信息学中的序列相似性比对算法算机中，建立数据库系统，并提供数据查询、搜索和数据通讯工具。第二。进行数据处理和分析。通过数据分析，发现数据之间的关系，认识数据的本质，进而上升为生物学知识。并在此基础上，解释与生物分子信息复制、传递和表达有关的生物过程，解释在生物过程中出现的信息变化与疾病的关系，帮助发现新的药物作用目标，设计新的药物分子，为进一步的研究和应用打下基础。目前生物信息学的主要研究对象是ＤＮＡ和蛋白质。在ＤＮＡ分析方面，着重分析ＤＮＡ序列中的基因信息及基因表达信息，分析基因表达数据，分析基因之间的相互作用关系，比较不同种属的基因组，研究基因组中非编码区域的生物学功能。在蛋白质分析方面，着重分析蛋白质序列与蛋白质结构及功能之间的关系，预测蛋白质的结构和功能，研究蛋白质的进化关系。第三，开发分析工具和实用软件，解决具体的问题，为具体的生物信息学应用服务，例如，开发生物分子序列比较工具、基因识别工具、生物分子结构预测工具、基因表达数据分析工具等。掌握互联网上各种生物信息学数据库以及相关软件的使用技术已成为生物学和医学研究人员的迫切需要。尤其是分子生物学的三大核心数据库—ＧｅｎＢａｎｋ核酸序列数据库、ＳＷＩＳＳ—ＰＲＯＩ’蛋白质序列数据库和ＰＤＢ生物大分子结构数据库，不仅是全世界分子生物学和医学研究人员获取生物分子的序列、结构和其他信息的基本来源，而且是发表自己序列或结构测定结果的重要媒体。围绕这三大核心数据库还有众多面向各种特定应用的衍生数据库和分析软件，这些数据库分别从不同角度、以不同方式对各类生物信息学数据进行归纳、总结和注释，而各种分析软件为挖掘这些数据提供了有力的工具。１．２．２序列比对的进化基础在生物学的研究中，有一个常用的方法，就是通过比较分析获取有用的信息和知识。我们从核酸以及氨基酸的层次去分析序列的相同点和不同点，以期能够推测它们的结构、功能以及进化上的联系。最常用的比较方法是序列比对，它为两个或更多个序列的残基之间的相互关系提供了一个非常明确的图谱。进行序列比对的目的之一是让人们能够判断两个序列之间是否具有足够的相似性，从而判定二者之间是否具有同源性。值得注意的是，相似性和同源性虽然在某种程度上具有一致性，但它们是完全不同的两个概念。相似性是指一种很直接的数量关系，比如部分相同或相似的百分比或其它一些合适的度量，而同源性是指从一些数据中推断出的两个基因在进化上曾具有共同祖先的结论，它是质的判断。基因之间要么同源，要么不同源，绝不象相似性那样具有多或少的数量关系。例如，比较家鼠和小龙虾的同源的胰蛋白酶序列，发现它们具有４１％的相似性。由于受到研究进化关系这一目的的影响，大多数比对方法很自然地都希望能够在某种程度上建立起分子进化的模型。我们通常都假定同源序列是从某一共同祖先不断变化而来，但事实上，我们无法得知这个祖先序列到底是什么样子，除非能够从化石中获得它的ＤＮＡ，我们所能够做到的只是从现存物种中，探求。从祖先序列以来所发生的变化包括取代、插入以及缺失。在理想情况下，同源基因或蛋白质序列在相互比较时，残基之间相互对应，从而使取代的情况很明显地表现出来。在残基一残基比对中，很明显，某些位置的氨基酸残基相对于其它位置的残基具有较高的保守性，这个信息揭示了某些残基对于～个蛋白质的结构和功能是极为重要的。另一方面，由于历史原因，某些保守位生物信息学中的序列相似性比对算法置对蛋白功能并无太大的重要性。当我们处理非常相近的物种时必须十分小心，因为相似性在某些情况下更多地是历史的反映而不是功能的反映，比如，ｍｏｕｓｅ和ｒａｔ的某些序列具有高度的相似性，可能仅仅是因为没有足够的时间进行分化而已。尽管如此，系列比对仍然是从已知获得未知的一个十分有用的方法，比如通过比较一个新的蛋白同其它已经经过深入研究的蛋白，可以推断这个未知蛋白的结构与功能的某些性质。必须指出的是，不能够仅仅是通过比较分析这一判据来断定结论是否正确，结论还必须经过实验验证。当我们发现两个基因或蛋白质具有惊人的相似性时，我们会认为他们之间具有一段共同的进化历程，从而我们判断他们会具有相似的生物学功能在生物信息学中，对序列数据进行相似性比较即序列相似性比对，是一种基本的信息处理方法，它对于发现生物序列中的功能、结构和进化的信息具有非常重要的意义。而序列相似性比对就是运用某种特定的数学模型或算法，找出两个或多个序列之间的最大匹配碱基或残基数，比对的结果反映了算法在多大程度上反映了序列之间的相似性关系以及它们的生物学特征，因此，设计一个合理高效的序列相似性比对算法已成为生物信息学领域中的一个非常重要的研究课题。下一章主要叙述了用于序列比对的各种算法，包括作者在这方面的工作。２序列相似性比对算法序列数据包括ＤＮＡ序列数据和蛋白质序列数据。由于ＤＮＡ序列是由４种碱基Ａ，Ｔ，Ｃ，Ｇ组成，蛋白质序列由２０种氨基酸残基组成，可以将一条序列数据看作是由特定的字母组成的字符串。这样，一个ＤＮＡ序列就可视为是由Ａ，Ｔ，Ｃ，Ｇ四种字母组成的一个字符串，蛋白质序列视为是由２０种字母组成的字符串。序列相似性比对算法（ｓｅｑｕｅｎｃｅａｌｉｇｎｍｅｎｔａｌｇｏｒｉｔｈｍ），就是根据一个给定的计分函数计算得到两个或多个字符串序列的最优比对。即对两个或多个字符串序列通过匹配相对应的字符或插入“一”来显示插入或删除而得到序列之间的最大相似性排列。如对ＡＴＡＣＴＡＧＡ和ＡＡＣＴＴＧＧＡ进行排列后得到的最优比对结果如图所示：ＡＴＡＣＴＡＧ—ＡＡ—ＡＣＴＴＧＧＡ目前，进行序列相似性比对的算法很多，而这些算法大多基于动态规划的算法思想，只是在其基础上进行了不同程度的改进而己。根据同时比对的序列数目的不同，将序列相似性比对算法分成双序列相似性比对算法和多序列相似性比对算法。常见的两类动态规划算法：全局排列算法（Ｎｅｅｄｌｅｍａｎ—Ｗｕｎｓｃｈ算法）和局部排列算法（Ｓｍｉｔｈ—Ｗａｔｅｒｍａｎ算法）。本章分别简要介绍这两类算法中目前最常用的典型算法。并给出一种基于生物大分子图形表示的新的比对算法。２．１双序列相似性比对算法双序列相似性比对分为全局比对和局部比对，全局比对是考察两个序列之间的全局相似性，局部比对则比较序列片段之间的相似性。典型的全局比对算法是Ｎｅｅｄｌｅｍａｎ－Ｗｕｎｓｃｈ算法，这种算法适用于全局水平上相似性程度较高的两个序列。局部比对算法的基础是Ｓｍｉｔｈ－Ｗａｔｅｒｍａｎ算法，这种算法适用于亲源关系较远、整体上不具有相似性而在一些较小的区域上存在局部相似性的两个序列［３］。生物信息学中的序列相似性比对算法由于生物学中局部比对通常比全局比对更具有实际的意义，所以以下简单介绍三种典型的局部ＣＬｘ，／算法Ｓｍｉｔｈ—Ｗａｔｅｒｍａｎ，ＦＡＳＴＡ和ＢＬＡＳＴ。对各种生物大分子序列进行分析是一件非常基本的工作。从序列的片段测定，拼接，基因的表达分析，到ＲＮＡ和蛋白质的结构功能预测，物种亲缘树的构建都需要进行生物分子序列相似性的比较。在遗传物质长期的演化过程中，原本相同的ＤＮＡ序列由于其中一条序列缺失了几个片断，或增加了几个片断，或某段子序列发生了位置的变化等，从而导致他们发生了不同，这两条序列不一定能进行精确的匹配，但是他们有一定的相似度。我们应该如何判定序列之间的这种相似性？对于这种情况，生物学家提出了一种用来评定序列相似性的方法，称为记分函数的方法［３］。定义ｌ：如果ｓ是一个序列，那么吲表示ｓ中的字符长度，ｓ［ｉ］表示序列的第ｉ个字符。如果序列ｓ和序列Ｔ相同，必须满足如下条件：（１）、Ｉｓｆ＝ｒＴ『：（２）、Ｓ［ｉ］＝Ｔｌｉ］，ｆＯ＜ｆ＜Ｓ）：定义２：如果。和ｙ是两个字符，那么盯（。，川表示Ｘ和ｙ字符在进行比较时所得的分值，盯称为一个记分函数，记分函数还包括当Ｘ为空字符或Ｙ为空字符的情况，在序列中一个所谓的空字符表示序列中空字符的位置可能缺失一个未知的字符，我们只能使用空字符来表示这种缺失；定义３：如果ｓ和Ｔ是两个序列，那么Ｓ和Ｔ的一个相似性比较ｄ可以用ｓ。和７＿’来表示，其中：（１）、ｌ酬＝ｌＴ。｛：（２）、将ｓ’和ｒ中的空字符除去后所得的序列分别和ｓ、Ｔ相同：相似性比较ｄ就是ｓ。和７’’中字符一一比对，相似性比较ｄ的得分Ｓｃｏｒｅ可以用如下公式表示：Ｓｃｏｒｅ＝∑Ｇ（ｓ讥Ｔ．［ｆ】）其中：ｔ＝ｆｓ’｝ＩＴ’ｌ；定义４：对于两个序列Ｓ和７１，它们的最优相似性比较Ａ是指在Ｓ和ｒ的所有相似性比较中得分最高的一个，序列相似性比较算法的主要目标就是如何寻找出序列间的最优相似性比较。２．１．１Ｓｍｉｔｈ—Ｗａｌｃｅｒｍａｎ算法Ｓｍｉｔｈ—Ｗａｔｅｒｍａｎ算法是１９８１年Ｓｍｉｔｈ和Ｗａｔｅｒｍａｎ提出的一种用来寻找并比较具有局部相似性区域的动态规划算法，在识别局部相似性时，具有很高的灵敏度，一直是局部序列ＬＬｘ，／算法的基础，后来有许多算法都是基于这一算法开发和改进的。ＳｍｉｔｈＷａｔ．ｅｒｍａｎ算法先用迭代方法计算出两个序列的所有可能相似性比较的分值，然后通过动态规划的方法回溯寻找最优相似性比较。生物信息学中的序列相似性比对算法ＳｍｉｔｈＷａｔｅｒｍａｎ算法的具体描述如下：对于两个序列Ｓ和Ｔ，ｓ［ｆ】和丁［ｆ】，其中０＜ｉｓｓｌ；ｌ，０＜ｉ≤ＴｌｉＩ，都属于某个字符集Ｑ，对Ｑ中的任何元素和空符号，他们两两之间都有一个记分值，用记分函数ｃｒ（ｘ，Ｙ）表示，Ｆ（ｉ，Ｊ）表示序列Ｓ的前缀ＳＩｌｌＳ［２１…Ｓ［ｉ一１］Ｓ［ｉ］￥ｔｌ序列Ｔ的前缀研１］丁【２］…Ｔ［ｉ一１］Ｔ［ｉ］：２２Ｉ＇ｆｆＪ的最优相似性比较的得分。那么有如下公式：ｗＦ（ｊ，』）＝ｍａＸ泸㈣㈣盯０√√１ｏ卜卜ｒ卜开叩∞确？通过公式我们可以得到一个得分矩阵Ｍ｝Ｆｒｒ厂广■广『＿：Ｆｒｉ■ｉＦ厂■厂■！ＦＰ曩ｒ万Ｆ厂■厂一通过得分矩阵进行动态规划回溯法获得相似性比较的算法如下：：厂厂一厂＿厂厂厂■：匮二Ｆ二厂＿＿丁＝匿霹乏夏：ｒ厂＿＿厂＿厂降可厂了万．ｆｏｒ（ｉ＝Ｉｓｌ，』；１７１；ｊ＞ｏ＆＆Ｊ＞ｏ：）（矿（ＭＢ，Ｊ］。时Ｂ一１，ｊ一１卜ａ（ｓＢｌ丁Ｍ））（ｉ一一；』一一：）ｅ／ｓｅｌ，（时Ｉ，讣；肘Ｄ一１，ｊ］＋ａ（ｓ８ｌ一））（ｉ一一；ｉｎｓｅｒｔ（＇－＇，Ｔ，』）：】ｅ蛔矿（且ｆＢ，』】＝且ｆ８，Ｊ一１】＋ａ（一，丁０—１ｂ）（』—一；ｉｎｓｅｒｔ（＇－％ｓ，ｉ）：））其中ｉｎｓｅｒｔ（ａ，ｂ，ｃ、函数表示在一个亭歹｛ｊｂ韵第ｃ令位置插入一令字祷ａＳｍｉｔｈＷａｔｅｒｍａｎ算法中，假设ｍ＝ｌＳＩ，ｎ＝ｌＴｌ，在开始计算得分矩阵Ｍ时需要生物信息学中的序列相似性比对算法计算矩阵的每一个得分值，计算复杂度为Ｏ（ｍ＋ｎ）。从上面的回溯算法中可以看到，第二步回溯算法的计算复杂度为Ｏ（ｍａｃ（ｍ，”））。这样ＳｍｉｔｈＷａｔｅｒｍａｎ算法的整体时间复杂度为Ｏ（ｍＸ”）。使用ＳｍｉｔｈＷａｔｅｒｍａｎ算法计算两个序列最大相似性比较时绝大部分计算时间将消耗在计算得分矩阵上Ｍ。的值。当Ｍ（ｉ一１，Ｊ—１），Ｍ（ｉ一１，／）和Ｍ（ｉ，Ｊ一１）已经计算出来后，我们称Ｍ（ｉ，Ｊ）是可计算的。如下图所示：Ｆ广ｒＦ『Ｆ厂『厂ＦＦＦｒ厂『－＿厂『Ｆ厂阳玎ｒＦ歹『］一』『ＦＦ厂厂厂厂ＩＦＦｒ一厂厂＿厂ｌ萤中一＞“表示浚矩阵元素当时霹计算通过上图的分析，在某个特定的时候，矩阵中出现多个可以同时计算的元素，实际上就是在计算得分矩阵的过程中包含着可并行性。ＳｍｉｔｈＷａｔｅｒｍａｎ算法就可以利用这种并行性进行并行优化。一般来说，类似于ＳｍｉｔｈＷａｔｅｒｍａｎ算法这种具有明显数据依赖和迭代的算法最适合于在数据流模型的并行计算机上进行并行化，但是这种数据流模型的计算机仅仅作为一种模型存在，这种体系结构的计算机现在并不存在。表１ＳｍｉｃｈＷａｔｅｒｍａｎ算法得到的最终得分矩阵ＪＯ】２３４５６ｆＸＸＸＣｄｅ０ＯＯ００ＯＯＯ１ⅡＯＯＯ０ＯＯＯ２ｂ００Ｏ及．０Ｏ０３ｃＯ０氏０１Ｏ４ｘＯ２２Ｖ·一众．。Ｖ１Ｏ５ｄＯ１ｌｌ１、０ｋ６ｅＯ０Ｏ００２、ｏ７ｘ０２２２１１４算法过程简单描述为：１．为每一碱基对或残基对赋值。相同或类似的赋予正值，对于不同的或有空位的赋予负值。２．用Ｏ对矩阵边缘单元初始化。生物信息学中的序列相似性比对算法３．矩阵中得分值相加，任何小于０的得分值均用０代替。４．通过动态规划的方法，从矩阵中的最大分值单元开始回溯寻找。５．继续，一直到分值为Ｏ的单元停止，此回溯路径的单元即为最优比对序列。例如，两个序歹１Ｊａｂｃｘｄｅｘ和ｘｘｚｃｄｅ，使用Ｓｍｉｔｈ—Ｗａｔｅｒｍａｎ算法进行局部序列相似性比对，相同值为２，不同值和插入空位值为一ｌ，得到表１的得分矩阵，表中黑体表示回溯路径，从回溯路径得出局部最优比对的结果为：ｃｘｄｅｃ－ｄｅ或ｘ—ｄｅｘｃｄｅ２．１．２ＦＡＳＴＡ算法ＦＡＳＴＡ算法是１９８５年由Ｐｅａｒｓｏｎ和Ｌｉｐｍａｎ提出并在１９８８年做了进一步改进的双序列相似性比对启发式算法，采用了改进了的Ｗｉｉｂｕｒ和Ｌｉｐｍａｎ算法以集中反映具有显著意义的比对结果。其基本思想是：一个能揭示出真实序列关系的比对至少包含一个两个序列都拥有的字（片段），把查询序列中的所有字编成Ｈａｓｈ表，然后在数据库搜索时查询这个Ｈａｈｓ表，以检索出可能的匹配，这样那些命中的字就能很快地被鉴定出来。算法过程简单描述为：１．根据点阵图逻辑，从比对的所有结构中计算出最佳的对角线。２．使用字符方法寻找查询字符和测试序列之间的精确匹配。３．当所有的对角线发现之后，通过增加空位来连接对角线。４．在最佳对角线区域中计算出比对结果。２．１．３ＢＬＡＳＴ算法ＢＬＡＳＴ算法是由Ａｌｔｓｃｈｕｌ等人在１９９０年提出，采用了一种短片段匹配算法和一种有效的统计模型来找出目的序列和数据库之间的最佳局部比对效果。ＢＬＡＳＴ是现在应用最广泛的序列相似性搜索工具，相比ＦＡＳＴＡ有更多改进，速度更快，并建立在严格的统计学基础之上。ＮＣＢＩ提供了基于Ｗｅｂ的ＢＬＡＳＴ服务，用户可以把序列填入网页上的表单里，选择相应的参数后提交到数据服务器上进行搜索，从电子邮件中获得序列搜索的结果。ＢＬＡＳＴ包含五个程序和若干个相应的数据库，分别针对不同的查询序列和要搜索的数据库类型。其中翻译的核酸库指搜索比对时会把核酸数据按密码子按所有可能的阅读框架转换成蛋白质序列。表１．ＢＬＡＳＴ程序：程序ｂｌａｓｔｐｂｌａｓｔｎｂｌａｓｔｘｔｂｌａｓｔｎ馓据库蛋白质核酸蛋白质核苷酸（翻译）核酸（翻译）座询蛋白质核苷酸核酸（翻译）蛋白质核酸（翻译）简述可能找到具有远源进化关系的匹配序列适合寻找分值较高的匹配，不适合远源关系适合新ＤＮＡ序列和ＥＳＴ序列的分析适合寻找数据库中尚未标注的编码区适合分析ＥＳＴ序列ｔｂｌａｓｔｘ生物信息学中的序列相似性比对算法表２．ＢＬＡＳＴ的蛋白质数据库库恼述汇集了ＳＷＩＳＳ—ＰＲＯＴ，ＰＩＲ，ＰＲＦ以及从ＧｅｎＢａｎｋ序列编码区中得到的蛋白质和ＰＤＢ中拥有原子坐标的蛋白质，并去除了冗余的序列ｎｒ中过去３０天内的最新序列ＳｗＩＳＳ—ＰＲＯＴ数据库ＰＤＢ结构数据库中的蛋白质序列酵母基因组中编码的全部蛋白质大肠杆菌基因组中编码的全部蛋白质Ｋａｂａｔ的免疫学相关蛋白质序列由ＲＥＰＢＡＳＥ中的Ａｌｕ重复序列翻译而来，＿Ｈ｛来遮敲查洵序列中的重复片段ｍＯｎｔｈＳＷｌＳｓｐｒｏｔｐｄｂＹｅａｓｔＥ．ｃｏｌｉＫａｂａｔ表３．ＢＬＡＳＴ的核酸数据库据库愉述非冗余的ＧｅｎＢａｎｋ＋ＥＭＢＬ＋Ｄ｝）ＢＪ＋ＰＤＢ序列，除了ＥＳＴ、ＳＴＳ、ＧＳＳ羽１０，ｌ，２阶段的ｌ｛１ＧＳ序列ｎＦ中过去３０天的最新序列非冗余的Ｇｅｎｂａｎｋ＋ＥＭＢＬ＋ＤＤＢＪ＋ＰＤＢ的ＥＳＩ’部分非冗余的Ｇｅｎｂａｎｋ＋ＥＭＢＬ＋ＤＤＢＪ＋ＰＤＢ的ＳＴＳ部分０，ｌ，２阶段的高产量基因细序列（３阶段完成的ＩＩＴＧ序列在ｎｒ库里）仙虬拈。乳以酵母的全基因组序列火肠杆菌的全基因组序列由三维结构库来的核酸序列㈣恤她恤ｍ‰邮胁ｍ牡∞ｏＫａｂａｔ的免疫学相关序列库Ｇｅｎｂａｎｋ的载体子集线粒体核酸序列ＲＥＰＢＡＳＥ中Ａｌｕ重复序列翻译而来，用米遮敲查询序列中的重复片段基因组ｌ｝Ｊｊ测序列（ＧｅｎｏｍｅＳｕｒｖｅｙｍ山ｌ曼Ｓｅｑｕｅｎｃｅ）算法过程简单描述为：１．从两个序列中找出一些长度相等且可以形成无空位完全匹配的子序列，即序列片段对。找出两个序列之间所有匹配程度超过一定阈值的序列片段对。２．３．将得到的序列片段对根据给定的相似性阈值延伸，得到一定长度的相似性片段，称为高分值片段对。２．２多序列相似性比对算法最初的多序列相似性比对算法基于动态规划法，由于实际数据利用的动态规划矩阵进行序列相似性比对不太现实，因此目前大多数实用的多序列相似性比对程序采用基于渐进思想的启发式算法，以降低运算复杂度。其中使用最广泛的ＣＬＵＳＴＡＬ算法，是由Ｆｅｎｇ和ＤｏｏｎｔＬｌｅ于１９８７年提出的，它的基本思想是：基于相似序列通常具有进化相关性这一假设。生物信息学中的序列相似性比对算法算法过程简单描述如下：１．２．先将多个序列两两比对构建距离矩阵，反映序列之间两两关系；然后根据距离矩阵计算产生系统进化指导树，临近的序列并不断重新构建比对，直到所有序列都被加入为止。３．对关系密切的序列进行加权；然后从最紧密的两条序列开始，逐步引入２．３基于知识发现的序列相似性比对算法鉴于目前序列相似性比对算法中存在的问题，而且知识发现领域中已经积累了许多有意义的序列模式分析和相似检索技术，可以对其进行改进加以应用，所以知识发现将逐渐成为序列分析中序列相似性比对的强有力工具［］［］。目前，国际上有人提出将知识发现运用于序列相似性比对，但只是处于探索和试验阶段，还未见有成熟的知识发现算法公开发表。知识发现（ＫｎｏｗｌｅｄｇｅＤｉｓｃｏｖｅｒｙｉｎＤａｔａｂａｓｅ，简称ＫＤＤ），亦称为数据挖掘（ＤａｔａＭｉｎｉｎｇ），是指从大量数据中提取出可信的、新颖的、有效的并能被人理解的模式的处理过程，这种处理过程是～种高级的处理过程，主要任务有数据总结、分类、聚类、关联规则发现、相似性搜索等，它可以帮助人们对数据进行更深层次的分析，更好地对研究及日常决策提供有力的支持。知识发现有三个过程，分为数据预处理、数据挖掘、数据评价。数据预处理，主要负责从序列数据库中提取出与挖掘相关的数据，并对提取出的数据进行再加工，检查数据的完整性及数据的一致性，对其中的噪音数据进行处理，对重复和丢失的数据进行统计方法处理。如，构成蛋白质序列的２０种氨基酸残基中有些序列中某个残基未定，对这些特殊残基进行预处理。在处理阶段，还可以尝试结合数据仓库技术。数据挖掘，是知识发现的核心部分，在生物序列相似性比对中，数据挖掘过程就是采用序列相似性比剥＋算法得到序列规则，即相似性序列。相似性是衡量对象之间相似程度的指标，一般通过计算对象在特征空间中的距离获得。知识发现领域中已经有许多有意义的序列模式分析和相似检索技术，可以用来进行序列相似性计算。如，高维数据的检索和挖掘算法、基于范例推理的相似性搜索方法、基于聚类的相似性测量方法和序列模式挖掘算法等，都可以在其基础上进行改进．然后要对得出的相似序列给出评估，即用统计方法给出每个序列的统计值，用来表示结果的可信度。如概率和期望值。数据评价，就是将发现的知识以用户能了解的方式呈现给用户。主要实现简单的相似序列可视化，将相似序列部分高亮度显示等。２．４基于图形表示的比对算法２．４．１ＤＮＡ的几何图形表示序列相似性比对的基本问题是比较两个或两个以上符号序列的相似性或不相戗性。早期的序列相似性比对是全局的序列相似性比对，但由于蛋白质具有模决性质，可能由于外显子的交换而产生新蛋白质，因此局部比对会更加合理。通常用打分矩阵描述序列两两比对，两条序列分别作为矩阵的两维，矩阵点是两维上对应两个残基的相似性分数，分数越高则说明两个残基越相似。因此，序列相似性比对问题变成在矩阵里寻找最佳对比路径。ＤＮＡ序列的传统表示是由Ａ、Ｃ、Ｇ、Ｔ四个字母来表示的，这种表示具有自身的优点，但是随着计算机技术的发展和可视化要求的提高，它固有的缺点也生物信息学中的序列相似性比对算法随之暴露出来。１９８３年Ｅ．Ｈａｍｏｒｉ和工Ｒｕｓｋｉｎ［４］提出了ＤＮＡ序列图形表示的思想——将ＤＮＡ序列表示为一条平面或空间中的曲线，自此国内外不少化学专家如Ｍ．ＲａｎｄｉＣ，Ａ．Ｎａｎｄｙ以及国内郭晓峰等人提出了众多的图形表示Ｅ５—１８］，最基本的ＤＮＡ序列的几何图形表示有下面几种：１．ＤＮＡ序列的Ｇ曲线和Ｈ一曲线［４］：这是一种５维空间表示，其中４个坐标方向分别为四种核苷酸，另一个方向说明ＤＮＡ序列核昔酸的位置特征。当用两个坐标轴的四个方向表示四种基时，曲线就变成３维空间的曲线。这样的曲线被称为Ｈ一曲线。Ｇ一曲线和Ｈ一曲线现在已经不用了。现在文献中出现的是下面几种曲线。２．ＤＮＡ序列的二维表示：建立一个笛卡儿坐标系Ｘ，Ｙ轴，它们的正负四个方向分别表示四种核苷酸，从左到右每次观察ＤＮＡ序列的一个基，根据每次观察到的基画出ＤＮＡ序列图。这样的表示有三种形式。最早在Ｇａｔｅｓ［１１］的论文中将ｘ轴的正方向设为Ｃ，负方向设为Ｇ，Ｙ轴的正负方向分别被设为Ｔ和Ａ。而在Ｎａｎ＠的文章中将ｘ轴的正方向设为Ｇ，负方向设为Ａ，ｙ轴的正负方向分别设为Ｃ和Ｔ。在Ｌｅｏｎｇ和ＭｏｒｇｅｎｔｈｌＯＦ［１２］的文章中将ｘ轴的正方向设为Ａ，负方向设为Ｃ，ｙ轴的『Ｅ负方向分别被设为Ｔ和Ｇ。３．ＤＮＡ序列的三维曲线表示［６］［１７］：ＤＮＡ序列的三维曲线表示是二维曲线表示的一种扩充。因为在二维曲线表示中，四个核营酸的地位是不一样的，即它是不对称的：当选定一个碱基后，剩下的三个碱基仅有一个是与第一个的方向相反的。这就是为什么在二维曲线中会出现三种形式。如果取定一个碱基后，我们还能取三个等价的方向，就能避免进行多次选择。从这个角度我们考虑正四面体，因为他的中心到四个顶点的方向是等价的。这就是说：当选择一个碱基后，其余的三个碱基的方向仍然是等价的，所以我们可以把四个碱基设计到一个四面体的等点上。为了说明它们的方向，我们可以在一个正方体中设计一个（ｘ，Ｙ，ｚ）笛卡儿坐标系，它的坐标原点为正方体的中心，四个基分别对应正方体的四个等点（１，１，１），（１，一１，一】），（一ｌ，１，一１）和（一１，一１，１），如下图。ＡＣ对于图中的正方体的六个面，我们分别称它为：后面为嘌呤面，前面为嘧啶面，上面为氨基面，下面为酮基面，左面为强氢基面，右面为弱氢基面。然而对上述的图形表示都有一个共同的缺陷，即存在退化现象，如序列ＡＣＧＴＧＴＣＡ和ＡＣＧＴＧＴＣＡＡＣＧＴＧＣＡ。虽然它们的几何表示应该是不一样的，然而我们并不能从它们的图形中表现出来，我们称这种现象序列图形的退化。这种现象主要是由于在画序列的几何图形时有圈（Ｃｉｒｃｕｉｔ）的存在，在二维图形表示中，一个最小圈的长度是２，在三维图形表示中，一个最小圈的长度是４。＾ｆ．Ｒａｎｄｉｃ等人还基于他们的图形表示，将ＤＮＡ序列转化为矩阵等数学表示，进一步用矩阵不变量（主要是最大特征值）来研究ＤＮＡ序列，取得了很好的结果［１５儿１８］。我国著名理论物理专家张春霆院士也提出了一种ＤＮＡ几何图形表示——ｚ曲线，ｚ曲线是表示ＤＮＡ序列的一个等价的三维空间曲线。通过对生物信息学中的序列相似性比对算法ｚ曲线的研究来对基因组序列进行研究是一种几何学的途径。天津大学生物信息中心用这种思路研究了真核和原核基因组中若干重要问题，这样的思路是切实可行的。原则上浣，基因组中的许多问题都可以通过这种途径加以解决，这种独树一帜别开生面的研究思路已经得到国内外学术界的普遍好评和认可，越来越多的同行，主要是国外同行，加入到对ｚ曲线研究的行列中来。可以预期，用几何学方法研究基因组将会有一个广阔的发展空间。根据几何图形表示，可以将序列数值化，利用数值不变量比较ＤＮＡ序列间的相似性，将相似性转化为距离记分构建进化树，并将这些数值特征返回到生物学中，探索生物序列的数值特征的生物学意义，给出合理的解释。可以将ＤＮＡ序列的几何图形表示应用于功能区预测、序列组合、序列分析、分子进化、比较基因组学和ＤＮＡ语言学等。这里我们仅仅介绍ＤＮＡ序列的几何图形表示在序列的相似性分析方面的应用。２．４．２最长公共子序列（ＬＯＳ）问题序列相似性比对的基本问题是比较两个或两个以上符号序列的相似性或不相似性。早期的序列相似性比对是全局的序列相似性比对，但由于蛋白质具有模块性质，可能由于外显子的交换而产生新蛋白质，因此局部比对会更加合理。通常用打分矩阵描述序列两两比对，两条序列分别作为矩阵的两维，矩阵点是两维上对应两个残基的相似性分数，分数越高则说明两个残基越相似。因此，序列相似性比对问题变成在矩阵里寻找最佳对比路径。具体地讲，对两个ＤＮＡ序列Ｗ。和Ⅵ，，，求出它们的扩张序列，使得它们的扩张序列的罚分Ｄ（ｗ，，Ｗ，）为最小。序列相似性比对算法是一个动态规划算法，最早是Ｎｅｅｄｌｅｍａｎ—Ｗｕｎｓｃｈ动态规划算法，在此基础上又改良产生了Ｓｍｉｔｈ—Ｗａｔｅｒｍａｎ算法和ＳＩＭ算法。自后又有许多算法被提出，它们的要点是下列递归公式：Ｄ（ｉ，Ｊ）＝ｍｉｎ／Ｄ（ｆ一１，ｌ，）十ｄ（ａ，，一），＿Ｄ（ｆ—ｌ，Ｊ一１）＋ｄ（ａ，，ｂ，），Ｄ（ｉ，．，一１）＋ｄ（一，６，）｝这里Ｄ（ｉ，ｆ）表示两个序列的前面长为ｉ的字首与前面长为，的字首之间的最小距离。利用上面的递归公式，我们能用一个矩阵表逐一求出两个扩张序列的所有字符的最小距离。序列的比较这个问题从一开始被提出就得到了研究者们的关注，并且有大量的可适用的软件来用于处理序列的比较。然而现在所用的软件都是基于上面的序列相似性比对算法而作以推广。序列两两比对的做法实际上是来自计算机算法中的字符串比较算法。在进行序列两两比对时，有两方面问题直接影响相似性分值：取代矩阵和空位罚分。粗糙的比对方法仅仅用相同或不同来描述两个残基的关系，显然这种方法无法描述残基取代对结构和功能的不同影响效果。空位罚分是为了补偿插入和缺失对序列相似性的影响。由于没有什么合适的理论模型能很好地描述空位问题，因此空位罚分缺乏理论依据而更多的带有主观色彩。一般的处理方法是用两个罚分值，一个对插入的第一个空位罚分，另一个对空位的延伸罚分。对于具体的比对问题，采用不同的罚分方法会取得不同的效果。由于序列相似性比对有上面的一些缺点，使得很多人试图寻找其它的方法来比较ＤＮＡ序列。所有这些算法有个共同的特点：算法是字符串比较算法，序列的比较是字生物信息学中的序列相似性比对算法符上的比较，它们的差异性体现在彼此间存在不同的子序列或子结构，而相似性体现在它们有共同的子序列或子结构，因此我们很自然的会想到寻找生物序列的最长公共子序列，这就是所谓的ＬＣＳ问题［１９—２５］。近两年国内外一些学者给出了ＤＮＡ序列的图形表示，用几何的方法比较生物序列，像Ｍ．Ｒａｎｄｉｃ，Ａ．Ｎａｎ＠，Ｂ．Ｌｉａｏ［４—１７］等给出了ＤＮＡ序列一些二维和三维图形表示，甚至更高维的表示。本节利用Ｂ．ＬｉａＯ［１６］等给出的一个二维表示来讨论ＤＮＡ序列的最长公共子序列问题。１．二维图形表示先置Ａ和Ｇ于＋ｘ轴，Ｔ和Ｃ于＋ｙ轴，曲线沿着ｙ轴仲展，具体地讲，令（１，０）斗Ａ，（１，０）一Ｇ，（Ｏ，１）一ｒ，（Ｏ，１）寸Ｃ设Ｇ＝ｇｌｇ：…ｇ，，为任意序列，构造映射≯（Ｇ）＝≯（ｇ。Ⅻ（ｇ：）…ｏ（ｇ。），对应于四种核苷酸Ａ，Ｃ，Ｇ，Ｔ的三种分类方法，存在三个映射≯，，Ｊ＝１，２，３将序列ｇ转化为不同点集，这里纪憎』户１ｉｏ，１）如果ｇ，∈｛ｃ．丁），、ｆｆｌ，０）如果ｇ，∈ｐ，Ｇ｝妒：憎户１ｉｏ，１）如瓢，∈｛Ｇ，Ｔ｝，、ｆ（１＇ｏ）如果ｇ。∈扣，Ｃ｝仍（ｇ』户１ｉｏ，１）如果ｇ，∈｛ｃ，Ｇ｝『（１，０）如果璺∈∽Ｔ｝映射≯。≯：丸分别对应于形式ＡＧ，Ａｃ和ＡＴ如序列ａ＝ＡＴＧＧＴＧＣＡＣＣ；ｂ＝ＧＣＡＡＣＡＴＧＴＴ；Ｃ＝ＣＧＴＴＧＴＡＣＡＡ；ｄ＝ＴＡＣＣＡＣＧＴＧＧ分别对应下面图１２几个定理定理ｌ：如果序列ａ和ｂ对应两条相同的折线，则ａ＝ｂ。证明：不妨设序列ｄ＝ａｉｄ：…ａ。，ｂ＝６。６：…ｂ．因为序列ａ和ｂ在三种形式下有某两条对应相同折线，则有，对任意ｄ，∈口，ｂ。ｅｂ都有≯，（口，）＝≯，（６，），Ｊ为ｌ，２，３中的某两个，故ｎ＝ｍ。下面证明：对任意的ｉ＝１，２，…，ｎ都有ｑ＝ｂ，。假设存在ｋ使得丸（ｄ。）＝≯，（钆），ｊ为１，２，３中的某两个，不妨设ｊ为１，２，但吼≠ｂ。，因为≯，（吼）＝丸（钆），则％和ｂ。在纯，仍中始终属于同一类的不同核苷酸，这显然矛盾。生物信息学中的序列相似性比对算法≮：＠：ｃ仪：Ⅸ‘ｆ叩’．…一…～＼ａ（ｂ）７ＡＧｙ‘×Ｘ＿Ｆ．．一。ｆ’．…－……，。｝ｒ∥叭“．＼＼ｂ（ｄ）图１：序列ａ，ｂ，Ｃ，ｄ对应的三条折线ＡＣｙ………＼ａ（ｄ）７ＡＴｙ推论：如果序列ａ和ｂ对应三条相同的折线，则ａ＝ｂ。定理２：对任意两序列ａ＝ｄｌａ２…ａｎ，ｂ＝ｂ，ｂ２…６卅中的任意两碱基ｑ∈口，ｂｊ∈ｂ，都存在映射≯∈溉，≯：，丸｝使得≯（ｑ）＝≯（６，）＋（ｏ，ｉ一＿，），即口。－－与ｂｊ对应相同的横坐标。证明：（１）如果口，＝ｂ，，显然有丸（口，）＝丸（ｂｊ）＋（Ｏ，ｉ－ｊ），ｋ＝ｌ，２，３ａ命题得证。（２）如果ａ，≠ｂ．，在核苷酸的三种分类中，它必然某种分类中属于同一类，不妨设口，和６，，都属于强键，则有丸（口。）＝九（６，）＋（Ｏ，ｉ一／），ｋ２ｌ，２，３。命题得证。通过上述两个定理一个推论我们可以得出这样的结论：对任意两序列ａ和ｂ，要么它们对应三条相同的折线，要么在某一个形式下它们有最长的公共的相同的子折线。而子折线对应子序列，下面我就给出算法寻找最长公共子序列。３算法第一步：赋初值：输入序列ａ和ｂ，并在同一坐标下绘制序列ａ和ｂ对应的曲线：令最长公共子折线，。＝ｏ。生物信息学中的序列相似性比对算法第二步：找最长公共子折线：沿着Ｙ轴方向移动ｂ曲线，使得ａ曲线和ｂ曲线在三种形式下有最长公共部分（即重合部分），不妨设此公共部分为，，它分别对应于序列ａ和ｂ中的子序列。·‘‘ｏ一和也…ｎ，设ｋ为ｂ曲线移动的单位数（ｋ为负表示沿ｙ轴负方向移动，反之则为沿ｙ轴正方向移动），则有ｉ＝Ｓ＋￡，Ｊ２ｆ＋ｋ。，＋：＝ｒｕｌ。（注意连接子序列，时按着其在原序列中出现的下标顺序依次连接）第三步：口·‘：＝ＣＩＩＧ２…ｄ“，ｂ·‘：＝ｂＬｂ：…ｂ“，如果括≠ｌ转第二步，否则转第四步。第四步：口；：＝Ｅｌｊ＋Ｉ…“”６ｊ：＝ｂｗ…ｂｗ，如果／＜＂一１且，＜珊一１转第二步，否则转第五步。第五步：输出ｒ。第六步：结束。４算法实例：假设序列“＝ＡＡＣＧＡＴＧＧＣＡＣＣＴ，ｂ＝ＧＡＣＧＴＧＣＡＣ，计算ＬＣＳ（ａ，６）方法：第一｛多，，２≯，绘制序列“和ｂ的图（见下图２）弋母Ｉ锅以一一。ＡＧｙ■＼八／’－－您．●…－…ｒ歹＼／气Ｖ：、、入／．＿一－…＿＿－ＡＣｙＡＴｙ图２：序列口＝州Ｃ侧粥Ｇ翻ＣＣＴ和ｂ＝例ＣＧｍ例Ｃ对应的三条曲线图中实线对应序列ａ，虚线对应序列ｂ，粗实线对应咖重合生物信息学中的序列相似性比对算法第二步：ｂ曲线移动零步得两曲线的最长公共子曲线，（见图３），其对应的序列为ＡＣＧ，即ｆ－ＡＣＧ，则ｒ＝ＡＣＧＸＡＧＶＡＣＶＶ图３：公共曲线第三步：ｄ？：＝爿，６ｊ．＿Ｇ，其没有公共，．ⅢｌＪｌ’＝ＡＣＧ。第四步：ａ：：＝ＡＴＧＧＣＡＣＣＴ，ｂ：：＝ＴＧＣＡＣ，对应曲线见图４。ＸＡＧＶＡＣｙ生物信息学中的序列相似性比对算法趴／，、、、入／ＡＴｙ图４：序列ａ：＝ＴＧＧＣＡＣＣ７１和ｂ：＝ＴＧＣＡＣ对应的三条曲线：圈中实线对应序列ａ，虚线对应序列ｂ，粗线对应ａ，ｂ重合曲线ｂ沿Ｙ轴移动２个单位得最长公共曲线为，＝ＣＡＣ，则，ｌ＝ＡＣＧＣＡＣ。第五步：置。：＝ＴＧＧ，６；＝ＴＧ，同样可得其最长公共曲线为ｆ＝粥，则，’＝ＡＣＧＴＧＣＡＣ第六步：置口；＝ｃ７１，ｂ：＝≯，无公共曲线，则ｆ．＝ＡＣＧＴＧＣＡＣ。第七步：置。；＝Ｇ，Ｅ＝≯，无公共曲线，则ｆ．＝ＡＣＧＴＧＣＡＣ。第八步：输出，４＝ＡＣＧＴＧＣＡＣ。第九步：结束。寻找生物大分子序列的最长公共子序列的简单有效算法题一直是生物学家关心的问题，通常做法都是采用动态规划等方法。算法复杂计算量大［１９－２４】。本文给出的这种基于图形表示的寻找最长公共子序列的算法，该算法简单并可可视化。很适合用于生物序列的比较和分析。３ｍＲＮＡ序列与蛋白序列的对比算法序列比对的基本问题是比较两个或两个以上符号序列的相似性或不相似性。早期的序列比对是全局的序列比对，但由于蛋白质具有模块性质，可能由于外显子的交换而产生新蛋白质，因此局部比对会更加合理。通常用打分矩阵描述序列两两比对，两条序列分别作为矩阵的两维，矩阵点是两维上对应两个残基的相似性分数，分数越高则说明两个残基越相似。因此，序列比对问题变成在矩阵里寻找最佳对比路径。具体地讲，对两个ＤＮＡ序列ｗ，和ｗ２，求出它们的扩张序列，使得它们的扩张序列的罚分Ｄ（ｗ。’，Ｗ：’）为最小。序列比对算法是一个动态规划算法，最早是Ｎｅｅｄｌｅｍａｎ．Ｗｕｎｓｃｈ动态规划算法，在此基础上又改良产生了Ｓｍｉｔｈ．Ｗａｔｅｒｍａｎ算法和ＳＩＭ算法。自后又有许多算法被提出，所有这些算法有一个共同的特点：算法只限于ＤＮＡ序列与ＤＮＡ序列，ＲＮＡ序列与ＲＮＡ序列，ＲＮＡ序列与ＤＮＡ序列，蛋白序列与蛋白序列之间的组成单元生物信息学中的序列相似性比对算法的一对一的比较（即核苷酸与核苷酸或氨基酸与氨基酸之间的一一对应）。而一个氨基酸对应一个三联体密码子，所以ｍＲＮＡ序列与蛋白序列之间的对比是３个核苷酸对应一个氨基酸，要解决这个问题就需要改进算法。本章利用动态规划算法寻求ｍＲａＮＡ序列与蛋白序列的最优局部对比和全局对比，该算法有助于破译遗传密码ｆ３１。３．１预备知识１９５３年当Ｗａｔｓｏｎ和Ｃｒｉｃｋ提出ＤＮＡ双螺旋结构后，科学家开始研究一个线性的ＤＮＡ分子或双螺旋ＤＮＡ分子怎样给线性蛋白分子编码问题。揭开遗传密码成为热门话题，当前生物学家所面临的最大挑战就是破译人体密码。遗传密码可由单链ＲＮＡ读出，并且从５’读到３’。密码是三联体密码：不相重迭的相继的３个字母组可被翻译成氨基酸。有确定的开始点或读框。表３．１给出了遗传密码的简并形式。有３个三联体密码子使蛋白转录停止。它们是ＵＡＡ，ＵＡＧ和ＵＯＡ。抽象地看，遗传密码是一种语言，在４个基Ｕ尿嘌呤，Ｃ胞密腚，Ａ腺嘌呤和Ｇ鸟嘌呤中，每次取３个的所有６４种组合。它们或确定一种氨基酸或终止蛋白序列。有６４种可能的词和２１个可能的意义（这２１种意义是２０种氨基酸加上终止或停止码）。显然，有可能不同的密码子给同一种氨基酸编码。事实上，有几个密码子给一种同一种氨基酸编码，而它们的区别仅在第三个基上。另一方面，第一个或第二个基不同的两个密码子通常给不同的氨基酸编码。翻译成蛋白的ＲＮＡ称为信使ＲＮＡ，ｍＲＮＡ。ⅡＩＲＮＡＵＩＦＪＵＡｃＵＧＣＧＢＣＣ蛋白ＰｈｅＴｙｒＣｙｓＧｌｙ如果向右移一个字母，读过同样核酸序列，会产生完全不同的氨基酸序列。】ＩＩＩ讯ＡＵ唧ＡＣＵＧＣＧ６ＣＣ蛋白阅读密码子的相位称为蛋白读框，从５’到３’有３个读框，阅读相补的ＤＮＡ链也有３个反方向读框。对于双链ＤＮＡ总计有６个可能的读框。遗传密码是用一种非常有趣的方法解决的。除ＲＮＡ模板，ｍＲＮＡ外，准备好细菌提取物。当实验者加入合成ｍＲＮＡ后，这些提取物将生成蛋白序列。开始加ＵＵＵＵｕ…．，则合成的蛋白是苯丙氨酸组成的ｐｈｅ．ｐｈｅ．。因为，这时读框无关紧要，这意味着ＵＵＵ为ｐｈｅ的密码。其次，试用像ＵＧＵＵＵＧ…的ｍＲＮＡ，结果是Ｃｙｓ或Ｖａｌ生成的多肽。这样我们不能确定唯一的密码子，所以再试ＵＵＧＵＵＧ…，结果是由Ｌｅｕ，Ｃｙｓ和Ｖａｌ组成的多肽。即使ＵＧＵ，ＧＵＧｆ１ＵＧＵ，ＧＧＵ，ＧＵＧ＝ＧＵＧ也生物信息学中的序列相似性比对算法不能确定一种密码予。再试ＵＧＧＵＧＧ。这时多肽包含Ｔｒｐ，Ｇｌｙｔ和Ｖａ］。这时公共密码子是所以，我们指定ＧＵＧ为这公共的氨基酸Ｖａｌ的密码。多数氨基酸密码子是用这种方法破译的。设Ｎ＝｛Ａ，Ｃ，Ｇ，Ｕ｝是核酸集合，ｃ＝｛（ｘ．Ｘ冰。）：ｘ．∈Ｎ｝，Ｑ是氨基酸和停止密码子的集合，遗传码就是一种映射。ｆｆ’：Ｃ一０不过这种方法需要给定模板和细菌提取物，对任意ｍＲＮＡ和蛋白序列我们就无法判断两者之间的关系，本节将给出局部对比算法和全局对比算法判断ｍＲＮＡ序列和蛋白序列的相似性。３．２局部对比算法已经发现在两个相似性很小的序列之间也有可能有一些片段具有很大的相似性。例如，在某些病毒与它们的宿主ＤＮＡ之间就确定了一些长的匹配片段。这一小节的主题寻找这些相似片段的算法，称为局部对比算法［２，３］。本文这一节给出ｍ［？ＮＡ序列与蛋白质序列进行局部对比的动态规划算法。图３．１是局部对比的示意图。蛋白质ｂ图３．１图示局部对比Ｆｉｇｕｒｅ３．１１０ｃａｌａｌｉｇｎｍｅｎｔ为了给出这个问题的数学描述，必须假设一个相似函数ｓ（ａ，ｂ）。目标是求Ｈ（ａ，６）＝ｍａｘ｛Ｓ（ａ．口…．．ａｊ．Ｉ臼Ｊ，ｂｋｂｋ＋１．．．６¨ｂ１）：１≤ｉ≤／≤盯，１≤ｋ≤，≤埘｝此处Ｈ（ｏ，ｏ）＝Ｏ。设口＝口】日２．．．口∥ａ，∈｛爿，ＣＧ，删，１≤ｉ≤胛ｂ＝ｂＬｂ２．．．ｂ。ｂ，∈ＩＡ，Ｒ．Ｄ，Ｎ，ＣＥ，Ｑ，Ｇ．Ｈ，ＬＬ．Ｋ，Ｍ．Ｆ．Ｐ．Ｓ．Ｔ，ｗ，Ｙ，ｙｊ，１ｓｊｓｍ假设从ａ中删除ｋ个字母的成本函数为匹＝口．＋∥．（七一１），从ｂ中删除ｋ个字母的成本函数为Ｊ：＝口：＋∥：（≈一１），显然从口中删除一个字母的成本为口。，从６中删除一个字母的成本为晓：，由于口中三联体ｘｙｚ对应６中一字母，不妨设对比打分为生物信息学中的序列相似性比对算法６‰。１２口ｍ６，户１。。，：、ｆｓ（ｇ（ａ∥一ｆ３），ｂｊ）其中ｇ代表ｄ，。口，：日。对应的遗传密码１ｉ，一ｉ，Ｉ＜２定义Ｈ，．ｊ是在Ⅱ，，ｂ，处结束的两个片断的最大相似性定理１设Ｈ柚＝ＨＯＪ＝０，１≤ｉ≤玎，１≤，≤埘，则，Ｈ，，，＝ｍａｘ｛Ｏ，Ｈ，．Ｊ—Ｉ一占２，ＨＨ．，一４，Ｈ．３．，一Ｉ＋ｓ（ｇ（ａｉ＿２口Ｈ口，），ｂ』），Ｈ’ｕ｝其中Ｈ’ｗ＝Ｈ，一４．Ｊ—Ｊ＋ｍａｘ｛ｓ（ｇ（ａ，一３口，一ｌ口，），ｂＪ），ｓ（ｇ（ａ．３日，一２口，一１），ｂｊ），Ｊ（ｇ（日，＿３口，一２ｄ，），ｂＪ）ｊ—Ｊ证明：令Ｅ。和Ｆ』，，满足Ｅ。＝ｍａｘ｛Ｈ。一。一口：，Ｅ。一．一∥：ｊ，Ｆ『，，＝ｍａｘ｛Ｈ，。．，一口。，Ｆ吐，一届ｊ显然Ｈ，．Ｊ＝ｍａｘ｛Ｈ』－３．Ｊ—Ｉ＋ｓ（ｇ（口ｔ－２ｃ／ｉ＿Ｉ口，），ｂＪ），Ｈ’ｕ，ＥＬＪ，Ｅ，／ｊ要证明上述恒等式，只需证明Ｅ。＝ｍａｘ｛Ｈ。一，一ａ＇２，Ｅ。一。一屈ｊ，Ｆ，，＝ｍａｘ｛Ｈ。，，一口。，ＦＪ吐，一层ｊ为了证明有关Ｅ。，Ｆ』，．的恒等式，我们建立等式Ｅ。ｍａｘ，；。；，｛Ｈ。一。一占：（ｋ）ｊ，Ｅ，，＝ｍａｘ。；。”。．，一占。（ｊ）ｊ我们将证明等式Ｅ。（Ｆ．，用类似方法证明）假设Ｅｉ，＝ｍａｘ。。厂｛Ｈ。。一艿：（七）｝，对ｏｓ＿，‘ｓ＿，则ｍａｘｌ“甜｛Ｈｕ—Ｉ—ｋ６２ｊ＝ｍａｘ｛ｍａｘ２１，ｋｇｊ｛Ｈｕ一女一占２（七）），Ｈｗ一，一口２ｊ＝ｍａｘ｛ｍａｘⅢ一。；．一。｛Ｈ“，枷一（。叫一占：（尼一１）一∥：｝，Ｈｕ一，一口：）＝ｍａｘ｛Ｅ。一，一∥：｝，Ｈ。一，一口：｝同理可证Ｆ』∥证毕。算法ｌｉｎｐｕｔ：ａ，ｂ１．Ｈ¨２０２．ｆｏｒｉ＝ｌｆｏｒｆｏｒｔｏｉ‘，２０ｒｌｊ＝１ｔｏｍＨ叫壬一ｍａｘ｛ｏ，Ｈ．．川－ｃｒ：，ＨＨ．，一ａ。，Ｈ一．川＋Ｊ（ｇ∞卜２ｄＨｑ），ｂ，），Ｈ。ｕｊ．其中，生塑笪星堂！塑壁型塑！些丝堕型墨鲨Ｈ，＝Ｈ。√．。＋ｍａｘ｛ｓ（ｇ（ａ，＿３ａｌ＿ｌａｉ），６Ａｓ（ｇ（ａ，＿３ａ，－２ａ，－ｉ），ｂＡｓ（ｇ（ａｉ＿３ａ，＿２ａ，），ｂ∥一占实例：设ａ＝ｕＵｕｕＡＣｕＧｃＧＧｃｃＡＣＵＧｃＧＧＣＣ，ｂ２ＦＹＣＧＦＴＡＡ，口１＝岱２＝１ｓ（ａ，］ａ，２ａ，３，ｂｊ）：ｊ２如果密码子Ｃ／ｉｌ日，：ａ。对应的氨基酸为６，否则比较序列ａ和ｂ，给出这个矩阵Ｈ。一ＵＶＶＶＡＣＵＧＣＧＧＣＣＡＣＵＧＣＧ６ＣＣ０Ｄ０００００００００００００００００００００一ＦＡｒ６ＣＧ０ｌ００ｏ００００ｄ］１０００００００００００００００００Ｉ口２１０Ｏ００００口０２００Ｏ０Ｊ０Ｄ０ｚ０ｌ口０００００００００ｏＪｏ口口Ｏ００ｚ０１０００００２１１０Ｏ０００口口１０００００２１０００００００２００００００１００００２ｌ１０Ｏ００１０００００２００ｉ００００００２０Ｉ０１０２１ｏ＾Ｔａ００Ｏ００００Ｏｏｏｏｏ００ｏ０２Ｄｌｏ２Ｉｌ００Ｏ０Ｆ００口０口０１３１３０口１３Ａ＾０ｎ０００００ｏ。ｏｏ２１ｏ２ｌｏｏ。ｏ。网ｔｏ圈！！１ｏｏ。ｏｏ０２｜１ｏｏｏｏ２１ｏ２０１１３０００Ｄ００Ｏ００００００２ｌ０２ｌ００００２儿Ｏ２最好的对比是ＵＵＵ——ＵＡＣ—。ＵＧＣＧＧＣＣ——ＡＣＵ——６ＣＧＧＣＣＦＡＹＧＣＧ—ＡＴＦＡＡ３．３全局对比算法下面，我们来考虑全局对比。取Ｓ（ｘ，ｂ’）是字符集上的相似性度量，即对所有ｘ（三联体）有Ｓ（ｘ，口’）＞０，对某些（ｘ，ｂ’）必定有Ｓ（ｘ，ｂ’）＜Ｏ，想法是相似（即日’与ａ７匹配）奖励正分，而将不相似的字母对比就罚以负分。图３．２是全局对比的示意图。假设从ｄ７中删除ｋ个字母的成本函数为岛＝％＋店（七一１），从ｂ’中删除ｋ个字母的成本函数为Ｊ。＝口。＋∥。（ｋ一１）生物信息学中的序列相似性比对算法删Ａ蛋白质ａｂ图３．２图示全局对比Ｆｉｇｕｒｅ３．２ｇｌｏｂａｌａｌｉｇｎｍｅｎｔ显然５ｋａ’中删除一个字母的成本为％，从ｂ’中删除一个字母的成本为盘。。设ａ’所能形成的密码集为中￡定义口’和６’的相似。Ｄ＿Ｎｓ（ａ’，ｂ’）＝ｍａｘ∑ｓ（ａ７，６ｊ）ｉ＝１ａｊ∈ｏ，此处，在所有对比上取最大值。定理２：如果口’＝ａＩａ２…口。，ｂ＝ｂｉｂ２…ｂ。，ｆ９３（ｓ。＝Ｊ（口ｌ口２…ｎ，，ｂｌｂ２…ｂｊ），又Ｊ邻叩。０，Ｓｏ√：荟㈣小＆。２∑ｗ。：彬，如（ａｌｌ口ｉ２ａｉ３），一）特另。地有：ｓ（ｇ（ａ，。订，：口。），ｂ，）＝一ｏｏ，Ｉ如一ｉ。｜＜２，贝ｏＳ。＝ｍａｘ｛Ｓ。一；一占。，，Ｓ，。，一５ｐ，Ｓ．，。，一。十ｓ（ｇ（日ｉ－２ａｉ－ｉｎ，），ｂ，），ｓｉ，ｊ其中墨，＝Ｓ，一４√一】＋ｍａｘ｛ｓ（ｇ（ａ．３日，．１口，），ｂＪ），ｓ（ｇ（ａ．一３ｄ．２ｄ，一Ｉ），ｂ』），Ｊ（ｇ（口．３口．２口，），ｂ』）ｊ一６ｂ证明：同定理ｌ。算法２ｉｎｐｕｔ：ａ，ｂ１。ｓ００却一¨２善５（一＾），Ｓｉ，ｏ２∑ｗ。：彬，ｓ（ｇ（ａｉｌｃｌｉ２ａｉ３），一）２．ｆｏｒｉ＝ｌｆｏｒｔｏｎｊ＝１ｔｏｍＳｕ卜ｍａｘ（Ｓｕ一】一口４，ＳＪ＿ｌ、』一ａ３，ＳＩ一¨一ｌ＋Ｊ（ｇ（口卜２口卜ｌ口，），ｂ』），ｓｉ』ｊ其中ｓｉ，＝ｓ．。，，一．＋ｍａｘ｛ｓ（ｇ（ａ．，口，。ａ，），ｂ』），ｓ（ｇ（ａ．。口，：口，一．），ｂ，），ｓ（ｇ（ａ．，口，：口，），ｂ，）｝一ｃｚ，计算Ｈ。，Ｓ。，用Ｏ（ｎ，Ⅲ）时间。生物信息学中的序列相似性比对算法生物序列的对比是计算分子生物学中的经典问题，目前已有许多算法对ＤＮＡ序列或蛋白序列之间进行对比［１９—２５］。本文利用动态规划算法给出了ｍＲＮＡ序列与蛋白序列之间的局部对比和全局对比算法，并举ｆｆ＇ＪＤＨ以说明，该算法解决了三个核苷酸与一个氨基酸之间的对比问题，该算法有助于破译氨基酸密码子。４结论与展望经典的生物序列的相似性分析是通过生物序列的比较来实现的，而序列的比较是通过将两个或多个核酸序列或蛋白质序列进行比对。通过比对未知序列与已知序列（尤其是功能和结构已知的序列）之间的相似性得到它们的同源性来预测未知序列的功能。从文中看出，目前序列比较的主要方法是：双序列相似性比对算法，多序列比对算法，基于知识发现的比对算法和基于图形表示的比对算法等。前两者是用动态规划的思想，有成熟的算法和软件来实现，但计算量是相当的复杂。而基于知识发现的方法也尚未成熟。由于生物序列图形表示的数值刻划方法是近几年刚发展起来。从文中可以看出我们给出的基于生物序列图形表示的序列分析方法计算相对比较简单，随着生物序列图形表示和相关理论的不段完善，基于图形表示的比对算法有很大的发展空间。所以，我们要做的工作是完善我们提出的生物序列比对算法，开发基于图形表示的生物序列（ＤＮＡ，ＲＮＡ，蛋白质）分析软件，并用这种思想研究寻找新基因和预测其功能的相关算法并开发具有相应的软件。众所周知，作为计算机科学和数学应用于分子生物学而形成的交叉学科，生物信息学已经成为基因组研究中必不可少的有力研究手段。我们期望能够用新的分析软件对生物的基因组进行大规模的分析并挖掘生物序列中有用的信息。用我们的方法寻找可能有研究价值的新基因，并用实验方法来研究证实。期望自己能在生物信息学方面发挥自己的一点作用。生物信息学中的序列相似性比对算法参考文献［１］［２］［３３ＴａｏＪｉａｎｇ等著，计算分子生物学前沿课题：（英文版］，清华大学出版社，２００２。朱浩（等译），计算分子生物学导论，科学出版社，２００３．Ｍ．Ｓ．Ｗａｔｅｒｍａｎ，ＩｎｔｒｏｄｕｃｔｉｏｎＣｈａｐｍａｎ＆Ｈａｌｌ，Ｌｏｎｄｏｎ，１９９５ｔｏＣｏｍｐｕｔａｔｉｏｎａｌＢｉｏｌｏｇｙ：Ｍａｐｓ，ＳｅｑｕｅｎｃｅｓａｎｄＧｅｎｏｍｅｓ［４］Ｅ．Ｈａｍｏｒｉ，Ｊ．Ｒｕｓｋｉｎ，ｓｅｒｉｅｓＨｃｕｒｖｅｓ，ａｎｏｖｅｌｍｅｔｈｏｄｏｆｒｅｐｒｅｓｅｎｔａｔｉｏｎｏｆｎｕｅｌｅｏｔｉｄｅｌｏｎｇＤＮＡｅｓｐｅｃｉａｌｌｙｓｕｉｔｅｄｆｏｒｓｅｑｕｅｎｃｅｓ，Ｊ．Ｂｉ０１．Ｃｈｅｍ，２５８（１９８３）１３１８—１３２７［５］ＭｉｌａｎＲａｎｄｉｃ，ＭａｊａｎＤＮＡＶｒａｃｋｏ，ＮｅｌｌａａｎｄＬｅｒｓ，ＤｅｊａｎＰｌａｖｓｉｃ，Ｎｏｖｅｌ２－ＤｇｒａｐｈｉｃａｌｒｅｐｒｅｓｅｎｔａｔｉｏｎｏｆＰｈｙｓｉｃｓｓｅｑｕｅｎｃｅｓｔｈｅｉｒｎｕｍｂｅｒｉｃａｌｃｈａｒａｃｔｅｒｉｚａｔｉｏｎ，ＣｈｅｍｉｃａｌＬｅＲｅｒｓ．３６８（２００３），１—６３－ＤｇｒａｐｈｉｃａｌｒｅｐｒｅｓｅｎｔａｔｉｏｎｏｆＤＮＡ［６］Ｍ．Ｒａｎｄｉｅ，Ｍ．Ｖｒａｃｋｏ，Ａ．Ｎａｎｄｙ，Ｓ．Ｃ．Ｂａｓａｋ，Ｏｎｐｒｉｍａｒｙｓｅｑｕｅｎｃｅａｎｄｔｈｅｉｒｎｕｍｅｒｉｃａｌｃｈａｒａｃｔｅｒｉｚａｔｉｏｎ，Ｊ．Ｃｈｅｍｌｎｆ．Ｃｏｍｐｕｔ．Ｓｃｉ，４０（２０００），１２３５．１２４４．ｎｅｗｇｒａｐｈｉｃａｌａｎｄａｎａｌｙｓｉｓｏｆＤＮＡｓｅｑｕｅｎｃｅｓｔｒｕｃｔｕｒｅ：Ｉ１４［７］Ａ．Ｎａｎｄｙ＇ＡｒｅｐｒｅｓｅｎｔａｔｉｏｎｔｏＭｅｔｈｏｄｏｌｏｇｙａｎｄＡｐｐｌｉｃａｔｉｏｎＧｌｏｂｉｎＧｅｎｅｓ，Ｃｕｒｒ．Ｓｃｉ，６６（１９９４），３０９－３ｏｆＤＮＡｓｅｑｕｅｎｃｅｓ［８］Ａ．Ｎａｎｄｙ，Ｐ．Ｎａｎ＠，Ｇｒａｐｈｉｃａｌａｎａｌｙｓｉｓｓｔｒｕｃｔｕｒｅ：ＩＩ．ＲｅｌａｔｉｖｅａｂｕｎｄａｎｃｅｏｆｕｕｃｌｅｏｔｉｄｅｓｉｎＤＮＡｓ，ｇｅｎｅｅｖｏｌｕｔｉｏｎａｎｄｄｕｐｌｉｃａｔｉｏｎ，Ｃｕｒｌ＇，Ｓｃｉ，６８（１９９５），［９］Ａ．Ｎａｎｄｙ，ＧｒａｐｈｉｃａｌａｎａｌｙｓｉＳｏｆＤＮＡｓｅｑｕｅｎｃｅＳｔｒｕｃｔｕｒｅ：ＩＩＩ．Ｉｎｄｉｃａｔｉｏｎｏｆｅｘｏｎｓ。ｅｖｏｌｕｔｉｏｎａｒｙｄｉｓｔｉｎｃｔｉｏｎｓａｎｄｃｈａｒａｃｔｅｒｉｓｔｉｃｓｏｆｉｎｔｒｏｎｓａｎｄＳｃｉＣｕｒｒ７０（１９９６），Ｒａｎｄｉｃ，６６１—６６８．ＯｎｔｈｅｃｈａｒａｃｔｅｒｉｚａｔｉｏｎｏｆＤＮＡＰｒｉｍａｒｙ［１０］Ｍ．ｘ．Ｆ．Ｇｕｏ，Ｓ．ｃ．Ｂａｓａｋ，Ｓｚｑｕｃｎｃｚ：ｉ；！：：＾：ｉｊ！：＝：＝，Ｊ．＝．Ｉｎｆ．！：！＝！！．！！ｉ４１（２００１），６１９—６２６［ｉＩ］［１２］Ｍ．Ａ．Ｇａｔｅｓ，ＡｓｉｍｐｌｅｗａｙｔｏｌｏｏｋａｔＤＮＡ，Ｊ．Ｔｈｅｏｒ．Ｂｉ０１．，１１９（１９８６），３１９—３２８Ｐ．Ｍ．Ｌｅｏｎｇ，Ｓ．Ｍｏｒｇｅｎｔｈａｌｅｒ，ＲａｎｄｏｍｗａｌｋａｎｄｇａｐｐｌｏｔｓｏｆＤＮＡｓｅｑｕｅｎｃｅｓＣｏｍｐｕｔ．Ａｐｐｌｉｃ．Ｂｉｏｓｃｉ．，１２（１９９５），５０３—５１１［１３］Ｍ．Ｒａｎｄｉｃ，Ｍ．Ｖｒａｃｋｏ，ＭＮｏｖｉｃ，ｉｎ：Ｍ．Ｖ．Ｄｉｕｄｅａ（Ｅｄ．），ＱＳＰＲ／ＱＳＡＲＳｔｕｄｉｅｓｂｙ生物信息学中的序列相似性比对算法ＭｏｌｅｃｕｌａｒＤｅｓｃｒｉｐｔｏｒｓ，ＮｏｖａＳｃｉｅｎｃｅ，Ｈｕｎｔｉｎｇｔｏｎ，ＮＹ，２００１，Ｐ，１４５．Ｗａｎｇ，Ｃｈａｒａｃｔｅｒｉｓｔｉｃｓｅｑｕｅｎｃｅｓ［１４］Ｐｉｎｇ—ａｎＩｔｅ，ＪｕｎｆｏｒＤＮＡｐｒｉｍａｒｙｓｅｑｕｅｎｃｅ，Ｊ．Ｃｈｅｍ．ＩｎｆＣｏｍｐｕｔ．Ｓｃｉ，４２（２００２），１０８０—１０８５．［１５］ＭＲａｎｄｉ，ｂｔ．Ｖｒａｃｋｏ，ＮｅＩｌａＬｅｒｓ，Ｄｅｊａｎｐｌａｖｓｃ，ＡｎａｌｙｓｉｏｎｓｏｆｓｉｍｉｌａｒｉｔｙＤｉｓｓｉｍｉｌａｒｉｔｙｏｆＤＮＡｓｅｑｕｅｎｃｅｓｂａｓｅｄＣｈｅｍｉｃａｌＰｈｙｓｉｃｓｎｏｖｅｌ２－Ｄｇｒａｐｈｉｃａｌｒｅｐｒｅｓｅｎｔａｔｉｏｎ，Ｌｅｔｔｅｒｓ，３７ｌ（２００３），２０２—２０７．ｒｅｐｒｅｓｅｎｔａｔｉｏｎｏｆＤＮＡｓｅｑｕｅｎｃｅｓ，［１６］ＢｏＬｉａｏ，ＷｉａｎｍｉｎｇＷａｎｇ，Ｎｅｗ２ＤＧｒａｐｈｉｃａｌＪｏｕｒｎａｌｃｏｍｐｕｔａｔｉｏｎａｌｃｈｅｍｉｓｔｒｙ２５（１１），２００４．１３６４—１３６８［１７］ＣｈｕｎｘｉｎＹｕａｎ，ＢｏＩ．ｉａｏ，，ｒｉａｎｍｉｎｇＷａｎｇ，Ｎｅｗ３－Ｄｇｒａｐｈｉｃａｌ１‘ｅｐｒｅｓｅｎｔａｔｉｏｎｏｆＤＮＡｓｅｑｕｅｎｃｅｓａｎｄｔｈｅｉｒｎｕｍｅｒｉｃａｌｃｈａｒａｃｔｅｒ’ｉｚａｔｉｏｎ，ＣｈｅｍｉｃａｌＰｈｙｓｉｃＬｅｔｔｅｒｓ，３７９（２００３）４１２－４１７［１８］ＢｏＬｌａＤ，ＴｉａｎｍｉｎｇＷａｎｇ，ＡｎａｌｙｓｉｓｏｆｓｉｍｉｌａｒｉｔｙｏｆＤＮＡｓｅｑｕｅｎｃｅｓｂａｓｅｄｐｈｙｓｉｃｓｏａ３Ｄｇｒａｐｈｉｃａｌｒｅｐｒｅｓｅｎｔａｔｉｏｎ，Ｃｈｅｍｉｃａｌｌｅｔｔｅｒｓ，３８８（２００４），１９５—２００ｃｏｍｍｏｎ［１９］ＪＴ．Ｌ¨ＷａｎｇａｎｄＫ．ＺｂａｓｅｄｏｎａＺｈａｎｇ，ＩｄｅｎｔｉｆｙｉｎｇａｐｐｒｏｘｉｍａｔｅｌＹｒｅｓｔｒｉｃｔｅｄｅｄｉｔｄｉｓｕｂｓｔｒｕｃｔｕｒｅｓｉｎｔｒｅｅｓＬａｎｃｅ．知ｔｂｔＷａｔｉｏｎＳｃｉ．２０００．１２６，１６５—１８９［２０］ＤＡｎｇｌｕｉｎ，Ｆｉｎｄｉｎｇｐａｔｔｅｒｎｓｃｏｍｍｏｎａｓｅｔｏｆｓｔｒｉｎｇｓ，，Ｃｏｍｐｕｔ．ＳＨ‘吧Ｓｃｉ１９８０，２１，４６—６２［２１］Ｗ．Ｊ．Ｍａｓｅｋ，ＡＦａｓｔｅｒＡｌｇｏｒｉｔｈｍＣｏｍｐｕｔｉｎｇｓｔｒｉｎｇＥｄｉｔＤｉｓｔａｎｃｅｓ，，ＣＯＩｚｚｐｕｔ．ＳｙｓｔｅｍＳｃｉ．１９８０．２０，１８—３１．［２２］ＶＣｈｒａｔａｌａｎｄＤ．Ｓａｎｋｏｆｆ，ＬｏｎｇｅｓｔＣｏｍｍｏｎｓｕｂｓｅｑｕｅｎｃｅｓｏｆｔｗｏｒａｎｄｏｍｓｅｑｕｅｎｃｅｓ，Ｊ．Ａｐｐ］．Ｐｒｏｂａｈ．１９７５．Ｚ２，３０６—３１５．［２３］Ｄ．Ｓ１１ｉｒｓｃｈｂｅｒｇ，Ａｌｉｎｅａｒｓｐａｃｅａｌｇｏｒｉｔｈｍｆｏｒｃｏｍｐｕｔｉｎｇｍａｘｉｍａｌｃｏｍｍｏｎｓｕｂｓｅｑｕｅｎｃｅｓ，Ｃｏｍｍｕｎ．Ａｇｇ／８，３４ｌ一３４３．［２４］Ｈｕａｎｇ，ｘ．ａｎｄｍａｐＷａｔｅｒｍａｎ，ＭＳ．ＤｙｎａｍｉｃＰｒｏｇｒａｍｍｉｎｓａｌｇｏｒｉｔｈｍｆｏｒｒｅｓｔｒｉｃｔｉｏｎｃｏｍｐａｒｉｓｏｎＣｏｍｐ．Ａｐｐｔ．Ｂｉ０１．Ｓｃｉ，８（１９９２），５１１—５２０ｅｆｆｉｃｌｅｎｔｍｅｔｈｏｄｆｏｒｆｉｎｄｉｎｇｒｅｐｅａｔｓｉｎｍｏｌｅｃｕｌａｒｓｅｑｕｅｎｃｅｓ［２５］Ｙａｒｔｉｎｅｚ．Ｈ．Ｍ，ＡｎＮｕｃｌｅｉｃＡｃｉｄｓＲｅｓ，１ｌ（１９８３），４６２９—４６３４生物信息学中的序列相似性比对算法致谢本研究是在导师魏志强教授、赵东旭高级工程师的悉心指导和关怀下完成的。二年来，两位老师广博的知识面、敏锐的观察力、忘我工作的精神和平易近人的风格深深的影响着我，并使我终生受益。在此，谨向两位老师表示最崇高的敬意和最真挚的感谢。感谢中国海洋大学和威海职业学院给了我再次学习的机会，感谢威海职业学院曲桂东主任给我们提供了良好的学习条件，感谢时秀波老师三年来入学前后在学习上为我提供了许多的方便，感谢威海班同学对我的鼓励和支持。同时感谢我的家人和朋友在学学习期间对我的支持和帮助支持。最后，—本次感谢我的两位导师魏志强教授和赵东旭高级工程师，没有他们就没有我今天的成绩，谢谢！陈伟２００６年４月５发表论文情况在山东大学学报、数学的实践与认识，ＲｏｃｋｙＭｏｕｎｔａｉｎ等国内外刊物上先后发表学术论文１０余篇：ＲｏｃｋｙＭｏｕｎｔａｉｎＪｏｕｒｎａｌｏｆＭａｔｈｅｍａｔｉｃｓＪｏｕｒｎａｌｏｆＭａｔｈｅｍａｔｉＣＳ，１．ｑ－ＴｒｉｐｌｉｃａｔｅＩｎｖｅｒｓｅＳｅｒｉｅｓＲｅｌａｔｉｏｎｓｗｉｔＩｌＡｐｐｌｉｃａｔｉｏｎｓｔｏｑ－ｓｅｒｉｅｓ３５（４）（２００５）１４０７．１４２７（ＳＣＩ收录）２．Ｆ．Ｈ．Ｊａｃｋｓｏｎ超几何级数公式的推广３．一个新的反演公式４．带参数１的Ｂａｉｌｅｙ引理５．几个基本超几何级数公式６．关于“ＯＭ（Ｉ，１）模型的适用范围“一文的～个注记７．两个ｑ—级数恒等式８．图的最长路与最长圈９．基于图形表示的ＬＣＳ问题１．参编教材２本；２．承担山东大学科研项目１项；３．山东大学威海分校科研项目２项生物信息学中的序列相似性比对算法
作者：
学位授予单位：
陈伟
中国海洋大学
1.TaoJiang 计算分子生物学前沿课题 20022.朱浩 计算分子生物学导论 2003
3.M S Waterman Introduction to Computational Biology:Maps,Sequences and Genomes 1995
4.E Hamori.J Ruskin H curves a novel method of representation of nucleotide series especially suitedfor long DNA sequences 1983
5.Milan Randic.Majan Vracko.Nella Lers.Dejan Plavsic Novel 2-D graphical representation of DNAsequences and their numberical characterization 2003
6.M Randic.M Vracko.A Nandy.S.C.Basak On 3-D graphical representation of DNA primary sequence andtheir numerical characterization 2000
7.A Nandy A new graphical representation and analysis of DNA sequence structure:I.Methodology andApplication to Globin Genes 1994
8.A Nandy.P Nandy Graphical analysis of DNA sequences structure:Ⅱ.Relative abundance of nucleotidesin DNAs,gene evolution and duplication 1995
9.A Nandy Graphical analysis of DNA sequence structure:Ⅲ.Indication of evolutionary distinctions andcharacteristics of introns and exons 1996
10.M Randic.X F Guo.S C Basak On the Characterizat ion of DNA Primary Sequence by Triplet of NucleicAcid Bases 2001
11.M A Gates A simple way to look at DNA 1986
12.P M Leong.S Morgenthaler Random walk and gap plots of DNA sequences 1995
13.M Randic.M Vracko.M Novic.M.V.Diudea QSPR/QSAR Studies byMolecular Descriptors 200114.Ping-an He.Jun Wang Characteristic sequences for DNA primary sequence 2002
15.M Randi.M Vracko.Nella Lets Dejanplavsc,Analysis of similarity Dissimilarity of DNAsequences basedon novel 2-D graphical representation 2003
16.Bo Liao.Tianming Wang New 2D Graphical representation of DNA sequences 2004(11)
17.Chunxin Yuan.Bo Liao.Tianming Wang New 3-D graphical representation of DNA sequences and theirnumerical characterization 2003
18.Bo Liao.Tianming Wang Analysis of similarity of DNA sequences based on 3D graphical representation2004
19.J T L Wang.K Z Zhang Identifying approximately common substructures in tree based on a restrictededit distance 2000
20.D Angluin Finding patterns common a set of strings 1980
21.W J Masek.h Faster Algorithm Computing string Edit Distances 1980
22.V Chratal.D Sankoff Longest Common subsequences of two random sequences 1975
23.D S Hirschberg h linear space algorithm for computing maximal common subsequences24.Huang X.Waterman M S Dynamic Programming algorithm for restriction map comparison 199225.Martinez H M An efficient method for finding repeats in molecular sequences 1983
1.学位论文 何华 DNA序列比对最大似然度进化模型 2008
序列比对是生物信息学中重要的研究课题，是发现序列的功能，结构和进化信息的重要手段。现有的很多比对算法都是基于目标函数，目标函数利用替换矩阵和空位罚分对比对过程和结果进行记分，用记分值来判断序列比对结果的好坏。基于目标函数的比对算法的缺点是记分系统的些许变动就可能导致局部或全局比对剧烈变化。由此，本文提出了DNA序列最大似然度比对算法来对DNA序列进行序列比对。
本文首先介绍序列比对的基本概念，详细叙述了替换矩阵、空位罚分和目标函数以及它们对序列比对的影响，然后深入研究了双序列各种常用的比对算法：点阵分析、动态规划算法和词或k-串方法，并给出了它们的算法思想或伪代码。接着，根据基于目标函数算法的缺点，提出最大似然度比对算法，该算法分为两个部分：参数估值算法和比对算法。最大似然度比对算法首先使用进化参数估值算法对一对DNA序列相关的进化参数进行估值，然后比对算法利用估算出来的参数值对DNA序列进行比对。它是一个的方法，完全避开了基于替换矩阵和空位罚分的序列比对算法由于DNA序列相似度的不同而要选择与之相适应的替换矩阵的问题。最后，通过对进化模型最大似然度DNA比对算法的序列比对结果和FASTA比对程序结果进行比较，验证了进化模型最大似然度DNA比对算法的正确性和精确性。
2.学位论文 段敏 生物DNA序列比对算法研究 2005
两个或者更多DNA序列之间的比对分析是目前生物信息学关注的热点问题之一。序列比对分析是一个数据挖掘的过程,本文结合实际应用的需要,对序列比对算法进行研究,对序列比对算法中的数据挖掘技术进行探讨。基于典型序列比对算法,本文采用一种局部优化的多序列比对算法,不同程度减少序列比对过程中罚分,从而提高比对总评分,一定程度提高序列比对敏感性,达到优化序列比对算法的目的,并用VisualC＃开发语言开发了一个DNA序列分析原型系统。
3.期刊论文 谢少荣.王东红.罗均.龚振邦.XIE Shao-rong.WANG Dong-hong.LUO Jun.GONG Zhen-bang 基于生物信息科学中双DNA序列比对算法的图像立体匹配及其实现 -光学精密工程2007,15(1)
提出了一种基于生物信息学中双DNA序列比对算法的图像立体匹配新方法.图像立体匹配和生物信息学中双DNA序列比对的实质都是在匹配准则下搜索最佳匹配基元,因而新颖地将双序列比对算法引入图像立体匹配.首先介绍了基于动态规划的双序列比对算法原理及其用于图像立体匹配的实现方法,然后根据左右摄像机的最大视差是一个有限定值,进行了算法改进,极大地减少了计算量,并给出了VC6.0中的实现流程,最后采用4组不同的图像对进行了实验验证.该方法具有较低的计算复杂度和适宜于并行计算的特点,生成的视差图效果表明双序列比对算法为图像立体匹配提供了一个实用有效的方法.
4.学位论文 王涛 基于集群式超级计算机的三序列比对算法的并行实现及研究 2005
序列比对算法用在许多不同的领域。当前，这些领域里面的一个重要应用就是比对大分子，例如比对DNA和蛋白质序列，以及蛋白质结构比较。基本上，所有的序列比对算法，或多或少都会用到Needleman和Wunsch(1970)的动态规划算法。虽然从理论上来说用两两比对的方法来实现多序列比对是非常简单方便的，但是，尽管目前人们做了大量的工作和努力，对于6条以上的多序列比对，用两两比对的方法是不现实的。而且对于属于NP难问题的多序列比对问题，任何试图找到一种快速的计算优化比对的方法的企图都很有可能要失败的。为了提高优化比对的算法，全世界的科技工作者都马不停蹄地在辛苦地工作。这样就产生了许许多多的近似优化比对的伪算法，同时也开发出一大堆应用程序。
许多情况下，都有必要同时比对三序列。DavidR.Powell提出了一种新的使用线性空位罚分的优化的三序列比对算法。这个算法最早是由Ukkonen基于两序列和简单打分而提出的。本文基于分治法的原理通过引入“检查点法”对其进行改进，并充分利用近期蓬勃发展的高性能计算技术，将其在cluster机上并行实现。
本文的主要贡献有以下四点：1)讨论了各种序列比对算法的优缺点，分析了一种基于线性空位罚分和Ukkonen算法的三序列比对算法的并行化问题。2)引入“检查点法”对这种三序列比对算法进行优化。3)利用分治法的原理将其在cluster机上并行实现。4)提出了将现有序列比对算法并行化使之适应网格的分布式环境的研究方向。
5.学位论文 黄宁 生物序列比对 2009
随着人类基因组计划(HGP)的实施，生物信息学成为当今最重要的学科之一。生物信息学可以看作是集统计学，数学和计算科学于一体的学科。主要用来分析生物序列，即：DNA、RNA和氨基酸(蛋白质)序列。序列比对是生物信息学中最基本、最重要的方法。通过序列比对，可以发现生物序列的功能、结构和进化信息，因而序列比对是生物信息学的基础。 在本文的第一章，首先介绍了序列比
对方法和得分方案。序列比对包括全局序列比对和局部序列比对。从比对序列的数目来划分，又包括两两序列比对和多重序列比对。接着，我们给出了一些序列比对的算法。第二章，介绍了BLAST算法(基本的局部比对搜索工具)，这个算法是建立在统计理论基础上的，并从两个方面出发，证明了
BLAST算法。第三章，给出了隐马尔可夫模型，介绍了怎样从多条序列建立隐马尔可夫模型，并用隐马尔可夫模型来进行多重序列比对。第四章，我们讨论了生物网络中的局部图比对和motif搜索。在得分函数的基础上，我们为拓扑motifs发展一个搜索算法，该算法称为图比对，这是一个与序列比对有些相似的方法。
在文章最后，对BLAST算法、隐马尔可夫模型(HMM)和图比对作了讨论，分析了算法存在的缺点，并且为将来进一步研究给出了几点建议。
6.期刊论文 段敏.许龙飞.DUAN Min.XU Long-fei 生物DNA序列比对算法研究 -佳木斯大学学报(自然科学版)2005,23(2)
基于典型CLUSTALW序列比对算法,研究一种局部优化的多序列比对算法,用减少序列比对过程中总评分的方法来达到优化算法的目的,并对基因库中的序列进行了测试.
7.学位论文 黄国华 基于图形表示的DNA序列分析研究 2009
随着人类基因组计划(Human Genome Project，HGP)的顺利完成及各种模式生物基因组计划的相继实施，大量的生物分子数据源源不断地产生。对这些数据的保存、处理、分析和研究推动了分子生物学、数学及计算机科学的结合，由此发展起来的生物信息学正逐渐成为当今生命科学和自然科学的重大前沿领域之一，同时也将是21世纪自然科学的核心领域之一。生物信息学的研究重点主要体现在基因组学(Genomics)和蛋白学(Proteomics)两方面，具体说就是从核酸或蛋白质序列出发，分析序列中所表达的结构和功能的生物信息。其研究内容非常丰富，如：序列比较、基因识别、分子进化和比较基因组学、RNA和蛋白质的结构预测、计算机辅助药物设计等等。
图形表示是最近发展起来的应用在DNA序列分析方面的强有力的可视化工具，它能够揭示蕴藏在DNA序列中的结构和功能的生物信息。本文在分析DNA序列的各种2维、3维图形和高维数学描述及其应用的研究现状的基础上，提出了DNA序列的2D图形表示，并应用它分析了DNA序列间的突变和相似性。主要的研究内容如下：
(1)通过定义四类碱基分别对应四个不同的2维向量，提出了DNA序列的H-L图表示。该图形表示的优点在于可视化DNA序列间的不同模式。基于该图形表
示，提出了分析DNA序列间突变的方法。
(2)基于H-L图表示，提出了DNA序列间相似性度量的数值化方法，并运用该方法分析7个物种的β-球蛋白基因的全编码序列间的相似性。较之以前其它的度量方式，该方法无需复杂的计算且易于理解。这为生物学家快速而有效地分析DNA序列间的相似性，从而为研究它们间的进化关系提供了一种可选的工具。
(3)改进了DNA序列的“四线”图表示方法，并基于改进的图形表示，提出了寻找最优序列比对和判断DNA序列间碱基突变的方法。
8.学位论文 龙海 小麦LMW-GS基因克隆、类群划分及其特异分子标记开发研究 2006
小麦LMW-GS是重要的种子贮臧蛋白，与品质关系密切。本文在对小麦LMW-GS基因克隆的基础上，结合已有信息对LMW-GS基因家族进行了分类与染色体定位，并针对各类基因开发染色体组特异性分子标记。主要研究结果如下： 1.小麦LMW-GS基因的分子克隆
根据已知LMW-GS基因保守序列设计引物，采用PCR法从小麦品种川农16、川麦42以及中国特有半野生小麦中克隆了6个LMW-GS新基因：LMWCN16-1、LMWCN16-2、LMWCM42-1、LMW908-1、LMW908-2及LMW908-3，其基因登录号分别为AY296752、AY296753、DQ4154、AY299458、AY299457及AY299459，其中LMWCN16-1和LMW908-3由于存在提前终止密码子，推测为假基因。LMWCN16-2和LMW908-1中与已知LMW-GS的主要差异为部分位置的氨基酸替换，而LMWCM42-1和LMW908-2则与已报道的LMW-GS基因及预测蛋白的一级结构存在较大差异，可能对谷蛋白多聚体形成有一定影响。 2.LMW-GS基因的类群划分与染色体定位
通过对从数据库下载的69个LMW-GS基因进行推导氨基酸序列比对及聚类分析发现，根据其高度保守的N末端推导氨基酸序列，可将这69个基因划分成9种类群。根据DNA序列比对结果，针对各类基因共设计了11对引物，利用中国春第1同源群双端体系的总DNA进行PCR扩增来对各类基因进行染色体定位分析。结果发现，9对引物为LMW-GS基因类群特异性引物。9类基因都具有唯一的染色体位置，其中3类基因位于染色体1AS上，2类基因位于1BS上，而染色体1DS上分布有4类基因。这不仅使我们对LMW-GS基因这个多基因家族的组成及组织结构有了深入的认识，同时也为根据基因序列来推测其所存染色体定位提供了理论依据。利用9对特异引物对27份二倍体小麦及山羊草属物种的扩增结果进一步验证了分类及染色体分析的可靠性。此外，LMW-GS基因类群1、2，以及3、4.1特异的引物分别在A基因组和S基因组的材料中检测到DNA片段的长度多念性，表明这些物种中具有新的LMW-GS基因等位变异，可作为重要的遗传资源，对小麦的品质改良及拓宽小麦的加工特性有潜在应用价值。同时本实验开发的9对特异引物可方便、快速地检测LMW-GS基因的长度变异，对分子标记辅助育种具有重要的应用价值。
3.LMW-GS基因5'侧翼保守序列染色体组特异性DNA变异分析与验证
根据33个LMW-GS基因5'侧翼序列的相似性进行聚类分析，可将其划分成8个类群，这与基于N末端推导氨基酸序列进行的类群划分结果完全一致。序列比对发现，各类群基因5'侧翼保守序列间存在DNA多态性，共发现34个多念性位点，其中18个为潜在单核苷酸多念性位点
(SNPs，singlenucleotidepolymorphisms)。除1个LMW-GS类群之外，其余7个类群的5'侧翼序列均具有类群特异性DNA变异位点。根据类群问的DNA多态性对这7个类群设计了特异引物，利用普通小麦品种中国春及其第1同源群双端体系对其进行染色体定位分析，揭示了1AS、1BS和1DS上分别有第2、1和4类群。对PCR产物的克隆测序进一步验证了不同染色体组上的LMW-GS基因类群间5'侧翼序列具有特异性。这些结果表明，LMW-GS基因的编码区及其5'侧翼保守序列可能是协调进化的。本文报道的7对引物可对7类LMW-GS基因的完整编码区进行特异扩增，因而能在小麦复杂的遗传背景下有目的地对某一类LMW-GS基因进行分离克隆，这有助于弄清单个LMW-GS对小麦品质的贡献。同时，在小麦育种中，这些标记对于有效地选择与品质密切相关的LMW-GS组分有一定应用价值。
4.二倍体小麦LMW-i基因的遗传变异分析
利用LMW-i型亚基编码基因特异分子标记对71份A基因组二倍体小麦进行PCR扩增，发现其中存在丰富的LMW-GS基因长度变异。共扩增出11种不同的带型，每份材料可扩增出1至4条带，共鉴定出8种不同迁移率的条带。比较发现，野生一粒小麦中的变异类型与乌拉尔图小麦相当，而栽培一粒小麦中的变异相对较少。然而，其单种带型所含条带数较乌拉尔图小麦多。这些丰富遗传变异对小麦育种有重要应用价值，有必要对不同基因变异类型进行克隆，以便对其进一步深入研究。
9.期刊论文 刘兵.李大超.Liu Bing.Li Dachao 生物信息学中两条DNA序列比对的计数 -海南师范大学学报(自然科学版)2008,21(2)
应用组合数学的技巧研究了两个序列比对的计数问题,根据已知两个长度分别为n、m的DNA序列比对的递归公式,利用发生函数求出了两序列比对数的表达式.
10.期刊论文 张利平.陈国庆.王海琴.黄振东 浙江柑橘黄龙病病原β-操纵子核糖体蛋白基因的PCR检测及其序列比对
-植物保护2010,36(1)
长期的观察发现,不同柑橘品种感染黄龙病后出现的病症也不尽相同,针对这种现象本文检测了浙江柑橘黄龙病病原p_操纵子核糖体蛋白基因并进行了序列比对,BLAST比对结果说明所扩增的基因序列之间差异性为0,与基因库(NCBI)中黄龙病亚洲韧皮杆菌DNA序列相似性为100%,由此说明浙江柑橘黄龙病病原β-操纵子核糖体蛋白基因并未发生变异,出现上述现象可能是其他基因发生变异或者与品种的抗病性有关.
本文链接：http://d.g.wanfangdata.com.cn/Thesis_Y9391.aspx
下载时间：2010年6月1日
