Background {#Sec1}
==========

With the completion of the sequencing of the human genome, proteomic research becomes one of the most important areas in the life science \[[@CR1]\]. Proteomics is the systematic study of the diverse properties of proteins to provide detailed descriptions of the structure, function and control of biological systems in health and disease \[[@CR2]\], where the analysis of underlying relationships in protein data can potentially yield and considerably expand useful insights into roles of proteins in biological processes. That is, protein-protein interactions (PPI) can provide us with a good opportunity to systematically analyze the structure of a large living system and also allow us to use them to understand essential principles. Therefore, the analysis of PPI networks naturally serves as the basis to a better understanding of cellular organization, processes, and functions \[[@CR3]\]. Since biologists have found that cellular functions and biochemical events are coordinately carried out by groups of proteins interacting each other in functional modules (or complexes), and the modular structure of a complex network is critical to functions, identifying such functional modules (or complexes) in PPI networks is very important for understanding the structures and functions of these fundamental cellular networks^a^. In the last decade, some biological experimental methods, e.g., tandem affinity purification with mass spectrometry \[[@CR4], [@CR5]\] and protein-fragment complementation assay (PCA) \[[@CR6]\], have already been used to detect functional modules in PPI networks. However, there are several limitations to these experimental methods, such as too many processing steps and too time-consuming, especially when dealing with a large-scale and densely connected PPI network. Therefore, computational approaches based on machine learning and data mining have been designed and become useful complements to the experimental methods. Over the last decade, a variety of classic clustering approaches, such as density-based clustering \[[@CR7]--[@CR9]\], hierarchical clustering \[[@CR10]--[@CR12]\], partition-based clustering \[[@CR13]--[@CR15]\], and flow simulation-based clustering \[[@CR16]--[@CR18]\], have been used for identifying functional modules in PPI networks. In recent years, there has also been a number of new emerging approaches \[[@CR19]--[@CR21]\], which employs novel computational models to identify functional modules in a PPI network. Especially, some nature-inspired swarm intelligence algorithms have been recently applied to the detection of functional modules in PPI networks \[[@CR22]--[@CR25]\]. Though using computational approaches to detect protein functional modules in PPI networks has received considerable attention and researchers have proposed many detection ideas and schemes over the past few years \[[@CR1]\], how to efficiently identify functional modules by means of novel computational approaches is still a vital and challenging scientific problem in computational biology.

Agent-based methods have been previously applied to solving certain search and optimization problems \[[@CR26], [@CR27]\]. In such methods, an agent, *a*, is a computational entity that resides in and reacts to its local environment. During the process of interacting with its environment and companion agents, each agent increases its energy level as much as possible, so that the multi-agent evolution can achieve the ultimate goal of solving a global optimization problem. As another example of nature-inspired methods, multi-agent evolution has shown some promises in producing low-cost, fast, and reasonably accurate solutions to certain computational problems, such as classification \[[@CR28]\], clustering \[[@CR29], [@CR30]\], and social network community mining \[[@CR31]\]. These encouraging applications are significant motivation for our research, thus we propose a novel multi-agent evolutionary method to detect functional modules in PPI networks (called MAE-FMD) in this paper. Based on a probability model, MAE-FMD first employs a group of agents as a population to carry out random walks from a start protein to other proteins in a PPI network and finish their individual solution encodings. Then, it randomly places these agents into an evolutionary environment modeled as a lattice, and performs innovative agent-based operations, i.e., competition, cooperation, and mutation, in an attempt to increase the energy levels of agents at each iteration. Experimental results and related comparisons have shown that the MAE-FMD algorithm is effective in achieving better functional module mining results.

Method {#Sec2}
======

Basic ideas {#Sec3}
-----------

In this section, we describe a global search algorithm based on a multi-agent evolutionary method for functional module detection, which consists of two phases: (1) the solution construction phase, and (2) the solution evolution phase. In the first phase, each agent traverses all the nodes of a PPI network through a random-walk process and forms its own solution. In the second phase, the population of agents (i.e., all solutions) are randomly placed into an evolutionary environment for their iterative evolutions until a predefined termination criterion is satisfied. During the evolutions, an energy level is employed to evaluate the ability of an agent to solve a problem in the multi-agent system. The higher the energy level of an agent, the better the quality of the corresponding solution.

Agent representation and its construction {#Sec4}
-----------------------------------------

In the MAE-FMD algorithm, each agent corresponds to a candidate solution. An agent is encoded as a graph with *N* directed edges: *A*={(1→*a*~1~),(2→*a*~2~),⋯,(*i*→*a*~*i*~),⋯,(*N*→*a*~*N*~)}, where *i* is a node label, *a*~*i*~ denotes the connected node from *i*^*th*^ node in the represented solution, and *N* is the number of nodes in a PPI network. Take the PPI network shown in Figure [1](#Fig1){ref-type="fig"}(a) as an example. It consists of eight nodes numbered from 1 to 8. Figure [1](#Fig1){ref-type="fig"}(b) gives an encoding form of its corresponding agent, which can be translated into the graph structure as given in Figure [1](#Fig1){ref-type="fig"}(c), where each connected component provides a group of nodes, corresponding to the same partition of the network as shown in Figure [1](#Fig1){ref-type="fig"}(a).Figure 1**The connection-based encoding of an agent.** **(a)** PPI network; **(b)** Encoding of an agent; **(c)** Represented solution.

To obtain a feasible solution, an agent proceeds from a start node and continuously employs a random-walk behavior to traverse other nodes in a PPI network. At each time step, the agent is on a node, tries to move to a functionally related or similar node that is chosen probabilistically from its topologically adjacent nodes, and builds a corresponding connection. When there is no any satisfied node, the agent will end its current traversal by pointing to itself and then randomly select an untraversed node in a PPI network and begin to a new traversal. This random-walk behavior will be performed until all nodes have been processed. Thereafter, the agent forms its solution. A main advantage of this solution is that the number *K* of clusters is automatically determined by the number of components obtained by an agent, namely, those nodes with a connected relationships are automatically classified into the same community during a later decoding process. Obviously, such an encoding method does not rely on knowing number of clusters beforehand.

During the random-walk process, an agent constructs a solution by proceeding from a start node and moving to feasible neighborhood nodes in a step-by-step fashion. In each step, an agent *k* moves from node *i* to node *j* based on the following probability:

where *s*~*i*,*j*~ denotes a measure of connection strength between two nodes *i* and *j* from the view of topology structures, *f*~*i*,*j*~ is a functional similarity score of the two nodes *i* and *j*, and is a set of available nodes in which each one *l* (or *j*) is a neighborhood node of node *i* not yet visited by the *k*^*th*^ agent in the current traversal and (*s*~*i*,*j*~+*f*~*i*,*j*~)≥*ε* (*ε* represents a specified strength threshold for the combination of topology and function similarities).

Given two nodes *i*,*j*∈*V*, we compute their connection strength by using the structural similarity formula as follows \[[@CR32]\]:

where *Γ*(*i*) is a set of the neighborhood nodes of node *i*, and \|*Γ*(*i*)\| is the size of the set.

Based on the annotation information of Gene Ontology (GO), the functional similarity measure for proteins can be implemented. For two proteins *i* and *j* that are annotated with two GO term sets *g*^*i*^ and *g*^*j*^, respectively, the functional similarity score can be calculated by \[[@CR33]\]:

Agent energy level and evolutionary environment {#Sec5}
-----------------------------------------------

According to the meaning of energy level mentioned above, we are interested in searching a graph partition with the largest energy level. To guarantee highly intra-connected and sparsely inter-connected modules, we adopt the modularity density function \[[@CR34]\] to compute the energy level of an agent:

where *K* is the number of detected modules for an agent *A*, *e*~*c*~ is the number of links between nodes in *c*~*th*~ module, \|*E*\| is the number of all links in the PPI network, and *d*~*c*~ is the sum of the degrees of nodes in *c*~*th*~ module. During each evolutionary process, an agent will try to increase its energy level as much as possible by sensing and performing some reactive behaviors to survive.

To realize the local perceptivity of agents, we select the common lattice structure used in \[[@CR27], [@CR29], [@CR30]\] as the evolutionary environment, which is more close to the real evolutionary mechanism in nature than the model of the population in traditional Genetic Algorithms (GAs). All *M* agents in a population live in such a lattice environment. The size of lattices is *m*×*m*, where *m* is an integer and . Each agent is randomly placed on a lattice-point and it can only interact with its neighbors. The agent lattice can be shown as the one in Figure [2](#Fig2){ref-type="fig"}. Each agent, who corresponds to a partition solution, can occupy a circle in the evolutionary environment, where the data in a circle represents its position in the lattice structure, and two agents can interact with each other if and only if there is a line connecting them.Figure 2**The lattice environment for the agent evolutionary.**

Suppose that the agent located at (*u*,*v*) is *A*~*u*,*v*~, *u*,*v*=1,2,...,*m*, then the neighborhood agents of *A*~*u*,*v*~, *Neighbor*(*A*~*u*,*v*~), are defined as follows:

where *u*^′^=*mod*(*u*−1+*m*−1,*m*)+1, *v*^′^=*mod*(*v*−1+*m*−1,*m*)+1, *u*^″^=*mod*(*u*,*m*)+1, *v*^″^=*mod*(*v*,*m*)+1.

Evolutionary operators {#Sec6}
----------------------

In the above evolutionary environment, computational agents will compete or cooperate with others so that they can gain higher energy level. To simulate the evolution phenomenon in a more natural way, each agent can only sense its local environment, and its behaviors of competition and cooperation can only take place between the agent and its neighborhood agents. That is, an agent interacts with its neighborhood agents, and useful information is transferred among them. In such a way, the information can be gradually diffused to the whole lattice environment so that the global evolution of the agent population is realized. To achieve this purpose, three basic operators are designed for detecting communities in a PPI network.

**1) Competition operator.** Suppose that the operator is performed on the agent located at (*u*,*v*), *A*~*u*,*v*~=((1→*a*~1~),(2→*a*~2~),...,(N→*a*~*N*~)), and *H*~*u*,*v*~=((1→*h*~1~),(2→*h*~2~),...,(N→*h*~*N*~)) is another agent with the highest energy level among the neighborhood agents of *A*~*u*,*v*~, namely, *H*~*u*,*v*~∈*Neighbor*(*A*~*u*,*v*~) and ∀*A*^′^∈*Neighbor*(*A*~*u*,*v*~), then *Energy*(*A*^′^)≤*Energy*(*H*~*u*,*v*~). If *Energy*(*A*~*u*,*v*~)≥*Energy*(*H*~*u*,*v*~), *A*~*u*,*v*~ is a winner, so it can still live in the original lattice; otherwise it will die as a loser, and its lattice-point will be occupied by *H*~*u*,*v*~. *H*~*u*,*v*~ has two candidate strategies to occupy a lattice-point, and it randomly selects one of them with a probability *p*~*o*~. Let *r*(0,1) be a uniform random number generator, the value range of which belongs to (0,1). If *r*(0,1)\<*p*~*o*~, occupying strategy 1 is selected; otherwise occupying strategy 2 is carried out. In the two occupying strategies, *H*~*u*,*v*~ first generates its clone agent *C*~*u*,*v*~ = ((1 →*c*~1~), (2 →*c*~2~), ..., (N →*c*~*N*~)), and then *C*~*u*,*v*~ is placed on the lattice-point to be occupied.

Let and , namely, the connection strengths of *A*~*u*,*v*~ are *Al*~1~,*Al*~2~,...,*Al*~*N*~, and the connection strengths of *H*~*u*,*v*~ are *Hl*~1~,*Hl*~2~,...,*Hl*~*N*~, respectively. If a node has no other nodes to be pointed in addition to point to its own, then we call it a breakpoint. In fact, a breakpoint represents the segmentation of two different modules in a PPI network with N directed edges. To distinguish breakpoints, we set only when *i*=*a*~*i*~ in an agent encoding.

**Strategy 1.** For the connection with the lowest strength in *H*~*u*,*v*~, *Hl*~*j*~=*Min*(*Hl*~1~,*Hl*~2~,...,*Hl*~*N*~), if *Al*~*j*~\>*Hl*~*j*~ then *c*~*j*~ is replaced with *a*~*j*~ (*j*=1,2,...,*N*) in the new agent.

**Strategy 2.** Each *Al*~*i*~ of *A*~*u*,*v*~ is respectively compared with the corresponding *Hl*~*i*~ of *H*~*u*,*v*~. If *Al*~*i*~\>*Hl*~*i*~, then *c*~*i*~=*a*~*i*~ in the new agent.

In the following, we take a PPI network with 8 nodes as an example to illustrate these operators. A schematic diagram of a competition operator is given in Figure [3](#Fig3){ref-type="fig"}, where *A* = ((1→ 6),(2→ 2),(3→ 7),(4→ 8),(5→ 5),(6→ 5),(7→2),(8→8)) is an agent to participate in a competition, *H*=((1→1),(2→4),(3→7),(4→8),(5→5),(6→5),(7→1),(8→8)) is its neighborhood agent with the highest energy level and *Energy*(*H*)≥*Energy*(*A*), and *A*~1~ and *A*~2~ are two new agents produced by the competition operator where a shape represents a change in the encoding of the clone agent of *H*. Assumpting that *Al*~1~\>*Hl*~1~,*Al*~7~\>*Hl*~7~ and *Hl*~1~=*Min*(*Hl*~1~,*Hl*~2~,···,*Hl*~8~), *A*~1~ is the result of Strategy 1 where the link (1→1) is replaced with (1→6) while *A*~2~ is that of Strategy 2 where the two links (1→1) and (7→1) are respectively replaced with (1→6) and (7→2).Figure 3**Competition operator.**

In fact, the two strategies in this operator are designed to play similar roles. More specifically, Strategy 1 only replaces the worst connection of a winner with the better information of a loser while Strategy 2 is in favor of reserving all advantaged information of a loser.

**2) Crossover operator.** Suppose that two parent agents are *F*~1~=((1→*f*~1~),(2→*f*~2~),...,(N→*f*~*N*~)) and *F*~2~=((1→*f*1′),(2→*f*2′),...,(N→*fN*′)) which will randomly produce a child agent *C*~1~=((1→*c*~1~),(2→*c*~2~),...,(N→*c*~*N*~)) by making use of their connection information and the corresponding crossover strategies. To obtain offsprings of the two parent agents, the rules of crossover operator are as follows.

**Alternating link crossover rule.** The rule works as follows: first it chooses a link from the first parent at random; secondly, the link is extended with the appropriate link of the second parent; thirdly, the partial tour created in this way is extended with the appropriate link of the first parent, etc. This process is repeated until traversing all the nodes in a PPI network. During the generation of a candidate agent, once a link is chosen which would produce a cycle into the partial tour, the next link will be selected randomly from the links of those untraversed nodes in the corresponding parent.

The schematic diagram of the alternating link crossover rule is shown in Figure [4](#Fig4){ref-type="fig"}, where *F*~1~=((1→6),(2→8),(3→7),(4→4),(5→5),(6→5),(7→4),(8→8)) and *F*~2~=((1→6),(2→2),(3→7),(4→8),(5→5),(6→5),(7→7),(8→8)) are two parent agents, and *C*~1~=((1→6),(2→2),(3→7),(4→8),(5→5),(6→5),(7→4),(8→8)) is an offspring agent. In generating a candidate agent, the links (1→6),(5→5),(7→4) and (8→8) are selected from the first parent while the other links from the second parent, and each shape represents a starting point of a new subtour in the candidate agent.Figure 4**Alternating link crossover operator.**

**Alternating chunk crossover rule.** Based on this rule, an offspring is constructed from two parent agents as follows: first it takes a random length subtour of the first parent; then this partial tour is extended by choosing a subtour of random length from the second parent; next the partial tour is constantly extended by taking subtours from alternating parents till up to the length of the solution. For each subtour, the random length range is 1 to the remaining digits of the constructing solution. In generating a candidate agent, if a link is chosen which would produce a cycle into the partial tour, the next link will be selected randomly from the links of those untraversed nodes in the corresponding parent. Different length subtours from two parent agents are alternatingly chosen to construct a child agent.

Figure [5](#Fig5){ref-type="fig"} gives an illustrative diagram of an alternating chunk crossover rule, where *F*~1~=((1→5),(2→5),(3→8),(4→4),(5→5),(6→6),(7→4),(8→6)) and *F*~2~=((1→2),(2→3),(3→3),(4→7),(5→5),(6→6),(7→5),(8→6)) are two parent agents, and *C*~1~=((1→5),(2→5),(3→8),(4→4),(5→5),(6→6),(7→5),(8→6)) is an offspring agent. In generating a candidate agent, we assume that the sizes of four chunks are respectively determined as 3, 2, 2 and 1 by four random functions, and chunk 1 and chunk 3 are selected from the first parent while the other two chunks from the second parent. The new agent is alternatively constructed by means of the subtours of different parents, where shapes represent the same meaning as in Figure [4](#Fig4){ref-type="fig"}.Figure 5**Alternating chunk crossover operator.**

Obviously, the crossover operator has the function of a random search, which is performed on an agent and its neighborhood agents to achieve the purpose of cooperation with a crossover probability *p*~*c*~. More specifically, if *r*(0,1)\<*p*~*c*~, then the algorithm performs the two crossover operators. Otherwise, it skips these operators. Once a child agent has higher energy level than its parent agent after performing crossover operators, the initial agent with lower energy level will be replaced with the child agent.

**3) Self-adaptive mutation operator.** In addition to the behaviors of competition and cooperation, an agent can also increase its energy level by using a self-adaptive mutation operator, which depends on the degree of its evolution and controls the number of digits to be mutated. The mechanism of the self-adaptive mutation operator is denoted as:

where *n* is the number of mutation digits, *l*~*i*~ is the number of continued stagnation steps for *i*~*th*~ agent, and *r* is the maximum step length at which an agent might have the same energy level. It is not difficult to find that *n* is not only associated with the encoding length of an agent (network size), but also related to the evolutionary process of the agent. More specifically, the larger the network scale, the more the number of potential mutations. On the other hand, the longer the stagnating time of an agent evolution, the more the number of potential mutations.

Based on a mutation probability *p*~*m*~, *n* connection elements of an agent *A* = ((1 → *a*~1~),(2 → *a*~2~),...,(N → *a*~*N*~)) are randomly selected when *r*(0,1)\<*p*~*m*~, and then they are mutated by replacing with other nodes possibly connected in the corresponding module.

Figure [6](#Fig6){ref-type="fig"} gives an illustration diagram of a mutation operator, where *D* = ((1→6),(2→2),(3→7),(4→8),(5→5),(6→5),(7→2),(8→8)) is an original agent, its mutation number *n*= 2, *M*= ((1→6),(2→2),(3→7),(4→2),(5→5),(6→5),(7→4),(8→8)) is the mutated agent in which two elements are replaced randomly, and shapes represent the changes in the encoding of the new agent. Essentially, the mutation operator realizes a local search, which only performs a small perturbation on some elements (node connections) of an agent encoding. If a mutation operator can increase the energy level of the current agent, the initial agent with lower energy level will be replaced with the new agent.Figure 6**Self-adaptive mutation operator.**

In the light of an energy level function, MAE-FMD algorithm employs competition, crossover and mutation operators to continually realize good information exchange among agents and improve the energy levels of a group of initial agents. During the competition process, if the current agent is winner, then it will be kept alive. Otherwise, the neighborhood agent with the highest energy level will be selected, and improved by combination with advantaged information of the current agent, then it replaces the current agent. Meantime, whether crossover operators or mutation operators, once they can produce new agents with higher energy level, the initial agents with lower energy level will be replaced with the new agents. By means of the three operators, the evolutionary process will gradually converge to a solution with the largest energy level which corresponds to the initial module structure of the PPI network.

Post-processing {#Sec7}
---------------

After a number of iterations, we can obtain a solution with the largest energy level. That is, the preliminary modules are generated by the multi-agent evolutionary method. To improve the detection quality, we adopt two post-processing strategies based on topological and functional information to produce final modules. The first step is merging the similar preliminary modules in light of functional annotation information. A merging module results from two or more preliminary modules which are close in view of function. The similarity *S*(*M*~*S*~,*M*~*T*~) between two modules *M*~*S*~ and *M*~*T*~ is measured by the functional similarity score defined as:

where

Two modules with the highest similarity are iteratively merged until there are no such two modules whose similarity is larger than the merging threshold *λ*.

To exclude some too sparsely connected nodes and very small clusters generated above, we perform the filtering step based on the topological density of PPI network subgraphs. The density of subgraphs of functional modules is measured by:

where *n*~*s*~ is the number of nodes and *e*~*s*~ is the number of interactions in a subgraph *s* of a PPI network. Let *δ* be a threshold value, those clusters with *D*~*s*~\<*δ* and \|*s*\|\<2 will be filtered from clusters generated above. By such two post-processing strategies, the preliminary modules are refined from the topological property and functional similarity, and the potential functional modules hidden in the PPI networks are generated.

Algorithm description and complexity analysis {#Sec8}
---------------------------------------------

The procedure of the proposed MAE-FMD algorithm is to carry out initialization, agent random-walk and solution construction, multi-agent evolution, post-processing, and output of detected modules. The detailed pseudocode is shown in Algorithm 1.

Based on the description of Algorithm 1, the complexity of MAE-FMD can be simply analyzed as follows: Let the maximum number of a node degree be *n*~1~ in a PPI network, and the maximum number of nodes be *n*~2~ in a module. In the initialization process, computing connection strengths (similarities) and the number of common neighbors for all pairs of nodes is time-consuming. For each node, since the number of its maximum neighborhood nodes is *n*~1~, the computing complexity of its all available connection strengths is *n*~1~, thus the time complexity is *O*(*n*~1~·*N*). In the agent random-walk and solution construction process, the time complexity is *O*(*M*·*N*·*n*~1~). In the multi-agent evolution process, the time complexity is . Generally speaking, *K*·*n*~2~≥*N*,*however*,*O*(*K*·*n*~2~)≈*O*(*N*). Thus, the time complexity of the multi-agent evolution process can be simplified as *O*(*T*·(*n*~2~+*M*)·*N*). In the post-processing and output process, the time complexity is *O*(*K*^2^+*K*))≈*O*(*K*^2^). Thus, the overall complexity of MAE-FMD is about *O*(*n*~1~·*N*)+*O*(*M*·*N*·*n*~1~)+*O*(*T*·(*n*~2~+*M*)·*N*)+*O*(*K*^2^). Because most PPI networks are small-world and scale-free networks, *n*~1~≪*N*,*n*~2~\<*N*,*K*≪*N*. Moreover, we usually select a constant (e.g, 100) as the population size of agents, which is far less than the number of nodes in a large-scale PPI network. Therefore, the time complexity of MAE-FMD can be decreased to *O*(*T*·(*n*~2~+*M*)·*N*) (*n*~2~\<*N* for all PPI networks, *M*≪*N* for a large-scale PPI network), which is better than that of most existing typical algorithms with *O*(*N*^2^). Especially for a large-scale complex network with near uniform community size, the efficiency of MAE-FMD is very promising for detecting modules in PPI networks.

Results and discussion {#Sec9}
======================

In this section, we use three different protein-protein interaction datasets to perform our empirical study. In light of many evaluation metrics, we assess the performance of our algorithm, and compare our test results to other existing algorithms on these PPI datasets. The experimental platform is a PC with Core 2, 2.13 GHz CPU, 2.99 GB RAM, and Windows XP, and all algorithms are implemented by Java language.

PPI datasets {#Sec10}
------------

We have performed our experiments over five publicly available benchmark PPI datasets including four yeast data and one human data, namely DIP data \[[@CR35]\], Gavin data \[[@CR36]\], MIPS data \[[@CR37]\], DIP Scere20140703 and DIP Hsapi20140703. Table [1](#Tab1){ref-type="table"} shows a summary of the data sets used in our experiments, where the 2th column gives the web links, the 3th and 4th columns respectively present the size of proteins and interactions in source data while the 5th and 6th columns respectively present the size of proteins and interactions in the preprocessed data. A cleaning step, which deletes all self-connected and repeated interactions, is performed in data preprocessing. To evaluate the protein modules mined by our algorithm, the set of real functional modules from \[[@CR38]\] is selected as the benchmark. This benchmark set, which consists of 428 protein functional modules, is constructed from three main sources: the MIPS \[[@CR27]\], Aloy et al. \[[@CR39]\] and the SGD database \[[@CR40]\] based on the Gene Ontology (GO) notations.Table 1**Data sets used in our experiments**Date setsHttp addressSource dataPreprocessed dataSize of P.Size of I.Size of P.Size of I.Gavin<http://www.thebiogrid.org/>\[BioGRID version 2.0.33\]1430653114306531DIP<http://dip.doe-mbi.ucla.edu/>\[version ScereCR20060402\]2554595225285728MIPS<ftp://ftpmips.gsf.de/yeast/PPI/>\[version PPI18052006\]455415456454512318DIPScere20140703<http://dip.doe-mbi.ucla.edu/dip/Download.cgi?SM=7&TX=4932>513722775512622402DIPHsapi20140703<http://dip.doe-mbi.ucla.edu/dip/Download.cgi?SM=7&TX=9606>4187624540865823

Evaluation metrics {#Sec11}
------------------

At present, there exist three popular measurements for the evaluation of the detection modules' quality and the calculation of the detection methods' general performance \[[@CR41]\].

### Precision, Recall, F-measure, and Coverage {#Sec12}

Many research works use a neighborhood affinity score to assess the degree of matching between the identified functional modules and real ones. The score *NA*(*p*,*b*) between an identified module *p*=(*V*~*p*~,*E*~*p*~) and a real module *b*=(*V*~*b*~,*E*~*b*~) in the benchmark module set is defined as:

If *NA*(*p*,*b*)≥*ω*, then *p* and *b* are considered to be matched (generally, *ω*=0.2). Let *P* be the set of functional modules identified by some computational methods and *B* be the real functional module set in benchmark networks. And then the number of the modules in *P* which at least matches one real module is denoted by *N*~*cp*~=\|{*p*\|*p*∈*P*,∃*b*∈*B*,*NA*(*p*,*b*)≥*ω*}\|, while the counterpart number in *B* can be denoted by *N*~*cb*~=\|{*b*\|*b*∈*B*,∃*p*∈*P*,*NA*(*p*,*b*)≥*ω*}\|. Thus, Precision and Recall can be defined as follows \[[@CR42]\]:

and

F-measure is a harmonic mean of Precision and Recall, so can be used to evaluate the overall performance. It is defined as:

Moreover, Coverage assesses how many proteins in a PPI network can be clustered into the detected modules by a computational method. That is, it indicates the percentage of proteins assigned to any functional module, i.e., 1-Discard-rate, which can be defined as follows \[[@CR43]\]:

where \|*V*\|=*N* denotes the size of the PPI network and *V*~*pi*~ is the set of the proteins in the *i*^*th*^ detected module.

### Sensitivity, positive predictive value, and accuracy {#Sec13}

Sensitivity (*S*~*n*~), Positive predictive value (*PPV*) and Accuracy (*Acc*) are also common measures to assess the performance of module detection methods. Let *T*~*ij*~ be the number of the common proteins in both of the *i*^*th*^ benchmark and the *j*^*th*^ identified module. Then *S*~*n*~ and *PPV* can be defined as \[[@CR38]\]:

and

where *N*~*i*~ is the number of the proteins in the *i*^*th*^ benchmark module, and . Generally speaking, *S*~*n*~ assesses how many proteins in the real functional modules can be covered by the predicted modules, while *PPV* indicates that identified modules are more likely to be true positives.

As a general metric, the accuracy of an identification (*Acc*) can be calculated as the geometric mean of *S*~*n*~ and *PPV*:

### p-value measure {#Sec14}

Modules can be statistically evaluated using the *p*-value from the hypergeometric distribution, which is defined as \[[@CR44]\]:

where \|*V*\| denotes the same means as mentioned in Equation [16](#Equ16){ref-type=""}, *C* is an identified module, \|*F*\| is the number of proteins in a reference function, and k is the number of proteins in common between the function and the module. *P*-value is also known as a metric of functional homogeneity. It is understood as the probability that at least k proteins in a module of size \|*C*\| are included in a reference function of size \|*F*\|. A low value of p indicates that the module closely corresponds to the function, because it is less probable that the network will produce the module by chance. Consequently, the minimum *p*-value in all modules will show the general performance of each detection method.

Effects of parameters {#Sec15}
---------------------

In this subsection, we take the Gavin data as an example to study respectively the effects of the algorithm parameters involved in the multi-agent evolution and post-processing. These parameters include the number of agent population (M), the strength threshold of connections (*ε*), the maximum step length with same energy level (*R*), the selection probability (*p*~*o*~), the crossover probability (*p*~*c*~), the mutation probability (*p*~*m*~), merging threshold (*λ*), and filtering threshold value (*δ*). During all experimentations, the value of a single parameter is changed, while keeping the values of other parameters fixed.

For the multi-agent random-walk and evolutionary processes, we take maximum energy of an agent and the number of iterations as two evaluation metrics to test the performance of the algorithm. Ten executions are independently carried out in each parametric combination. Figure [7](#Fig7){ref-type="fig"} reveals that the effects of three main parameters (*M*, *ε*, *R*) on the multi-agent method performance by mean value curve with error bars. Figure [7](#Fig7){ref-type="fig"}(a) shows the evolutionary performance with 7 different agent sizes (*M*). Multi-agent evolutionary method is a population-based optimization algorithm, where the number of agent population determines the number of solutions at each iteration. The left graph in Figure [7](#Fig7){ref-type="fig"}(a) shows the results about the maximum energy value, and the right graph in Figure [7](#Fig7){ref-type="fig"}(a) illustrates the results about the number of iterations. As reflected in Figure [7](#Fig7){ref-type="fig"}(a), smaller maximum energy values and larger number of iterationss are obtained when using a small number of agents. Along with the number of agents increasing, the maximum energy slowly increases and the number of iterations decreases on the whole. The reason is that more agents means more initial search points in the search space to be employed so that the search range is larger at each iteration, which induces the algorithm to rapid converge. However, after a sufficient value for the number of agents, any increment does not obviously improve the maximum energy, and also does not dramatically reduce the number of iterations. On the contrary, the search time in each iteration will increase as the size of the number of agents increases. Therefore, to acquire a balance between getting a better solution and using less time, we recommend an agent size of 225 (*M*=225).Figure 7**The effects of three parameters (** ***M*** **,** ***ε*** **,** ***R*** **) on the multi-agent method performance.** **(a)** the plots of the maximum energy value and the number of iterations for different values *M*; **(b)** the plots of the maximum energy value and the number of iterations for different values *ε*; and **(c)** the plots of the maximum energy value and the number of iterations for different values *R*.

The strength threshold of connections *ε* is an important parameter in the constructing solution process of an agent, which controls the feasible neighborhood for each node in an agent random-walk process. To investigate the effect of *ε* on our algorithm, we perform experiments using different values of *ε*. The results are presented in Figure [7](#Fig7){ref-type="fig"}(b) where the curve of maximum energy has 2 distinct ranges for various values of *ε*, i.e. \[0.05, 0.10\] and \[0.15, 0.60\], while the curve of the number of iterations also has 2 rough ranges for various values of *ε*, i.e. \[0.05, 0.20\] and \[0.25, 0.6\]. As *ε* increases, the maximum energy increases in the first range, and then decreases dramatically in the second range. However, our algorithm can keep the maximum energy value being larger than 0.5 when *ε* locates in \[0.05, 0.35\]. For the curve of the number of iterations, the first range has far larger values than the second range though there are some small fluctuations in both ranges. The reason is as follows: Smaller *ε* is, larger the feasible neighborhood of each node and the search space of a solution are, thus the algorithm will cost more iterations to search a better solution, and vice versa. It is worth noting that the algorithm is easy to fall into local optimal if *ε* is too large though it has s fast convergence performance. Combining above experimental results and such analysis, we select *ε*=0.25 in our algorithm.

The maximum step length with same energy level *R* is also a key parameter which plays an important role in determining the end of evolution. Figure [7](#Fig7){ref-type="fig"}(c) shows two plots of the maximum energy value and number of iterations for different *R*. From the left graph in Figure [7](#Fig7){ref-type="fig"}(c), the maximum energy value is insensitive to the parameter *R* and increases slightly along with increasing of *R*. From the right graph in Figure [7](#Fig7){ref-type="fig"}(c), the number of iterations will have a more significant increase as the parameter *R* increases. These results illustrate that if the algorithm uses a large value of *R*, which is bound to increase the number of iterations and not necessarily able to get a better result. Considering the two factors together, we set *R*=60.

Figure [8](#Fig8){ref-type="fig"} reveals that the effects of three operator parameters (*p*~*o*~, *p*~*c*~, *p*~*m*~) on the performance of the multi-agent method by mean value curve with error bars. As shown in the left graph of Figure [8](#Fig8){ref-type="fig"}(a), the maximum energy is insensitive to the occupying probability *p*~*o*~, and its value maintains around at 0.56 within all values of *p*~*o*~. From the right graph in Figure [8](#Fig8){ref-type="fig"}(a), we can see that the number of iterations decreases as *p*~*o*~ increases on the whole. This is because no matter what value *p*~*o*~ is, the competition operator (Strategy 1 or Strategy 2) is performed, thus the difference on the maximum energy is very small (e.g. the maximum gap of the average value is 0.006). However, since Strategy 2 reserves more advantaged information of a loser than Strategy 1, excessively using Strategy 2 will slow the convergence of the algorithm. Hence, we set *p*~*o*~=0.5 in our algorithm to obtain a balance between two strategies. The relationship curve between the method performance and *p*~*c*~ is shown in the Figure [8](#Fig8){ref-type="fig"}(b). Similar to the curve of *p*~*o*~, the maximum energy values vary from the different values of *p*~*c*~, but the difference is very small (e.g. the maximum gap of the average value is 0.009), which suggests that the multi-agent evolutionary process is also not sensitive to the crossover probability. There are three varying ranges for the number of iterations along with *p*~*c*~ increasing, i.e., \[0.1, 0.4), \[0.4, 0.6\] and (0.6, 0.9\]. The number of iterations curve decreases gradually in \[0.1, 0.4), then maintains the smaller value of almost equal in \[0.4, 0.6\], and finally increases gradually in (0.6, 0.9\], which means that moderate crossover operations can contribute to the convergence of the algorithm, however, too few or too many crossover operations will reduce the convergence of the algorithm. To shorten the evolutionary process, we set *p*~*c*~=0.5 in our algorithm. Figure [8](#Fig8){ref-type="fig"}(c) gives the curve of the evolutionary performance on mutation probability *p*~*m*~. As *p*~*m*~ increases, the maximum energy values slowly increase, and the number of iterations decreases with a small amount of fluctuation. That is, the rich mutation operators will not only benefit the convergence of the multi-agent evolutionary process, but also get a better maximum energy value. To obtain a good result and save evolution time, we select *p*~*m*~=0.8 in our algorithm.Figure 8**The effects of three operation parameters** ***(p*** ~***c***~ ***,p*** ~***o***~ ***,p*** ~***m***~ ***)*** **on the multi-agent method performance.** **(a)** indicates how the maximum energy and the iteration number changes when the *p* ~*c*~ increases; **(b)** indicates how the maximum energy and the number of iterations changes when the *p* ~*o*~ increases; **(c)** indicates how the maximum energy and the iteration number changes when the *p* ~*m*~ increases.

For the postprocessing process, we employ recall, F-measure, precision, sensitivity, accuracy and PPV metrics to evaluate algorithm performance. Figure [9](#Fig9){ref-type="fig"} gives the effects of merging threshold *λ* on 6 performance metrics. Figure [9](#Fig9){ref-type="fig"}(a) demonstrates that the F-measure and recall increase as *λ* increases on the whole range while the precision also increases as *λ* increases at the beginning and decreases after *λ* passes over 1.0. Figure [9](#Fig9){ref-type="fig"}(b) shows that the relationship between *λ* and the sensitivity, the accuracy and the PPV. The accuracy and the PPV have the same trend: both values subtly increase as *λ* increases. Conversely, the sensitivity decreases at the beginning, then keep the value low (0.74) after *λ* gets to 1.4. As shown in Figure [9](#Fig9){ref-type="fig"}(a) and Figure [9](#Fig9){ref-type="fig"}(b), the larger *λ* is, the better F-measure and accuracy seems to be. However, once *λ* is set a larger value, the number of clusters will become too large due to many small clusters. To balance between the scale and size of clusters, the value of *λ* is set to 1.8 in our following experiments.Figure 9**The effects of merging threshold** ***λ*** **on 6 performance metrics.** **(a)** reveals the relation between the *λ* value and recall, F-measure and precision; and **(b)** displays the relation between the *λ* value and sensitivity, accuracy and PPV.

Figure [10](#Fig10){ref-type="fig"} gives the effects of filter threshold *δ* on 6 performance metrics. As shown in Figure [10](#Fig10){ref-type="fig"}(a), the recall and F-measure have a similar trend, namely, their values slowly increase as *δ* increases at the beginning, then gently decrease after *δ* gets to 0.12. However, the rate of change is slightly different for the two metrics where the values of recall have larger changes than those of F-measure. Meanwhile, the precision maintains a relatively stable value around 0.45 though there are two small peaks at *δ*=0.04 and 0.12. Figure [10](#Fig10){ref-type="fig"}(b) investigates the relationship between *δ* and PPV, the accuracy and the sensitivity. As *δ* increases, three metrics have different tendencies. In detail, the sensitivity obviously decreases from 0.75 to 0.52, the PPV increases from 0.30 to 0.32 when *δ* locates in \[0.02, 0.16\], then keeps a larger value (0.32) when *δ*\>0.16 while the accuracy holds steady at 0.46 when *δ* varies from 0.02 to 0.14, then slightly decreases from 0.46 to 0.41 when *δ* locates in \[0.14, 0.2\]. The main reason for these different trends is that only those modules whose similarity is strong enough are merged along with the value of *δ* increasing, thus making the number of clusters to increase and the average size of a cluster to be small. To make a balance, we employ *δ*=0.12 in our algorithm.Figure 10**The effects of filter threshold** ***δ*** **on 6 performance metrics.** **(a)** reveals the relation between the *δ* value and recall, F-measure and precision; and **(b)** displays the relation between the *δ* value and sensitivity, accuracy and PPV.

Based on similar tests, we have determined the parameter sets for other different data sets, and Table [2](#Tab2){ref-type="table"} summaries these parameters used in the following experiments.Table 2**Summary of parameters used in our experiments**Data setsAgent random-walkMulti-agent evolutionPost-processingM***ε***R***p*** ~***o***~***p*** ~***c***~***p*** ~***m***~***λ**δ***Gavin2250.25600.50.50.81.80.12Dip1000.27600.50.50.80.210.04MIPS1000.27600.50.50.80.190.05DIPScere201407031000.29600.50.50.80.60.05DIPHsapi201407031000.28600.50.50.80.60.05

From these results, we can give some simple suggestions to preset these parameters. For *M*, a certain size population is necessary for MAE-FMD to obtain good quality solution while keeping a smaller value not to increase the running time. For *ε*, a medium value between \[0, 0.6\] is recommended. For *R*, a smaller value is favorable to rapidly converge. For *p*~*o*~, *p*~*c*~ and *p*~*m*~, we can set a medium value between \[0, 1\] to *p*~*o*~ and *p*~*c*~ and a higher value to *p*~*m*~ to save the running time. The two parameters in post-processing depend on different datasets. For the curated databases, such as DIP and MIPS, *λ* and *δ* can be set two smaller values in respective domains, however, two larger values in respective domains have to be employed for the database with more noise (such as Gavin).

Comparative evaluations {#Sec16}
-----------------------

To demonstrate the strengths of the MAE-FMD method, we compared it to the six competing methods: HAMFMD, NACO-FMD, Coach, CFinder, MCL and MCODE in our experiments, where CFinder and MCL run without parameter settings, the only parameter of Coach is the filter threshold *ω* which was set to 0.225, NACO-FMD runs with *α*=1.5, *β*=4 and *δ*=0.3, MCODE adopts the default values for their parameters as provided by its binary executable system, and HAM-FMD uses five different combinations of parameter values (100, 0.5, 2, 4, 286, 0.2, 0.8, 0.1, 0.6), (300, 0.4, 2, 4, 510.8, 0.2, 0.8, 0.3, 0.4), (400, 0.5, 2, 4, 910.8, 0.2, 0.8, 0.1, 0.7), (500, 0.5, 1.5, 5, 1025.2, 0.2, 0.5, 0.1, 0.3) and (400, 0.5, 1.5, 5, 817.2, 0.2, 0.5, 0.1, 0.3) for the parameter set of (m, *ρ*, *α*, *β*, Q, *P*~*o*~, *P*~*c*~, *P*~*m*~, *δ*) on Gavin, DIP and MIPS, respectively.

The detailed comparative results of the various algorithms on the five different data sets are shown respectively in Table [3](#Tab3){ref-type="table"}, where *\"*−*\"* denotes an invalid result. For each detection method, we have listed the number of clusters detected (Number of clusters), the average number of proteins in each cluster (size of average module), the number of detected modules which match at least one real module (*N*~*cp*~) and the number of real modules that match at least one detected module (*N*~*cb*~). Taking MAE-FMD on Gavin data as an example, it has detected 193 modules, of which 110 match 224 real modules. Each of 193 detected modules has about 6 proteins in Gavin. These results show that MAE-FMD generates smaller scale clusters on most of data, and MCL doesn't effectively detect modules when a dataset is largely sparse (i.e. human interaction networks).Figures [11](#Fig11){ref-type="fig"}, [12](#Fig12){ref-type="fig"}, [13](#Fig13){ref-type="fig"}, [14](#Fig14){ref-type="fig"} and [15](#Fig15){ref-type="fig"} show the overall comparison results of these methods in terms of various evaluation metrics, including Coverage, Precision, Recall, F-measure, Sensitivity, PPV and Accuracy for five different data, respectively. From the first panel of these figures, we can conclude that our algorithm archives good performance on the Coverage for all five data sets. For instance, one can easily see that the Coverage of our algorithm is the third highest one among seven algorithms on DIP, MIPS and DIPScere20140703, which is higher than that of other four algorithms and only lower than that of NACO-FMD and MCL. The main reason is that these algorithms adopted different clustering mechanisms which can seriously exert influence on the percentage of proteins clustered into functional modules in a PPI network. Essentially, MAE-FMD, NACO-FMD, HAM-FMD and MCL have two similar characteristics: 1) Three representations of solutions are established on the basis of all nodes of the PPI network. For example, MCL uses a matrix representation of nodes, NACO-FMD employs an ordered sequence of nodes while HAM-FMD and MAE-FMD adopt a connection encoding of nodes; 2) All four algorithms use random clustering mechanisms though specific methods are different. Both characteristics insure that clustering results can include most of nodes in the PPI network. However, MAE-FMD, NACO-FMD and HAM-FMD adopt similar filter operators in post-processing process, thus their coverage values are smaller than that of MCL. Moreover, HAM-FMD combines the random search mechanism used by NACO-FMD with the similar random mechanism used by MAE-FMD, so its coverage value is smaller than those of NACO-FMD and MAE-FMD. Moreover, for the human data (i.e. DIP Hsapi20140703) with large sparsity, our algorithm obtains the best result which shows that MAE-FMD can still keep good coverage performance even when there are seriously sparse connections in the data set.From the second to fourth panels of these figures, we can see that the Precision values of our algorithm are 57%, 50%, 29.9%, 27%, and 18%, respectively. In detail, MAE-FMD obtains the second best result which is only inferior to that of MCODE (72.5%) on Gavin, the third best result which is only inferior to that of CFinder (51.4%, and 30.9%) and MCODE (64.8% and 37.3%) on DIP and MIPS data and that of CFinder (21%) and Coarch (19%) on DIPHsapi20140703 data, and fourth best result which is superior to that of NACO-FMD (22%), MCL (15%) and HAM-FMD (22%) on DIPScere20140703 data. Further, it is easy to observe that our algorithm obtains the best performance on the Recall for Gavin (67.9%), MIPS (46.9%) and DIPHsapi20140703 (17%) data, and is only inferior to that of NACO-FMD on DIP data (less 1.3%) and Coach on DIPScere20140703 data (less 1%). In combination, our algorithm archives the most excellent F-measure on Gavin, DIP, MIPS and DIPHsapi20140703 data, and the second best result on DIPScere20140703 data. That is, our algorithm obtains the highest F-measure value 62.0% with the Gavin data as shown in Figure [11](#Fig11){ref-type="fig"}, which is 31.77%, 14.84%, 16.2%, 17.31%, 17.3% and 18.92% higher than that of CFinder, Coach, NACO-FMD, MCL, HAM-FMD and MCODE, 52.2% with the DIP data as shown in Figure [12](#Fig12){ref-type="fig"}, which is 12.4%, 5.3%, 7.9%, 15.6%, 2.0% and 16.4% higher than that of CFinder, Coach, NACO-FMD, MCL, HAM-FMD and MCODE, 36.6% with the MIPS data as shown in Figure [13](#Fig13){ref-type="fig"}, which is 12.2%, 4.3%, 8.3%, 15.7%, 7.2% and 16.4% higher than that of CFinder, Coach, NACO-FMD, MCL, HAM-FMD and MCODE, 17% with the DIPHsapi20140703 data as shown in Figure [15](#Fig15){ref-type="fig"}, which is 9%, 16%, 8.9%, 2% and 15% higher than that of CFinder, Coach, NACO-FMD, HAM-FMD and MCODE, and 37% with the DIPScere20140703 data as shown in Figure [14](#Fig14){ref-type="fig"}, which is 13%, 7%, 14%, 7% and 20% higher than that of CFinder, NACO-FMD, MCL, HAM-FMD and MCODE, and only 0.3% lower than that of Coach, respectively.From these figures, we also can observe that MAE-FMD gets the best sensitivity in four data sets (Gavin, DIP, MIPS and DIPHsapi20140703) and the second best result in another data (DIPScere20140703), which indicates the modules detected by our algorithm can cover the real functional modules to a great extent. More specifically, we can see that the sensitivity of our algorithm is 72.4% in Figure [11](#Fig11){ref-type="fig"}, which is 24.4%, 40.0%, 32.7%, 33.2%, 36.9% and 34.6% higher than that of CFinder, Coach, NACO-FMD, MCL, HAM-FMD and MCODE algorithms with the Gavin data. Figure [12](#Fig12){ref-type="fig"} shows the sensitivity of our algorithm is 57.0%, which is 25.5%, 33.5%, 25.4%, 27.6%, 29.3% and 32.5% higher than that of CFinder, Coach, NACO-FMD, MCL, HAM-FMD and MCODE algorithms with the DIP data. Figure [13](#Fig13){ref-type="fig"} shows the sensitivity of our algorithm is 36.2%, which is better than that of CFinder (30.9%), Coach (20.7%), NACO-FMD (24.6%), MCL (22%), HAM-FMD (19.3%) and MCODE (15.9%) algorithms with the MIPS data. Figure [15](#Fig15){ref-type="fig"} shows the sensitivity of our algorithm is 30%, which is much better than that of CFinder (18%), Coach (16%), NACO-FMD (17%), HAM-FMD (24.7%) and MCODE (8%) algorithms with the DIPHsapi20140703 data. Though MAE-FMD gets the second best result (59%) on DIPScere20140703 data, it is only inferior to that of CFinder (61%) and also much better than that of Coach (36%), NACO-FMD (50%), MCL (33%), HAM-FMD (47%) and MCODE (20%) algorithms.On Gavin, MIPS, DIPScere20140703 and DIPHsapi20140703 data, MAE-FMD attains the best or the second best PPV value while its PPV performance is not outstanding on DIP data. In detail, the PPV value of MAE-FMD is 30.7% shown in Figure [11](#Fig11){ref-type="fig"}, which is 9.9%, 4.7%, 1.4%, 0.4% and 5.0% higher than that of CFinder, Coach, NACO-FMD, MCL and MCODE and is 0.9% lower than that of HAM-FMD. Figure [12](#Fig12){ref-type="fig"} shows the PPV value of MAE-FMD is 29.9%, which is 4.4% and 1.4% higher than the CFinder and MCODE algorithms, and is 1.1%, 3.5%, 5.2% and 5.4% lower than that of Coach, NACO-FMD, MCL and HAM-FMD algorithms with the DIP data. In Figure [13](#Fig13){ref-type="fig"}, the PPV value of MAE-FMD is 34.2%, which is 15.3%, 10.6%, 1.2%, 5.1% and 8.2% higher than that of CFinder, Coach, NACO-FMD, MCL and MCODE, and only is 2.1% lower than that of HAM-FMD. The PPV value of MAE-FMD is 32% shown in Figure [14](#Fig14){ref-type="fig"}, which is 17%, 9%, 1%, 1% and 15% higher than that of CFinder, Coach, NACO-FMD and MCODE and is equal to that of MCL. In Figure [15](#Fig15){ref-type="fig"}, the PPV value of MAE-FMD is 48%, which is equal to that of NACO-FMD, and 16%, 11% and 17% higher than that of CFinder, Coach and MCODE while it is only 4% lower than that of HAM-FMD.Overall, our algorithm achieves the highest Acc on all five tested data due to its balanced effort between Sensitivity and PPV. The Acc value of our algorithm is 47.2% shown in Figure [11](#Fig11){ref-type="fig"}, which is 15.6%, 18.2%, 13.1%, 12.8%, 13.7% and 16.1% higher than that of CFinder, Coach, NACO-FMD, MCL, HAM-FMD and MCODE with the Gavin data, respectively. Figure [12](#Fig12){ref-type="fig"} shows the Acc value of our algorithm is 41.3%, which is 12.9%, 14.3%, 8.8%, 9.2%, 10.1% and 14.9% higher than that of CFinder, Coach, NACO-FMD, MCL, HAM-FMD and MCODE with the DIP data, respectively. Figure [13](#Fig13){ref-type="fig"} shows the Acc value of our algorithm is 35.2%, which is 11.0%, 13.1%, 6.8%, 9.9%, 8.7% and 14.9% higher than that of CFinder, Coach, NACO-FMD, MCL, HAM-FMD and MCODE with the MIPS data. Figure [14](#Fig14){ref-type="fig"} shows the Acc value of our algorithm is 43%, which is 12%, 14%, 3.4%, 11%, 5% and 25% higher than that of CFinder, Coach, NACO-FMD, MCL, HAM-FMD and MCODE with the DIPScere20140703 data. Similarly, our algorithm attains 38% on Acc metric, which is 14%, 14%, 9%, 2% and 22% higher than that of CFinder, Coach, NACO-FMD, HAM-FMD and MCODE with the DIPHsapi20140703 data. These experimental results on the Acc performance show that our algorithm is superior to other six algorithms.Table 3**The results of various algorithms on different data sets**Data setsResultsAlgorithmsMAE-FMDCFinderCoachNACO-FMDMCLHAM-FMDMCODENumber of clusters1939832516220816369GavinSize of average module6.3012.9110.378.136.766.879.35*N* ~*cp*~\>0.21105417892998849*N* ~*cb*~\>0.22248917716418016386Number of clusters23417338340650029688DIPSize of average module8.408.095.665.574.574.886.52*N* ~*cp*~\>0.21178917714914413956*N* ~*cb*~\>0.222313920423921523197Number of clusters38417848854359344983MIPSSize of average module5.849.299.234.936.163.926.23*N* ~*cp*~\>0.2115551461199211030*N* ~*cb*~\>0.21978615117313815755Number of clusters52620489157196859855DIPScere20140703Size of average module5.5513.038.967.525.044.5114.38*N* ~*cp*~\>0.21476527412714813322*N* ~*cb*~\>0.22428624621220821547Number of clusters741202304350---62678DIPHsapi20140703Size of average module4.395.764.574.85---3.895.17*N* ~*cp*~\>0.2136436045---1129*N* ~*cb*~\>0.2136415347---1129Figure 11**Comparative results of some methods in terms of various evaluation metrics for Gavin data.**Figure 12**Comparative results of some methods in terms of various evaluation metrics for DIP data.**Figure 13**Comparative results of some methods in terms of various evaluation metrics for MIPS data.**Figure 14**Comparative results of some methods in terms of various evaluation metrics for DIPScere20140703 data.**Figure 15**Comparative results of some methods in terms of various evaluation metrics for DIPHsapi20140703 data.**

Table [4](#Tab4){ref-type="table"} compares the distribution of the p-values of protein modules obtained by 7 different algorithms on DIP data, where the first column gives different types of p-values, the second column lists 7 algorithms, and the third to eighth columns respectively present the number of modules located in the corresponding range while the ninth column shows the ratio of the modules with a p-value and all modules detected for each algorithm. From these results, we can find that MCODE, Coach, and CFinder have the three highest ratios in all the statistics, however, MCODE only obtains the minimum amount of modules while Coach can obtains the maximum amount of modules. The ratio difference of three swarm intelligence algorithms (MAE-FMD, HAM-FMD and NACO-FMD) is not obvious, particularly to MAE-FMD and HAM-FMD. MCL has the worst ratio in three types of p-values. Moreover, it is worth noting that most modules with a p-value are concentrated in the area (1.0e-10, 1.0e-3\], and only a few modules fall into the range (0, 1.0e-20\] where MAE-FMD has obvious advantages comparing with other algorithms.Table 4**Distribution comparisons of the p-values of protein modules obtained from different algorithms on DIP**p-valuesAlgorithmsDistribution rangesRatio(0,1 ***.*** 0 ***e*** −30\](1 ***.*** 0 ***e*** −30,1 ***.*** 0 ***e*** −20\](1 ***.*** 0 ***e*** −20,1 ***.*** 0 ***e*** −10\](1 ***.*** 0 ***e*** −10,1 ***.*** 0 ***e*** −3\](1 ***.*** 0 ***e*** −3,0 ***.*** 05\](0 ***.*** 05,1\]MAE-FMD4123310035170.859CFinder34268032150.925BiologicalCoach125721374240.966ProcessNACO-FMD252815896400.810MCL1535180110570.733HAM-FMD232713964250.878MCODE0115551130.966MAE-FMD714307628220.756CFinder56187618100.769CellularCoach295418760260.880ComponentNACO-FMD293413761380.692MCL3113814467550.601HAM-FMD163510951230.760MCODE012142870.898MAE-FMD46227238200.692CFinder13136336150.757MolecularCoach1120128108450.789FunctionNACO-FMD121910869470.606MCL132210284500.495HAM-FMD01159459320.679MCODE0083913120.818

To further investigate the computational results, 10 protein modules with low p-values and high matching rate predicted by different algorithms using DIP data are respectively presented in Tables [5](#Tab5){ref-type="table"}, [6](#Tab6){ref-type="table"}, [7](#Tab7){ref-type="table"}, [8](#Tab8){ref-type="table"}, [9](#Tab9){ref-type="table"}, [10](#Tab10){ref-type="table"} and [11](#Tab11){ref-type="table"}. In these tables, the first column is a cluster identifier. The second column indicates the number of proteins in each cluster. The third column gives proteins in the predicted module. The four column lists the corresponding real protein module. The fifth column refers to the matching rate (%) between our predicted module and a real module, which can be computed as *N*~*pm*~/*N*~*pc*~, where *N*~*pm*~ is the number of proteins belonging to the same MIPS module (real module) within the matched module, and *N*~*pc*~ is the number of proteins contained in the matched module. The last three columns show corresponding *p*-values of the predicted module from the view of Biological Process, Cellular Component and Molecular Function. From the column of matching rate, we can see that many of the protein modules detected by the seven algorithms match well with the benchmark modules. The p-values of modules in these tables are very low, which further demonstrates that the modules identified have high statistical significance from three different Gene Ontology categories.Table 5**Some functional modules predicted by MAE-FMD using DIP data**IDSizeProteins in the predicted moduleReal protein moduleMR(%)p-valuesBiologicalCellularMolecular15yor132w yor069w yjl154c yhr012w yjl053wRetromer module1003.13e-095.58e-134.67e-08213ykl022c ynl172w yfr036w yhr166c ybl084c ylr127cAnaphase-promoting1004.76e-251.82e-312.84e-14yor249c ygl240w ylr102c ydl008w ydr118w ygl003cygr225w310ymr094w yjr060w ydr318w ygr179c ypl018w ygr140wKinetochore module1001.70e-075.95e-162.29e-13ymr168c yjr089w ykl049c ykl089w429yer148w ygr274c ycr042c ydr448w ydr176w ygr252wTranscription factor86.22.80e-241.48e-251.18e-24yol148c yel009c ymr236w ygl112c ybr198c ybr081cydr216w ydr167w ypl254w ypr086w yor023c ycr082wyml114c yml098w ydr392w ydr145w yor194c ykl058wyml015c ypl011c yil129c ymr005w ymr227c510yjl203w ydl043c ydl030w ymr240c yor319w ynl286wRibonucleo protein1004.63e-147.74e-191.93e-06yml049c ymr288w ypl213w yir009w616yjl194w yml065w ybr060c yll004w ypr162c ynl261wDNA replication preinitiation87.53.72e-291.46e-307.63e-28yhr118c ybl023c ylr103c ylr274w yil150c yel032wybr202w ypr019w ymr216c ygl201c719ybl099w ynl315c yjl180c yjr121w ydr322c ylr295cMitochondrial proton-transportin73.72.80e-241.48e-251.18e-24ypl271w ydl004w ydr377w yml081c ypr020w ybr039wATP synthaseyypl078c ydr298c q0085 ykl016c q0080 q0130ydl181w89ykr026c ypl237w yor260w yjr007w ydr211w ygr083cInteracting eIF2 (Sui2/3/4) and88.95.43e-132.50e-112.89e-14ylr291c ypl070w yer025weIF2B (Gcd1/2/6/7/Gcn3)921yhr041c yer022w ydr308c ybr253w ymr112c yor174wDNA-directed RNA90.51.55e-181.04e-372.36e-13yol135c ykl028w ykr062w yhr058c yol051w ypr070wpolymerase IIydl005c ybr193c ygl025c ylr071c ybl093c ynl236wygr104c ycr081w yor140w106ylr418c ybr279w yol145c yor123c ygl244w yml010wTranscription elongation factor1007.43e-154.11e-112.63e-12Table 6**Some functional modules predicted by CFinder using DIP data**IDSizeProteins in the predicted moduleReal protein moduleMR(%)p-valuesBiologicalCellularMolecular15yor132w yjl154c yhr012w yjl053w yor069wRetromer module1003.13e-095.58e-134.67e-08221ydl140c ydl108w yor151c yil021w ydr138w yjl140wDNA-directed RNA85.76.88e-173.27e-248.45e-19ybr154c ypr187w yor210w yml010w ygl070c ykl145wpolymerase II, holoenzymeydr404c ypl129w ybr279w yor123c yol005c ygl244wyol145c ylr418c ylr384c320ydl140c yer165w ymr061w ygl044c ykr002w yer133wmRNA cleavage factor901.60e-287.90e-395.71e-13ykl059c ykl018w ydr228c ydr195w ynl317w yjr093cyal043c ypr107c ylr277c ydr301w yor179c yor250cylr115w yol123w418yjr121w q0085 q0080 ydl181w ypl078c ybl099wMitochondrial proton-transporting83.33.88e-373.88e-373.88e-37ydr298c ypl271w ykl016c ynl315c ybr039w q0130ATP synthaseydr322c-a yml081c-a ydr377w ydl004w ypr020w ylr295c513yjr050w yer013w yal032c ykl095w yll036c ybr188cSpliceosomal network92.32.08e-181.83e-221.83e-22ygl120c ygr129w ymr213w ydr416w ypr101w ylr117cypl151c611yor361c ymr309c ynl244c ybr079c ypr041w ygr162weIF1/eIF3/eIF5 complex72.73.22e-145.19e-141.34e-18ygl049c ymr146c yil071c ydr429c ylr192c79ykl052c ykr037c ykr083c ybr156c ypl209c gl061cCondensed nuclear88.97.78e-171.88e-129.31e-15ygr113w ydr201w ydr016cchromosome kinetochore88yor260w ypl237w ygr083c ykr026c yjr007w yer025winteracting eIF2 (Sui2/3/4) and1005.08e-149.27e-122.69e-15ydr211w ylr291cand eIF2B (Gcd1/2/6/7/Gcn3)98ykl018w ybr175w ybr258c yhr119w yar003w ylr015wCOMPASS1004.31e-176.70e-216.70e-21ypl138c ydr469w106yel032w ybl023c ylr274w yil150c ybr202w ylr103cpre-replicative complex83.34.70e-114.70e-114.12e-10Table 7**Some functional modules predicted by Coach using DIP data**IDSizeProteins in the predicted moduleReal protein moduleMR(%)p-valuesBiologicalCellularMolecular15yor132w yor069w yjl154c yhr012w yjl053wRetromer module1003.13e-095.58e-134.67e-08211yor249c ygl240w ydl008w ydr118w ykl022c yfr036wAnaphase-promoting1006.17e-231.38e-252.81e-16yhr166c ybl084c ylr127c ynl172w ylr102c316ydr335w ygl092w ykl068w ymr047c ykr082w ydl116wNuclear pore81.32.49e-195.02e-148.81e-13ygl172w ylr335w ygr119c ymr308c ygr218w yer165wydr192c ylr347c yjr042w ynl189w417ydr448w ydr176w yol148c yhr041c yer022w ydr392wTranscription factor76.53.93e-133.16e-181.88e-06ydr308c ypl181w yer148w yel009c ybr198c ybr081cyhr099w ygr274c ymr236w ypl254w ygl112c58ydr469w yar003w ybr175w ylr015w ypl138c yhr119wChromatin remodeling module1004.10e-122.99e-132.24e-10ybr258c ykl018w68ycr057c yjl069c ydr449c ylr222c ygr090w ylr409cRibonucleoprotein module87.51.09e-111.51e-147.63e-08yjl109c ylr129w77ypr110c ynr003c yor116c yor207c ynl113w ykl144cRNA polymerase III1007.97e-152.39e-152.39e-15ypr190c88ybl099w yjr121w ydr377w yml081c q0085 ykl016cMitochondrial proton-transporting87.55.41e-155.41e-155.41e-15ypl078c ydr298cand ATP synthase97yor260w ykr026c yjr007w ydr211w ygr083c ylr291cInteracting eIF2 (Sui2/3/4)1003.57e-122.57e-122.89e-13ypl237wand eIF2B (Gcd1/2/6/7/Gcn3)109ybl105c yjl002c yel002c yor103c yor085w ydl232wOligosaccharyl transferase88.91.48e-131.30e-171.33e-11ygl226c ygl022w ymr149wTable 8**Some functional modules predicted by NACO-FMD using DIP data**IDSizeProteins in the predicted moduleReal protein moduleMR(%)p-valuesBiologicalCellularMolecular15yor132w yor069w yjl154c yhr012w yjl053wRetromer module1003.13e-095.58e-134.67e-08211ykl022c yhr166c ybl084c yfr036w ynl172w ylr127cAnaphase-promoting1006.17e-231.38e-252.81e-16yor249c ylr102c ygl240w ydl008w ydr118w324yor098c ynl189w yhr129c ygr119c ygl172w yil063cNuclear pore70.89.65e-274.29e-212.36e-19ygl092w ydr002w ydr192c ypl174c ylr347c yer009wykl068w ylr335w ymr047c ymr294w ygl097w ydl116wykl057c ykr082w ydr488c yjr042w yar002w ypl125w415yer148w ydr448w ydr176w yel009c ybr198c ygr274cTranscription factor TFIIIB93.35.87e-144.65e-192.36e-10ybr081c yol148c ydr167w ymr236w ydr392w ygl112cypl254w ypl181w ypl011c59ybl023c yil150c ylr103c ylr274w ygl201c yel032wDNA replication preinitiation77.81.86e-141.86e-149.40e-14ybr202w ypr019w ymr216c69ynr003c ypr110c ynl113w ydr045c yor116c yor207cRNA polymerase III88.92.28e-194.69e-204.69e-20ypr190c yhr143w-a ykl144c712yll036c ydr416w ybr188c yjr050w yir009w yal032cRibonucleo protein91.75.96e-173.33e-233.33e-23ymr213w ygr129w ylr117c ykl095w ypl213w ypr101w814ydr228c ypr107c yol123w ymr061w ygl044c yjr093cmRNA cleavage factor1001.23e-301.23e-301.82e-12ykr002w ydr301w ylr277c ynl317w ylr115w yor250cyal043c ykl059c97yhr090c yhr099w yor244w yjl081c ypr023c yfl024cTranscription factor1008.08e-098.08e-162.34e-10ynl107w106ygl061c ydr201w ykr083c ydr016c ykr037c ykl052cKinetochore module1002.63e-152.63e-157.90e-14Table 9**Some functional modules predicted by MCL using DIP data**IDSizeProteins in the predicted moduleReal protein moduleMR(%)p-valuesBiologicalCellularMolecular15yyor132w yor069w yjl154c yhr012w yjl053wRetromer module1003.13e-095.58e-134.67e-08212ykl022c ynl172w yfr036w yhr166c ybl084c ylr127cAnaphase-promoting1004.62e-222.08e-284.13e-15yor249c ygl240w ylr102c ydl008w ydr118w ygr225w38yar003w ybr175w ydr469w ylr015w yhr119w ypl138cCOMPASS module1004.31e-174.31e-176.70e-21ybr258c ykl018w410ymr309c ynl244c ypr041w yor361c ymr146c ydr429ceIF1/eIF3/eIF5 module807.12e-102.05e-141.51e-13yil071c ybr079c ynl062c ylr192c516ydr195w ydr228c yor250c ymr061w ypr107c yjr093cmRNA cleavage factor93.86.79e-264.48e-331.92e-11ykr002w ydr301w ylr115w yal043c ylr277c ynl317wykl059c yor179c ynl222w ydl094c67yjl194w yml065w ybr060c yll004w ypr162c ynl261wDNA replication preinitiation1005.38e-144.19e-152.64e-12yhr118c713yor076c ygr158c ydl111c ygr195w ydr280w yol021cExosome1002.62e-284.57e-304.36e-02yhr069c ynl232w yol142w ycr035c ygr095c yor001wyhr081w810ynr003c ypr190c ypr110c ynl113w yor116c ydr045cRNA polymerase III1001.93e-154.50e-164.50e-16yor207c yfr011c ynl248c ykl144c98ybl023c ylr103c ylr274w yil150c yel032w ybr202wDNA replication preinitiation752.93e-122.93e-123.92e-11ymr216c ygl201c106ylr418c ybr279w yol145c yor123c ygl244w yml010wTranscription elongation factor1007.43e-154.11e-112.63e-12Table 10**Some functional modules predicted by HAM-FMD using DIP data**IDSizeProteins in the predicted moduleReal protein moduleMR(%)p-valuesBiologicalCellularMolecular15yor132w yjl154c yhr012w yjl053w yor069wRetromer module1003.13e-095.58e-134.67e-08212ybl084c ydl008w ydr118w yfr036w ygl240w ygr225wAnaphase-promoting1004.62e-222.08e-284.13e-15yhr166c ykl022c ylr102c ylr127c ynl172w yor249c318yal043c ydr195w ydr228c ydr301w yer032w ygl044cRNA 3' end processing factor72.21.44e-332.76e-376.81e-13ygr156w yjr093c ykl018w ykl059c ykr002w ylr115wylr277c ymr061w ynl317w yor179c yor250c ypr107c411q0080 q0130 ybl099w ybr039w ydl004w ydl181wMitochondrial proton-transporting81.82.53e-132.53e-132.53e-13ydr322c yjr121w yrl295c ynl315c ypl271wATP synthase510yar019c ybr127c ydl185w yel051w ygr020c ygr092wNo description801.09e-163.49e-161.74e-15ylr447c ymr054w yor270c yor332w610ycr057c ydr449c yer082c ygr090w yjl069c yjl109cSmall-subunit processome1004.59e-151.46e-181.40e-09ylr129w ylr222c ylr409c ypl126w79ybr156c ydr016c ydr201w ygl061c ygr113w ykl052cmutLbeta module88.97.78e-177.78e-179.31e-15ykr037c ykr083c ypl209c88ydr211w yer025w ygr083c yjr007w ykr026c ylr291cInteracting eIF2 (Sui2/3/41005.08e-149.27e-122.69e-15yor260w ypl237wand eIF2B (Gcd1/2/6/7/Gcn3)97yar003w ybr175w ybr258c ydr469w yhr119w ylr015wTranscription factor1001.23e-141.53e-171.53e-17ypl138c107q0085 ydr298c ydr377w ykl016c yml081c ypl078cMitochondrial proton-transporting85.71.64e-124.58e-141.64e-12ypl138cATP synthaseTable 11**Some functional modules predicted by MCODE using DIP data**IDSizeProteins in the predicted moduleReal protein moduleMR(%)p-valuesBiologicalCellularMolecular15yhr012w yjl053w yjl154c yor069w yor132wRetromer module1003.13e-095.58e-134.67e-08210ybl084c ydl008w ydr118w yfr036w ygl240w yhr166cAnaphase-promoting1005.62e-248.52e-231.29e-14ykl022c ylr127c ynl172w yor249c39ybl026w ycr077c ydr378c yer112w yer146w yjl124cRibonucleo protein1001.25e-079.18e-141.16e-05yjr022w ylr438c ynl147w48ydl232w yel002c ygl022w ygl226c yjl002c ymr149wOligosaccharyl transferase87.59.37e-158.19e-192.51e-12yor085w yor103c57ycr002c ydl225w ydr507c yhr107c yjr076c ylr314cSeptin module71.48.31e-121.36e-132.49e-08ynl166c66ygr200c yhr187w ylr384c ymr312w ypl086c ypl101wElongator holoenzyme1007.17e-113.11e-166.61e-0576ydr211w ygr083c yjr007w ykr026c ylr291cInteracting eIF2 (Sui2/3/4)1003.14e-107.03e-133.82e-11yor260wand eIF2B (Gcd1/2/6/7/Gcn3)86ybr087w yhr191c yjr068w ymr078c ynl290w yol094cCtf18 RFC-like module1008.60e-102.59e-151.70e-0896q0085 ybl099w ydr377w yjr121w ykl016cMitochondrial proton-transporting83.34.59e-104.59e-104.59e-10yml081cATP synthase106ybr079c ydr429c ylr192c ynl244c yor361c ypr041weIF1/eIF3/eIF5 module1002.39e-072.56e-105.52e-11

To explicitly reveal the results obtained by our algorithm, we take two modules as the examples to explain. For the retromer module, corresponding to the first module in these seven tables, the seven algorithms have obtained the same good performance in terms of p-values and matching rates. That is, the real retromer module is correctly detected by all seven algorithms. Compared to the anaphase-promoting module (corresponding to the second module in Tables [7](#Tab7){ref-type="table"}, [8](#Tab8){ref-type="table"}, [9](#Tab9){ref-type="table"}, [10](#Tab10){ref-type="table"} and [11](#Tab11){ref-type="table"}) that is respectively detected by the Coach, NACO-FMD, MCL, HAM-FMD and MCODE algorithms, the minimum p-value of our algorithm in Table [5](#Tab5){ref-type="table"} is 1.82e-31, which is much less than those of the other five algorithms since the minimum p-values of the module predicted by the Coach, NACO-FMD, MCL, HAM-FMD and MCODE algorithms are 1.38e-25, 1.38e-25, 2.08e-28, 2.08e-28 and 5.62e-24, respectively. The real anaphase-promoting module in the benchmark consists of 16 proteins, of which 1 protein (ygl116w) is isolated by other proteins within the same module and 2 proteins (yir025w and ydr260c) don't exist in DIP data. Thus, the real structure of the anaphase-promoting module including 13 proteins is shown in Figure [16](#Fig16){ref-type="fig"}(a). The protein module obtained by our algorithm consists of 13 proteins and succeeds in matching all 13 proteins in the benchmark module (shown in Figure [16](#Fig16){ref-type="fig"}(b)). Though the matching rates of Coach, NACO-FMD, MCL, HAM-FMD and MCODE algorithms are also 100%, Coach, NACO-FMD, MCL, HAM-FMD and MCODE only cover 11, 11, 12, 12 and 10 proteins of the real anaphase-promoting module, respectively (shown in Figure [16](#Fig16){ref-type="fig"}(c), Figure [16](#Fig16){ref-type="fig"}(d) and Figure [16](#Fig16){ref-type="fig"}(e)). In addition, CFinder has not obtained the real anaphase-promoting module. Actually, CFinder finds a huge cluster which contains 13 proteins in the real anaphase-promoting module and 49 other proteins. In other words, the example demonstrates that our algorithm can accurately predict protein modules. To show more biological details of Figure [16](#Fig16){ref-type="fig"}, Table [12](#Tab12){ref-type="table"} gives some corresponding messages of the sixteen proteins in anaphase-promoting module.Figure 16**The anaphase-promoting module detected by various algorithms.** **(a)** Benchmark; **(b)** MAE-FMD algorithms; **(c)** Coach and NACO-FMD algorithms; **(d)** MCL and HAM-FMD algorithms; and **(e)** MCODE algorithm.

###### 

**Sixteen proteins in anaphase-promoting module**

  ID   Gene name   Protein name                                    Detail messages (url)
  ---- ----------- ----------------------------------------------- -----------------------------------------
  1    yir025w     Anaphase-promoting complex subunit MND2         <http://www.uniprot.org/uniprot/P40577>
  2    ydr260c     Anaphase-promoting complex subunit SWM1         <http://www.uniprot.org/uniprot/Q12379>
  3    ygl116w     APC/C activator protein CDC20                   <http://www.uniprot.org/uniprot/P26309>
  4    yor249c     Anaphase-promoting complex subunit 5            <http://www.uniprot.org/uniprot/Q08683>
  5    ylr127c     Anaphase-promoting complex subunit 2            <http://www.uniprot.org/uniprot/Q12440>
  6    ygl240w     Anaphase-promoting complex subunit DOC1         <http://www.uniprot.org/uniprot/P53068>
  7    ylr102c     Anaphase-promoting complex subunit 9            <http://www.uniprot.org/uniprot/Q12107>
  8    ydl008w     Anaphase-promoting complex subunit 11           <http://www.uniprot.org/uniprot/Q12157>
  9    ygr225w     Meiosis-specific APC/C activator protein AMA1   <http://www.uniprot.org/uniprot/P50082>
  10   ydr118w     Anaphase-promoting complex subunit 4            <http://www.uniprot.org/uniprot/P0C5L7>
  11   ykl022c     Anaphase-promoting complex subunit CDC16        <http://www.uniprot.org/uniprot/P09798>
  12   yfr036w     Anaphase-promoting complex subunit CDC26        <http://www.uniprot.org/uniprot/P14724>
  13   ygl003c     APC/C activator protein CDH1 CDC20 homolog 1    <http://www.uniprot.org/uniprot/P53197>
  14   ybl084c     Anaphase-promoting complex subunit CDC27        <http://www.uniprot.org/uniprot/P38042>
  15   yhr166c     Anaphase-promoting complex subunit CDC23        <http://www.uniprot.org/uniprot/P16522>
  16   ynl172w     Anaphase-promoting complex subunit 1            <http://www.uniprot.org/uniprot/P53886>

Moreover, our algorithm also obtains some new modules on all five data sets. Table [13](#Tab13){ref-type="table"} lists 5 new modules with lower p-values on the DIP data, which are not previously described or not detected by other six algorithms. This means that MAE-FMD has certain exploratory ability in detection functional modules from a PPI network.Table 13**Some new functional modules predicted by MAE-FMD algorithm using DIP data**IDSizeProteins in the predicted modulep-valuesBiologicalCellularMolecular122yjr045c yil022w yor232w ybr091c yhr005c ydl217c2.67e-272.04e-216.19e-23yjl064w yjl143w ynl121c ynl131w yfl016c ynr017wygr082w ymr203w yel020w ybl030c yml054c yjl054wyor297c ygr181w yjr135w ypl063w215ydr382w ylr340w ydl081c ydl130w yel054c4.66e-128.88e-121.22e-12yol039w ylr287c ylr199c ylr177w yjr125cyor111w ygr034w ymr131c yor063w ygr214w315ymr055c yml064c yfr028c yjl076w yjr053w4.14e-191.14e-152.26e-12ybr211c ygr113w ygl061c ydr016c ydr201wykr037c ykr083c ykl052c ypl209c ybr156c413yll036c ymr213w ydr416w yjr050w ybr188c2.17e-181.91e-221.91e-22ygr129w ylr117c ykl095w ypr101w yal032cypl151c ygl120c ydr364c510ydr036c ybr251w yhl004w ydr175c ylr009w1.21e-128.40e-145.46e-13yil093c ygl068w ypl013c ybl038w ynl284c

In this section, we have performed complete comparisons among MAE-FMD, CFinder, Coach, NACO-FMD, MCL, HAM-FMD and MCODE algorithms in terms of various evaluation metrics (e.g. F-measure, accuracy, p-value etc). These evaluation comparisons from different perspectives show that MAE-FMD is a promising method to effectively identify functional module structures in PPI networks. It should be noted that F-measure and accuracy are two comprehensive evaluation metrics whose values can more objectively reflect the detection quality from different computational views. In light of accuracy, MAE-FMD significantly outperforms CFinder, Coach, NACO-FMD, MCL, HAM-FMD and MCODE on five protein data sets. Based on F-measure, MAE-FMD also outperforms other six algorithms on Gavin, DIP, MIPS and DIPHsapi20140703 data, and is slightly worse than Coach on DIPScere20140703 data. On the other hand, since the p-value of modules is a metric to incarnate the biological significance, the more number of modules we get with lower p-values, the greater significant the application is. Though the number of modules discovered by MAE-FMD is smaller than most of algorithms compared on yeast data, the number of modules with lower p-value discovered by MAE-FMD is no less than those algorithms did. For instance, MAE-FMD detects 234 modules on DIP data which is less than those of HAM-FMD, NACO-FMD, Coarch and MCL, however, the number of modules located in (0, 1.0e-20\] is 16, 21 and 10 from three types of p-values, which is much larger than those of other four algorithms. Moreover, MAE-FMD can identify some new modules that were not previously identified by other algorithms, especially for the human data. All these results show MAE-FMD can identify more biological functional modules.

In summary, the outstanding experimental results of MAE-FMD on five different data sets demonstrate that MAE-FMD is robust algorithm whose performances are not dependent on the underlying data.

Conclusions {#Sec17}
===========

To reveal unknown functional ties between proteins and predict functions for unknown proteins, people have remained a great interest in mining functional modules from PPI networks over the past decade. However, how to accurately predict these protein modules through computational methods is still a highly challenging issue. This paper presented a multi-agent evolution approach called MAE-FMD, which can achieve a high accuracy for identifying functional modules in PPI networks. The most significant feature of MAE-FMD is that the algorithm utilizes random search and optimization mechanisms in the solution constructing and evolutionary processes. First, MAE-FMD employs a random-walk model merged topological characteristics with functional information to construct a candidate solution for each agent, which can effectively and reasonably find a feasible solution. And then, it applies some simple evolutionary operators, i.e., competition, crossover, and mutation, to realize information exchange among agents during the evolution process. The competition operator can replace the worst connection information with the better information to improve the winner anent, the crossover operator performs a random search in a solution space by the cooperation between neighborhood agents while the mutation operator carries out local searches with randomness. The experimental results indicate that our algorithm has the characteristics of outstanding recall, F-measure, sensitivity, accuracy and p-value and can obtain some new modules on five benchmark data sets while keeping other competitive performances, so it can be applied to the biological study which requires a higher accuracy. It should be pointed out that the algorithm doesn't take into account overlapping functional modules based on the current representation and evolution of solutions, and may require longer running time for larger scale PPI networks due to the iterative evolution of the population. Thus, our future work includes investigating some new strategies to further improve the time efficiency and detect overlapping modules in PPI networks.

Endnote {#Sec18}
=======

^a^ Because the underlying protein interaction data used in the paper do not provide temporal and spatial information, we use the concept of functional modules.

**Competing interests**

The authors declare that they have no competing interests.

**Authors' contributions**

JZJ and LJ conceived the work. LJ and JWL performed the experimental analysis. JZJ and CCY prepared the manuscript with revisions by ADZ. All authors read and approved the final manuscript.

This work is partly supported by National "973" Key Basic Research Program of China (2014CB744601), NSFC Research Program (61375059, 61332016), Specialized Research Fund for the Doctoral Program of Higher Education (20121103110031), and the Beijing Municipal Education Research Plan key project (Beijing Municipal Fund Class B) (KZ201410005004).
