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

1、编号： 毕业设计说明书题 目： 基于生物信息学数据库的 基因序列比对算法的设计与实现院 （系）： 应用科技学院 专 业： 计算机科学与技术 学生姓名： 易聪聪 学 号： 0401110231 指导教师单位： 桂林电子科技大学 姓 名： 王文翰 职 称： 讲 师 题目类型：¨理论研究 ¨实验研究 þ工程设计 ¨工程技术研究 ¨软件开发2008年 6 月 5 日摘 要序列比对是生物信息学中的一个基本问题,通过序列比较可以发现生物序列中的功能、结构和进化的信息,序列比较的基本操作是比对。随着生物序列数据库中序列数据的激增，开发兼有高度生物敏感性和高效

2、率的算法就显得非常迫切。本文研究了生物信息学中的双序列和基于生物序列数据库的序列比对算法。通过C#语言结合面向对象与动态规划思想设计实现了一个包含Needleman-Wunsch、Smith-Waterman和BLAST算法的基于Windows操作系统的中文序列比对系统。其功能主要有序列查看，序列比对算法选择、参数选择，比对结果输出等。可分别适用与双序列间的全局比对、局部比对以及基于生物序列数据库的序列搜索。虽然系统实现的初期有一些不完善的功能。经过测试和修整，系统已经可以长时间稳定运行。用户通过使用该系统从数据库中搜索可以轻松获取基因序列功能、结构信息。从而可以进一步判断序列是否同源。该系统

3、的投入使用，可以在一定程度上提高生物工作者的工作效率，从而使得人力物力得到有效利用。加之本系统操作简洁明了，可以让更多对生物信息学学有兴趣的人能够加入到研究序列比对的队伍中来。关键词：生物信息学；数据库；序列比对 AbstractSequence alignment is a basic field in Bioinformatics.We may discover functional,structural and evolutionary information in biological sequences by sequence comparing. Because sequence

4、data increase rapidly in biology sequence database, it is very exigent to develop algorithms that have high biology sensitivity and efficiency.Pairwise and sequence alignment algorithms base in biology sequence database of Bioinformaics are studied in this Paper.And a Chinese sequence alignment soft

5、ware system which was based in Windows operating system and included Needleman-Wunsch, Smith-Waterman and BLAST algorithms was programmed in C# programme language with using the thought of the object-oriented and Dynamic programming.Its Main functional are show the sequence, choose the algorithms, p

6、references, Output and so on.The system should be used in the Global sequence alignment and the local sequence alignment in Pairwise sequence or to find out sequence in biology sequence database of Bioinformaics. Although the system realizes the initial period has some imperfect function. After the

7、test and the conditioning, the system already might be steady operation for a long time.Users could easily get functional and structural information in biological sequences by using this system to search in the database.Then they can Further judgement whether the Two species are Homology. The invest

8、ment of using the system will have a certain extent improve the biologist service potency,and then save a lot of manpower and resources. And the foundation systems operation is simple and brief, it may let more people who have the interest to the biological information sciences study can join compar

9、es to the Sequence alignment.Keywords: Bioinformatics;Database;Sequence Alignment目 录引言11 基因序列比对系统概述21.1 基因序列比对系统背景21.2 生物信息学简介21.3 序列比对系统的内容21.4 目的与意义31.5 国内外现状32 基因序列比对系统需求及相关技术52.1 业务需求52.2 硬件需求52.3 相关技术52.3.1面向对象技术简介52.3.2动态规划技术简介63 基因序列和序列比对算法83.1 基因资料83.2 序列比对83.2.1Needleman-Wunsch算法83.2.2Smith

10、-Waterman93.2.3Blast算法104 基因序列比对系统概要设计124.1 总体框架124.2 数据库格式说明124.3 系统实体图和ER图124.3.1系统实体图124.3.2系统ER图165 基因序列比对系统详细设计175.1 系统详细设计介绍175.2 系统数据流图175.3 序列管理模块185.4 参数设置模块205.5 双序列比对模块215.6 序列查询模块226 基因序列比对系统的实现246.1 系统界面的实现246.2 连接数据库的实现246.3 具体算法的实现256.3.1Needleman_Wunsch算法的实现256.3.2Smith_Waterman算法的实现

