蛋白质是一种十分重要的生物分子。生物学研究表明,蛋白质很少单独参与生命活动,而是通过多个蛋白质之间的物理相互作用形成多分子聚合体——蛋白质复合体。复合体是蛋白质执行其功能的主要形式。在细胞中很多重要的生物过程都是由蛋白质复合体参与执行的。因此,准确识别细胞中蛋白质复合体对于揭示蛋白质活动规律、理解蛋白质的功能具有十分重要的意义。蛋白质网络是一种用来刻画细胞中蛋白质之间相互作用的生物网络。利用计算方法从蛋白质网络中识别蛋白质复合体,是当前生物信息学领域的研究热点之一。本课题即围绕以蛋白质网络为基础的复合体识别问题,针对局部搜索、离散和连续优化以及采用时序蛋白质网络等不同类型识别方法分别展开研究。具体研究内容包括以下四个方面:(1)研究基于标签传播思想的复合体识别方法。在局部搜索类方法方面,本文提出了一种基于多标签传播的识别算法。该算法中引入了标签传播机制,利用标签表示蛋白质所属复合体类别,并通过蛋白质之间相互传播标签的过程识别蛋白质网络中复合体对应的模块。具体来讲,本文针对蛋白质复合体的特点,对传统标签传播算法进行了相应的改进与拓展,主要体现在如下几方面:采用蛋白质的多标签存储与传播机制,解决复合体之间的重叠问题;定义标签的传播强度,强化共有邻居蛋白质的作用,提高传播效率;提出基于自适应阈值的多标签更新策略,以合理控制复合体规模;确定了以蛋白质度为基础的标签更新顺序,增强了算法的鲁棒性。实验结果表明,上述算法在识别蛋白质复合体方面具有一定的优势。该算法的提出为从蛋白质网络中识别复合体提供了一种新的有效启发式手段。(2)研究基于离散模块度函数的复合体识别方法。模块度函数是度量网络模块划分质量的离散函数,是引导层次聚类簇合并的重要指标。针对复合体相互重叠和规模小等特点,本文提出了一种蛋白质模块度函数用以度量网络中复合体模块划分质量,并利用该函数作为引导簇合并的指导准则。与传统模块度函数相比,该新型模块度函数具有两方面特点:一是在重叠模块方面具有更强的描述能力;二是可以避免分辨率限制问题,更加适合于规模较小的复合体。此外,在层次聚类算法设计方面,还提出了一种基于度相关性的初始簇选择方法。文中通过实验验证了该算法的有效性,证明其更适合于解决蛋白质复合体识别问题。本工作对于基于模块度函数识别复合体的相关研究具有重要意义。(3)研究面向复合体识别的连续优化模型及相应算法。在连续优化方法方面,本文提出一种以最小二乘法为基础的最优化模型,用以在输入蛋白质网络数据和未知复合体模块划分之间建立合理联系。该模型的优化目标是最小化所有蛋白质对的相互作用与参与共同复合体系数之间的差异。此外,通过对蛋白质相互作用强度进行加权以及引入惩罚项等相应策略进一步提高模型描述能力。在所构建模型基础上,给出了一种基于小粒度稠密子网络和乘法更新规则的快速优化算法以将该模型与给定输入蛋白质网络相拟合,从而推测得到蛋白质隶属不同复合体的隶属系数。通过实验测试及与其它基于连续优化算法的对比,验证了上述模型及算法的有效性。(4)研究基于时序蛋白质网络的复合体识别方法。在基于时序蛋白质网络的识别方法方面,关键问题是如何利用基因表达数据构建能够客观描述蛋白质动态活动规律的时序蛋白质网络。现有相关方法普遍假设所有蛋白质都是动态变化。然而,除动态蛋白质外细胞中还包含丰度相对稳定的静态蛋白质。因此,本文提出一种基于动态-静态蛋白质混合思想的方法构建时序蛋白质网络,并将这种网络应用于复合体识别问题。该方法不仅考虑动态蛋白质之间的相互作用,而且同时关注动态蛋白质与静态蛋白质之间的相互作用关系。实验表明,利用该方法构建的时序蛋白质网络可以提高识别蛋白质复合体的准确性。综上所述,本课题以基于蛋白质网络的复合体识别问题为主线,从不同角度展开研究,并分别提出了基于多标签传播、蛋白质模块度函数、最小二乘模型以及时序蛋白质网络等多种不同类型的识别方法。本课题对于生物网络分析方法和蛋白质组学研究具有重要的研究意义和潜在的应用价值。