September 3, 2009

15:56

WSPC - Proceedings Trim Size: 9.75in x 6.5in

05-Srihari

1

REFINING MARKOV CLUSTERING FOR
PROTEIN COMPLEX PREDICTION BY INCORPORATING
CORE-ATTACHMENT STRUCTURE
SRIGANESH SRIHARI1
srigsri@comp.nus.edu.sg

KANG NING2
kning@umich.edu

HON WAI LEONG1
leonghw@comp.nus.edu.sg

1 School of Computing, National University of Singapore, Singapore 117590
2 Department of Pathology, University of Michigan, Ann Arbor, MI

Protein complexes are responsible for most of vital biological processes within the cell.
Understanding the machinery behind these biological processes requires detection andanalysis of complexes and their constituent proteins. A wealth of computational approaches towards detection of complexes deal with clustering of protein-protein interaction (PPI) networks. Among these clustering approaches, the Markov Clustering (MCL)
algorithm has proved to be reasonably successful, mainly due to its scalability and robustness. However, MCL produces many noisy clusters, which either do not represent
any known complexes or have additional proteins (noise) that reduce the accuracies
of correctly predicted complexes. Consequently, the accuracies of these clusters whenmatched with known complexes are quite low. Refinement of these clusters to improve
the accuracy requires deeper understanding of the organization of complexes. Recently,
experiments on yeast by Gavin et al. (2006) revealed that proteins within a complex
are organized in two parts: core and attachment. Based on these insights, we propose
our method (MCL-CA), which couples core-attachment based refinement steps to refine
the clusters produced by MCL. We evaluated the effectiveness of our approach on two
different datasets and compared the quality of our predicted complexes with that produced by MCL. The results show that our approach significantly improves the accuracies
of predicted complexes when matched with known complexes. A direct result of this isthat MCL-CA is able to cover larger number of known complexes than MCL. Further, we
also compare our method with two very recently proposed methods CORE and COACH,
which also capitalize on the core-attachment structure. We also discuss several instances
to show that our predicted complexes clearly adhere to the core-attachment structure as
revealed by Gavin et al.
Keywords: Protein complex; PPI network; Markov Clustering.

1. Introduction
One of the most interesting challenges of postgenomic biology is to understandhow proteins interact and organize themselves to generate vital biological functions. Biological processes such as cell cycle, replication, and signal transduction
require precise arrangement of protein molecules for proper assembly and function.
However, many principles as to how individual proteins form such molecular struc-September 3, 2009

2

15:56

WSPC - Proceedings Trim Size: 9.75in x 6.5in

05-Srihari

