{'fraction_non_alphanumeric': 0.026064610866372982, 'fraction_numerical': 0.009687550987110459, 'mean_word_length': 5.200429944360142, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A survey of computational methods for protein complex prediction from protein interaction networks

Complexes of physically interacting proteins are one of the fundamental functional units responsible for driving key biological mechanisms within the cell. Their identification is therefore necessary not only to understand complex formation but also the higher level organization of the cell. With the advent of high-throughput techniques in molecular biology, significant amount of physical interaction data has been cataloged from organisms such as yeast, which has in turn fueled computational approaches to systematically mine complexes from the network of physical interactions among proteins (PPI network). In this survey, we review, classify and evaluate some of the key computational methods developed till date for the identification of protein complexes from PPI networks. We present two insightful taxonomies that reflect how these methods have evolved over the years towards improving automated complex prediction. We also discuss some open challenges facing accurate reconstruction of complexes, the crucial ones being presence of high proportion of errors and noise in current high-throughput datasets and some key aspects overlooked by current complex detection methods. We hope this review will not only help to condense the history of computational complex detection for easy reference, but also provide valuable insights to drive further research in this area.


Introduction
Most biological processes within the cell are carried out by proteins that physically interact to form stoichiometrically stable complexes. Even in the relatively simple model organism Saccharomyces cerevisiae (budding yeast), these complexes are comprised of many subunits that work in a coherent fashion. These complexes interact with individual proteins or other complexes to form functional modules and pathways that drive the cellular machinery. Therefore, a faithful reconstruction of the entire set of complexes (the 'complexosome') from the physical interactions among proteins (the 'interactome') is essential to not only understand complex formations, but also the higher level cellular organization.
Protein complexes constitute modular functional units within the network of physical interactions, the PPI network 1 . From a biological perspective, this mod-ularity is a result division of labor and of evolution to provide robustness against mutation and chemical attacks 2 . From a topological perspective, this modularity is a result of proteins within complexes being densely connected to each other than to the rest of the network 3 .
Since the advent of "high-throughput" screening in molecular biology in the late 1990s and early 2000s, several techniques have been introduced to infer physical interactions among proteins within organisms in a large-scale ("genome-wide") manner. These have helped to catalogue significant amount of protein interactions in organisms such as yeast thereby fueling computational techniques to systematically mine and analyze such large-scale interaction data. In yeast, the Yeast two-hybrid (Y2H) 4,5 , Protein Complementation Assay (PCA) 6 and Tandem Affinity Purification followed by Mass Spectrometry (TAP-MS) 7,8,9,10 are some of the widely adopted experimental systems that have helped to identify a considerable fraction of physical interactions among proteins. However, even at the current 'state-of-theart', these high-throughput techniques have been shown to produce considerable proportion of spurious (false positive) interactions 11,12,13,14 . Therefore, once the interactions are identified their qualities need to be first assessed to generate a reliable set of interactions that is deemed suitable for further mining and analysis. This process includes assigning each interaction a confidence score that typically accounts for the biological variability and technical limitations of the experimental conditions, and therefore reflects the reliability of the inferred interaction 15,16,17,18,19,20,21,22,23,24 . The interactions with confidence scores below a certain threshold are discarded to build a reliable "cleaned-up" PPI network. This PPI network is then mined to identify groups of proteins potentially forming complexes. The whole process can be summarized in the following steps: (1) Integrating high-throughput datasets from multiple experiments and assessing the reliabilities of interactions; (2) Constructing a reliable PPI network; (3) Identifying modular subnetworks from the PPI network to generate a candidate list of complexes; (4) Evaluating the identified complexes against bona fide complexes, and validating and assigning roles to novel complexes.
The identification of complexes from high-throughput interaction datasets has attracted considerable attention from both biologists as well as computational research communities, and over the years, several computational techniques have been developed to systematically identify complexes. Quite naturally, a number of surveys have come out from time-to-time evaluating and comparing these techniques for their performance on available PPI datasets. One of the earliest comprehensive evaluations was by Brohee and van Helden (2006) 25  The purpose of our work is to provide an up-to-date survey, classification (taxonomy) and evaluation of some the representative works done till date (2011/2012). We build upon the existing surveys so as to not repeat entirely the evaluations and conclusions already drawn, yet we provide our own classifications and evaluations of more recent techniques across up-to-date PPI datasets. We also compare across unscored (raw) and scored PPI datasets, which is missing in these existing surveys. We also highlight and comment on some of the newer challenges and open problems in complex prediction, which can guide future directions for research in this area.

Review of existing methods for complex detection
We begin by mentioning some definitions and terminologies widely adopted across the reviewed works. A PPI network is modeled as an undirected graph G = (V, E), where V is the set of proteins and E = {(u, v) : u, v ∈ V } is the set of interactions among protein pairs. For any protein . This is a real number between 0 and 1, and typically quantifies the "richness of interactions" within G: 0 for a network without any interactions and 1 for a fully connected network. The clustering coefficient CC(v) measures the "cliquishness" of the neighborhood of v: where E(v) is the set of edges in the neighborhood of v. If the interactions of the network are reliability scored (weighted), these definitions can be extended to their corresponding weighted versions: scoring function on the interactions in E. There are several interesting variants proposed for weighted clustering coefficient CC w ; for a survey see 28 .

Taxonomy of existing methods
Although at a very generic level most existing methods make the key assumption that complexes are embedded among densely-interacting groups of proteins within PPI networks, these methods vary considerably either in the algorithmic methodologies or the kind of biological insights employed to detect complexes. Accordingly, we classified some popular complex detection methods into two broad categories (a soft classification): (i) methods based solely on graph clustering; (ii) methods based on graph clustering and some additional biological insights. These biological insights may be in the form of functional, structural, organizational or evolutionary information known about complexes or their constituent proteins from experimental or other biological studies.
We present this classification in two snapshots. The first snapshot, shown in Figure 1, gives a chronology-based "bin-and-stack" classification, while the second snapshot, shown in Figure 2 gives a methodology-based "tree" classification of the methods. Fig. 1. The "Bin-and-Stack" classification: Chronological binning of complex detection methods based on biological information used. It is interesting to note that over the years, as researchers have tried to improve the basic graph clustering ideas, they have also incorporated biological information into their methods.
In the chronology-based classification, we binned methods based on the years in which they were developed, and stacked them based on the kind of biological insights used (see Figure 1). The biological insights are grouped as: core-attachment structure, evolutionary information, functional coherence, and mutually exclusive and co-operative interactions. It is interesting to note from this classification that, over the years, as researchers tried to improve the basic graph clustering ideas, they also incorporated a variety of biological information into their methods.
In the methodology-based classification, we distributed the methods to different branches of a classification tree based on the kind of computational strategy used (see Figure 2). At the first level from the root, we grouped these methods into those based solely on graph clustering, and those employing additional biological insights. At subsequent levels, we further divided these methods based on the kind of algorithmic strategies used, into: (i) methods employing merging or growing of clusters; (ii) methods employing repeated partitioning of networks; and (iii) methods employing network alignment. The methods employing merging or growing clusters go "bottom-up", that is, typically start with small "seeds" (for example, triangles or cliques), and repeatedly add or remove proteins or merge clusters based on some similarity measures to arrive at the final set of complexes. On the other hand, the methods based on network partitioning go "top-down", that is, repeatedly partition or break the network into multiple subnetworks based on certain divisive criteria. The methods based on network alignment use multiple networks (typically from different species) to arrive at isomorphic regions that likely correspond to complexes, the inituition being that proteins belonging to real complexes should generally be conserved through the evolution process to act as an integrated functional unit 3 .

Methods based solely on graph clustering
Most methods that cluster the PPI network into multiple dense subnetworks make use of solely the topology of the network.

Molecular COmplex DEtection (MCODE)
MCODE, proposed by Bader and Hogue (2003) 29 , is one of the first computational methods (and therefore, seminal) developed for complex detection from PPI networks. The MCODE algorithm operates in mainly in two stages, vertex weighting and complex prediction, and an optional third stage for post-processing.
In the first stage, each vertex v in the network G = (V, E) is weighted based on its neighborbood density. Instead of directly using clustering coefficient, MCODE uses core-clustering coefficient which measures the density of the highest k-core in the neighborhood of v. This amplifies the weighting of densely connected regions in G.
In the second stage, the vertex v with the highest weight is used to seed a complex. MCODE then recursively moves outwards from the seed vertex, including vertices into the complex whose weight is a given percentage (vertex weight parameter -VWP) away from the seed vertex. A vertex once added to a complex is not checked subsequently. The process stops when there are no more vertices to be added to the complex, and is repeated using the next unseeded vertex. At the end of this process multiple non-overlapping complexes are generated. The optional third stage performs a post-processing on the complexes generated from the second stage. Complexes without 2-cores are filtered out, and new vertices in the neighborhood with weights higher than a given 'fluff' parameter are added to existing complexes. The resultant complexes are scored and ranked based on their densities. The time complexity of the algorithm is O(|V |.|E|.h 3 ), where h is the vertex size of the average vertex neighbourhood in the network G.

Markov CLustering (MCL)
The Markov Clustering (MCL) algorithm, proposed by Stijn van Dongen (2000) 30 , is a general graph clustering algorithm that simulates random walks (called flow) to extract out relatively dense regions within networks. In biological applications, it was first applied to cluster protein families and ortholog groups 31 before it proved to be effective in detecting complexes from protein interaction networks 19,32,33 . MCL manipulates the adjacency matrix of networks with two operators called expansion and inflation to control the random walks (flow). Expansion models the spreading out of the flow, while inflation models the contraction of the flow, making it thicker in dense regions and thinner in sparse regions. These parameters boost the probabilities of intra-cluster walks and demote those of inter-cluster walks. Mathematically, expansion coincides with normal matrix multiplication, while inflation is a Hadamard power followed by a diagonal scaling. Therefore, MCL is highly efficient and scalable. The iterative expansion and inflation separates the network into multiple non-overlapping regions.

Clustering based on merging Maximal Cliques (CMC)
CMC was proposed by Liu et al. (2009) 34 to detect complexes from PPI networks based on repeated merging of maximal cliques. Some earlier algorithms like CFinder 35 and Local Clique Merging Algorithm (LCMA) 36 also adopted clique merging to find dense neighborhoods, but the distinct advantage of CMC over these algorithms is its ability to work on weighted networks and to find relatively low density regions (in subsequent improved versions of CMC).
CMC begins by enumerating all maximal cliques in the PPI network using the Cliques algorithm proposed by Tomita et al. 37 . Although enumerating all maximal cliques is NP-hard, this does not pose a problem in PPI networks because these networks are usually sparse. CMC then assigns a score to each clique C based on its weighted density, which considers the reliabilities (weights) of the interactions within the clique: A Survey of Methods for Complex Detection from Protein Interaction Networks 7 .
CMC then ranks these cliques in decreasing order of their scores and iteratively merges or removes highly overlapping cliques based on their inter-connectivity scores. The inter-connectivity score of two cliques C i and C j is based on the nonoverlapping regions of the two cliques and is defined as: (2) CMC determines whether two cliques C i and C j sufficiently overlap: |C i ∩ C j |/|C j | ≥ overlap thresh. If so, C j is either removed or merged with C i based on the inter score: if the inter score(C i , C j ) ≥ merge thresh, then C i and C j are merged, else C j is removed. Finally, all the resultant merged clusters are output as the predicted complexes.

Clustering with Overlapping Neighborhood Expansion (ClusterONE)
Nepusz et al. (2012) 38 proposed ClusterONE, a method for detecting overlapping protein complexes from weighted PPI networks, based on seeding and greedy growth, similar to MCODE 29 . ClusterONE uses a cohesiveness measure to determine how likely a group of proteins form a complex, and is based on the weight of the interactions within the group and with the rest of the network.
To begin with, ClusterONE identifies seed proteins and greedily grows them into groups with high cohesiveness. When the greedy growth for a group cannot progress any more, a next seed protein is selected to repeat the procedure until no more seed proteins remain. In the second step, ClusterONE identifies highly overlapping cohesive groups and merges them into potential complex candidates. ClusterONE allows identification of overlapping complexes if each of the merged groups represent individual complexes that share proteins. Nepusz et al.'s comparisons with methods like MCODE, MCL and CMC showed that the complexes from ClusterONE achieved comparable accuracies when matched against known 'gold standard' complexes and MCL achieved the closest performance to ClusterONE with the exception that MCL produced only non-overlapping clusters -a distinct advantange of ClusterONE.

Some other methods based on graph clustering
Apart from these discussed methods, three other methods worth mentioning here are LCMA (2005)

Methods incorporating core-attachment structure
Gavin and colleagues (2006) 9 performed large-scale analysis of yeast complexes and found that the proteins with complexes were divided into two distinct groups, "cores" and "attachments". The cores formed central functional units of complexes, while the attachment proteins aided these cores in performing their functions. Several computational methods were proposed to reconstruct complexes from PPI newtorks by capitalizing on this structural organization.
Wu Min et al. (2009) 45 proposed the COACH method which reconstructs complexes in two stages -it identifies dense core regions, and subsequently includes proteins as attachments to these cores. Figure 3 summarizes how COACH identifies core and attachment proteins to build complexes.   46 proposed the CORE method to identify protein cores within the PPI network. They defined the probability of two proteins p 1 and p 2 (of degrees d 1 and d 2 , respectively) to belong to the same core using two main factors: whether the two proteins interact or not and the number of common neighbors m between them. The probability that p 1 and p 2 have ≥ i interactions and ≥ m common neighbors is calculated under the null hypothesis that d 1 edges connecting p 1 and d 2 edges connecting p 2 are randomly assigned in the PPI network according to a uniform distribution. This probability is used to arrive at a p-value for whether p 1 and p 2 belong to the same core. Subsequently, CORE merges sets of core proteins of sizes two, three, etc. until further increase in size is not possible, to produce the final set of cores. CORE then scores and ranks the predicted cores based on the number of internal and external interactions in them. The attachments are added to these cores in a manner similar to COACH to produce the final set of complexes.
Srihari et al. proposed MCL-CA (2009) 47 and the improved (weighted) version MCL-CAw (2010) 48 which identify complexes by refining clusters produced by the MCL algorithm 31,33 by incorporating core-attachment structure. Essentially, MCL-CAw categorizes proteins within MCL clusters into "core" and "attachment" proteins based on their connectivities, and then selects only these categorized proteins into complexes while discarding the remaining "noisy" proteins. This enables MCL-CAw to "trim" the raw MCL clusters. Further, unlike CORE and COACH, the refinement in MCL-CAw capitalizes on reliability scores assigned to the interactions. Consequently, MCL-CAw reconstructs significantly higher number of 'gold standard' complexes (∼30% higher) and with better accuracies compared to plain MCL.
Chin et al. (2010) 44 proposed the HUNTER algorithm which begins by generating a module seed M S(v) for each node v in the PPI network. M S(v) is then pruned by removing vertices having low weight edges to other members of M S(v). Then the maximal q-connected subnetwork of M S(v) is selected as the initial core M QC(v). This core is then expanded into a module by adding new vertices that share many neighbors with M QC(v). If two modules overlap beyond a certain threshold, these modules are merged. The resultant collection of modules form the final set of predicted complexes.

Methods incorporating functional information
Proteins within complexes are generally enriched with same or similar functions 3,9 . If the functional information for proteins from an organism are available, then this information can be combined with topological information from PPI networks for the reconstruction of complexes from the organism. One possible way to incorporate functional information is to score the interactions based on the functional similarity between the interacting pairs of proteins. Alternately, functional annotations (for example, from Gene Ontology 49 ) can be used to aid decisions where including or excluding a protein into complexes purely based on topological information might be difficult.

Restricted Neighborhood Search Clustering (RNSC)
King et al. (2004) 50 proposed the RNSC algorithm that combines topological and Gene Ontology information to detect complexes. The algorithm operates in two steps -it begins by clustering the PPI network and then filters the clusters based on cluster properties and functional homogeneity.
The network G = (V, E) is first randomly partitioned into multiple subnetworks, which is essentially a partitioning of the node set V . The algorithm then iteratively moves nodes from one cluster to another in a randomized fashion till an integer-valued cost function is optimized. A common problem among such clustering algorithms is the tendency to settle in poor local minima. To avoid this, the RNSC algorithm adopts diversification moves, which shuffle the clustering by occasionally dispersing the contents of a cluster at random. Once the clustering process is completed, clusters of small sizes or densities (the lower bound on cluster sizes and densities are experimentally determined) are discarded. Finally, a p-value is calculated using functional annotations (from GO) for each cluster that measures the functional homogeneity of the clusters. All clusters above a certain p-value are discarded to produce the final list of predicted complexes. Based on experiments, King et al. recommend cluster density cut-off of 0.70 and p-value cut-off of 10 −3 .

Dense neighborhood Extraction using Connectivity and conFidence Features (DECAFF)
Li et al. (2007) 51 proposed the DECAFF algorithm which essentially is an extention of the LCMA algorithm 36 proposed earlier by the same group. DECAFF identifies dense subgraphs in a neighborhood graph using a hub-removal algorithm. Local cliques are identified in these dense subgraphs and merged based on overlaps to produce clusters. Each cluster is assigned a functional reliability score, which is the average of the reliabilities of the edges within the cluster. All clusters with low reliabilities are discarded to produce the final set of predicted complexes.
The PCP algorithm 39 described earlier can also be categorized into this set of methods because PCP uses a weighting scheme based on functional similarity (though the similarity is inferred from topology) to assign reliability scores to interactions, and then uses a clique merging strategy to detect complexes.

Methods incorporating evolutionary information
The increasing availability of PPI data from multiple species like yeast, fly, worm and some mammals has made it feasible to use insights from cross-species analysis for detection of (conserved) complexes. The assumption is that proteins belonging to real complexes should generally be conserved through the evolution process to act as an integrated functional unit 3 .  53 for detection of conserved complexes across species based on the evolution of PPI networks. In these methods, an orthology network (network alignment graph) is constructed from the PPI networks of different species, which essentially represents the orthologous proteins and their conserved interactions across the species. For a protein pair {u 1 , v 1 } in network G 1 of species S 1 and (u 2 , v 2 ) in G 2 of species S 2 , the orthology network G 12 contains the pair {u, v} if u 1 is orthologous to u 2 , and v 1 is orthologous to v 2 . The edge (u, v) is weighted by the sequence similarities between the pairs {u 1 , v 1 }, and {u 2 , v 2 }. Any subgraph in this orthology network G 12 is therefore a conserved subnetwork of G 1 and G 2 . Such candidate subgraphs are then evaluated for parts of conserved complexes. Based on this idea, a tool QNet 54 was developed which returns conserved complexes from different species when queried using known complexes from yeast.

Methods based on co-operative and exclusive interactions
The overlapping binding interfaces in a protein may prevent multiple interactions involving these interfaces from occurring simultaneously 55 . In other words, the set of interactions in which a protein participates may be either co-operative or mutually exclusive. The information about the co-occurrence or exclusiveness of interactions can therefore be useful for predicting complexes with higher accuracy. This information can be gathered from the interacting domains of protein pairs or the three-dimensional structures of the interacting surfaces.
Ozawa et al. (2010) 56 proposed a refinement method over MCODE and MCL to filter predicted complexes based on exclusive and co-operative interactions. They used domain-domain interactions to identify conflicting pairs of protein interactions in order to include or exclude proteins within candidate complexes. Based on their results, the accuracies of predicted complexes from MCODE and MCL improved by two-fold.
On the other hand, Jung et al. (2010) 57 used structural interface data to construct a simultaneous PPI network (SPIN) containing only co-operative interactions and excluding competition from mutually exclusive interactions. MCODE and LCMA algorithms tested on this SPIN displayed a sizeable improvement in correctly predicted complexes.
Even though incorporating information about co-operative and exclusive interactions shows promising improvement in complex detection algorithms, there are still several practical problems related to this approach. Gathering more data on conflicting interactions, especially based on three-dimensional structures of interfaces, needs to be addressed before this approach can be more easily adopted.

Incorporating other possible kinds of information
In a recent foresightful survey by Przytycka et al. 58 , the application of network dynamics (temporal information) into current computational analysis is discussed at good lengths, especially with respect to detection of complexes and pathways from protein interaction networks. The authors suggest that if sufficient information about the 'timing activities' of proteins can be obtained, the dynamical nature of the underlying organizational principles in interaction networks can be better understood. This shift from static to dynamic network analysis is vital to understanding several cellular processes, some of which may have been wrongly understood due to ignoring dynamic information.

Comparative assessment of existing methods
Considering the wide variety of proposed methods for complex detection, one can gauge the seriousness in the research effort towards computational identification and categorization of complexes. Several surveys and experiments 25,26,27 have focused on the comparative analyses of these proposed methods for complex detection. Each new work on complex detection also comes with detailed comparative analyses of the new method with some earlier methods. However, due to the differences in PPI and benchmark datasets, evaluation criteria, thresholds and parameters used, and the subset of methods considered for these comparative assessments, different works arrive at different results on the relative performance of methods. But, typically the following broadly accepted criteria are used across the works.
If a reasonably large 'gold standard' set of complexes is available (as in the case of yeast), the performance of a method can be gauged on how accurately its predicted complexes reconstruct or recover the 'gold standard'. Two commonly adopted measures for this are precision and recall 34 . Precision measures how many among the predicted complexes match some 'gold standard' complex, in turn measuring the proportion of realible predictions (accuracy) from the method. Recall measures how many of the 'gold standard' complexes are reconstructed by the method, in turn measuring the coverage or sensitivity of the method. Some methods tend to produce too many (sometimes arbitrary) predictions resulting in high recall but very low precision, and therefore too many false positives to consider the method even reasonably reliable. To handle this, a combination of precision and recall, usually through a harmonic mean called F-measure, is used to evaluate how "balanced" is the method.
On the other hand, if a 'gold standard' set is not available (as in the case mammals, currently), "self-evaluatory" measures like cluster cohesiveness and separability is used 29,50 . The cohesiveness of a predicted complex (cluster) usually measures topological characteristics of the cluster, for example, its interaction density or size, while separability measures how separated is the cluster from others 29 . A combination of cohesiveness and separability reveals how modular is the clustering and therefore how likely the individual clusters represent real complexes.
Another typically independent way to evaluate the predictions is to measure the functional or co-localization coherence of the clusters subjected, however, to availability of appropriate annotation data 34,50 . This captures how functionally coher-ent are the proteins within a predicted complex and whether they are co-localized within the cell. The usual annotations required for these calculations are functions and sub-cellular localizations of the proteins. This evaluation is particularly useful for alternative validation of the predictions. Now, we present a summary of some representative surveys and comparative assessments and their conclusions. One of the first comprehensive assessments was performed by Brohee and van Helden (2006) 25 . They performed a detailed empirical comparison between MCODE 29 , MCL 30 , RNSC 50 and Super-paramagnetic Clustering (SPC) 59 . These algorithms were tested on PPI datasets from highthroughput experiments, and the resultant complexes were evaluated against benchmark complexes from MIPS 60 . Additionally, the PPI datasets were introduced with artificial noise (random edge addition and deletion) to test the robustness of these algorithms. They concluded that MCL and RNSC outperformed MCODE and SPC in terms of precision (the proportion of correctly predicted complexes) and recall (the proportion of correctly derived benchmarks). RNSC was robust to variation in its input parameter settings, while the performance of the other three varied widely for parameter changes. MCL was remarkably robust even upon introducing 80%-100% random noise. Overall, the experiments confirmed the general superiority of MCL over the other three algorithms.
Vlasblom et al. (2009) 26 compared MCL with another clustering algorithm, Affinity Propagation (AP) 61 on unweighted as well as weighted PPI networks. The initial unweighted network was built from a set of 408 hand-curated complexes from Wodak lab 63 followed by random addition and removal of edges to mimic real PPI networks. The weighted network was obtained from the Collins et al.'s work 15 , generated from Gavin and Krogan datasets 9,10 . They concluded that MCL performed considerably better than AP in terms of accuracy and separation of predicted clusters, and robustness to random noise. In particular, MCL was able to achieve about 90% accuracy and 80% separation compared to only 70% accuracy and 50% separation of AP on unweighted PPI networks with introduced random noise. MCL was able to discover benchmark complexes even at high (40%) noise levels.
More recently (2010) Figure 4 (adapted from 27 ). The methods are arranged in chronological order, and it is interesting to note that over the years, the F-

Preparation of experimental data
In our assessment, we experimentally evaluated some key complex detection methods on both unscored (raw) and scored PPI networks. To build our unscored network, we combined the physical interaction from two TAP  Table 1.
The benchmark (reference or 'gold standard') set of complexes was built from three independent sources: 408 complexes of the Wodak lab CYC2008 catalogue 63 , 313 complexes of MIPS 60 , and 101 complexes curated by Aloy et al. 64 . The properties of these reference sets are shown in Table 2. We considered each of these reference sets independently for the evaluation of the methods. We did not merge them into one comprehensive list of complexes because the individual complex compositions are different across the three sources and some complexes may also get

Metrics for evaluating the predicted complexes
Let B = {B 1 , B 2 , ..., B m } and C = {C 1 , C 2 , ..., C n } be the sets of benchmark and predicted complexes, respectively. We use the Jaccard coefficient J to quantify the overlap between a benchmark complex B i and a predicted complex C j : We consider B i to be covered by C j , if J(B i , C j ) ≥ overlap threshold t. In our experiments, we set the threshold t = 0.5, which requires . For example, if |B i | = |C j | = 8, the overlap between B i and C j should be at least 6.
We use previously reported 34 definitions of recall (coverage) and precision (sensitivity) of the set of predicted complexes: Here, |{B i |B i ∈ B ∧ ∃C j ∈ C; J(B i , C j ) ≥ t}| gives the number of derived benchmarks.
Here, |{C j |C j ∈ C ∧ ∃B i ∈ B; J(B i , C j ) ≥ t}| gives the number of matched predictions.
We calculated the F-measure as the harmonic mean of precision and recall,

Experimental evaluation of methods
We considered the following methods for our evaluation: , instead we included MCL as a benchmark in all our comparisons since MCL has been repeatedly shown to perform better than these older methods 25,26,27 . Further, not all methods are devised to make use of interaction confidence scores, and therefore we selected only the ones capable of doing so for the evaluations on the scored network. Table 3 shows the precision and recall values for methods evaluated on the unscored Gavin+Krogan network across the three benchmark sets. The table shows that CORE, HACO and MCL-CAw performed significantly better in terms of recall compared to the rest of the methods. In particular, MCL-CAw performed considerably better than plain MCL indicating that incorporating core-attachment structure into raw MCL clusters helped to improve the accuracies of the predicted complexes. This indicated that incorporating some kind of biological knowledge helped to identify complexes more accurately.
Next, Table 4 shows these values for the methods evaluated on the scored Consolidated network. This table shows that all methods were able to reconstruct significantly higher number of complexes upon scoring as compared to on the unscored network. This clearly indicated that noise in raw datasets (negatively) impacted the performance of methods, and reliability scoring aided in alleviating this impact and thereby improving the performance of methods. This demonstrated the effectiveness of current reliability scoring schemes in cleaning raw interaction datasets for focused studies such as complex detection.

Plugging experimental results into our taxonomy
We next "plugged-in" these evaluation results as well as results obtained from some earlier surveys 26,27 into our "bin-and-stack" classification, as shown in Figure 5. For   each method, we show the F-values before / after scoring, that is, on the unscored G+K network and the scored Consolidated network. Such a representation in our classification revealed two interesting insights, (1) incorporating biological information in addition to PPI topology improved performance of the methods (the F measures have increased in the vertical layers compared to the lowest layer); (2) reliability scoring significantly improved performance of the methods, as shown by the before-after values.
This representation also shows how complex detection methods have evolved over the years to improve performance, and therefore our taxonomy can be useful to guide future directions for further improvement.

Open challenges in complex detection from PPI networks
The review and evaluation of computational methods in the above sections reveal several critical challenges facing accurate identification of complexes from highthroughput interaction datasets. We saw that most methods are considerably impacted by noise in raw datasets. Further, most methods are able to reconstruct only a fraction of the known complexes (achieve at the most 65% recall) even upon scoring. This points towards some inherent limitations within the methods itself. On this basis, we broadly classify the challenges facing current methods into two categories, (i) challenges originating from biological datasets; (ii) challenges originating from existing computational techniques.

Challenges from interaction datasets
Even though over the last few years, several independent high-throughput experiments have helped to catalogue enormous amount of interactions from yeast, they show surprising lack of correlation with each other, and lack of coverage -bias towards high abundance proteins and against proteins from certain cellular compartments (like cell wall and plasma membrane) 12,11,13,14 . Also, each dataset still contains a substantial number of false positives (noise) that can compromise the utility of these datasets for more focused studies like complex detection, as seen from our evaluation results. In order to reduce the impact of such discrepancies, a number of data integration and reliability scoring schemes have been devised 15,16,17,18,19,20,21,22,23,24 . To overcome these challenges to some extent, in our evaluation, we combined multiple datasets (from Gavin et al. 9 and Krogan et al. 10 ) to account for the lack of interaction coverage, and also adopted scoring prior to predicting complexes. In spite of these precautionary steps, we notice that most methods are able to reconstruct only a fraction of the known complexes, and we still have a long way to go towards identification of meaningful novel complexes through computational means.

Challenges from existing complex detection methods
As noted earlier, even though there have been numerous methods developed for complex detection, most of them suffer from low recall (at most 65% recall even on the scored network; Table 4). Even a "union" of these methods achieves at most 70-75% recall on average across a variety of PPI datasets 66 . One of the crucial reasons for this limitation is that every method, in one way or another, relies on the key assumption that complexes are embedded among "dense" regions of the network. However, recent experiments have indicated that relying too much on this assumption in the wake of insufficient credible interaction data causes these methods to miss many complexes that are of low densities, that is, "sparse" in the network 66 . Therefore the need is to find alternative ways to model complexes than mere dense subnetworks, and also to compensate for the sparsity of topological information by augmenting other kinds of biological information.

Detection of sparse complexes
In the attempt to detect sparse complexes, the recent work by   66 is insightful and can guide futher directions towards tackling this challenge.  66 noticed that most existing computational methods based on PPI networks rely overly on the assumption that complexes are embedded among "dense" regions of the network, and therefore miss most of the "sparse" complexes that have very low interaction densities or lie disconnected in the network. These complexes are missed by current methods due to the lack of crucial topological information (missing interactions and/or proteins) -for example, even in the well-studied organism yeast, only ∼ 70% of the interactome has been validated and catalogued 13 . In order to overcome these "topological gaps", the authors proposed careful augmenting of functional interactions to PPI networks. Functional interactions represent logical or conceptual associations among proteins, and therefore "encode" a variety of biological similarities or affinities among proteins beyond just physical interactivity, thereby compensating for the lack of topological information in PPI networks. In order to do this augmentation systematically they proposed the SPARC algorithm.
SPARC selects low quality clusters predicted from the physical (PPI) network using existing methods, and then selectively enhances these clusters to reconstruct (sparse) complexes. The key idea is that many of these low quality clusters are in fact fractions (or "pieces") of sparse complexes embedded in the PPI network, but due to missing interactions they lie "scattered" in the network and do not represent whole complexes in their current forms. If these clusters can be carefully enhanced by augmenting functional interactions, then several of the sparse complexes can be reconstructed accurately. This enhancement involves increasing their interaction densities and "pulling-in" together their disconnected components. However, during the selection of the initial set of low quality clusters, many may just represent noisy predictions (false positives). In order to determine the clusters that are more likely to represent complexes, SPARC makes use of a novel Component-Edge (CE) score. The CE-score is a topological measure combining connectivity and relative density of the clusters, and is shown to more accurately correlate with the topological characteristics of real complexes compared to traditionally accepted measures like edge density. The CE-score is calculated for every low quality cluster predicted from the PPI network. SPARC then augments functional interactions to the clusters and checks if their CE-scores improve beyond a certain threshold. If a cluster shows the required improvement, it is output as a potential candidate representing a sparse complex. Srihari et al. showed through extensive experiments on clusters produced from methods like MCL 30,33 , MCL-CAw 48 , CMC 34 and HACO 40 that SPARC was capable of improving the overall recall of these methods by upto 47% on average across a variety of networks. Specifically, SPARC helped to reconstruct 25% more complexes among the ones that were sparse.

Detection of small and temporal complexes
Small complexes (complexes of two or three proteins) also pose severe challenges in identification, particularly if PPI network topology is the only available information.
In fact most complex detection methods based solely on the PPI network only attempt to identify complexes with at least 4 or more proteins in the network 34,46,48 . The attempt to predict small complexes (pairs or triplets) from the network based only on connectivity typically produces a significant fraction of false positives. Further, the smaller the size of a complex, the more prone it is to sparsity -missing even a few interactions can result in very low densities or render the complexes disconnected. Due to these challenges, additional information apart from PPI network topology is required for detection of such complexes.
In a recent work (2012), Srihari et al. 67 incorporated temporal information to identify small complexes. The authors focused on identifying small complexes that are assembled during the yeast cell cycle in a temporal manner. They noticed that several high-degree proteins such as kinases interacted with different subsets of proteins during different phases of the yeast cell cycle to assemble multiple phase-specific complexes. However, due to the lack of temporal information to disambiguate (segregate) the different phase-specific complexes, existing topologybased methods produced large clusters of complexes fused together. Srihari et al. decomposed such large clusters by incorporating temporal information on the yeast cell cycle in which each protein showed peak expression, and thereby segregated the individual constituent complexes. Many of the segregated complexes were small and represented complexes of kinases and their temporal substrates.
Srihari et al. also noticed that by incorporating such temporal information the "dynamics" of protein complexes could be better understood. They observed an interesting relationship between the "staticness" (constitutive expression) of a protein and its participation in multiple complexes 67 -cells tend to maintain generic proteins as 'static' to enable their "reusability" across multiple temporal complexes.

Challenges in detecting membrane complexes
Membrane protein complexes are formed by physical interactions among membrane proteins. Membrane proteins are attached to or associated with the membranes of the cell or its organelles. Membrane proteins constitute approximately 30% of the proteomes of organisms, yet they are one of the least studied subsets of proteins. The study of membrane proteins and their complexes is crucial in understanding diseases and aiding new drug discoveries 68 .
Membrane protein complexes are notoriously difficult to study using traditional high-throughput techniques like Y2H and TAP-MS 69 . This is due in part to the hydrophobic (insoluble) nature of membrane proteins, as well as the ready dissociation of subunit interactions, either between transmembrane subunits or between transmembrane and cytoplasmic subunits 69,70 . In order to counter the disadvantages of conventional techniques, new biochemical techniques have been developed recently to facilitate the characterization of interactions among membrane proteins. Among these is the split-ubiquitin membrane yeast two-hybrid (MYTH) system 71,72,73 . With the development of the highthroughput MYTH system, a fair number of interactions among membrane proteins have been recently catalogued in species such as Arabidopsis thaliana 69 and yeast Saccharomyces cerevisiae 71,72 .
The identification of membrane complexes requires understanding their assembly -how the individual proteins come together to form complexes, and how these complexes are eventually degraded. This is because membrane proteins are not stable entities as their soluble counterparts. Studies reveal that this assembly occurs in an orderly fashion, that is, membrane complexes are formed by an ordered assembly of intermediaries, and in order to prevent unwanted intermediaries, this assembly is highly aided by chaperones 74 . Many membrane complexes are formed by transient interactions involving exchange of proteins in and out of existing complexes via membranes -a phenomenon called 'dynamic exchange' 74 . The need therefore now is to develop sophisticated algorithms that take into account these aspects specific to membrane complexes to mine them effectively from membrane sub-interactomes.

Conclusions
Protein complexes are the fundamental functional units responsible for many biological mechanisms within the cell. Their identification is therefore necessary to understand the cellular organization and machinery. The advent of high-throughput techniques for inferring protein interactions in a large-scale fashion has fueled development of computational techniques to systematically mine for potential complexes from the network of interactions. In this work, we reviewed, classified and evaluated some of the key computational methods developed till date for the detection of protein complexes from PPI networks. We presented two insightful taxonomies of existing methods -'bin-and-stack' and 'tree'. From these taxonomies we note that scoring of raw interaction datasets (followed by filtering of false positives) and integrating key biological insights with topology can significantly improve complex prediction.
Even though more than 20 methods have been developed over the years, complex detection still requires careful attention in handling errors and noise in experimental datasets, and reconstructing complexes with high accuracies. On this front, we identified some of the crucial limitations and challenges facing current experimental and computational techniques. Interaction datasets coming from different experimental sources show surprising lack of correlation and also contain sizeable fraction of spurious (false positive) interactions. This severely impacts the accuracy and coverage of complex detection methods. Further, computational methods also overly rely on the assumption that complexes are embedded among densely connected groups of proteins, an assumption that is not fully valid in the wake of insufficient credible interactions. Finally, the interactions among membrane proteins have not been catalogued adequately making it difficult to identify an important group of complexes necessary for understanding diseases -membrane complexes.
We hope that our review and assessment of computational methods as well as the challenges highlighted here will provide valuable insights to drive future research for further advancing the 'state-of-the-art' in computational prediction, characterization and analysis of protein complexes from organisms.