11、256.3.3Blast算法的实现267 基因序列比对系统测试277.1 界面初始化内容测试277.2 序列管理模块功能测试277.3 参数设置模块功能测试277.4 双序列比对模块功能测试287.5 序列查询模块功能测试287.6 测试环境298 结论30谢 辞31参考文献32附 录33引言由于最近几年生物测序工作的快速进展,基因和蛋白质序列数据量急剧增长,生物信息学面临着从海量的数据中发现新的规律和知识的任务。在生物信息学的研究中,有一个常用的方法,就是通过比较分析获取有用的信息和知识。最常用的比较方法是序列比对，它为两个或更多个序列的残基之间的相互关系提供了一个非常明确的图谱。序列比对是

12、通过对序列间的相似性进行打分,从而评估序列间相似性大小的一种方法。由于这种方法是生物信息学中进行其它诸如基因结构、功能等研究中的基本操作,因此比对方法的好坏在很大程度上决定这些研究的结果。将未知序列同已知序列进行比较分析已经成为一种强有力的研究手段 ，生物序列相似性比较中绝大部分的问题在计算机科学领域中主要体现为字符串的匹配和查找 。本文在对序列比对系统进行了全面的需求分析后，结合生物工作者的具休情况，对系统进行了设计与实现。该系统使用了目前比较流行的Microsoft Visual Studio 2005开发软件运用C#语言编程实现。其中采用了面向对象和动态规划的编程技术，极大的提升了系统的

13、性能与安全性。全文共分为七个部分，首先对基因序列比对系统的背景进行概述，其次是进行系统需求以及项目中所涉及的关键技术进行阐述，再次对系统的概要设计进行描述，最后详细叙述了系统的详细设计以及系统功能测试。1 基因序列比对系统概述1.1 基因序列比对系统背景当前人类基因组研究已进入一个重要时期，2004年已获得人类基因组的全部序列，这是基因组研究的转折点和关键时刻，意味着人类基因组的研究将全面进入信息提取和数据分析阶段，即生物信息学发挥重要作用的阶段。到1999年12月15日发布的第115版为止，GenBank中的DNA碱基数目已达46亿5千万，DNA序列数目达到535万；其中EST序列超过339

14、万条； UniGene的数目已达到7万个；已有25个模式生物的完整基因组被测序完成，另外的70个模式生物基因组正在测序当中；到2005年初为止，人类基因组的序列完成测定；同时功能基因组和蛋白质组的大量数据已开始涌现。如何分析这些数据，从中获得生物结构、功能的相关信息是基因组研究取得成果的决定性步骤。基因序列比对系统由此应需而生。1.2 生物信息学简介生物信息学是新发展起来的综合运用生物学、数学、物理学、信息科学以及计算机科学等诸多学科的理论方法的崭新交叉学科。生物信息学是内涵非常丰富的学科，其核心是基因组信息学，包括基因组信息的获取、处理、存储、分配和解释。基因组信息学的关键是“读懂”基因组的

15、核苷酸顺序，即全部基因在染色体上的确切位置以及各DNA片段的功能；同时在发现了新基因信息之后进行蛋白质空间结构模拟和预测，然后依据特定蛋白质的功能进行药物设计。了解基因表达的调控机理也是生物信息学的重要内容，根据生物分子在基因调控中的作用，描述人类疾病的诊断、治疗内在规律。它的研究目标是揭示"基因组信息结构的复杂性及遗传语言的根本规律"，解释生命的遗传语言。生物信息学已成为整个生命科学发展的重要组成部分，成为生命科学研究的前沿。1.3 序列比对系统的内容比较是科学研究中最常见的方法，通过将研究对象相互比较来寻找对象可能具备的特性。在生物信息学研究中，比对是最常用和最经典的研

16、究手段。最常见的比对是核酸序列之间的两两比对，通过比较两个序列之间的相似区域和保守性位点，寻找二者可能的分子进化关系。比对还是数据库搜索算法的基础，将查询序列与整个数据库的所有序列进行比对，从数据库中获得与其最相似序列的已有的数据，能最快速的获得有关查询序列的大量有价值的参考信息，对于进一步分析其结构和功能都会有很大的帮助。本系统正是针对序列间的两两比对与数据库搜索而设计。用户可以根据自己的需要选择不同的算法进行不同的操作。比如比较两条已知的序列，或在数据库中搜索与未知序列相似的序列。以获得有价值的信息。1.4 目的与意义自从1990年美国启动人类基因组计划以来，人与模式生物基因组的测序工作进

