随着生物学中高通量的实验方法,如基因测序、DNA芯片等的使用,产生了海量的数据。如何有效地理解并利用这些数据,阐明数据当中所蕴含的生物学意义是生物信息学的主要目的。生物信息学的一个重要研究领域是对生物序列进行比对和聚类。本文就多重序列比对和蛋白质聚类方面进行了深入的探讨和研究,主要的研究内容和结果如下:1.综合研究并分析了近年来多重序列比对方法存在的问题及改进情况。多重序列比对是生物信息学的基本理论与方法之一,对结构建模,功能位点预测,进化树分析等方面起着非常关键的作用。本文综述了近年来的一些比对方法上的改进,如使用快速的方法计算序列的相似度,运用迭代优化策略和序列一致性信息等,并阐述了综合序列的结构信息和同源序列进行比对的方法。最后综述了一些对于比对质量的评估的方法和测试数据集以及比对速度的问题。2.提出了一种改进Kalign比对质量的算法。Kalign算法是一种常见的多重序列比对算法,然而由于对序列的距离估计不准导致比对的质量不高。本文提出了一种改进Kalign比对质量的算法,根据Kalign最初比对的结果,计算出新的两两序列之间的距离,然后使用UPGMA(Unweighted Pair Group Method Average,不加权成对分组平均)方法构建向导树,再进行渐进比对,产生新的比对结果。重复这一过程,直到比对的SP得分不再改变或者达到一定迭代次数为止。本文用BAliBASE 3.0对改进后的Kalign算法进行了测试,结果显示该算法较好地改进了Kalign的比对质量。3.提出了一种快速多重序列比对算法。本文使用了一种类似BLAST的算法来快速地估计序列之间的距离,并且为了能够比对大量的序列,采用了节省空间的动态规划算法来比对序列,使用ROSE程序生成的具有不同序列长度和数量的测试集。本文提出的算法在运行时间、比对质量和内存的使用上和其他常用的程序相比,算法在速度上是最快的程序之一,在比对分化大的序列时质量最好,而且使用的内存相对较少。4.提出了一种新的计算蛋白质序列相似度的算法。该算法基于相似子序列和序列的L-tuple频率,充分考虑了两个序列之间的相似子序列和非相似子序列之间的相似度,使用新近提出的一种聚类算法—仿射传播聚类(Affinity Propagation,AP),对蛋白质序列进行聚类,并在COG、G-protein、CAZy和SCOP四个数据集上进行了测试。结果表明新的相似度度量方法能够更好地描述蛋白质序列之间的相似度,特别是对那些很难比对的序列。5.分析了使用AP算法聚类随机产生的数据集时出现的性能上的问题,并发现AP算法不能通过调整其参数preference来得到更合理的结果的问题。为了解决这个问题,本文提出了一种对AP算法的结果进行后处理的算法。这种算法使用输入相似度的中值作为preference,利用简单合并和重分配算法对聚类的结果进行重新聚类。本文将改进的算法和原始的AP算法及其他几个常用的算法在COG、SCOP和G-protein数据集上进行了比较,结果表明:在比对质量上,改进的算法比原始的AP算法提高很多,比其他的常用算法也有所提高。