S. Srihari, K. Ning, & H. W. Leongtures are still unknown. Protein complexes are amongst the fundamental units ofthis macromolecular organization and are responsible for most of vital biologicalprocesses within the cell. For example, the HOPS complex associates with the vacuolar membrane and is involved in homotypic fusion and vacuole protein sortingin yeast [11]. Therefore, understanding the underlying organizational principles ofcellular machinery requires detection and analysis of protein complexes.
Most computational methods for detection of protein complexes work on protein
interaction data. The interactions among proteins are assembled in the form of aprotein-protein interaction (PPI) network: each node represents a unique protein,
and an edge between a pair of nodes represents an interaction (verified throughreliable biological experiments) between the two corresponding proteins. Transientinteractions are not considered. PPI networks are undirected and may be unweighted
or weighted, with the weight on an edge representing the confidence score (usually
between 0 and 1) for the interaction. Protein complexes within the PPI network form
stable subnetworks which are believed to have relatively more number of interactions. Therefore, most computational methods focus on detecting dense subnetworks
within the PPI network.
A wealth of methods make use of graph clustering procedures to detect complexes [2, 6, 13]. The K-means and hierarchical clustering methods are the classicalones, along with some more recent ones (see [6]). Clustering is an unsupervised
learning method that identifies intrinsic similarities between data elements in order to group them into disjoint or overlapping substructures. It typically involves
a metric or similarity measure to achieve this grouping. It requires solving an optimization problem to arrive at the best solution (global minimum of a defined error
quantity). However, the application of clustering approaches to biological networks
encounters yet another challenge: their ability to deal with high levels of noise.
Among the clustering algorithms, the Markov Clustering Algorithm (MCL) has
become very popular since its proposal in 2000 [2]. It is a fast and scalable unsupervised clustering algorithm. It makes use of the concept of random walks: given
a graph G, assume a walk taken along the graph starting at an arbitrary nodev. The walker visits every neighbor u of v with equal probability. If she enters adense region of G, she will remain in the dense region with high probability. So, by
simulating a large number of random walks (called a flow), the underlying cluster
structure in the graph can be identified. Unlike other clustering procedures, MCL
considers the connectivity properties of the underlying network, and is therefore
capable of deriving clusters that are relatively dense, even though they may nothave high absolute densities.
So far, MCL seems to be the most successful clustering algorithm for deriving
protein complexes from PPI networks [3, 13]. It was shown to outperform a numberof algorithms like MCODE [1] specifically designed for partitioning PPI networks.
It has been used for comprehensive analysis of complexes derived from the yeastinteractome [7, 12]. Very recently, Vlasblom et al. [13] showed that MCL performed
far better than other successful algorithms like Affinity Propagation (AP) [4] on

September 3, 2009

15:56

WSPC - Proceedings Trim Size: 9.75in x 6.5in

05-SrihariProtein Complex Prediction by Core-Attachment

3

PPI networks. MCL was shown to be highly robust and tolerant to varying levelsof noise, typical to biological networks.
Inspite of these advantages, MCL has some limitations when applied to PPI networks. MCL mainly produces disjoint clusters from the underlying network (thoughrarely it may report overlapping clusters by changing some ‘options’ in the software).
However, it is known from previous studies [1] that protein complexes may be overlapping: a protein may take part in more than one complex. Secondly, MCL is a
general network clustering algorithm and does not take into account the biologicalproperties or organization within protein complexes. Our experiments show that
MCL produces many noisy clusters, which either do not represent any known complexes or have additional proteins (noise) that reduce the accuracies of correctlypredicted complexes. Consequently, the accuracies of these clusters when matchedwith known complexes are quite low. Additionally, MCL generates many clusters
without actually ranking them using some biologically meaningful criteria.
In view of the existing interest in applying MCL (and clustering methods ingeneral) to identify complexes from PPI networks, this paper attempts to make useof the advantages of MCL, and also overcome some of the limitations mentioned
above. We refine the clusters produced by MCL to improve their accuracies. These
refinement steps make use of deeper understanding of protein complex organization,
recently revealed by Gavin et al. [5].
The experiments by Gavin et al. [5] on yeast revealed that proteins within a complex are organized as cores and attachments (see Figure 1 in supplementary materials). These core proteins show high-level of functional similarity and have relatively
more interactions among themselves. Attachment proteins are closely-associatedwith these core proteins, and they together form the complex. An attachment protein may be present in more than one complex. Among the attachments there may
be modules, which are sets of two or more proteins always together and present in
multiple complexes.
We propose our method to refine the clusters produced by MCL using the coreattachment structure as revealed by Gavin et al.’s work. We call our method MCL
coupled with Core-Attachment (MCL-CA). Very recently (2009), Henry Leung etal. proposed the CORE algorithm [8], and Min Wu et al. proposed the COACH
algorithm [9], which also make use of the core-attachment structure to predict complexes from PPI networks.
We tested MCL-CA on two high-quality yeast PPI datasets from Gavin et al. [5]and Krogan et al. [7]. We show that MCL-CA is able to significantly improve theaccuracies of complexes predicted by MCL when matched with known complexes. A
direct result of this is that MCL-CA is able cover larger number of known complexes
than MCL. Further, we also compare our method with CORE and COACH, sincethese two methods also capitalize on the core-attachment structure.

