论文部分内容阅读
许多生物序列数据库中都含有大量的冗余序列，这些冗余序列通常不利于对数据库的统计分析和处理，而且它们要占用更多的计算机存储和处理资源。去除这些冗余信息具有很高的实用价值，不但可以减小数据库的大小提高序列搜索的速度，而且有助于对数据库的统计分析。目前存在不少蛋白质去冗余程序，它们多数采用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程序具有较好的通用型和扩展性，可以在其基础上对去冗余问题做进一步的研究。