Biomedical Engineering Reference
In-Depth Information
Detecting the protein complexes from the available PPI data will help to deeply
understand biological activity mechanism and the architecture of protein interaction
network (PIN). In recent years, a huge number of computational approaches based
on graph clustering have been applied to PPI networks for protein complexes
identi
cation. These graph clustering algorithms mainly depend on the association
of topological analysis of PPI networks to classify protein complexes [
2
5
].
Computational approaches can be applied to identify protein complex infor-
mation by searching closely connected regions in a PPI network [
3
], which is like a
graphical map of an entire organism
-
s interactome. This is assembled from existing
PPI knowledge by considering unit of proteins as nodes and the subsistence of
physical interactions between a pair of proteins as connections. The titanic quantity
of genes and proteins that participate in biological networks that in
'
ict the need for
determination of protein complexes within the network, while these complexes will
be the
fl
rst step in decoding the composite genetic or cellular interactions of the
overall network. Many algorithms for detecting protein complexes from PPI net-
work have been developed, and these algorithms adopt different strategies to detect
protein complexes and thus obtain different results.
2 Review of Algorithms
In this section, we
rst pioneer some basic terminologies for graphs and then review
the different algorithms for protein complex detection.
2.1 Terminology
Given a PPI network G =(V, E) with a set of nodes V
¼
f
v
1
;
v
2
;
...
;
v
n
g
and a set
of edges E
, where the nodes represent proteins and edges rep-
resent pairwise interactions. A walk is a sequence of vertices where edges exist
between two adjacent vertices. The neighborhood of a vertex v in a graph G is the
induced subgraph of G consisting of all vertices adjacent to v and all edges con-
necting two such vertices. A k-core is a subgraph in which all the vertices have
degrees no less than k and the order of a k-core is k, if it is not a (k + 1)-core. Given
two graphs A =(V
A
, E
A
) and B =(V
B
, E
B
), their neighborhood af
¼
f
e
1
;
e
2
;
...
;
e
m
g
nity NA(A, B)is
de
ned as to measure the similarity between them.
2
Þ¼
j
V
A
\
V
B
j
NA
ð
A
;
B
ð
1
Þ
j
V
A
jj
V
B
j
For a given PPI network G =(V, E), the degree of a vertex v
V is the number of
ϵ
v
'
s neighbors in G, represented as deg(v). The average degree of graph G is de
ned
Search WWH ::
Custom Search