September 3, 2009

4

15:56

WSPC - Proceedings Trim Size: 9.75in x 6.5in

05-Srihari

S. Srihari, K. Ning, & H. W. Leong

2. Methods
In this section, we describe the various steps in our computational approach. Before we describe our algorithm, we introduce a few notations. Our PPI graph isundirected and unweighted, and is denoted as G = (V, E), where V is the set ofproteins and E is the set of interactions between the proteins. Any subgraph of G
is represented as S = (Vs , Es ) for Vs ⊆ V and Es ⊆ E. For a protein p ∈ V , N (p)is the set of neighbors of p. Our algorithm is structured as a sequence of following
steps:(i) Cluster the PPI graph using MCL.
(ii) Determine core proteins.
(iii) Filter out noisy clusters.
(iv) Determine attachment proteins.
(v) Determine module proteins.
(vi) Determine complexes and rank them.
2.1. Clustering the PPI graph using MCL
The first step in our algorithm is to cluster the PPI graph using the MCL algorithm.
Upon running MCL on G = (V, E), we obtain a set of k disjoint clusters of proteins,Sgiven by {Ci : Ci = (Vi , Ei ), 1 ≤ i ≤ k}, where Vi ⊆ V and Ei ⊆ E. Also, i Vi = V .
And, for any 1 ≤ i, j ≤ k, i 6= j, Vi ∩ Vj = ∅. Among these clusters, we discard away
all clusters of size 1 and retain the remaining.
2.2. Determining core proteinsCore proteins, as described by Gavin et al. [5], show greatest degree of physicalassociation, high similarity in expression levels, and represent functional units withincomplexes. In our model, we consider core proteins as the set of proteins that satisfy
the following two properties: (a) Every complex has a set of core proteins; (b)The core proteins in a protein complex have relatively more interactions among
themselves, and less interactions with proteins outside the complex.
We categorize a protein p ∈ Vi to be a core protein in cluster Ci , given byp ∈ Core(Ci ), if: (a) The in-degree of p with respect to the cluster Ci is greaterthan the average in-degree of Ci , given by: din (p, Ci ) ≥ davg (Ci ); and (b) The indegree of p with respect to Ci is greater than the out-degree of p with respect to
Ci , which is given by: din (p, Ci ) > dout (p, Ci ). The in-degree of p ∈ Vi with respect
to Ci is the number of interactions p has with proteins within the cluster Ci . It isdefined as din (p, Ci ) = |N (p, Ci )| = |{(p, q) : (p, q) ∈ Ei , q ∈ Vi }|. Similarly, the outdegree of p ∈ Vi with respect to Ci is the number of interactions p has with proteinsoutside the cluster Ci . It is defined as dout (p, Ci ) = |{(p, r) : (p, r) ∈ E, r ∈/ Vi }|.
Then the average in-degree of cluster Ci is the average of in-degrees of all proteinsP
within Ci , given by davg (Ci ) =din (p, Ci )/|Ci |.

September 3, 2009

15:56

WSPC - Proceedings Trim Size: 9.75in x 6.5in

05-SrihariProtein Complex Prediction by Core-Attachment

5

