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

2.2.6 Dynamic Protein Complex Algorithm

The algorithm DPC operates in three stages:

1. detecting protein complex cores,
2. generating potential dynamic complexes, and
3.

ltering false-positive complexes.

Detecting Protein Complex Cores

Detecting possible protein complex cores is divided into two main steps: searching
always active proteins and forming possible protein complex cores. Forming pos-
sible protein complex cores is designed to group always active proteins into many
connected subgraphs according to the topological and dynamic features of protein
complex cores. The core candidate proteins are sorted by the numbers of their own
always active neighbors in descending order in G [ 18 ]. The sorted always active
proteins will be stored into a queue Q. The

rst vertex in the queue Q is picked and
used as a seed to grow a new possible protein complex core. Once a protein
complex core is completed, all vertices in it will be tagged with “ 1 ” and cannot be

extended into any other protein complex cores [ 19 ].
A nal protein complex core is generated by removing vertices recursively from

the preliminary core according to the edge clustering coef

cient until its density is
larger than or equal to a given threshold T d . For an edge(u, v) ∈ E, its edge

clustering coef ned as the number of triangles to which

(u, v) belongs and is divided by the number of triangles that might potentially
include (u, v), as

cient [ 16 ] ECC ð v ; u Þ is de

Z ð u ; v Þ

ECC ð u ; v Þ¼ ð 12 Þ

min f deg ð u Þ 1 ; deg ð v Þ 1 g

cient ECC
(u, v) of each edge connecting the seed vertex v and a rest vertex u is calculated.
Then, the vertex with minimum ECC will be removed from the preliminary core
C [ 20 ]. Suppose, if the preliminary core C with den(C)

For a preliminary core C with den(C)<T d , the edge clustering coef

≤

T d is outputted as a

potential protein complex core.

Generating Potential Dynamic Protein Complexes

After nding the potential protein complex cores, the important point is how to nd

the attachments for each core to form protein complexes. For this, we nd a

best protein complex core for each potential attachment in the set. We say that there
is a connection between a protein complex core and an attachment if there is at least
an edge connecting the attachment and one protein in the protein complex core. For

rst