17、展极为迅速。迄今已完成了约40多种生物的全基因组测序工作，人基因组约3x109碱基对的测序工作也接近完成。至2004年，被誉为生命"阿波罗计划"的人类基因组计划，经过美、英、日、法、德和中国科学家的艰苦努力终于完成。这是人类科学世上又一个里程碑式的事件。截止目前为止，仅登录在美国GenBank数据库中的DNA序列总量已超过70亿碱基对。人类科学研究史表明，科学数据的大量积累将导致重大的科学规律的发现。例如：对数百颗天体运行数据的分析导致了开普勒三大定律和万有引力定律的发现；数十种元素和上万种化合物数据的积累导致了元素周期表的发现；氢原子光谱学数据的积累促成了量子理论的提出，

18、为量子力学的建立奠定了基础。历史的经验值得注意，有理由认为，今日生物学数据的巨大积累也将导致重大生物学规律的发现。数据并不等于信息和知识，但却是信息和知识的源泉，关键在于如何从中挖掘它们。由此可见研究序列之间的关系是十分必要的。而将未知序列同已知序列进行比较分析又正是一种强有力的研究手段。所以设计出一种更快，更准确的序列比对算法和序列比对系统是非常有意义的。1.5 国内外现状生物信息学的发展在国内、外基本上都处在起步阶段，所拥有的条件也大体相同，即使我国有关条件差一些，但差别也不大。目前最常见基因序列比对工具有FASTA工具和BLAST工具。FASTA是第一个被广泛应用的序列比对和搜索工具包，

19、包含若干个独立的程序。FASTA为了提供序列搜索的速度，会先建立序列片段的“字典”，查询序列先会在字典里搜索可能的匹配序列，字典中的序列长度由ktup参数控制，缺省的ktup=2。FASTA的结果报告中会给出每个搜索到的序列与查询序列的最佳比对结果，以及这个比对的统计学显著性评估E值。BLAST是现在应用最广泛的序列相似性搜索工具，相比FASTA有更多改进，速度更快，并建立在严格的统计学基础之上。NCBI提供了基于Web的BLAST服务，用户可以把序列填入网页上的表单里，选择相应的参数后提交到数据服务器上进行搜索，从电子邮件中获得序列搜索的结果。BLAST包含五个程序和若干个相应的数据库，分别

20、针对不同的查询序列和要搜索的数据库类型。其中翻译的核酸库指搜索比对时会把核酸数据按密码子按所有可能的阅读框架转换成蛋白质序列。BLAST对序列格式的要求是常见的FASTA格式。FASTA格式第一行是描述行，第一个字符必须是“>”字符；随后的行是序列本身，一般每行序列不要超过80个字符，回车符不会影响程序对序列连续性的看法。序列由标准的IUB/IUPAC氨基酸和核酸代码代表；小写字符会全部转换成大写；单个“-”号代表不明长度的空位；在氨基酸序列里允许出现“U”和“*”号；任何数字都应该被去掉或换成字母(如，不明核酸用“N”，不明氨基酸用“X”)。此外，对于核酸序列，除了A、C、G、T、U分

21、别代表各种核酸之外，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代表任意氨基酸；“*”代表翻译结束标志。2 基因序列比对系统需求及相关技术2.1 业务需求根据生物工作者与爱好者的需要，该系统需求如下：（1）可以以明文查看序列数据库中的某一条序列的具体信息，其中包括该序列的序列号，定义