2.3. Filtering out noisy clusters
As per Gavin et al.’s work [5], core proteins represent functional units within complexes. Therefore, we consider clusters without any core proteins as noisy clusters. Additionally, our experiments showed that MCL produces many isolated twoprotein clusters (two proteins linked to each other, and not linked to any otherprotein) that have very low significance and do not represent any real complexes.
We consider all such clusters as noisy and filter them out.
2.4. Determining attachment proteinsAttachment proteins, as described by Gavin et al. [5], are densely associated withthe core proteins, and show greater heterogeneity in expression levels. In our model,
we consider attachment proteins as the set of proteins that satisfy the following
property: The attachment proteins of any complex are densely connected to thecore proteins of that complex. An attachment protein is not unique to a complex,
instead may be present in more than one complex.
We categorize the attachment proteins in cluster Ci into local and foreign attachments, together represented by the set Attach(Ci ). We consider a protein p to
be a local attachment in cluster Ci if: (a) p ∈ Vi ; and (b) p is a common neighbor toat least half the core proteins in Ci , that is, |N (p, Ci ) ∩ Core(Ci )| ≥ |Core(Ci )|/2.
However, our experiments revealed that with (b) we might miss out some true local attachments and therefore, we also include the following heuristic: if p ∈ Vi isconnected to at least two core proteins in Ci but has more neighbors within Ci
than outside, that is, |N (p, Ci ) ∩ Core(Ci )| ≥ 2 and din (p, Ci ) > dout (p, Ci ), thenp is a local attachment in Ci . We consider a protein p to be a foreign attachment
in cluster Ci if: (a) p ∈/ Vi ; and (b) p is a common neighbor to more than halfcore proteins of Ci , that is, |N (p, Ci ) ∩ Core(Ci )| > |Core(Ci )|/2 and |Ci | > 2.
With these properties, p may be an attachment in two clusters Ci and Cj , that is,p ∈ Attach(Ci ) and p ∈ Attach(Cj ).
2.5. Determining module proteins
Modules, as described by Gavin et al. [5], are groups of proteins that are most likely
to be in direct physical contact with cores, show greatest degree of functional similarity, are least likely to be present partially, and give rise to “cross-talk” between
various functional categories. In our model, we consider modules as proteins thatsatisfy the following two properties: (a) The set of module proteins of a complex
form a proper subset of the attachment proteins in that complex; (b) The set ofmodule proteins are present in more than one complex in entirety.
Let proteins p and q be attachments in two clusters Ci and Cj . We consider theset M = {p, q} to be a module in clusters Ci and Cj , if M is present in entirety within
the attachment sets of Ci and Cj . This is given by the condition: M ⊆ Attach(Ci )and M ⊆ Attach(Cj ). Note that M can have more than two proteins and may bepresent in more than two clusters as well.

September 3, 2009

6

15:56

WSPC - Proceedings Trim Size: 9.75in x 6.5in

05-Srihari

S. Srihari, K. Ning, & H. W. Leong

2.6. Determining complexes and ranking them
As per Gavin et al.’s work [5], protein complexes are composed of cores and attachments. In our model, we form a unique protein complex Ci0 from each cluster
Ci : The constituent proteins of the complex Ci0 include all the core and attachment proteins of Ci . We discard away all proteins categorized as neither cores nor
attachments. Therefore, Ci0 = (Vi0 , Ei0 ), where Vi0 = [Core(Ci ) ∪ Attach(Ci )] andEi0 = {(p, q) : (p, q) ∈ E, p ∈ Vi0 , q ∈ Vi0 }. The resulting protein complexes may beoverlapping with attachment proteins forming part of multiple complexes.
After the protein complexes are constructed, we rank them based on a scoring
function Score, which is based on the edge density γ and in-to-out ratio R of thecomplexes. The scoring function for Ci0 is defined as: Score(Ci0 ) = γ(Ci0 ) ∗ R(Ci0 ),000where γ(Ci0 ) = |Ei0 |/|Emax| and R(Ci0 ) = |Eout|/|Ei0 |. Here, Emax
is the set of all
i
i
i
0
0
possible interactions between proteins in Vi , that is, |Emaxi | = (|Vi0 |) ∗ (|Vi0 | − 1)/2,0
is the set of all external interactions involving proteins in Vi0 , that is,and Eouti0Eouti = {(p, q) : (p, q) ∈ E, p ∈ Vi0 , q ∈/ Vi0 }.
3. Results and discussions
We extended the MCL software [2] to implement MCL-CA using C/C++ combinedwith PL/SQL on a Pentium P4 Dual Core 3GHz 2GB RAM Linux machine. We
used two high-quality protein-protein interaction datasets of yeast from Gavin etal. [5] and Krogan et al. [7]a . The details of the datasets are shown in Table 1.
As of now, biological experiments to show the core-attachment structure have been
revealed only on yeast, so we do not know yet whether complexes of other organisms
display similar structures.
Table 1.
DatasetGavin, 2006
Krogan, 2006

