A Survey on Identification of Protein Complexes in Protein–protein Interaction Data: Methods and Evaluation - Computational Intelligence Techniques for Comparative Genomics - page 59

where N 3 cliques are the number of 3 cliques in the neighborhood graph.
Once the degree is calculated, we sort the sequence of proteins in the
neighborhood graph accordingly from minimum to maximum [ 15 ]. The
protein v j with the lowest degree and its corresponding interactions are
removed from the neighborhood graph and c i is recalculated. This
process stops when the neighborhood graph contains only 3 proteins and
the sequence of proteins with the highest c i is returned as a valid core
protein complex.

Assessing the quality of predicted complexes to evaluate the accuracy of the
proposed method, we used the Jaccard index which de

ned as follows:

Þ¼ j

V K \ V R j

MathScore ð K ; R ð 8 Þ

j V K [ V R j

where K is a cluster and R is a reference complex. V K and V R are the set of proteins
in K and R, respectively. The complex K is dened to match the complex R if match
score (K, R)

≥ α .

2.2.5 Detection of Protein Complex Core and Attachment Algorithm

The basic idea behind this method resides of two main steps. In the rst step, it

extracts the complex core based on the weighted PPI network from the view of
edge. In the second step, it identi es the attachments for each core to form the

protein complex.
The protein complex core is de

ned as follows:

1. Each complex has a set of core proteins.
2. The core has relatively more interactions; the functional similarity between core
proteins should be high [ 16 ].

Detecting the Protein Complex Core

The PPI interaction data are an undirected weighted graph G =(V, E, W) where
V represents the proteins and E represents the interactions between proteins and
W is a weight to each edge with co-expressed correlation between proteins. The
sum of weight is de ned as,

j V j j V j

j W j¼ A ij ð 9 Þ

i j