# An Algorithm for Finding Functional Modules and Protein Complexes in Protein-Protein Interaction Networks

Authors: Guangyu Cui; Yu Chen; De-Shuang Huang; Kyungsook Han
Journal: Journal of Biomedicine and Biotechnology
 (2007-12-31)

---

## Abstract

Biological processes are often performed by a group of proteins rather than by individual proteins, and proteins
in a same biological group form a densely connected subgraph in a protein-protein interaction network. Therefore,
finding a densely connected subgraph provides useful information to predict the function or protein complex of uncharacterized proteins in the highly connected subgraph. We have developed an efficient algorithm and program for finding cliques and near-cliques in a protein-protein interaction network. Analysis of the interaction network of yeast proteins using the algorithm demonstrates that 59% of the near-cliques identified by our algorithm have at least one function shared by all the proteins within a near-clique, and that 56% of the near-cliques show a good agreement with the experimentally determined protein complexes catalogued in MIPS.


---

## Body

## 1. Introduction

Proteins in a
highly connected subgraph of a protein interaction network usually share a
common function [1]. Therefore, a highly connected subgraph such as clique and
near-clique in a protein interaction network can be used to predict the
function of uncharacterized proteins in the highly connected subgraph. Finding
a clique with a maximum size in a graph is an NP-hard
problem
[2]. There are several heuristic algorithms for the
maximum clique problem [2, 3], but most of them focus on finding a complete
subgraph (i.e., clique) and cannot be used to find near-cliques.Several topological analysis methods have been
developed for identifying biologically meaningful groups from protein
interaction networks or for assessing the reliability of protein interactions.
A recent program called CFinder [4, 5] finds overlapping cliques in protein
interaction networks. It allows a protein to belong to more than one clique, but cannot find near-cliques. Our study shows that the near-cliques can reveal
higher functional coherence than the overlapping cliques.The primary focus of this study is to find functional
groups by identifying cliques and near-cliques in protein interaction networks.
This study attempts to answer two questions as follows. “Can we
efficiently find all cliques and near-cliques?" and “does a dense
subgraph such as clique and near-clique indeed represent a functional module or
protein complex?" This study demonstrates that the answers to both
questions are “yes." This paper presents an algorithm for finding
near-cliques and its application to the interaction network of yeast proteins.


## 2. Algorithms for Finding Near-Cliques

