本论文的研究内容是从结构的角度，通过在进化过程中相对保守，并且相互作用的结构域(domain)来描述蛋白质的相互作用。为此我们首先基于序列相似性的比较对生物序列数据进行了同源(haomologous)聚类，同时我们归纳合并了所有已知的酵母和果蝇的蛋白质相互作用数据，对其进行评估，提炼出高可信的相互作用数据。我们的聚类技术和评估策略可以应用于其它生物物种的聚类分析和相互作用的评估。 因为生物系统在蛋白质相互作用网络方面是保守的，即从序列到结构，进而到相互作用网络都存在着某种生物共性，这种共性或者一致性(universality)通常可以描述为一种模式保守的蛋白质相互作用网络，而该网络的基本构成单元就是蛋白质结构域。由于当前蛋白质相互作用数据主要来自序列的相互作用，每条蛋白质序列可能含有多条保守的结构域，这样相互作用的可能性就会成指数级的增长，使得寻找某一相关的相互作用变得异常困难。因此需要到找一种确定结构域之间相互作用的途径。为此我们对蛋白质序列进行了结构域的划分和映射，并采用机器学习的方法提取出结构域之间的相互作用。考虑到当前只有一小部分结构域具有三维结构信息，我们在论文中提出了一种系统的预测同源结构的方法。特别是我们构建了基于结构域聚类的模板数据库，提高了模板的涵盖范围。另外我们提出了一种以模板的三维结构比对作为profile或者anchor的比-对算法，有效的提高了未知序列同相应模板之间的比对准确性，进而提高了预测结构的质量。数据分析显示，我们的方法可以是现有的同源建模(Homology Modeling)算法预测出近三分之二的蛋白质结构。最后，我们同时采用rigid body和flexible这两种对接工具来研究结构域对接后所形成合成体的同源和一致性。 本论文的组织结构如下： 第一章绪论，简要介绍了该论文的研究背景和意义，对蛋白质相互作用网络拼接过程中所涉及到的研究内容和方法进行了分类介绍，并结合现有方法总结了所涉及研究内容存在的问题。 第二章基于序列和结构域相似性的蛋白质序列聚类。本论文的研究内容是从结构的角度，拼接出蛋白质的相互作用网络，因此本课题的第一步工作是对蛋白质序列进行聚类分析，我们的目的是将直向同源物进行(orthologs)聚类。首先我们利用BLSTAP算法对蛋白质序列进行相似性比较，构建出比对间的相似距离矩阵，同时将蛋白质结构域作为一个附加的准则来筛选出假的同源关系。然后将剩余的比对用图论的理论进行描述：节点为序列，边为两条序列间的对应关系。最后我们采用Markov graph-flow算法对其进行聚类分析。利用该算法，我们对六种真核生物的序列进行了聚类分析，其结果要明显优于NCBI和TIGR的聚类结果。 第三章蛋白质相互作用数据的整合。蛋白质—蛋白质相互作用是系统生物系的研究核心，生物体的各种代谢和调控途径都是有蛋白质—蛋白质相互作用来体现的。但是通过试验手段获得的相互作用数据包含着很多的错误，曾经的统计表明：仅仅有10％的相互作用数据可以支持不同的、独立的试验，而近50％的相互作用数据是假阳性的。针对这一问题，我们首先合并了所有的公共数据库(11个)中关于酵母和蠕虫的蛋白质相互作用数据，通过交叉验证(cross-reference)并结合序列的信息，对这些数据进行了提炼，删除了其中的冗余信息。然后我们采用机器学习的方法对每一种实验方法赋予一定的权值，这样对于每一个蛋白质相互作用可以获得一个分值，最终根据设置不同的cutoff可以筛选出高可信度(高分值)的相互作用数据。 第四章基于序列保守结构域(domain)的同源建模算法。蛋白质三维结构特征是蛋白质功能分析、蛋白质相互作用、进化树构建和药物设计等研究的基础。通常蛋白质结构的确定取决于X-射线晶体衍射和核磁共振等试验方法，但是X-射线晶体衍射法非常耗时，核磁共振又无法准确地测定大蛋白质分子的结构。因此，利用计算技术开发准确、快速的蛋白质三维结构预测算法就显得尤为关键和迫切。目前蛋白质结构的预测算法主要分为以下三类：同源建模(Homology Modeling)、结构模式预测(Threading)和从头预测(ab initio)。其中同源建模法采用已知的蛋白质结构作为模板，可以准确地预测其它同源蛋白质的结构，被认为是当前最成功的预测算法。 第五章基于结构的蛋白质相互作用网络的拼接。因为蛋白质相互作用是通过保守的结构域来体现的，因此结构域被认为是生物系统的最基本单位(building blocks)。综合上述各章的研究成果，在所有的酵母、蠕虫和果蝇的序列中，我们从46,742个蛋白质同源聚类中提取出了135,744条蛋白质相互作用，其中有6,679个蛋白质同源聚类包含有多个物种，约占总数的15％。采用最大相似度估计(Maximum Likelihood Estimation，MLE)算法，我们将这些蛋白质相互作用精简成33,068条结构域间的相互作用，构建出了结构域之间的相互作用映射。另外，利用我们的同源建模算法，我们成功的预测出了酵母、蠕虫或者果蝇的167,300条蛋白质结构。我们从相互作用映射中挑选出至少含有3个已知结构，并且分别源自同样的三个物种的相互作用对(interaction pair)，以此来确保其同源性。最后利用刚体(rigid-body)和柔性(flexible)的对接(docking)工具，即Zdock和Rosetta，从结构域的角度论证了同源蛋白质相互作用的保守一致性，为蛋白质相互作用网络的拼接提供了理论依据。 第六章结论。系统总结了该论文的各项研究成果，并讨论了下一步的工作。 附录一基于Smith-Waterman算法的生物序列并行比较。生物序列相似性比较是生物信息学中最常见的问题，其中基于动态规划思想的Smith-Waterman算法是相似性比较中最流行的算法。然而现有的并行Smith-Waterman都需要庞大的内存，随着生物数据的急剧增长，并行Smith-Waterman算法内存空间的需求已经成为一个需要紧迫解决的问题。基于这一问题，我们提出了一种基于分而治之策略的并行Smith-Waterman算法，PSW-DC算法。其基本思想是：采用数据分割的方法给每个处理器分配一定的数据，然后每个处理器独立的运行Smith-Waterman算法，最后再把各个处理器计算的结果进行合并，得到局部最优比对序列。与现有的并行Smith-Waterman算法相比，该算法对内存空间的需求有了很大的降低。在曙光20001并行机上进行了模拟试验，有效降低了算法对内存的需求，提高了算法的运算速度。 论文的主要贡献本论文在蛋白质序列同源聚类、蛋白质相互作用的评估和验证、蛋白质空间结构的预测、蛋白质相互作用网络的拼接以及生物序列比对等关键问题上展开研究，取得如下成果： 1．在蛋白质序列同源聚类方面，如何准确、快速、自动的对蛋白质序列进行聚类一直是研究人员在努力解决的难题。基于蛋白质结构域序列的相似性，本文提出一种准确的蛋白质序列同源聚类方法。该方法利用Markov Graph-Flow算法，可以自动、准确的聚类orthologs(直向同源物)and in-paralogs(横向同源物)。对多个物种序列的 聚类结果显示，其结果的精确度比NCBI和TIGR的结果有明显的提高。该方法可以应用于所有已知真核生物的序列聚类中，能够大幅提高聚类结果的准确性。 2．通过试验确定的蛋白质相互作用都存在一定范围的误差。我们合并了所有yeast和worm的蛋白质相互作用数据，提出了一种评价和交叉验证蛋白质相互作用的方法。该方法采用机器学习的理论，从进化的角度对每一相互作用的可信度进行了评价。试验结果显示，该方法可以筛选出高可信度的相互作用。另外该方法可以评价其它物种蛋白质相互作用的可信度。 3．蛋白质空间结构的预测一直是国际上研究的热点和难点问题。本文为了解决同源比较建模(IIomology Modeling)算法的两个瓶颈问题：模板的选择和目标一模板序列比对的准确性，提出了相应的解决方案，完善了同源建模算法。在模板选择方面，我们以结构域为基础，通过构建模板库极大的提高模板的涵盖范围；针对目标一模板序列比对的准确性问题，我们基于结构域的三维结构信息，提出了一种新的序列比对算法，该算法能够产生更准确的目标一模板序列比对。采用所提出的方法，极大拓宽了已有同源建模算法的应用范围。更精确的预测出了更多的蛋白质结构。 4．在蛋白质相互作用网络的拼接方面，由于确定结构域一结构域的相互作用一直是一个研究难点，本文根据已知的蛋白质一蛋白质相互作用关系，构建出结构域一结构域的相互作用映射。通过蛋白质对接(docking)程序，我们从结构域的角度论证了同源蛋白质相互作用的保守一致性，从而为蛋白质相互作用网络的拼接提供了理论依据。 5．生物序列的相似性比较是生物信息学中最常见的问题，其中基于动态规划的smith-waterman算法是最基本的算法之一。然而该算法的运算速度以及对内存的需求严重制约着算法的应用。我们提出了一种基于分而治之策略的并行smith-waterman算法，大幅降低了算法的存储需求，并有效地提高了算法的运行速度，扩展了该算法的应用范围。