Number ofproteins
1430
2675

Details of datasets
Number ofinteractions
6531
7080

Average number ofinteractions per protein
10.62
6.98

For the evaluation of our predicted complexes, we used the manually curated
yeast complexes from Wodaklab [10] as the benchmark. The Wodaklab CYC2008b
catalogue contains 408 yeast complexes. Each of our predicted complexes was compared to the known complexes from the benchmark. For this, we used the accuracy
2
measure as proposed in [1], given by Acc = (Nc ) /(Np .Nt ), where Nc is the numberof common proteins shared by the predicted and known complexes, and Np and Nt
are the numbers of proteins in the predicted and known complexes, respectively.
a Gavin and Krogan download from GRID database [BioGRID version 2.0.33]: http://www.
thebiogrid.org/
b Wodaklab Curated complexes 2008: http://wodaklab.org/cyc2008/

September 3, 2009

15:56

WSPC - Proceedings Trim Size: 9.75in x 6.5in

05-SrihariProtein Complex Prediction by Core-Attachment

7

If the accuracy is greater than or equal to a threshold t, we assume the known
complex has been found in our dataset. Sensitivity is the proportion of known complexes found for a given threshold. Finally, we used the co-annotations from Gene
Ontologyc to validate the functional similarities between proteins within complexes.
3.1. Improvement over MCL
We did a three-fold comparison between MCL and MCL-CA in terms of: (a) the
total number of predicted complexes; (b) the number of predicted complexes thatmatched known complexes; (c) the accuracies of predicted complexes. Table 1 in
supplementary materials compares the total number of complexes predicted by MCL
and MCL-CA (with inf lation = 2.0) from the two datasets. It shows that MCL
produced many insignificant (noisy) clusters, which were discarded by MCL-CA in
the filtering step. Table 2 shows the number of known complexes that were correctlypredicted by MCL and MCL-CA for thresholds t = {0.6, 0.7, 0.8}. The number ofknown complexes covered by MCL-CA was significantly higher than that of MCL
for all threshold values. There was no complex correctly predicted by MCL that was
missed by MCL-CA. The difference in the numbers of known complexes covered by
MCL and MCL-CA was larger for threshold t = 0.6 than for t = {0.7, 0.8}. For
example, for the Gavin dataset, MCL-CA covered 14 more known complexes for
t = 0.6, and 8 more known complexes for t = 0.8.
Table 2.

No. of known complexes predicted by MCL and MCL-CA

No. of known complexes correctly predicted for t = {0.6, 0.7, 0.8}.
Dataset
Gavin

MCL
53

Krogan81

t = 0.6
MCL-CA
67
100

MCL
38
48

t = 0.7
MCL-CA
45
65

MCL
27
36

t = 0.8
MCL-CA
35
50

In order to analyse the variation in increase in the number of known complexes
covered by MCL-CA over MCL, we considered two sets of complexes predictedeach from Gavin and Krogan datasets: (a) set A = MCL ∩ MCL-CA consisted of allcomplexes correctly predicted by both methods, but with different accuracies; (b) set
B = MCL-CA \ MCL consisted of all complexes correctly predicted by MCL-CA
and not by MCL. The accuracy threshold was set to t = 0.6. For the Gavin dataset,|A| = 16 and |B| = 14, while for the Krogan dataset, |A| = 23 and |B| = 19. Table 3
shows the minimum, maximum and average increase in accuracies for MCL-CA over
MCL for the complexes in sets A and B. The increase in accuracies for predictedcomplexes in A was noticably high, with the average being 16.01% and 15.29% for
Gavin and Krogan datasets, respectively. The increase in accuracies for predictedcomplexes in B was significant, with the average being 53.02% and 51.34% for Gavinc Gene Ontology: http://geneontology.org