A clique is a complete graphG=(N,E) in which every
node is connected to every other node in the graph. In our previous work, we
developed a heuristic algorithm and implemented the algorithm in a program
called InterViewer [6], which identifies all edge-disjoint cliques (i.e.,
cliques that do not share an edge).Our experience with protein interaction networks
suggests that a near-clique as well as a clique often represents a biologically
meaningful unit such as functional module or protein complex. A near-clique is
almost a clique but is not a clique due to a few missing edges. We consider
near-cliques of the followingbasic types, which are biologically meaningful clusters (see Figure 1).Near-cliques of types A, B, and C. Proteins outside a
clique are represented as shaded nodes.
(a)(b)(c)Type A
When a
protein outside a clique interacts with two or more proteins in the clique, the
protein and the clique forms a near-clique.Type B
When a
clique shares a protein with other cliques, the cliques form a near-clique.Type C
When two or
more cliques interact with a common protein outside them and the protein has at
least two interactions with each clique, the cliques and the protein form a
near-clique.The near-cliques of types A and C can be refined using
the indegree and outdegree of a node (there is no change to the near-clique of
type B). For a nodex in subgraph G′⊂G, indegree(x,G′) is the number
of the edges connecting node x to other nodes
in G′, and outdegree(x,G′) is the number
of edges connecting node x to other nodes
that are in G but not in G′. We use the definition of a community in a strong
sense [7] to find more near-cliques in a graph.Definition 1.
A subgraphG′ is a community
in a strong sense if indegree(x,G′)>outdegree(x,G′) for every x in G′.The original definition of a strong community misses
many near-cliques due to a single node in the communities. For example, in
Figure2(a), node x cannot belong
to a near-clique since indegree(x,G′)=3<outdegree(x,G′)=4. Likewise, node x in Figure 2(b)
cannot belong to a near-clique because indegree(x,G′)<outdegree(x,G′). Thus, nodes with only one edge connected to them and
their edges are removed from the graph when we search near-cliques in the
graph. In the graph of Figure 2(a), nodes p, q, r, and s and their edges
are removed. After removing them, node x and the
existing clique form a near-clique of type A. A cluster
that satisfies indegree(x,G′)≥0.5|G′| for every x in G′, where |G′| is the number
of nodes in G′, forms a near-clique, too.
The example shown in Figure 2(b) becomes a near-clique since
it satisfies indegree(x,G′)≥0.5|G′| even if it does
not satisfy indegree(x,G′)<outdegree(x,G′).(a) After removing nodesp, q, r, and s and their
edges, node x forms a near-clique of type A with the remaining nodes. (b) This
graph becomes a near-clique G of type C since indegree(x,G)≥0.5|G|. (c) A big near-clique is too big (e.g., near-clique
with more than 50 nodes) and is split into smaller near-cliques (in this example, 3
small near-cliques).
(a)(b)(c)Therefore, a near-cliqueG of basic types
A and C should satisfy at least one of the
following conditions.(1)
indegree(x,G)≥outdegree(x,G) for every x in G.(2)
indegree(x,G)≥0.5|G|.After finding all edge-disjoint cliques first, we
identify near-cliques as follows. More detailed description of finding
near-cliques are outlined in Algorithms1 and 2. In the algorithms, cIdx
represents the index of a clique.Algorithm 1:AssignNearCliqueIdx.
(1)for all node N∈Gdo(2)N.cldx=0                         {initialize cIdx of all nodes to 0}(3)end for(4)curCIdx=1                        {set the current clique index to 1}(5)for all node N∈Gdo(6)if (isClique(N)) then{if the node N belongs to a clique}(7)for all edge E∈Ndo(8)if (E.target.cIdx>0) then{if the cIdx of the node connected to N is
positive}(9)for alltmpN∈Gdo{for all nodes in G}(10)if (tmpN.cIdx=E.target.cIdx) then(11)tmpN.cIdx=curCIdx     {assign curCIdx to tmpN as its cIdx}(12)end if(13)end for(14)else(15)E.target.cIdx=curCIdx(16)end if(17)end for(18)N.cIdx=curCIdx                 {set cIdx of N to curCIdx}(19)curCIdx++                     {increase curCIdx by one}(20)end if(21)end forAlgorithm 2:ExtendNearClique.
(1)for all node N∈Gdo(2)if (N.cIdx=0) then{find node outside the clique}(3)qCliqueCnts=∅{qCliqueCnts the number of edges, which the node N
connected with different near-cliques}(4)for all edge E∈Ndo(5)if (E.target.cIdx>0) then(6)qCliqueCnts[E.target.cIdx]++(7)end if(8)end for(9)qCvalue=0{initialize cIdx of node N}(10)for all (c∈qCliqueCnts) do(11)if ((c>1)andindegree(x,G′)≥outdegree(x,G′)) or
((c>1)andindegree(x,G′)≥0.5*|G′|)then{a nodeoutside a clique
interacts with multiple nodes in the clique, and eitherindegree(x,G′)≥outdegree(x,G′) orindegree(x,G′)≥0.5*|G′|) is true}(12)if (qCvalue>0) then(13)for alltmpN∈Gdo(14)if (tmpN.cIdx=qCvalue) then(15)tmpN.cIdx=qCvalue{near-clique of type C}(16)end if(17)end for(18)else(19)qCvalue=c{near-clique of type A}(20)end if(21)end if(22)end for(23)N.cIdx=qCvalue{assign qCvalue to node N as its cIdx}(24)end if(25)end for(1)
Assign every
node of a clique the index of the clique containing the node.(2)
When a node of
a clique has already an assigned clique index, assign the index to all nodes of
the clique, and merge two cliques into a near-clique of type
B.(3)
When a nodex outside a
clique forms a basic near-clique G of type A due
to the interactions with two or more proteins in the clique, and either indegree(x,G)≥outdegree(x,G) or indegreei(x,G)≥0.5|G| is true, assign
the index of the clique to the node.(4)
When two or
more cliques form a near-cliqueG due to two or
more interactions with a common protein outside the cliques, and either indegree(x,G)≥outdegree(x,G) or indegreei(x,G)≥0.5|G| is true, merge
the cliques and the protein into a near-clique of type C. A near-clique is
formed by selecting nodes with the same clique index (cIdx) as those
nodes with cIdx>0.Since the most relevant processes form a group of
proteins of moderate size in biological networks [8], we obtain near-cliques
smaller than the maximum size specified by a user. That is, when a near-clique
bigger than the maximum size is found (e.g., near-clique with more than 50
nodes), it is split into smaller near-cliques (3 near-cliques in Figure 2(c)).
The way we split a big near-clique is as follows. When our program finds a big
near-clique with the minimum clique size set to k, we rerun the program on the big near-clique with the
minimum clique size set to k+1 to find a new
clique and a near-clique with the clique. After removing the new near-clique
from the original, big near-clique, we run the program again with the minimum
clique size set to k. The big near-clique shown in Figure 2(c) is split
into 3 small near-cliques with at least 4 proteins each.


