Abstract: Detecting protein complexes is crucial to understand the principles of cellular organization and predict diseases. Yet up to now, the performance of existing protein complex detection algorithms is not very ideal for the deficiencies of low accuracy, sensitive to noisy data and so on. This paper proposes a novel algorithm named pigeon-inspired optimization clustering (PIOC) algorithm. It puts forward the concepts of cluster's closely adjacent nodes and attachment's attachment degree on core, and identifies protein complexes by simulating the process of pigeons finding home based on these two concepts. The PIOC algorithm combines the characters of first global search then local search of pigeon-inspired optimization (PIO) algorithm and the core-attachment structure of protein complexes. Particularly, it first develops the cores of protein complexes by the global search of PIO's map and compass operator, and then forms the protein complexes by gathering in the attachment proteins to the cores based on the local search of PIO landmark operation. The experimental results on yeast protein DIP dataset demonstrate that PIOC is more   effective in detecting protein complexes than the state-of-the-art complex detection algorithms.

Key words:  protein-protein interaction (PPI), pigeon-inspired optimization algorithm, protein complex, clustering

摘要： 蛋白质复合物的检测对人类了解细胞组织和疾病预测起着至关重要的作用。然而，当前的蛋白质复合物识别方法的准确率低，对噪音敏感等缺点导致其识别效果并不理想。提出了一种新的蛋白质复合物识别方法PIOC（pigeon-inspired optimization clustering）。该方法根据蛋白质复合物的特性提出了簇的紧密邻接点概念和附件对核心的附着度概念，基于这两个概念，PIOC通过模拟鸽子优化算法中鸽子寻找目的地的过程来识别蛋白质复合物；结合鸽子算法中先全局搜索再局部搜索的特性和蛋白质复合物的核心附件结构，先通过鸽子算法中地图罗盘操作的全局搜索形成蛋白质复合物的核心，再通过鸽子算法地标操作的局部搜索将附件蛋白质聚集到核心簇中形成蛋白质复合物。基于酵母蛋白质相互作用网络DIP上的实验表明，PIOC比当前其他的蛋白质复合物识别算法能更有效地识别蛋白质复合物。

关键词: 蛋白质相互作用（PPI）, 鸽子优化算法, 蛋白质复合物, 聚类