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

and the density of the cluster remains higher than a user-de ned threshold T s ;

otherwise, the cluster is output. Consequently, the ClusterBFS has two parameters:
T s , the weighted density threshold and R.
In the PPI network, each vertex is represented as seed. After achieving the seed
vertex, we use the breadth-

rst search technique to produce each cluster in terms of
the weighted density. For a cluster, at each step, we have a current vertex set C,
which primarily contains one seed as protein v. Then, from all unclustered vertices,
we search for the vertex u with maximum value of the edge weight that is adjacent
to the v in BFS [ 7 ].
If the weighted density of the cluster is smaller than a threshold, we stop
intensifying this cluster and output it. If not, we put vertex u into C and update the
density value. If the density value is smaller than our density threshold T s ,wedo
not include u in the cluster and output C. We repeat this procedure until all vertices
in the graph are clustered.
Since all vertices in the graph have been selected as seeds, the clusters produced
have large overlaps, which will result in high redundancy. Hence, a redundancy-

ltering procedure is designed to process candidate clusters and nally generate

protein complexes by eliminating such kind of redundancy.

2.2.3 Connected Afnity Clique Extension (CACE)

In this algorithm, the value of the protein connected af nity which is inferred from

protein complexes is interpreted as the reliability and possibility of interaction.
The algorithm works by rst detecting a set of seeds in the graph G, then

expanding these seeds into modules based on af

nity clique extension. Firstly, the

input as PIN and PCT information to identi ed the protein complexes modules [ 8 ].

Step: (1) The process starts to utilize the available data for building the Weighted
PIN (protein interaction dataset). Calculate the connected af nity coef-

cient value for each complex from protein complex dataset represented
as CAC ij and also get the value of interaction for each pair of proteins
from PPI network represented as PB ij [ 9 ].
Based on the above value which affects the protein relations and then
calculates the weight to represent the likelihood interaction between any
two proteins:

WP i P j ¼ a CAC ij þ ð 1 a Þ PB ij ;

where α is a parameter.
Now, we can construct a Weighted PIN using the above values.
Step: (2) Now, we choose the seeds from the weighted PIN by nding all of the

maximal cliques with size greater than CZ in the network [ 10 ].
Step: (3) Now, mining the complexes from the connected af

nity clique extension
(CACE) which is the key point to determine the quality of community.