September 3, 2009

8

15:56

WSPC - Proceedings Trim Size: 9.75in x 6.5in

05-Srihari

S. Srihari, K. Ning, & H. W. Leongand Krogan datasets, respectively. Tables 2 and 3 show that MCL-CA significantly
improved the accuracies of many low quality complexes present in the datasets. As
a result, these low quality complexes, which were difficult to be covered by only
MCL, matched known complexes with better accuracies and therefore covered by
MCL-CA.
Table 3.

Overall increase in accuracy for MCL-CA over MCL for t = 0.6
A = MCL ∩ MCL-CA; B = MCL-CA \ MCL.
Increase in accuracy(%)
A

B

Dataset

Min

Max

Avg

Min

Max

Gavin

5.0%

40.84%

16.01%

13.21%

103.03%Avg
53.02%

Krogan4.16%

63.93%

15.28%

11.11%

91.0%

51.34%

Table 2 in supplementary materials displays the improvement in accuracies fora sample of 10 complexes predicted from the Gavin dataset with threshold t = 0.6.
The complexes in the upper half belonged to set A, while those in lower half belonged
to set B. The improvement was noticably high for complexes in set A. For example,
the Exocyst complex. The improvement was significant for complexes in set B.
These were the low quality complexes that did not match any known complex withaccuracy ≥ t = 0.6 using only MCL. MCL had induced many additional (noise)proteins in these complexes. With the refinement due to MCL-CA, these matched
known complexes with better accuracies. For example, the COPI complex.
Table 4.

Comparisons between all four methods

No. of known complexes correctly predicted for t = {0.6, 0.7, 0.8}
Threshold t
DatasetMCL
MCL-CA COACH CORE
0.6
0.7
0.8

Gavin
KroganGavin
KroganGavin
Krogan

53
81
38
48
27
36

67
100
45
65
35
50

59
96
43
59
39
53

73
106
48
89
31
65

3.2. Comparisons with CORE and COACH
CORE [8] and COACH [9] are two very recently (2009) proposed methods that
also make use of the core-attachment structure to detect complexes from yeast
PPI networks. However, all the three methods (CORE, COACH and MCL-CA) are
different from one another in the computational essense. While CORE calculates
p-values between proteins within the entire network and builds cores from them,
COACH finds dense subgraphs (preliminary cores) and adds attachments to them.
COACH and MCL-CA are significantly faster computationally compared to CORE.

September 3, 2009

15:56

WSPC - Proceedings Trim Size: 9.75in x 6.5in

05-SrihariProtein Complex Prediction by Core-Attachment

9

Fig. 1. Overlaps in known complexes covered by CORE, COACH and MCL-CA for t = 0.6 on
the Gavin dataset.

On the same Gavin and Krogan datasets, CORE produced 295 and 819 complexes, while COACH (f ilter = 0.225) produced 326 and 345 complexes, respectively. We matched these complexes against the same benchmark. Since each method
produced different number of complexes and with or without ranking, we considered
all the produced clusters for the comparison. Table 4 summarizes this comparison.
Though COACH and CORE performed better than MCL-CA at higher thresholds,
MCL-CA was successful in substantially increasing the accuracies of mainly low
quality complexes beyond the threshold t = 0.6. The ratios of correctly predictedcomplexes to total clusters produced were also higher for MCL-CA for t = {0.6, 0.7}.
Figure 1 shows the overlaps in known complexes covered by the three methods for
t = 0.6 on the Gavin dataset: CORE ∩ MCL-CA = 56, COACH ∩ MCL-CA =41, CORE ∩ COACH = 49, and CORE ∩ COACH ∩ MCL-CA = 37. This showsamong the three methods, there is none which totally covers all complexes predictedby another.
3.3. Analysis of complexes predicted by MCL-CA
We visualized the predicted complexes of MCL-CA using Cytoscape environmentd .
The supplementary materials contain visualizations and explanations for a sample
of complexes that include the Golgi Transport complex (PubMed id: 11703943),
Arp 2/3 Protein complex (PubMed id: 10377407) and Kornberg’s Mediator complex (PubMed id: 15477388). Additionally, we found a set of module proteins thatformed the constituents of RNA polymerase complexes I, II, III. We also discovered potential novel complexes that matched the novel complexes found by Gavinet al. Further we also did analysis of our predicted complexes to validate the coreattachment structures (all details in supplementary materials).
4. Conclusions and future work
Considering the immense popularity of the Markov Clustering (MCL) algorithm inclustering PPI networks, we have developed the MCL-CA approach to predict yeastd Cytoscape: http://www.cytoscape.org/

