在生物体中,催化酶反应、疫苗培育、器官体外重建等多种生物过程都是通过蛋白质之间的相互作用以及蛋白质与其他分子间的相互作用实现的。蛋白质分子三维结构和物化性质这些基本信息可以用于预测蛋白质之间的相互作用。本文研究了以下三个问题：蛋白质分子对接过程的计算、两个蛋白质分子间结合位点的预测、多个蛋白质形成复合体三维构象的预测。当今,计算机有能力计算数据量巨大的预测模型,因此研究人员可以通过蛋白质三维结构模型和分子对接方法预测复合体三维构象。在计算生物学中,分子对接方法通过使用空间匹配信息和能量匹配信息模拟多个蛋白质分子之间的相互作用过程。空间匹配信息决定了分子间是否发生相互作用,能量匹配信息决定了分子是否能够稳定结合。分子对接方法在药物设计、材料设计等领域有着广泛的应用,可以分为刚性对接和柔性对接两大类。刚性对接不改变每个对接分子的三维构象,仅通过改变分子间的相对位置和方向来确定对接过程。柔性对接允许分子自身构象在对接过程中发生变化,计算量较大,但可以预测分子对接后的结构变化情况。本文设计了两个刚性分子对接方法。我们可以通过刚性移位操作来预测蛋白质分子的对接结果。在刚性分子对接中,我们必须保证两个对接分子的三维结构均不发生变化,通过改变两个分子之间的相对位置和方向来预测复合体的三维构象。我们使用三维结构信息计算相互作用区域中距离小于d的原子对个数最多的对接结构。我们还使用统计能量函数评估多个对接结构,并计算能量值最低的对接结构。本文还设计了一个柔性分子对接方法。我们可以预测蛋白质间相互作用界面上残基侧链的结构变化,计算出更为稳定的复合体三维构象。蛋白质结合位点的预测是计算生物学中的一个基本问题。在生物体中,蛋白质功能具有特异性,并且能够以不同的力度与其它各类分子结合,其中也包括蛋白质分子。蛋白质与其它分子相互结合的区域被称为蛋白质的结合位点,而蛋白质结构决定了结合位点的位置和形状。蛋白质结合位点的相似性预测可以抽象为单一子结构搜索问题和子结构对搜索问题。已有一个时间复杂度为O((1/ε)5n)的离散化算法实现了子结构的刚性变换。在此基础上,我们提出了一个时间复杂度为O(log(1/ε)55n)的局部搜索算法解决相同的问题。计算生物学的另一个重要研究内容是复合体三维构象的预测。两个以上功能相关的蛋白质通过分子对接形成了具有特殊功能的复合体三维构象。分子对接时,蛋白质之间的相对位置和方向、蛋白质自身构象变化都是用于描述蛋白质三维构象的基本信息。复合体构象可以通过计算机模拟分子结构在三维空间中的对接过程预测得到。复合体三维构象算法可以用于解决三个蛋白质形成复合体构象的预测问题。首先,我们提出了一个时间复杂度为O(q13q23q3(log(1/ε)55)2)的离散化算法用于预测蛋白质复合体构象。在此基础上,我们还提出了一个限定结合位点距离上界的启发式算法解决同样的问题,同时将时间复杂度降低至O(q13q23q3+(M qr2q22q3+MNq12q22q3)log(1/ε)55)。本文的主要研究工作和创新点：一、三维空间子结构搜索问题的算法设计1.我们提出了一个局部搜索算法解决相似子结构搜索问题。与已有的离散化算法相比,新算法将时间复杂度从O((1/ε)5n)降低至O(log(1/ε)55n),其中n是三维结构中原子点的个数,ε×d为三维网格的单位长度。当ε非常小时,我们设计的新算法非常有效。二、蛋白质形成复合体构象的算法设计2.我们提出了一个离散化算法用于预测蛋白质复合体构象,时间复杂度为O(q13q23q3(log(1/ε)55)2),其中q1、q2、q3分别是三对结合位点的长度。在此基础上,我们还提出了一个限定结合位点距离上界的启发式算法解决同样的问题,时间复杂度降低至O(q13q23q3+(M q12q22q3+MNq12q22q3)log(1/ε)55),其中M、N分别是在距离上界限定下可行的轴点对数和轴点三维坐标个数。这两种方法预测得到的复合体三维构象基本相同。三、分子对接方法设计3.我们设计了两个刚性分子对接方法,通过使用空间匹配信息和能量匹配信息预测蛋白质分子的对接过程。这两种方法预测得到蛋白质结合位点的查全率和查准率均比已有的预测方法至少提高了5%。4.我们还设计了一个柔性分子对接方法,通过预测蛋白质间相互作用界面上残基侧链的结构变化,解决复合体三维构象的预测问题。与刚性分子对接相比,柔性分子对接方法计算可得预测构象的蛋白质结合位点的查全率和查准率至少提高3%。本文的进一步工作主要包括以下几个方面：1.分子结构的变化是由化学键的转动引起的,三个连续的化学键可以组成一个二面角。我们计划使用von Mises分布预测这些二面角的分布。2.在一个分子中,相邻的二面角并不是相互独立的。我们计划采用概率图模型以及角度变化模型来刻画所有可能的分子结构。3.对称型复合体分为两种类型Cn和Dn,Cn可以抽象为环,Dn可以抽象为双环。我们可以在相互作用网络中寻找环和双环以预测复合体。4.在相互作用网络中,我们可以改进聚类算法预测复合体：基于密度的局部搜索算法,图划分方法。5.我们可以将拓扑结构分类与生物特性、序列信息相结合来预测复合体。