22、，长度，数据内容等。（2）可以手动输入两条序列进行比对并根据选择的不同的算法和参数显示出比对结果。（3）可以把一条未知的序列与数据库中某一条特定的序列进行比对并根据选择的不同的算法和参数显示出比对结果。（4）可以把一条未知的序列与数据库中的某些序列进行比对并根据选择的不同的算法和参数显示出比对结果。（5）可以在数据库搜索出与未知序列最为匹配或者相似的序列。（6）可以对输入的序列字符串进行翻转旋转等操作。2.2 硬件需求处理器：Pentium IV级，1600MHz或以上内存：256M内存或以上硬盘：200M或以上空闲硬盘空间操作系统：Windows2000(sp0,sp1,sp2,sp3,sp

23、4)，WindowsXP(sp0,sp1)编程环境：Microsoft Visual Studio 20052.3 相关技术在为了提高系统的可靠性，可重用性、维护性以及运行效率，开发序列比对系统时主要运用了面向对象的开发方法和动态规划的编程技术。在规范了开发流程的同时也缩短了理论模型与实际的应用系统开发之间的差距。2.3.1面向对象技术简介面向对象是一种新兴的程序设计方法，或者说它是一种新的程序设计范型，其基本思想是使用对象，类，继承，封装，消息等基本概念来进行程序设计。 它是从现实世界中客观存在的事物（即对象）出发来构造软件系统，并在系统构造中尽可能运用人类的自然思维方式，强调直接以问题域（

24、现实世界）中的事物为中心来思考问题，认识问题，并根据这些事物的本质特点，把它们抽象地表示为系统中的对象，作为系统的基本构成单位（而不是用一些与现实世界中的事物相关比较远，并且没有对应关系的其它概念来构造系统）。这可以使系统直接地映射问题域，保持问题域中事物及其相互关系的本来面貌。 Peter Coad 和 Edward Yourdon提出用下面的等式识别面向对象方法：面向对象=对象(Object)+分类(classification)+继承(inheritance)+通过消息的通信(communication with message)。可以说，采用这4个概念开发的软件是面向对象的。类是构成面

25、向对象编程的基础，一个类定义了一组大体上相似的对象。一个类所包含的方法和数据描述一组对象的共同行为和属性。把一组对象的共同特征加以抽象并存储在一个类中的能力，是面向对象技术最重要的一点；是否建立了一个丰富的类库，是衡量一个面向对象程序设计语言成熟与否的重要标志。使用类来编程有如下好处：（1）类具有"独立性". 由于这种独立的存在,使得和其他的"过程也好,对象也罢"能够不彼此牵引.避免"牵一发而动全身"的局面.这有利于维护和调试. （2）类具有"通用性". 这种通用性,是通过抽象得来的.所谓抽象,就是抽取出事物的共同

26、特征并且加以概括.正是因为这种"通用性"的实现,才造就了"re-use"的可能. （3）类具有"灵活性". 由于第二个特征的存在,加上客观事物的特殊性,有可能通用的类中一部分成员方法变得"不通用",这个时候通过继承和Overload的机制,使得它能够应付某些特殊情况,从而实现了"灵活性".2.3.2动态规划技术简介动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程最优化的数学方法。它建立在最优原则的基础上。采用动态规划方法，可以优雅而高效地解决许多用贪婪算法或分

27、而治之算法无法解决的问题。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，以至于最后解决原问题需要耗费指数级时间。然而不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复了许多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，从而得到多项式时间的算法。为了达到这个目的，我们可以用一个表来记录所有已解决的子问题的答案。不管该

28、子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解，每个解都对应于一个值，我们希望找到具有最优值（最大值或最小值）的那个解。设计一个动态规划算法，通常可按以下几个步骤进行：（1）找出最优解的性质，并刻画其结构特征；（2）递归地定义最优值；（3）以自底向上的方式计算出最优值；（4）根据计算最优值时得到的信息，构造一个最优解。步骤（1）（3）是动态规划算法的基本步骤。在只需要求出最优值的情形下步骤（4）可以省略。若需要求出问题的一个最优解，则必须执行步骤（4）。此时，在步骤（3）中计

29、算最优值，通常需记录更多的信息，以便在步骤（4）中根据所记录的信息，快速构造出一个最优解。3 基因序列和序列比对算法3.1 基因资料DNA,即脱氧核糖核酸。DNA是由脱氧核苷酸和碱基间通过碱基互补配对,在氢键的作用下形成的双螺旋结构.在脱氧核苷酸内部,磷酸基和脱氧核糖是通过3,5磷酸二脂键连接的.DNA是反向(向右)双螺旋结构. DNA的碱基有4种，分别是腺嘌呤(Adenine)、鸟嘌呤(Guanine)、胞嘧啶(Cytosine)和胸腺嘧啶(Thymine)。DNA 链是称为核苷酸 的小单元组成的序列。为了回答某些重要的研究问题，研究人员把基因串看作计算机科学的字符串 也就是说，可以忽略基因

