Search

• A novel variable neighborhood search heuristic approach for supporting known complexes in weighted PPI networks by integrating data from different sources: PPI networks, protein complexes and gene co-expression. • The proposed approach efficiently searches the overall searching space and is a successful method for solving both artificial and large real PPI networks. • The proposed three-phase method revealed meaningful protein groups with high enrichment scores, which previously were not interconnected in PPI networks. • Grouping the proteins in PPI networks in the described way may help to understand their intrinsic structures and functions. Identifying significant protein groups is of great importance for further understanding protein functions. This paper introduces a novel three-phase heuristic method for identifying such groups in weighted PPI networks. In the first phase a variable neighborhood search (VNS) algorithm is applied on a weighted PPI network, in order to support protein complexes by adding a minimum number of new PPIs. In the second phase proteins from different complexes are merged into larger protein groups. In the third phase these groups are expanded by a number of 2-level neighbor proteins, favoring proteins that have higher average gene co-expression with the base group proteins. Experimental results show that: (i) the proposed VNS algorithm outperforms the existing approach described in literature and (ii) the above-mentioned three-phase method identifies protein groups with very high statistical significance. [ABSTRACT FROM AUTHOR]