September 3, 2009

10

15:56

WSPC - Proceedings Trim Size: 9.75in x 6.5in

05-Srihari

S. Srihari, K. Ning, & H. W. Leongprotein complexes with better accuracies.
There is a lot of scope for further improvements and research in this direction.
The proposed ranking method tends to favor larger complexes. Better statisticalmeasures to rank complexes can be developed that reflect vital biological measures.
Further, we have shown results only on unweighted PPI datasets. It will be worthwhile to see the results on weighted PPI datasets. Together with these weights, it will
be interesting to develop new ranking measures for the complexes. We also intend
to analyse the performance of MCL-CA using a larger benchmark set of manuallycurated complexes. Finally, these techniques are based on core-attachment structures found in yeast complexes. It will be interesting to check by computational
means if complexes from other organisms display these structures even before wetlab experiments are performed.
Acknowledgements
This work was supported in part by the National University of Singapore under ARF
grant R252-000-361-112. We would like to thank Henry Leung and Qian Xiang forproviding the list of predicted clusters from CORE [8], Wu Min for providing the
COACH software [9] and the reviewers for their valuable comments.
References[1] Bader G.D., and Hogue C.W.V., An automated method for finding molecular complexes in large protein interaction networks, BMC Bioinformatics, 4, 2003.
[2] Dongen S., Graph clustering by flow simulation, PhD thesis, CIW, University of
Utrecht, 2000.
[3] Enright A.J., Dongen S.,Ouzounis C.A., An efficient algorithm for large-scale detection of protein families, Nucleic Acids Research, 30, 1575-1584, 2002.
[4] Frey B.J., Dueck D., Clustering by passing messages between data points. Science,
315(5814), 972-976, 2007.
[5] Gavin A.C., et al., Proteome survey reveals modularity of the yeast cell machinery,
Nature, 440, 631-636, 2006.
[6] Hastie T., Tibshirani R., Friedman J., The Elements of Statistical Learning: Data
Mining, Inference, and Prediction, New York: Springer, 2001.
[7] Krogan N.J., et al., Global landscape of protein complexes in yeast Saccharomyces
cerevisiae, Nature, 440, 637-643, 2006.
[8] Leung H., Xiang Q., Yiu S.M., Chin F., Predicting protein complexes from PPI data:
A core-attachment approach, Journal of Computational Biology, 16, 133-144, 2009.
[9] Min W., Li X., Kwoh C.K., Ng S.K., A core-attachment based method to detect
protein complexes in PPI networks, BMC Bioinformatics, 10:169, 2009.
[10] Pu S., et al., Up-to-date catalogues of yeast protein complexes. Nucleic Acids Research., 18, 2008.
[11] Seals D.F., et al., A Ypt/Rab effector complex containing the Sec1 homolog Vps33p
is required for homotypic vacuole fusion, Proc Natl Acad Sci, 97(17), 9402-9407, 2000.
[12] Vlasblom J., et al., Identifying functional modules in the physical interactome of
Saccharomyces cerevisiae, Proteomics, 7, 944-960, 2007.
[13] Vlasblom J., Wodak S.J., Markov clustering versus affinity propagation for the partitioning of protein interaction graphs, BMC Bioinformatics, 10, 2009.