## 3. Results and Comparison with Experimental Data

We tested the algorithms on the data with 8,397
interactions between 4,380 yeast proteins, which is the combined data of Ito et
al. [9], Uetz et al. [10], and MIPS (http://mips.gsf.de) with redundant data
removed. To every protein in the near-cliques, we assigned the functional
categories of the Functional Catalog (FunCat) version 2.0 [11], which
includes 97 functional categories. There are six
levels of hierarchy in the FunCat structure.In the data with 8,397 interactions between 4,380
yeast proteins, we found 100 near-cliques with the minimum size of a clique set
to 3 and the maximum size of a near-clique set to 40. Only one near-clique
contains more than 40 proteins, and so it was split into 17 small near-cliques,
resulting in total 116 near-cliques. Figure3 shows an example of the network
of yeast protein interactions with 6 near-cliques. Proteins in each near-clique
share at least one function with other proteins within the near-clique.Figure 3
Six near-cliques found in yeast protein interaction networks.
Proteins in each near-clique share at least one function with other proteins
within the near-clique.As shown in Table1, 68 (59%) out of the 116
near-cliques have at least one function shared by all the proteins in the
near-cliques (100% sharing), and 39 near-cliques have a function shared by more
than 50% of the proteins in the near-cliques, supporting data are
available at http://wilab.inha.ac.kr/ppi/homepage.mht. Only
9 near-cliques have no function shared by > 50% of the
proteins in the near-cliques. As shown in Figure 4, the functional coherence of
each near-clique is high. The functional coherence was computed by the ratios
of the number of proteins having a specific functional category to the group
size (i.e., the number of proteins in the group).Table 1
Functional groups identified from the yeast protein interaction data. 68
modules have at least one function shared by all the proteins in the groups
(100% sharing), and 39 groups have a function shared by more than 50% of the
proteins in the groups. Only 9 groups have no function shared by>50% of the
proteins in the group. This table shows only one function with the highest
functional coherence in each group. All the functions shared by more than 50%
of the proteins in each group are available at
http://wilab.inha.ac.kr/ppi/homepage.mht.
Group IDProteins in the groupCommon function (proportion of proteins with the function)Group IDProteins in the groupCommon function (proportion of proteins with the function)Group IDProteins in the groupCommon function (proportion of proteins with the function)1311.02.02 (100%)40310.01.03.03 (100%)79342.01 (100%)2514.01 (100%)41320.09.13 (100%)80330.01.05.01 (66.7%)3442.10 (100%)42542.01 (80%)81342.04.03 (100%)41242.10.05 (75%)43540.01 (80%)82442.25 (100%)5401.03.16.01 (75%)44314.10 (100%)833none6611.02.03.04 (100%)45812.04.01 (87.5%)84301.06.01.07.11 (100%)7414.07.02.01 (100%)46414.13.01.01 (100%)85332.01.07 (66.7%)8610.03.01 (100%)47410.01.05.01 (100%)86434.11.03.07 (100%)92211.04.01 (63.6%)48310.01.05.01 (100%)87320.09.07 (100%)102120.09 (66.7%)49620.09.04 (100%)88302.19 (100%)113none50432.01 (100%)89316.19.03 (100%)12811.04.03.05 (100%)51310.01.03 (100%)9042.07 (75%)131110.03.01 (63.6%)52312.04.03 (66.7%)91316.03.01 (100%)14710.03.01 (76.5%)531320.09.07.03 (61.5%)92310.01.05.01 (100%)1541.03 (50%)54811.02.03.01 (100%)93732.01 (100%)16501.05.01.03.02.02 (100%)55420.09.07.03 (100%)94340.20 (66.7%)17316.03.01 (100%)565none95334.01.01.03 (100%)18411.04.02 (100%)57520.09.01 (100%)96443.01.03.05 (100%)19540.01 (80%)58520.09.18 (80%)97314.04 (100%)20318.02.01 (60%)59501.04.01 (80%)98420.09.13 (100%)212343.01.03.05 (82.6%)60343.01.03.05 (100%)99316.03.01 (66.7%)22432.01 (50%)61511.04.01 (100%)1001243.01.03.05 (91.7%)23411.02.03.04.01 (100%)62520.09.10 (100%)101610.03.01.01.03 (100%)24414.13.01.01 (100%)63343.01.03.09 (66.7%)102916.01 (88.9%)2536none64311.02.03.04 (100%)103743.01.03.05 (100%)26420.09.07.03 (100%)65334.11.03.13 (100%)104543.01.03.05 (80%)271042.04 (50%)66516.19.03 (80%)1051120.09.07.03 (100%)281114.13.01.01 (100%)67411.04 (100%)106710.03.04.03 (85.7%)29643.01.03.05 (83.3%)68310.01.09.05 (66.7%)107640.01 (50%)30812.04 (100%)69401.04.01 (100%)108910.03.01.01 (88.9%)31410.03.01 (100%)70311.06.01 (100%)109320.09.07.27 (100%)32412.04.02 (75%)716none110320.09.14 (100%)33334.01.01.01 (100%)72320.09.13 (100%)1111243.01.03.05 (100%)345none73311.02.03.04 (100%)112510.03.04.05 (100%)35311.04.01 (66.7%)74342.10.03 (100%)113510.03.04.05 (100%)363111.02.03.04 (80.6%)753none114542.10.03 (80%)37416.03.01 (100%)76720.09.04 (100%)1153none38643.01.03.05 (100%)773none116543.01.03.05 (80%)39714.04 (57.1%)78310.03.02 (100%)———The functional coherence in each of the 116 groups,
computed as the ratio of the number of proteins having a specific functional
category to the number of proteins in the group. The black, white, and grey
bars represent functional categories with the ratios≥0.5 and the maximum
number of such ratios is limited to 3 in each group.
(a)(b)(c)(d)Interestingly, most near-cliques found by our
algorithm belong to multifunctional categories. For example, two functional
categories are common to all the proteins in a near-clique of Figure5. As
shown in Table 2, the near-clique identified as group 93 by our program is
involved in both stress response (functional category 32.01) and biosynthesis
of vitamins, cofactors, and prosthetic groups (functional category 01.07.01).Table 2
Functional annotation of group 93 shown in Figure5.
The code represents functional category.
GroupProteinProtein functional categoriesGroup 93YFL059w32.0101.07.01YMR096w32.0101.07.01YMR322c32.01.0701.07YNL334c32.0101.07.01YMR095c32.0101.07.01YNL333w32.0101.07.01YFL060c32.0101.07.01Figure 5
Group 93 identified as a near-clique by our
algorithm.Near-cliques may correspond to protein complexes in
addition to functional modules. So, we compared the near-cliques identified by
our algorithms with known yeast protein complexes, which are cataloged in the
MIPS Saccharomyces cerevisiae genome database
(http://mips.gsf.de/genre/proj/yeast). For each near-clique, we found a
best-matching protein complex by minimizing the probability of a random overlap
between the two, using the following equation [4, 5]: (1)Poverlap=(n2k)(N−n2n1−k)(Nn1),
where n1, n2 are the sizes
of a known protein complex and a computed module, k is the number
of their common proteins, and N is the size of
the network.As shown in Table3, 65 near-cliques (56% of the total
116 near-cliques) identified by our algorithm show a good agreement (ln⁡(Poverlap)<−14) with the
protein complexes cataloged in MIPS.Table 3
The near-cliques matched with experimentally determined
protein complexes cataloged in MIPS. The overlap column
represents the number of proteins common to the near-cliques and
the protein complexes.
Group IDGroup sizeMIPS tag of protein complexProtein complex sizeOverlap  (common proteins)ln(Poverlap)Main functional categories3429522−14.2842.10/43.01.03.0954510.190.110133−16.3201.03.16.016632084−23.4011.02.03.04/10.01.09.05/16.03.01922550.1.1498821−84.6011.04.01/12.01128550.1.148358−39.4911.04.03.05/16.03.03/11.04.03.011311550.1.7108−47.5510.03.01/14.01/16.011417140.303211−46.6510.03.01164550.1.4493−17.5514.07.02.02/01.05.01.03.02.02173410.40.2033−23.3616.03.01 /16.03.01
/10.01.05.01/10.01.03.05/10.01.03.01184440.30.30114−24.5611.04.022123470.2055−26.7143.01.03.05/34.11.03.07234510.16044−30.3611.02.03.04.01/01.05.04244360.10364−19.3814.13.01.01/14.07.112536550.1.1383611−34.43none264550.2.31733−21.9820.09.07.03/20.09.07.05/14.10271013084−20.7742.04/16.012811601111−74.7114.13.01.01/10.03.01.01.11/14.07.05
/14.10/16.01 /16.19.03296120.2044−27.6543.01.03.05/40.01/34.07.01/34.01/32.01.09/11.02.02/10.03.01.01.09/10.03.01.01.03308550.1.142254−16.6812.04314140.30.30.3032−13.1810.03.01/42.04/20.09323510.2043−21.9812.04.02/12.01.013631230.20.201614−67.9911.02.03.04/10.01.09.05374410.30164−22.8516.03.01/10.01.03.03/10.01.03.01/16.19.03386550.1.8175−32.2943.01.03.05/20.09.16.09.03/16.01/20.09.07.27/10.03.03403410.30163−17.0310.01.03.03/10.01.09.05
/11.02.03.04/16.19.03/34.11.03.07443350.10.1022−14.9714.10/01.04.01/14.13/16.19.03/20.01.10/20.09.04458500.10.4076−38.4412.04.01474410.40.3053−19.6710.01.05.01/10.01.03.05/10.03.01.03/16.03.01/18.02.01483410.40.9033−23.3610.01.05.01/10.01.03.05496290.20.1055−35.3420.09.04/20.01.10/14.04/42.16504550.1.29164−22.8532.01/2.19/01.05.01.03.01/01.05.01.01.01523550.3.8222−14.9712.04.03/01.03.16.015313260.30.20116−30.1520.09.07.03548510.40.10137−40.6311.02.03.01/11.02.03.04585550.2.43622−13.7720.09.18595470.1065−35.3401.04.01 /01.05.04/14.07.03/30.01.05/43.01.03.05/11.02.03.04615440.12.1075−34.0811.04.01/01.03.16.01643400103−18.5743.01.03.09/01.06.01.07.11665550.1.212355−24.4416.19.03/10.01.05.01/01.04.01/16.03.01674510.190.4054−28.7511.04/01.03.16.01/11.02.03.04/34.11.03.07703440.12.3033−23.3611.06.01/11.04.01723550.1.8473−19.8020.09.13/16.01/14.10/20.09.18743510.180.30.1022−14.9742.10.03/32.01.09/16.03.03/10.03.01.03/10.01.09.05/10.01.05.01767290.1097−46.5820.09.04/20.01.10/14.04/20.03803550.2.52722−14.9730.01.05.01/18.02.01/18.01.01/14.07.03813260.9063−20.3642.04.03/20.09.14/16.07/14.10/16.01/43.01.03.05824260.8044−30.3542.25/20.09.13/20.09.07/20.09.07/20.09.16.09.03864510.180.2074−26.8034.11.03.07/10.01.05.03.01/10.01.05.01/10.03.02873550.1.7443−21.9720.09.07/42.04.03893550.2.32163−20.3616.19.03
/14.13.01.01/14.07.11/01.04.01913550.2.31733−23.3616.03.01/11.02.01/11.02.0295390.3022−14.9734.01.01.03/14.1096411044−30.3543.01.03.05/11.02.03.04/16.19.01/30.01.09.07/14.07.03/01.04.01973260.30.30.2022−14.9714.04 /20.09.07.0510012140.20.3074−20.6043.01.03.05/42.04/40.011016550.3.1274−24.0910.03.01.01.03/43.01.03.05/30.01.05.01/14.07.031029445.2044−25.5216.01/16.19.03/10.03.01.01.03/14.13.01.01/14.10/14.07.051037140.20.20255−23.2143.01.03.05/40.01/16.01/42.04.03/20.09.18.09.011045140.20.3074−25.1943.01.03.05/42.01/32.01.03/20.09.18.09.0110511260.601010−66.3320.09.07.031067270.20.4043−18.4210.03.04.031089133.10107−41.7910.03.01.01/18.02.011103140.30.30143−17.4620.09.14/10.03.05.01/10.03.04.09/10.03.01.01.11/02.45.111125270.20.2033−21.0510.03.04.05/16.011135270.20.1033−21.0510.03.04.05Table 4
Comparison of our method and CFinder in terms of the
number of functional categories shared by all the proteins in the
groups.
Functional categories common to all proteins in the groupGroups found by our programGroups found by CFinder< 19 (7.8%)35 (18.0%)= 119 (16.3%)37 (18.9%)= 227 (23.3%)35 (18.0%)> 261 (52.6%)88 (45.1%)Total116 (100%)195 (100%)To compare the functional coherence of the groups
found by our program with that of cliques found by CFinder, we tested both
programs on the same dataset. 75.9% of the groups identified by our program
have at least two functional categories shared by all the proteins in the
groups, whereas 63.1% of the groups identified by CFinder have at least two
functional categories shared by all the proteins in the groups (Table 4). This result
indicates that our program finds groups with stronger functional coherence than
CFinder.Table5 shows the actual running times of our program
and CFinder on three datasets of yeast protein interactions. Our program is
faster than CFinder on all datasets, and the difference in speed becomes more
obvious as the dataset becomes bigger.Table 5
Running times of the programs on 3 data sets
of yeast protein interactions on a Pentium IV 3.0 GHz processor with 512 MB
memory.
ProgramMIPS data (4874 nodes 15660 edges)DIP data (4932 nodes 17491 edges)BOND data (18692 nodes 59516 edges)Our program10.06 s13.06 s1 m 06.63 sCFinder17.45 s24.33 s2 m 22.46 sMIPS data: PPI_180105.tab from MIPS
(1/18/2005).DIP data: yeast20071104.lst from DIP (11/04/2007).BOND data: data from BOND (11/9/2007).


## 4. Conclusion

Identifying
hidden topological structures of protein interaction networks often unveil
biologically relevant functional groups and structural complexes. We developed
an efficient heuristic algorithm for finding cliques and near-cliques in
protein interaction networks. From the interaction data of yeast proteins, the
algorithm identified 116 near-cliques. Comparison with the experimental data
showed that 59% of the near-cliques have at least one function shared by all
the proteins within a near-clique, and that 56% of the near-cliques show a good
agreement with known protein complexes, which are cataloged in the MIPS
Saccharomyces cerevisiae genome database.



---

*Source: 860270-2008-03-12.xml*