Determining the minimum number of protein-protein interactions required to support known protein complexes

The prediction of protein complexes from protein-protein interactions (PPIs) is a well-studied problem in bioinformatics. However, the currently available PPI data is not enough to describe all known protein complexes. In this paper, we express the problem of determining the minimum number of (additional) required protein-protein interactions as a graph theoretic problem under the constraint that each complex constitutes a connected component in a PPI network. For this problem, we develop two computational methods: one is based on integer linear programming (ILPMinPPI) and the other one is based on an existing greedy-type approximation algorithm (GreedyMinPPI) originally developed in the context of communication and social networks. Since the former method is only applicable to datasets of small size, we apply the latter method to a combination of the CYC2008 protein complex dataset and each of eight PPI datasets (STRING, MINT, BioGRID, IntAct, DIP, BIND, WI-PHI, iRefIndex). The results...

基于蛋白质-蛋白质相互作用（protein-protein interactions, PPIs）预测蛋白质复合物，是生物信息学领域中广受研究的经典问题。然而，当前可用的PPI数据尚无法完整覆盖所有已知的蛋白质复合物。本文将“确定最小所需（额外）蛋白质-蛋白质相互作用数目”这一问题建模为图论问题，约束条件为每个蛋白质复合物均为PPI网络中的一个连通分量。针对该问题，我们提出了两种计算方法：一种基于整数线性规划（integer linear programming, ILPMinPPI），另一种基于原本面向通信与社交网络场景开发的现有贪心型近似算法（GreedyMinPPI）。鉴于前者仅适用于小规模数据集，我们将后者应用于CYC2008蛋白质复合物数据集与8种PPI数据集（STRING、MINT、BioGRID、IntAct、DIP、BIND、WI-PHI、iRefIndex）的组合数据集。研究结果……