30、串的物理和化学性质，而将其想像成字符的序列。比如说A 和 T 是互补的碱基对，C 和 G 也是互补的碱基对。这意味着一个链中的 A 与另一个链中的 T 组成一对（反之亦然），一个链中的 C 与另一个链中的 G 组成一对（反之亦然）。所以，如果知道一个链中的 A、C、T 和 G 的顺序，那么就能推导出另一个链中的顺序。所以，可以将一条 DNA 链想像成由字母 A、C、G 和 T 组成的字符串。3.2 序列比对基因学的一个主要主题就是比较 DNA 序列并尝试找出两个序列的公共部分。如果两个 DNA 序列有类似的公共子序列，那么这些两个序列很可能是同源的。在比对两个序列时，不仅要考虑完全匹配的字符，

31、还要考虑一个序列中的空格或间隙（或者，相反地，要考虑另一个序列中的插入部分）和不匹配，这两个方面都可能意味着突变。在序列比对中，需要找到最优的比对（最优比对大致是指要将匹配的数量最大化，将空格和不匹配的数量最小化）。如果要更正式些，您可以确定一个分数，为匹配的字符添加分数、为空格和不匹配的字符减去分数。比对的算法可分为两类：全局比对和局部比对。本文主要研究了其中的Needleman-Wunsch、Smith-Waterman和Blast算法。其中Needleman-Wunsch算法主要运用于序列间的全局比对，Smith-Waterman算法主要运用于序列间的局部比对，而Blast算法则主要运用

32、于在大型序列数据库中搜索与用户输入的序列相似的序列。3.2.1Needleman-Wunsch算法Needleman-Wunsch算法由Bellman于50年代提出。这个算法使用二维表格，一个序列沿顶部展开，一个序列沿左侧展开。而且也能通过以下三个途径到达每个单元格：（1）来自上面的单元格，代表将左侧的字符与空格比对。 （2）来自左侧的单元格，代表将上面的字符与空格比对。 （3）来自左上侧的单元格，代表与左侧和上面的字符比对（可能匹配也可能不匹配） 然后计算出两个序列的相似分值，存于这个二维表格中。根据此表格，按照回溯的方法寻找最优的比对序列。Needleman-Wunsch算法可用伪代码表示

