基于生物信息学数据库的基因序列比对算法的设计与实现

编号毕业设计说明书题目基于生物信息学数据库的基因序列比对算法的设计与实现院（系）应用科技学院专业计算机科学与技术学生姓名易聪聪学号0401110231指导教师单位桂林电子科技大学姓名王文翰职称讲师题目类型理论研究实验研究工程设计工程技术研究软件开发2008年6月5日桂林电子科技大学毕业设计（论文）报告用纸摘要序列比对是生物信息学中的一个基本问题,通过序列比较可以发现生物序列中的功能、结构和进化的信息,序列比较的基本操作是比对。随着生物序列数据库中序列数据的激增，开发兼有高度生物敏感性和高效率的算法就显得非常迫切。本文研究了生物信息学中的双序列和基于生物序列数据库的序列比对算法。通过C语言结合面向对象与动态规划思想设计实现了一个包含NEEDLEMANWUNSCH、SMITHWATERMAN和BLAST算法的基于WINDOWS操作系统的中文序列比对系统。其功能主要有序列查看，序列比对算法选择、参数选择，比对结果输出等。可分别适用与双序列间的全局比对、局部比对以及基于生物序列数据库的序列搜索。虽然系统实现的初期有一些不完善的功能。经过测试和修整，系统已经可以长时间稳定运行。用户通过使用该系统从数据库中搜索可以轻松获取基因序列功能、结构信息。从而可以进一步判断序列是否同源。该系统的投入使用，可以在一定程度上提高生物工作者的工作效率，从而使得人力物力得到有效利用。加之本系统操作简洁明了，可以让更多对生物信息学学有兴趣的人能够加入到研究序列比对的队伍中来。关键词生物信息学；数据库；序列比对桂林电子科技大学毕业设计（论文）报告用纸ABSTRACTSEQUENCEALIGNMENTISABASICFIELDINBIOINFORMATICSWEMAYDISCOVERFUNCTIONAL,STRUCTURALANDEVOLUTIONARYINFORMATIONINBIOLOGICALSEQUENCESBYSEQUENCECOMPARINGBECAUSESEQUENCEDATAINCREASERAPIDLYINBIOLOGYSEQUENCEDATABASE,ITISVERYEXIGENTTODEVELOPALGORITHMSTHATHAVEHIGHBIOLOGYSENSITIVITYANDEFFICIENCYPAIRWISEANDSEQUENCEALIGNMENTALGORITHMSBASEINBIOLOGYSEQUENCEDATABASEOFBIOINFORMAICSARESTUDIEDINTHISPAPERANDACHINESESEQUENCEALIGNMENTSOFTWARESYSTEMWHICHWASBASEDINWINDOWSOPERATINGSYSTEMANDINCLUDEDNEEDLEMANWUNSCH,SMITHWATERMANANDBLASTALGORITHMSWASPROGRAMMEDINCPROGRAMMELANGUAGEWITHUSINGTHETHOUGHTOFTHEOBJECTORIENTEDANDDYNAMICPROGRAMMINGITSMAINFUNCTIONALARESHOWTHESEQUENCE,CHOOSETHEALGORITHMS,PREFERENCES,OUTPUTANDSOONTHESYSTEMSHOULDBEUSEDINTHEGLOBALSEQUENCEALIGNMENTANDTHELOCALSEQUENCEALIGNMENTINPAIRWISESEQUENCEORTOFINDOUTSEQUENCEINBIOLOGYSEQUENCEDATABASEOFBIOINFORMAICSALTHOUGHTHESYSTEMREALIZESTHEINITIALPERIODHASSOMEIMPERFECTFUNCTIONAFTERTHETESTANDTHECONDITIONING,THESYSTEMALREADYMIGHTBESTEADYOPERATIONFORALONGTIMEUSERSCOULDEASILYGETFUNCTIONALANDSTRUCTURALINFORMATIONINBIOLOGICALSEQUENCESBYUSINGTHISSYSTEMTOSEARCHINTHEDATABASETHENTHEYCANFURTHERJUDGEMENTWHETHERTHETWOSPECIESAREHOMOLOGYTHEINVESTMENTOFUSINGTHESYSTEMWILLHAVEACERTAINEXTENTIMPROVETHEBIOLOGISTSERVICEPOTENCY,ANDTHENSAVEALOTOFMANPOWERANDRESOURCESANDTHEFOUNDATIONSYSTEMSOPERATIONISSIMPLEANDBRIEF,ITMAYLETMOREPEOPLEWHOHAVETHEINTERESTTOTHEBIOLOGICALINFORMATIONSCIENCESSTUDYCANJOINCOMPARESTOTHESEQUENCEALIGNMENTKEYWORDSBIOINFORMATICSDATABASESEQUENCEALIGNMENT桂林电子科技大学毕业设计（论文）报告用纸目录引言11基因序列比对系统概述211基因序列比对系统背景212生物信息学简介213序列比对系统的内容214目的与意义315国内外现状32基因序列比对系统需求及相关技术521业务需求522硬件需求523相关技术5231面向对象技术简介5232动态规划技术简介63基因序列和序列比对算法831基因资料832序列比对8321NEEDLEMANWUNSCH算法8322SMITHWATERMAN9323BLAST算法104基因序列比对系统概要设计1241总体框架1242数据库格式说明1243系统实体图和ER图12431系统实体图12432系统ER图165基因序列比对系统详细设计1751系统详细设计介绍1752系统数据流图1753序列管理模块1854参数设置模块2055双序列比对模块2156序列查询模块22桂林电子科技大学毕业设计（论文）报告用纸6基因序列比对系统的实现2461系统界面的实现2462连接数据库的实现2463具体算法的实现25631NEEDLEMAN_WUNSCH算法的实现25632SMITH_WATERMAN算法的实现25633BLAST算法的实现267基因序列比对系统测试2771界面初始化内容测试2772序列管理模块功能测试2773参数设置模块功能测试2774双序列比对模块功能测试2875序列查询模块功能测试2876测试环境298结论30谢辞31参考文献32附录33桂林电子科技大学毕业设计（论文）报告用纸引言由于最近几年生物测序工作的快速进展,基因和蛋白质序列数据量急剧增长,生物信息学面临着从海量的数据中发现新的规律和知识的任务。在生物信息学的研究中,有一个常用的方法,就是通过比较分析获取有用的信息和知识。最常用的比较方法是序列比对，它为两个或更多个序列的残基之间的相互关系提供了一个非常明确的图谱。序列比对是通过对序列间的相似性进行打分,从而评估序列间相似性大小的一种方法。由于这种方法是生物信息学中进行其它诸如基因结构、功能等研究中的基本操作,因此比对方法的好坏在很大程度上决定这些研究的结果。将未知序列同已知序列进行比较分析已经成为一种强有力的研究手段，生物序列相似性比较中绝大部分的问题在计算机科学领域中主要体现为字符串的匹配和查找。本文在对序列比对系统进行了全面的需求分析后，结合生物工作者的具休情况，对系统进行了设计与实现。该系统使用了目前比较流行的MICROSOFTVISUALSTUDIO2005开发软件运用C语言编程实现。其中采用了面向对象和动态规划的编程技术，极大的提升了系统的性能与安全性。全文共分为七个部分，首先对基因序列比对系统的背景进行概述，其次是进行系统需求以及项目中所涉及的关键技术进行阐述，再次对系统的概要设计进行描述，最后详细叙述了系统的详细设计以及系统功能测试。桂林电子科技大学毕业设计（论文）报告用纸第1页共58页1基因序列比对系统概述11基因序列比对系统背景当前人类基因组研究已进入一个重要时期，2004年已获得人类基因组的全部序列，这是基因组研究的转折点和关键时刻，意味着人类基因组的研究将全面进入信息提取和数据分析阶段，即生物信息学发挥重要作用的阶段。到1999年12月15日发布的第115版为止，GENBANK中的DNA碱基数目已达46亿5千万，DNA序列数目达到535万；其中EST序列超过339万条；UNIGENE的数目已达到7万个；已有25个模式生物的完整基因组被测序完成，另外的70个模式生物基因组正在测序当中；到2005年初为止，人类基因组的序列完成测定；同时功能基因组和蛋白质组的大量数据已开始涌现。如何分析这些数据，从中获得生物结构、功能的相关信息是基因组研究取得成果的决定性步骤。基因序列比对系统由此应需而生。12生物信息学简介生物信息学是新发展起来的综合运用生物学、数学、物理学、信息科学以及计算机科学等诸多学科的理论方法的崭新交叉学科。生物信息学是内涵非常丰富的学科，其核心是基因组信息学，包括基因组信息的获取、处理、存储、分配和解释。基因组信息学的关键是“读懂”基因组的核苷酸顺序，即全部基因在染色体上的确切位置以及各DNA片段的功能；同时在发现了新基因信息之后进行蛋白质空间结构模拟和预测，然后依据特定蛋白质的功能进行药物设计。了解基因表达的调控机理也是生物信息学的重要内容，根据生物分子在基因调控中的作用，描述人类疾病的诊断、治疗内在规律。它的研究目标是揭示“基因组信息结构的复杂性及遗传语言的根本规律“，解释生命的遗传语言。生物信息学已成为整个生命科学发展的重要组成部分，成为生命科学研究的前沿。桂林电子科技大学毕业设计（论文）报告用纸第2页共58页13序列比对系统的内容比较是科学研究中最常见的方法，通过将研究对象相互比较来寻找对象可能具备的特性。在生物信息学研究中，比对是最常用和最经典的研究手段。最常见的比对是核酸序列之间的两两比对，通过比较两个序列之间的相似区域和保守性位点，寻找二者可能的分子进化关系。比对还是数据库搜索算法的基础，将查询序列与整个数据库的所有序列进行比对，从数据库中获得与其最相似序列的已有的数据，能最快速的获得有关查询序列的大量有价值的参考信息，对于进一步分析其结构和功能都会有很大的帮助。本系统正是针对序列间的两两比对与数据库搜索而设计。用户可以根据自己的需要选择不同的算法进行不同的操作。比如比较两条已知的序列，或在数据库中搜索与未知序列相似的序列。以获得有价值的信息。14目的与意义自从1990年美国启动人类基因组计划以来，人与模式生物基因组的测序工作进展极为迅速。迄今已完成了约40多种生物的全基因组测序工作，人基因组约3X109碱基对的测序工作也接近完成。至2004年，被誉为生命“阿波罗计划“的人类基因组计划，经过美、英、日、法、德和中国科学家的艰苦努力终于完成。这是人类科学世上又一个里程碑式的事件。截止目前为止，仅登录在美国GENBANK数据库中的DNA序列总量已超过70亿碱基对。人类科学研究史表明，科学数据的大量积累将导致重大的科学规律的发现。例如对数百颗天体运行数据的分析导致了开普勒三大定律和万有引力定律的发现；数十种元素和上万种化合物数据的积累导致了元素周期表的发现；氢原子光谱学数据的积累促成了量子理论的提出，为量子力学的建立奠定了基础。历史的经验值得注意，有理由认为，今日生物学数据的巨大积累也将导致重大生物学规律的发现。数据并不等于信息和知识，但却是信息和知识的源泉，关键在于如何从中挖掘它们。由此可见研究序列之间的关系是十分必要的。而将未知序列同已知序列进行比较分析又正是一种强有力的研究手段。所以设计出一种更快，更准确的序列比对算法和序列比对系统是非常有意义的。15国内外现状生物信息学的发展在国内、外基本上都处在起步阶段，所拥有的条件也大体相同，即使我国有关条件差一些，但差别也不大。目前最常见基因序列比对桂林电子科技大学毕业设计（论文）报告用纸第3页共58页工具有FASTA工具和BLAST工具。FASTA是第一个被广泛应用的序列比对和搜索工具包，包含若干个独立的程序。FASTA为了提供序列搜索的速度，会先建立序列片段的“字典”，查询序列先会在字典里搜索可能的匹配序列，字典中的序列长度由KTUP参数控制，缺省的KTUP2。FASTA的结果报告中会给出每个搜索到的序列与查询序列的最佳比对结果，以及这个比对的统计学显著性评估E值。BLAST是现在应用最广泛的序列相似性搜索工具，相比FASTA有更多改进，速度更快，并建立在严格的统计学基础之上。NCBI提供了基于WEB的BLAST服务，用户可以把序列填入网页上的表单里，选择相应的参数后提交到数据服务器上进行搜索，从电子邮件中获得序列搜索的结果。BLAST包含五个程序和若干个相应的数据库，分别针对不同的查询序列和要搜索的数据库类型。其中翻译的核酸库指搜索比对时会把核酸数据按密码子按所有可能的阅读框架转换成蛋白质序列。BLAST对序列格式的要求是常见的FASTA格式。FASTA格式第一行是描述行，第一个字符必须是“”字符；随后的行是序列本身，一般每行序列不要超过80个字符，回车符不会影响程序对序列连续性的看法。序列由标准的IUB/IUPAC氨基酸和核酸代码代表；小写字符会全部转换成大写；单个“”号代表不明长度的空位；在氨基酸序列里允许出现“U”和“”号；任何数字都应该被去掉或换成字母如，不明核酸用“N”，不明氨基酸用“X”。此外，对于核酸序列，除了A、C、G、T、U分别代表各种核酸之外，R代表G或A嘌呤；Y代表T或C嘧啶；K代表G或T带酮基；M代表A或C带氨基；S代表G或C强；W代表A或T弱；B代表G、T或C；D代表G、A或T；H代表A、C或T；V代表G、C或A；N代表A、G、C、T中任意一种。对于氨基酸序列，除了20种常见氨基酸的标准单字符标识之外，B代表ASP或ASN；U代表硒代半胱氨酸；Z代表GLU或GLN；X代表任意氨基酸；“”代表翻译结束标志。桂林电子科技大学毕业设计（论文）报告用纸第4页共58页2基因序列比对系统需求及相关技术21业务需求根据生物工作者与爱好者的需要，该系统需求如下（1）可以以明文查看序列数据库中的某一条序列的具体信息，其中包括该序列的序列号，定义，长度，数据内容等。（2）可以手动输入两条序列进行比对并根据选择的不同的算法和参数显示出比对结果。（3）可以把一条未知的序列与数据库中某一条特定的序列进行比对并根据选择的不同的算法和参数显示出比对结果。（4）可以把一条未知的序列与数据库中的某些序列进行比对并根据选择的不同的算法和参数显示出比对结果。（5）可以在数据库搜索出与未知序列最为匹配或者相似的序列。（6）可以对输入的序列字符串进行翻转旋转等操作。22硬件需求处理器PENTIUMIV级，1600MHZ或以上内存256M内存或以上硬盘200M或以上空闲硬盘空间操作系统WINDOWS2000SP0,SP1,SP2,SP3,SP4，WINDOWSXPSP0,SP1编程环境MICROSOFTVISUALSTUDIO200523相关技术在为了提高系统的可靠性，可重用性、维护性以及运行效率，开发序列比桂林电子科技大学毕业设计（论文）报告用纸第5页共58页对系统时主要运用了面向对象的开发方法和动态规划的编程技术。在规范了开发流程的同时也缩短了理论模型与实际的应用系统开发之间的差距。231面向对象技术简介面向对象是一种新兴的程序设计方法，或者说它是一种新的程序设计范型，其基本思想是使用对象，类，继承，封装，消息等基本概念来进行程序设计。它是从现实世界中客观存在的事物（即对象）出发来构造软件系统，并在系统构造中尽可能运用人类的自然思维方式，强调直接以问题域（现实世界）中的事物为中心来思考问题，认识问题，并根据这些事物的本质特点，把它们抽象地表示为系统中的对象，作为系统的基本构成单位（而不是用一些与现实世界中的事物相关比较远，并且没有对应关系的其它概念来构造系统）。这可以使系统直接地映射问题域，保持问题域中事物及其相互关系的本来面貌。PETERCOAD和EDWARDYOURDON提出用下面的等式识别面向对象方法面向对象对象OBJECT分类CLASSIFICATION继承INHERITANCE通过消息的通信COMMUNICATIONWITHMESSAGE。可以说，采用这4个概念开发的软件是面向对象的。类是构成面向对象编程的基础，一个类定义了一组大体上相似的对象。一个类所包含的方法和数据描述一组对象的共同行为和属性。把一组对象的共同特征加以抽象并存储在一个类中的能力，是面向对象技术最重要的一点；是否建立了一个丰富的类库，是衡量一个面向对象程序设计语言成熟与否的重要标志。使用类来编程有如下好处（1）类具有“独立性“由于这种独立的存在,使得和其他的“过程也好,对象也罢“能够不彼此牵引避免“牵一发而动全身“的局面这有利于维护和调试（2）类具有“通用性“这种通用性,是通过抽象得来的所谓抽象,就是抽取出事物的共同特征并且加以概括正是因为这种“通用性“的实现,才造就了“REUSE“的可能（3）类具有“灵活性“由于第二个特征的存在,加上客观事物的特殊性,有可能通用的类中一部分成员方法变得“不通用“,这个时候通过继承和OVERLOAD的机制,使得它能够应付某些特殊情况,从而实现了“灵活性“232动态规划技术简介动态规划DYNAMICPROGRAMMING是运筹学的一个分支，是求解决策过程最桂林电子科技大学毕业设计（论文）报告用纸第6页共58页优化的数学方法。它建立在最优原则的基础上。采用动态规划方法，可以优雅而高效地解决许多用贪婪算法或分而治之算法无法解决的问题。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，以至于最后解决原问题需要耗费指数级时间。然而不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复了许多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，从而得到多项式时间的算法。为了达到这个目的，我们可以用一个表来记录所有已解决的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解，每个解都对应于一个值，我们希望找到具有最优值（最大值或最小值）的那个解。设计一个动态规划算法，通常可按以下几个步骤进行（1）找出最优解的性质，并刻画其结构特征；（2）递归地定义最优值；（3）以自底向上的方式计算出最优值；（4）根据计算最优值时得到的信息，构造一个最优解。步骤（1）（3）是动态规划算法的基本步骤。在只需要求出最优值的情形下步骤（4）可以省略。若需要求出问题的一个最优解，则必须执行步骤（4）。此时，在步骤（3）中计算最优值，通常需记录更多的信息，以便在步骤（4）中根据所记录的信息，快速构造出一个最优解。桂林电子科技大学毕业设计（论文）报告用纸第7页共58页3基因序列和序列比对算法31基因资料DNA,即脱氧核糖核酸。DNA是由脱氧核苷酸和碱基间通过碱基互补配对,在氢键的作用下形成的双螺旋结构在脱氧核苷酸内部,磷酸基和脱氧核糖是通过3,5磷酸二脂键连接的DNA是反向向右双螺旋结构DNA的碱基有4种，分别是腺嘌呤ADENINE、鸟嘌呤GUANINE、胞嘧啶CYTOSINE和胸腺嘧啶THYMINE。DNA链是称为核苷酸的小单元组成的序列。为了回答某些重要的研究问题，研究人员把基因串看作计算机科学的字符串也就是说，可以忽略基因串的物理和化学性质，而将其想像成字符的序列。比如说A和T是互补的碱基对，C和G也是互补的碱基对。这意味着一个链中的A与另一个链中的T组成一对（反之亦然），一个链中的C与另一个链中的G组成一对（反之亦然）。所以，如果知道一个链中的A、C、T和G的顺序，那么就能推导出另一个链中的顺序。所以，可以将一条DNA链想像成由字母A、C、G和T组成的字符串。32序列比对基因学的一个主要主题就是比较DNA序列并尝试找出两个序列的公共部分。如果两个DNA序列有类似的公共子序列，那么这些两个序列很可能是同源的。在比对两个序列时，不仅要考虑完全匹配的字符，还要考虑一个序列中的空格或间隙（或者，相反地，要考虑另一个序列中的插入部分）和不匹配，桂林电子科技大学毕业设计（论文）报告用纸第8页共58页这两个方面都可能意味着突变。在序列比对中，需要找到最优的比对（最优比对大致是指要将匹配的数量最大化，将空格和不匹配的数量最小化）。如果要更正式些，您可以确定一个分数，为匹配的字符添加分数、为空格和不匹配的字符减去分数。比对的算法可分为两类全局比对和局部比对。本文主要研究了其中的NEEDLEMANWUNSCH、SMITHWATERMAN和BLAST算法。其中NEEDLEMANWUNSCH算法主要运用于序列间的全局比对，SMITHWATERMAN算法主要运用于序列间的局部比对，而BLAST算法则主要运用于在大型序列数据库中搜索与用户输入的序列相似的序列。321NEEDLEMANWUNSCH算法NEEDLEMANWUNSCH算法由BELLMAN于50年代提出。这个算法使用二维表格，一个序列沿顶部展开，一个序列沿左侧展开。而且也能通过以下三个途径到达每个单元格（1）来自上面的单元格，代表将左侧的字符与空格比对。（2）来自左侧的单元格，代表将上面的字符与空格比对。（3）来自左上侧的单元格，代表与左侧和上面的字符比对（可能匹配也可能不匹配）然后计算出两个序列的相似分值，存于这个二维表格中。根据此表格，按照回溯的方法寻找最优的比对序列。NEEDLEMANWUNSCH算法可用伪代码表示如下前提条件，用于填充二维表格的第一行与第一列分数0,00分数I,0分数I1,0匹配得分前提序列第I个字符,空位分数0,J分数0,J1匹配得分空位,命中序列第J个字符递归关系,用于填充二维表格的其余位置分数I1,J1匹配得分前提序列第I个字符,命中序列第J个分数I,J最大值字符,分数I1,J匹配得分前提序列第I个字符,空位分数I,J1匹配得分空位,命中序列第J个字符回溯，根据填充完毕的二维表格的分值还原出两条序列的最优比对FORI前提序列的长度，J命中序列的长度I0IF分数I,J分数I1,J1是否相同前提序列的第I个字符,命中序列第J个字符桂林电子科技大学毕业设计（论文）报告用纸第9页共58页IJELSEIF分数I,J分数I1,J是否相同前提序列的第I个字符,空位I在命中序列的第J个字符上插入空位ELSEIF分数I,J分数I,J1是否相同空位,命中序列第J个字符J在前提序列的第I个字符上插入空位至此，前提序列和命中序列都已为最佳比对。一般来说规定每个匹配字符一分，一个空格扣两分，一个不匹配字符扣一分。322SMITHWATERMAN在生物学中局部比对比全局比对更具有实际的意义。SMITHWATERMAN算法致力于发现两条序列在哪一些局部的区域内具有很高的相似度。在SMITHWATERMAN算法中，不必比对整个序列。两个零长字符串即为得分为0的局部比对，这一事实表明在构建局部比对时，不需要使用负分。这样会造成进一步比对所得到的分数低于通过“重设”两个零长字符串所能得到的分数。而且局部比对不需要到达任何一个序列的末端，所以也不需要从右下角开始回溯，可以从得分最高的单元格开始回溯。这导致SMITHWATERMAN算法与NEEDLEMANWUNSCH算法存在着三个区别。首先，在初始化阶段，第一行和第一列全填充为0（而且第一行和第一列的指针均为空）。第二，在填充表格时，如果某个得分为负，那么就用0代替，只对得分为正的单元格添加返回指针，最后，在回溯的时候，从得分最高的单元格开始，回溯到得分为0的单元格为止。除此之外，回溯的方式与NEEDLEMANWUNSCH算法完全相同。SMITHWATERMAN算法可用伪代码表示如下前提条件，用于填充二维表格的第一行与第一列分数I,00分数0,J0递归关系,用于填充二维表格的其余位置。并找出分数最高的格子的位置分数I1,J1匹配得分前提序列第I个字符,命中序列第J个字符,分数I,J最大值分数I1,J匹配得分前提序列第I个字符,空位分数I,J1匹配得分空位,命中序列第J个字符回溯，根据填充完毕的二维表格的分值从分数最高的格子开始回溯还原出两条序列的最优比对。回溯方式同NEEDLEMANWUNSCH算法。桂林电子科技大学毕业设计（论文）报告用纸第10页共58页323BLAST算法本文介绍了NEEDLEMANWUNSCH和SMITHWATERMAN算法的基本实现，查找全局和局部比对的时间为OMN。实际的研究人员通常不是比较两个序列，而是试图找出与特定序列相似的所有序列。如果发现某个相似序列具有已知的生物学功能，那么原来的序列也很有可能具有相似的功能，因为相似的序列通常会有相似的功能。如果直接使用SMITHWATERMAN算法在数据库里搜索，即使使用具有二次数量级的运行时间，将输入序列与超大型基因序列数据库的每个序列（每个序列可能还包含30亿或者更多个碱基对）进行比对还是太慢。这种时候就要考虑BLAST算法了。BLAST是一种启发式算法，通过比对ALIGNMENT在数据库中寻找和查询序列QUERY相似度很高的序列。两个序列的最大片段对（MSP，MAXIMUMSEGMENTPAIR）就是最高得分的片段对。这个得分是序列相似性的度量，可以利用动态规划算法准确地算出。但是，BLAST却能比任何基于动态规划的算法更快地估计最高得分值。在进行序列两两比较之前，BLAST首先寻找一颗“种子”，它是两个序列之间的一个非常短的片段对。种子可以向两个方向扩展，直至达到扩展的最大可能的得分。程序对何时停止扩展有一个判断准则，即当扩展的得分低于某个计算的下限时，停止扩展。是正确的扩展但未被发现的可能性非常小。BLAST的计算过程分为三个阶段（1）生成单词表。单词表由所有长度等于设定步长的连续字符串组成。种子可以通过在序列中滑动获得。例如设定步长为4，则一个DNA序列ACGCGT有ACGC,CGCG,GCGT这3个种子。（2）搜索种子。把单词表里这些单词组织在一个哈希表（HASHTABLE）中，对于数据库中的每个长度为设定步长的单词，取它们在哈希表中的对应下标，并将它们与哈希表该位置上的所有单词（高得分单词表的一部分）进行比较。若相同则找到一颗种子。由于单词表可能很大，用一般的数据组织方法查询速度慢，而用哈希表可以实现直接寻址，提高查询速度。（3）扩展种子。最后一步扩展过程比较直观。当扩展时的得分低于该扩展前面的最佳得分的某个下限时，扩展停止。扩展是双向的，并保存从对应种子扩展而得到的高得分片段对。桂林电子科技大学毕业设计（论文）报告用纸第11页共58页4基因序列比对系统概要设计41总体框架基于对生物工作者的需求的研究，该系统的设计可分为为界面和操作两个结构。界面部分主要负责显示经过操作部分处理回馈回来的结果和对操作部分一些必要的参数进行设置。42数据库格式说明该系统支持标准FASTA序列数据库格式的数据库文件。FASTA格式第一行是描述行，第一个字符必须是“”字符；随后的行是序列本身，一般每行序列不要超过80个字符，回车符不会影响程序对序列连续性的看法。序列由标准的IUB/IUPAC氨基酸和核酸代码代表；小写字符会全部转换成大写；单个“”号代表不明长度的空位；在氨基酸序列里允许出现“U”和“”号；任何数字都应该被去掉或换成字母如，不明核酸用“N”，不明氨基酸用“X”。此外，对于核酸序列，除了A、C、G、T、U分别代表各种核酸之外，R代表G或A嘌呤；Y代表T或C嘧啶；K代表G或T带酮基；M代表A或C带氨基；S代表G或C强；W代表A或T弱；B代表G、T或C；D代表G、A或T；H代表A、C或T；V代表G、C或A；N代表A、G、C、T中任意一种。对于氨基酸序列，除了20种常见氨基酸的标准单字符标识之外，B代表ASP或ASN；U代表硒代半胱氨酸；Z代表GLU或GLN；X代表任意氨基酸；“”代表翻译结束标志。桂林电子科技大学毕业设计（论文）报告用纸第12页共58页43系统实体图和ER图431系统实体图图41CELL实体及其属性图每一个CELL类的实体代表分值二维表格里的一个格子。它的属性分别如下PREVCELL也是一个CELL类的实体，表示这个实体的前置格子COL表示该格子在二维表格里的列号ROW表示该格子在二维表格里的行号SCORE表示该格子上的比对分值图42CELLACTION实体及其属性图桂林电子科技大学毕业设计（论文）报告用纸第13页共58页CELLACTION类里主要封装了对序列的各种操作函数，其属性分别如下FIRSTSEQUENCE待分析序列1SECONDSEQUENCE待分析序列2TMPSEQUENCE1临时序列1TMPSEQUENCE2临时序列2CELLS一个CELL类的实体数组，用来模拟一个二维表格TMPCELL一个临时的格子，用于记录二维表格中的最值INITSCORE用于记录比对开始时的初始分值TMPNUM用于临时记录比对中最值的序列号DNANUM用于保存比对中最值的序列号BHSEQ1用于保存经过处理后的待分析序列1BHSEQ2用于保存经过处理后的待分析序列2SCORELIST用于保存进行BLAST算法比对后的分值列表ARRBLAST用于传递BLAST风格的输出序列信息图43DNA实体及其属性图DNA类主要用于逐条输出比对结果，其属性分别如下DNANUMBERDNA序列的序号DNASEQUENCEDNA序列的序列内容桂林电子科技大学毕业设计（论文）报告用纸第14页共58页图44SEED实体及其属性图SEED类主要描述BLAST算法里种子和命中序列的情况。其属性分别如下SEEDS种子序列QUERYINDEX种子序列的开始位置SBJCT命中序列SBJCTINDEX命中序列的开始位置SOCRE比对分值HIGHSOCREINDEX种子和命中序列比对的最高分值开始位置HIGHSOCREEND种子和命中序列比对的最高分值结束位置IDENTITIES种子和命中序列的匹配百分比图45OPTIONS实体及其属性图OPTIONS类主要是封装了对各算法的参数，其属性分别如下W步长M匹配分值N不匹配分值Y中止阈值S最小分值桂林电子科技大学毕业设计（论文）报告用纸第15页共58页图46BLASTOUTPUT实体及其属性图BLASTOUTPUT类主要用来保存BLAST风格的序列比对输出结果，其属性分别如下NUMBER表示与未知序列进行比对的已知序列的序列号HIGHSCORE表示某条已知序列和未知序列比对的各种结果中的最高分值SEQ表示两条序列比对的情况LENGTH表示该已知序列的长度432系统ER图图47系统ER图桂林电子科技大学毕业设计（论文）报告用纸第16页共58页5基因序列比对系统详细设计本基因序列比对系统为生物工作者使用的序列比对及搜索工具，在进行了充分的客户调研和概要设计后，本系统分为序列管理模块、参数设置模块、双序列比对模块和序列查询模块。51系统详细设计介绍根据系统的概要设计，界面部分通过VISUALSTUDIO封装好的WINDOWS窗体来实现。功能部分则新建一个名为“CLASS”的文件包，里面存放所有操作类。比如其中BLASTOUTPUTCS用于控制输出BLAST风格的比对查询结果；CELLCS用于表示二维分数表格里的每一个格子；CELLACTIONCS里主要存放绝大部分算法函数；OPTIONSCS用于存放用户所作的参数设置。同时，为了代码更具有重用性，系统还专门用一个类MODULECS来存放那些需要被重复调用的函数，比如过滤字符串函数等。52系统数据流图桂林电子科技大学毕业设计（论文）报告用纸第17页共58页图51序列比对系统顶级数据流图图52序列比对系统1级数据流图桂林电子科技大学毕业设计（论文）报告用纸第18页共58页53序列管理模块在本模块中，主要有三种操作查看序列，编辑序列和保存序列。其中保存序列又可分为在原有数据库文件中保存和导出到新的数据库文件。查看序列从序列数据库中读入序列信息后，主界面左边的列表框中会显示数据库中存在的序列，选中后某一条序列后，列表框右下方的序列基本信息栏会显示出该条序列的基本信息，如序列号，序列长度，序列的存储格式和路径等。如果想更进一步了解该序列的内容则可通过点击列表框下方的“查看所选序列”按钮来打开该序列的信息窗体。在该窗体不同碱基用不同的颜色来显示，十分直观。如下图所示图53序列管理模块流程图桂林电子科技大学毕业设计（论文）报告用纸第19页共58页图54查看序列编辑序列在查看序列窗体中可以对序列进行编辑。关闭该窗体时如序列内容已经发生了改变则提示保存。保存序列在原有数据库文件中保存序列的流程基本同上，主要要说明将序列导出到新的数据库文件。由于序列数据库的数据量太大，而生物工作者们研究的往往只是整个数据库中的某一些特定的序列。所以，在本系统中用户可以通过在列表框中选中一条或复述条序列导出到一个新的数据库文件里。下次进行查询时所花费的时间就可以大大减少了。54参数设置模块不同的比对算法会有不同的参数要求，比如NEEDLEMANWUNSCH、SMITHWATERMAN要求知道两个碱基之间匹配对应分值。通常来说匹配一个字符加1分，不匹配字符减1分，引入一个空位减2分。而BLAST不同于前面两种算法，它是一种启发式算法，要设置的参数相对较多。除了匹配分值外还有步长、阈值和最小分值等。设置不同的参数会对比对的结果造成影响，比如把步长设置得长一些可以提升比对的速度而同时也会降低比对的灵敏度。所以设置参数时一定要慎重。参数设置成功后，将会产生一个OPTIONS类的实体。当各算法要用到这些参数时可以通过读取这个实体相应的属性来获得。桂林电子科技大学毕业设计（论文）报告用纸第20页共58页图55参数设置模块流程图图56参数设置55双序列比对模块在本模块中，用户可以选择手动输入两条序列利用不同算法来进行比对，也可以输入一条序列并将该条序列与数据库中的某条序列进行比对。可供选择的比对算法有三种NEEDLEMANWUNSCH、SMITHWATERMAN和BLAST。一般来说双序列比对不会选择用BLAST算法，而倾向于选择灵敏度和精度更高的NEEDLEMANWUNSCH和SMITHWATERMAN算法。用户可以根据需求自行选择合适的算法。桂林电子科技大学毕业设计（论文）报告用纸第21页共58页图57双序列比对模块流程图比对结束后，将显示比对结果。两序列中相同的部分用红色表示，空位用”_”表示。值得一提的是由于BLAST算法的特殊性，选择它后会有不同的显示输出效果。图58比对结果56序列查询模块本模块是该系统的核心模块。在这里用户可以通过输入一条序列，然后在数据库中检索与该序列相似的序列。可供选择的算法同样有三种NEEDLEMANWUNSCH、SMITHWATERMAN和BLAST。不过由于NEEDLEMANWUNSCH和SMITHWATERMAN算法的时间复杂度过高，在实际大型数据库中进行搜索时显得有点不切实际。一般选用BLAST算法。用NEEDLEMANWUNSCH、SMITHWATERMAN算法进行查询时，系统根据比对分值的高低只会显示最高分值的比对。而用BLAST算法进行查询时，系统会返回经过排桂林电子科技大学毕业设计（论文）报告用纸第22页共58页序后的所有适合的比对结果。图59序列查询模块流程图桂林电子科技大学毕业设计（论文）报告用纸第23页共58页图510BLAST比对结果6基因序列比对系统的实现61系统界面的实现一个好的界面是一个系统成功的一半。所以设计一个简洁明了，美观协调的同时又具易用合理的界面就显得十分必要了。本系统采用MICROSOFTVISUALSTUDIO2005自带的WINFORM窗体来制作界面。整个界面布局合理，所有功能一目了然，并且很符合用户的操作习惯。桂林电子科技大学毕业设计（论文）报告用纸第24页共58页图61系统主界面截图62连接数据库的实现本系统采用的数据库格式是基因序列标准的保存格式FASTA格式。它是一种类似于文本文件的静态数据库。鉴于这种特点，本系统是通过如下方式实现连接并读取其中的信息的（1）首先在主窗体上添加一个OPENFILEDIALOG，当选择打开数据库时将弹出对话框让用户选择要打开的文件的路径。用户选择了数据库后把路径保存下来；（2）在公用模块类MODULECS里添加一个静态函数GETSEQUENCES。它通过接收从步骤一中所得的路径新建一个STREAMREADER类的实体并打开所选路径的文件；（3）逐行扫描，当当前一行的第一个字符为”时，说明这是一条序列的序列号，保存下来。若第一个字符不为”则说明这是一条序列序列内容的某一行，追加保存。（4）把步骤三获得的序列号和序列内容追加到一个链表，暂存下来以供调用。步骤四中的链表既为数据库在系统中的缓存。63具体算法的实现631NEEDLEMAN_WUNSCH算法的实现NEEDLEMAN_WUNSCH算法的实现主要是依靠CELLACTIONCS类里的两个函数NEEDLEMAN_WUNSCH和TRACEBACKNW。其中NEEDLEMAN_WUNSCH用来填充比对的分值二维表格，TRACEBACKNW用来根据二维表格的分值进行回溯已找出最优的比对结果。NEEDLEMAN_WUNSCH的功能可以用如下步骤来表示（1）新建一个行和列分别是两个待比对序列的长度的二维表格，即一个二维的CELL类实体的数组。（2）初始化表格里每个格子的分数，其中左上角的格子的分值为0（3）根据每一个格子和它周围的格子的分数的算数关系给每个格子赋值，并记录他们的前置格子TRACEBACKNW的功能可以用如下步骤来表示（1）根据二维表格的分值从表格的右下角格子开始寻找回溯路径桂林电子科技大学毕业设计（论文）报告用纸第25页共58页（2）比较两条经过处理后的序列的长度，长度小的在前面插入相应的空位632SMITH_WATERMAN算法的实现SMITH_WATERMAN算法的实现主要是依靠CELLACTIONCS类里的两个函数SMITH_WATERMAN和TRACEBACKSM。其中SMITH_WATERMAN用来填充比对的分值二维表格，TRACEBACKSM用来根据二维表格的分值进行回溯已找出最优的比对结果。SMITH_WATERMAN的功能可以用如下步骤来表示（1）新建一个行和列分别是两个待比对序列的长度的二维表格，即一个二维的CELL类实体的数组；（2）初始化表格里每个格子的分数，其中第一行和第一列格子的分值都为0；（3）根据每一个格子和它周围的格子的分数的算数关系给每个格子赋值，并记录他们的前置格子；（4）记录表格中分值最大的格子的行号和列号TRACEBACKSM的功能可以用如下步骤来表示（1）根据二维表格的分值从表格中最大的格子开始寻找回溯路径（2）比较两条经过处理后的序列的长度，长度小的在前面插入相应的空位633BLAST算法的实现BLAST算法的实现主要是依靠CELLACTIONCS类里的BLAST函数。该函数需要用到的变量较多，需要调用到其他函数也多。BLAST函数的功能可以用如下步骤来表示（1）获取需比对的两条序列；（2）生成单词表。首先根据用户设定的步长参数对待比对序列进行滑动获取各个长度等于步长参数的连续字符串。根据字符串的内容用哈希函数取得一下标，把该字符串的起始位置存入相应哈希表下标的位置内。系统所用的哈希函数算法大概为每一个碱基都有一个特有的数字A0,C1,G2,T3。哈希值等于每个碱基对应的数字乘上4的碱基维数减一次放只和；（3）如果哈希表目标下标位置内已经有了数据，则通过分割符“，”追加到目标下标的字符后，要读取时就调用MODULECS内的GETHASHINDEX函数来获得；（4）生成种子。在已知序列中搜索哈希表里的单词，如有匹配的，则记录下已知序列中与种子匹配的碱基串的起始位置；桂林电子科技大学毕业设计（论文）报告用纸第26页共58页（5）扩展种子。把步骤（4）中获得的种子往左右两边延伸，匹配则加上相应的分值，不匹配则扣掉相应的分值。记录下当前获得过的最高分值的位置，当扩展产生的分值低与原来的最高分值时，宣告扩展结束。回溯到原始最高分值的位置；（6）通过调用MODULECS中的FILTER和TAXIS将比对结果进行过滤，排序。输出BLAST风格的比对结果。7基因序列比对系统测试尽管软件质量保证是贯穿软件开发全过程的活动，但最关键的步骤是软件测试，软件测试是对软件规格说明、软件设计和编码的最后复审，目的是在软件产品交付之前尽可能发现软件中潜伏的错误。软件测试的过程亦是程序运行的过程。程序运行需要数据，为测试设计的数据称测试用例。设计测试用例的原则自然是尽可能暴露错误。71界面初始化内容测试测试内容（1）界面初始化时，各控件的摆放位置，大小，文字控件的字体，文字，字体颜色是否正确；（2）界面初始化时，各控件的可用状态是否正确；（3）界面初始化时，窗体的整体布局是否合理。测试方法观察测试结果界面初始化时，窗体的整体布局合理，各控件的摆放位置，大小，文字控件的字体，文字，字体颜色正确，各控件的可用状态正确。72序列管理模块功能测试测试内容点击界面内各按钮是否可以响应对应的事件；测试方法（1）点击序列列表中的某条记录，选择查看；桂林电子科技大学毕业设计（论文）报告用纸第27页共58页（2）选择序列列表中的多条记录，选择导出到数据库。观察数据库又无有变化；（3）编辑某一条序列并保存，观察数据库内的变化。测试结果各按钮和操作都能正确响应。点击序列列表中的某条记录，选择查看可以查看正确的序列信息，选择序列列表中的多条记录，选择导出到数据库。所选序列可以正常导入到一个新的数据库文件。编辑某一条序列并保存数据库内该条序列的序列内容也发生相应的变化。73参数设置模块功能测试测试内容设置好相关参数后，序列的比对是否按照相应是设置进行；测试方法断点调试，观察算法获得的相应参数是否正确；测试结果序列比对算法能按照参数设置里设置好的参数进行序列的比对。74双序列比对模块功能测试测试内容（1）点击界面内各按钮是否可以响应对应的事件（2）选择不同的算法进行序列比对，是否可以得到正确的比对结果测试方法（1）选择与数据库中单条序列比对时单击序列列表中的序列；（2）改变“反转序列”CHECKBOX的值；（3）当序列输入不完整、错误或算法、参数等设置不完全时选择执行；（4）分别选择三种不同的算法，输入不同的序列进行比对测试结果（1）选中的序列的序列内容可以正确填充到序列2中；（2）序列1的内容可以正确翻转；（3）可以提示相应的错误；（4）结果如下表所示表41比对结果NEEDLEMAN_WUNSCHSMITH_WATERMANBLAST序列1序列2理