蛋白质数据库去冗余程序的研究与开发

摘要

许多生物序列数据库中都含有大量的冗余序列，这些冗余序列通常不利于对数据库的统计分析和处理，而且它们要占用更多的计算机存储和处理资源。去除这些冗余信息具有很高的实用价值，不但可以减小数据库的大小提高序列搜索的速度，而且有助于对数据库的统计分析。目前存在不少蛋白质去冗余程序，它们多数采用Hobohm和Sander的算法来生成代表序列以达到去除冗余序列的目的。然而，这种算法生成的代表序列集合不是足够大的，某些非冗余的蛋白质序列也被去除了。 在本文中，我们对蛋白质去冗余问题进行了深入的分析和研究，主要研究内容和取得的成果如下： 1．改进了Hobohm和Sander的算法：我们基于图论最大独立集的概念来生成非冗余序列集合，对目前存在的蛋白质去冗余程序如CD—HIT、PISCES等所采用的由Hobohm和Sander最早设计的一种首先将序列集合分成若干个簇然后取出每个簇的代表序列的算法进行了改进，使得生成了更大的非冗余代表序列集合，避免了一些非冗余的序列也被去除。 2．基于上述改进算法，开发了两个版本的FastCluster：第一个版本基于全局比对算法来确定序列之间的相似度，提供了一种从全局比对角度来去除冗余序列的程序，其缺点在于运行速度较慢，不太适合处理大规模的数据集；第二个版本采用了Blast来确定序列之间的相似度，提高了运行速度，可以在较短的时间内处理较大规模的蛋白质数据库。FastCluster的下载地址是： http://pcal.biosino.org/FastCluster.html． 3．建立了蛋白质序列数据库的无向图模型，并开发了相应的程序BlastCuller：一个蛋白质序列集合可以看作是一个无向图，序列对应图中的顶点，如果两个序列之间的相似度超过某个设定的阈值则这两个序列之间存在一条边。基于该模型开发的BlastCuller不仅具有很高的实用价值，能够处理较大规模的蛋白质序列数据库，而且为去冗余问题提供了一个有效的可扩展的程序框架，可以加入新的算法来更好地解决去冗余问题。BlastCuller的下载地址是：http://pcal．biosino.org/BlastCuller.html． 测试数据证明，本文所设计的生成非冗余代表序列的改进算法具有很强的实用性，有效地避免了一些非冗余的序列也被去除，生成了更多的非冗余代表序列集合；基于无向图模型所开发的BlastCuller程序具有较好的通用型和扩展性，可以在其基础上对去冗余问题做进一步的研究。

目录

文摘

英文文摘

声明

第1章绪论

1.1引言

1.2相关研究工作

1.3本文所做的工作

1.4本章小结

第2章背景知识

2.1生物信息学简介

2.2分子生物学基础

2.2.1 DNA

2.2.2蛋白质

2.2.3基因和基因组

2.2.4序列数据库

2.3生物信息学主要内容

2.3.1序列比对

2.3.2结构比对

2.3.3蛋白质结构预测

2.3.4计算机辅助基因识别

2.3.5非编码区分析和DNA语言研究

2.3.6分子进化和比较基因组学

2.3.7序列装配

2.3.8遗传密码的起源

2.3.9基于结构的药物设计

2.3.10其他

2.4序列比对

2.4.1概述

2.4.2序列两两比对和多重序列比对

2.4.3数据库搜索

2.5生物信息学相关软件包介绍

2.5.1 BioJava

2.5.2 BioPython

2.5.3 BioPerl

2.6本章小结

第3章FastCluster的设计与实现

3.1 FastCluster简介

3.2程序流程图

3.3算法描述

3.3.1 Hobohm和Sander的算法

3.3.2基于图论的算法

3.4算法比较

3.5例子说明

3.6程序实现

3.7实验结果

3.8本章小结

第4章BlastCuller的设计与实现

4.1 BlastCuller简介

4.2程序流程图

4.3算法描述

4.3.1.基于Blast的相似度

4.3.2基于图论的算法

4.4程序实现

4.5实验结果

4.6本章小结

第5章FastCluster与BlastCuller的比较

5.1实验结果

5.2非冗余序列数目与阈值关系图比较

5.3运行时间

5.4本章小结

第6章结论与展望

附录

参考文献

致谢