33、如下：前提条件，用于填充二维表格的第一行与第一列：分数(0,0)=0分数(i,0)= 分数(i-1,0)+ 匹配得分(前提序列第i个字符,空位)分数(0,j)= 分数(0,j-1)+ 匹配得分(空位, 命中序列第j个字符)递归关系,用于填充二维表格的其余位置： 分数(i-1,j-1)+ 匹配得分(前提序列第i个字符, 命中序列第j个分数(i,j)=最大值 字符,) 分数(i-1,j)+ 匹配得分(前提序列第i个字符,空位) 分数(i,j-1)+ 匹配得分(空位, 命中序列第j个字符)回溯，根据填充完毕的二维表格的分值还原出两条序列的最优比对：for ( i = 前提序列的长度，j = 命中序列

34、的长度; i > 0 && j > 0;) if (分数i, j = 分数 i 1, j 1 + 是否相同(前提序列的第i个字符, 命中序列第j个字符) i ; j ; else if (分数i, j =分数 i 1, j +是否相同(前提序列的第i个字符, 空位 ) i ;在命中序列的第j个字符上插入空位 else if (分数i, j =分数 i, j1 +是否相同(空位, 命中序列第j个字符) ) j ; 在前提序列的第i个字符上插入空位; 至此，前提序列和命中序列都已为最佳比对。一般来说规定每个匹配字符一分，一个空格扣两分，一个不匹配字符扣一分。 3.2.2

35、Smith-Waterman在生物学中局部比对比全局比对更具有实际的意义。Smith-Waterman算法致力于发现两条序列在哪一些局部的区域内具有很高的相似度。在 Smith-Waterman 算法中，不必比对整个序列。两个零长字符串即为得分为 0 的局部比对，这一事实表明在构建局部比对时，不需要使用负分。这样会造成进一步比对所得到的分数低于通过 “重设” 两个零长字符串所能得到的分数。而且局部比对不需要到达任何一个序列的末端，所以也不需要从右下角开始回溯，可以从得分最高的单元格开始回溯。这导致 Smith-Waterman 算法与 Needleman-Wunsch 算法存在着三个区别。首先

36、，在初始化阶段，第一行和第一列全填充为 0（而且第一行和第一列的指针均为空）。第二，在填充表格时，如果某个得分为负，那么就用 0 代替，只对得分为正的单元格添加返回指针，最后，在回溯的时候，从得分最高的单元格开始，回溯到得分为 0 的单元格为止。除此之外，回溯的方式与 Needleman-Wunsch 算法完全相同。Smith-Waterman算法可用伪代码表示如下：前提条件，用于填充二维表格的第一行与第一列：分数(i,0)= 0分数(0,j)= 0递归关系,用于填充二维表格的其余位置。并找出分数最高的格子的位置分数(i-1,j-1)+ 匹配得分(前提序列第i个字符, 命中序列第j个字符,)分

37、数(i,j)=最大值 分数(i-1,j)+ 匹配得分(前提序列第i个字符,空位) 分数(i,j-1)+ 匹配得分(空位, 命中序列第j个字符) 回溯，根据填充完毕的二维表格的分值从分数最高的格子开始回溯还原出两条序列的最优比对。回溯方式同Needleman-Wunsch 算法。3.2.3Blast算法本文介绍了 Needleman-Wunsch 和 Smith-Waterman 算法的基本实现，查找全局和局部比对的时间为 O(mn)。实际的研究人员通常不是比较两个序列，而是试图找出与特定序列相似的所有序列。如果发现某个相似序列具有已知的生物学功能，那么原来的序列也很有可能具有相似的功能，因为相

38、似的序列通常会有相似的功能。如果直接使用 Smith-Waterman 算法在数据库里搜索，即使使用具有二次数量级的运行时间，将输入序列与超大型基因序列数据库的每个序列（每个序列可能还包含 30 亿或者更多个碱基对）进行比对还是太慢。这种时候就要考虑Blast算法了。Blast是一种启发式算法，通过比对(alignment)在数据库中寻找和查询序列(query)相似度很高的序列!。两个序列的最大片段对（MSP，maximum segment pair）就是最高得分的片段对。这个得分是序列相似性的度量，可以利用动态规划算法准确地算出。但是，BLAST却能比任何基于动态规划的算法更快地估计最高得分

39、值。在进行序列两两比较之前，BLAST首先寻找一颗“种子”，它是两个序列之间的一个非常短的片段对。种子可以向两个方向扩展，直至达到扩展的最大可能的得分。程序对何时停止扩展有一个判断准则，即当扩展的得分低于某个计算的下限时，停止扩展。是正确的扩展但未被发现的可能性非常小。BLAST的计算过程分为三个阶段：（1）生成单词表。单词表由所有长度等于设定步长的连续字符串组成。种子可以通过在序列中滑动获得。例如设定步长为4，则一个DNA序列ACGCGT有ACGC,CGCG,GCGT这3个种子。（2）搜索种子。把单词表里这些单词组织在一个哈希表（hash table）中，对于数据库中的每个长度为设定步长的单

40、词，取它们在哈希表中的对应下标，并将它们与哈希表该位置上的所有单词（高得分单词表的一部分）进行比较。若相同则找到一颗种子。由于单词表可能很大，用一般的数据组织方法查询速度慢，而用哈希表可以实现直接寻址，提高查询速度。（3）扩展种子。最后一步扩展过程比较直观。当扩展时的得分低于该扩展前面的最佳得分的某个下限时，扩展停止。扩展是双向的，并保存从对应种子扩展而得到的高得分片段对。4 基因序列比对系统概要设计4.1 总体框架基于对生物工作者的需求的研究，该系统的设计可分为为界面和操作两个结构。界面部分主要负责显示经过操作部分处理回馈回来的结果和对操作部分一些必要的参数进行设置。4.2 数据库格式说明该

41、系统支持标准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(

42、强)；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.3 系统实体图和ER图4.3.1系统实体图图4.1 Cell实体及其属性图每一个Cell类的实体代表分值二维表格里的一个格子。它的属性分别如下：PrevCell：也是一个Cell类的实体，表示这个实体的前置格子Col：表示该格子在二维表格里的列号Row：表示该格子在二维表格里的行号Score：表示该格

43、子上的比对分值 图4.2 CellAction实体及其属性图CellAction类里主要封装了对序列的各种操作函数，其属性分别如下：FirstSequence：待分析序列1SecondSequence：待分析序列2TmpSequence1：临时序列1TmpSequence2：临时序列2Cells：一个Cell类的实体数组，用来模拟一个二维表格TmpCell：一个临时的格子，用于记录二维表格中的最值InitScore：用于记录比对开始时的初始分值Tmpnum：用于临时记录比对中最值的序列号Dnanum：用于保存比对中最值的序列号Bhseq1：用于保存经过处理后的待分析序列1Bhseq2：用于保存

44、经过处理后的待分析序列2Scorelist：用于保存进行Blast算法比对后的分值列表ArrBlast：用于传递Blast风格的输出序列信息图4.3 DNA实体及其属性图DNA类主要用于逐条输出比对结果，其属性分别如下：DnaNumber：DNA序列的序号DnaSequence：DNA序列的序列内容图4.4 Seed实体及其属性图Seed类主要描述Blast算法里种子和命中序列的情况。其属性分别如下：Seeds：种子序列Queryindex：种子序列的开始位置Sbjct：命中序列Sbjctindex：命中序列的开始位置Socre：比对分值Highsocreindex：种子和命中序列比对的最高分

45、值开始位置Highsocreend：种子和命中序列比对的最高分值结束位置Identities：种子和命中序列的匹配百分比图4.5 Options实体及其属性图Options类主要是封装了对各算法的参数，其属性分别如下：W：步长M：匹配分值N：不匹配分值Y：中止阈值S：最小分值图4.6 BlastOutput实体及其属性图BlastOutput类主要用来保存Blast风格的序列比对输出结果，其属性分别如下：Number：表示与未知序列进行比对的已知序列的序列号Highscore：表示某条已知序列和未知序列比对的各种结果中的最高分值Seq：表示两条序列比对的情况Length：表示该已知序列的 长度

46、4.3.2系统ER图图4.7 系统ER图5 基因序列比对系统详细设计本基因序列比对系统为生物工作者使用的序列比对及搜索工具，在进行了充分的客户调研和概要设计后，本系统分为序列管理模块、参数设置模块、双序列比对模块和序列查询模块。5.1 系统详细设计介绍根据系统的概要设计，界面部分通过Visual Studio封装好的Windows窗体来实现。功能部分则新建一个名为“Class”的文件包，里面存放所有操作类。比如其中BlastOutput.cs用于控制输出Blast风格的比对查询结果；Cell.cs用于表示二维分数表格里的每一个格子；CellAction.cs里主要存放绝大部分算法函数；Opti

47、ons.cs用于存放用户所作的参数设置。同时，为了代码更具有重用性，系统还专门用一个类Module.cs来存放那些需要被重复调用的函数，比如过滤字符串函数等。5.2 系统数据流图图5.1 序列比对系统顶级数据流图图5.2 序列比对系统1级数据流图5.3 序列管理模块在本模块中，主要有三种操作：查看序列，编辑序列和保存序列。其中保存序列又可分为在原有数据库文件中保存和导出到新的数据库文件。查看序列：从序列数据库中读入序列信息后，主界面左边的列表框中会显示数据库中存在的序列，选中后某一条序列后，列表框右下方的序列基本信息栏会显示出该条序列的基本信息，如：序列号，序列长度，序列的存储格式和路径等。如

48、果想更进一步了解该序列的内容则可通过点击列表框下方的“查看所选序列”按钮来打开该序列的信息窗体。在该窗体不同碱基用不同的颜色来显示，十分直观。如下图所示图5.3 序列管理模块流程图图5.4 查看序列编辑序列：在查看序列窗体中可以对序列进行编辑。关闭该窗体时如序列内容已经发生了改变则提示保存。保存序列：在原有数据库文件中保存序列的流程基本同上，主要要说明将序列导出到新的数据库文件。由于序列数据库的数据量太大，而生物工作者们研究的往往只是整个数据库中的某一些特定的序列。所以，在本系统中用户可以通过在列表框中选中一条或复述条序列导出到一个新的数据库文件里。下次进行查询时所花费的时间就可以大大减少了。

49、5.4 参数设置模块不同的比对算法会有不同的参数要求，比如Needleman-Wunsch、Smith-Waterman要求知道两个碱基之间匹配对应分值。通常来说匹配一个字符加1分，不匹配字符减1分，引入一个空位减2分。而Blast不同于前面两种算法，它是一种启发式算法，要设置的参数相对较多。除了匹配分值外还有步长、阈值和最小分值等。设置不同的参数会对比对的结果造成影响，比如把步长设置得长一些可以提升比对的速度而同时也会降低比对的灵敏度。所以设置参数时一定要慎重。参数设置成功后，将会产生一个Options类的实体。当各算法要用到这些参数时可以通过读取这个实体相应的属性来获得。图5.5 参数设置

50、模块流程图图5.6 参数设置5.5 双序列比对模块在本模块中，用户可以选择手动输入两条序列利用不同算法来进行比对，也可以输入一条序列并将该条序列与数据库中的某条序列进行比对。可供选择的比对算法有三种：Needleman-Wunsch、Smith-Waterman和Blast。一般来说双序列比对不会选择用Blast算法，而倾向于选择灵敏度和精度更高的Needleman-Wunsch和Smith-Waterman算法。用户可以根据需求自行选择合适的算法。图5.7 双序列比对模块流程图比对结束后，将显示比对结果。两序列中相同的部分用红色表示，空位用”_”表示。值得一提的是由于Blast算法的特殊性，

51、选择它后会有不同的显示输出效果。图5.8 比对结果5.6 序列查询模块本模块是该系统的核心模块。在这里用户可以通过输入一条序列，然后在数据库中检索与该序列相似的序列。可供选择的算法同样有三种：Needleman-Wunsch、Smith-Waterman和Blast。不过由于Needleman-Wunsch和Smith-Waterman算法的时间复杂度过高，在实际大型数据库中进行搜索时显得有点不切实际。一般选用Blast算法。用Needleman-Wunsch、Smith-Waterman算法进行查询时，系统根据比对分值的高低只会显示最高分值的比对。而用Blast算法进行查询时，系统会返回经过

52、排序后的所有适合的比对结果。图5.9 序列查询模块流程图图5.10 Blast比对结果6 基因序列比对系统的实现6.1 系统界面的实现一个好的界面是一个系统成功的一半。所以设计一个简洁明了，美观协调的同时又具易用合理的界面就显得十分必要了。本系统采用Microsoft Visual Studio 2005 自带的winform窗体来制作界面。整个界面布局合理，所有功能一目了然，并且很符合用户的操作习惯。图6.1 系统主界面截图6.2 连接数据库的实现本系统采用的数据库格式是基因序列标准的保存格式FASTA格式。它是一种类似于文本文件的静态数据库。鉴于这种特点，本系统是通过如下方式实现连接并读取

53、其中的信息的：（1） 首先在主窗体上添加一个OpenFileDialog，当选择打开数据库时将弹出对话框让用户选择要打开的文件的路径。用户选择了数据库后把路径保存下来；（2） 在公用模块类Module.cs里添加一个静态函数GetSequences。它通过接收从步骤一中所得的路径新建一个StreamReader类的实体并打开所选路径的文件；（3） 逐行扫描，当当前一行的第一个字符为”>”时，说明这是一条序列的序列号，保存下来。若第一个字符不为”>”则说明这是一条序列序列内容的某一行，追加保存。（4） 把步骤三获得的序列号和序列内容追加到一个链表，暂存下来以供调用。步骤四中的链表既为

54、数据库在系统中的缓存。6.3 具体算法的实现6.3.1Needleman_Wunsch算法的实现Needleman_Wunsch算法的实现主要是依靠CellAction.cs类里的两个函数：Needleman_Wunsch和TracebackNW。其中Needleman_Wunsch用来填充比对的分值二维表格，TracebackNW用来根据二维表格的分值进行回溯已找出最优的比对结果。Needleman_Wunsch的功能可以用如下步骤来表示：（1）新建一个行和列分别是两个待比对序列的长度的二维表格，即一个二维的Cell类实体的数组。（2）初始化表格里每个格子的分数，其中左上角的格子的分值为0（3）根据每一个格子和它周围的格子的分数的算数关系给每个格子赋值，并记录他们的前置格子TracebackNW的功能可以用如下步骤来表示：（1）根据二维表格的分值从表格的右下角格子开始寻找回溯路径（2）比较两条经过处理后的序列的长度，长度小的在前面插入相应的空位6.3.2Smi