# Identifying Protein Complexes from Dynamic Temporal Interval Protein-Protein Interaction Networks

Authors: Jinxiong Zhang; Cheng Zhong; Hai Xiang Lin; Mian Wang
Journal: BioMed Research International
 (2019)

---

## Abstract

Identification of protein complex is very important for revealing the underlying mechanism of biological processes. Many computational methods have been developed to identify protein complexes from static protein-protein interaction (PPI) networks. Recently, researchers are considering the dynamics of protein-protein interactions. Dynamic PPI networks are closer to reality in the cell system. It is expected that more protein complexes can be accurately identified from dynamic PPI networks. In this paper, we use the undulating degree above the base level of gene expression instead of the gene expression level to construct dynamic temporal PPI networks. Further we convert dynamic temporal PPI networks into dynamic Temporal Interval Protein Interaction Networks (TI-PINs) and propose a novel method to accurately identify more protein complexes from the constructed TI-PINs. Owing to preserving continuous interactions within temporal interval, the constructed TI-PINs contain more dynamical information for accurately identifying more protein complexes. Our proposed identification method uses multisource biological data to judge whether the joint colocalization condition, the joint coexpression condition, and the expanding cluster condition are satisfied; this is to ensure that the identified protein complexes have the features of colocalization, coexpression, and functional homogeneity. The experimental results on yeast data sets demonstrated that using the constructed TI-PINs can obtain better identification of protein complexes than five existing dynamic PPI networks, and our proposed identification method can find more protein complexes accurately than four other methods.


---

## Body

## 1. Introduction

The majority of proteins interact with each other to perform a specific biological process [1]. The fast accumulation of protein-protein interaction (PPI) data has made maps of PPI networks of several model organisms become available [2]. Identifying protein complexes from PPI networks plays a key role in understanding cellular organizations and functional mechanisms [3].Over the past decades, the studies on identifying protein complexes from static protein-protein interaction network (SPIN) have yielded many effective methods. The clustering-based methods such as MCODE [4], ClusterONE [5], MCL [6], PCP [7], APcluster [8], SPICi [9], and DPCLus [10] identify complexes by detecting closely connected structures from SPIN. Gavin et al. [1] discovered the core-attachment structure of yeast protein complexes based on genome-wide analysis. Accordingly, CORE [11], COACH [12], WPNCA [13], and MCL-CAw [14] were designed to find protein complexes from SPIN. Some methods [15–17] detect protein complexes with biological significance by integrating GO-based functional annotations and SPIN, and other methods [18, 19] measure Pearson correlation coefficient between two proteins and weight SPIN to identify protein complexes.The aforementioned methods mainly focus on identifying complexes from static protein-protein interaction network (SPIN). However, the real PPI network in cell keeps changing over different stages of the cell cycle [20]. In fact, cellular systems are highly dynamic and responsive to environment cues [21]. So it is expected that modelling the real PPI network as dynamic PPI networks can lead to identifying more protein complexes accurately.Fortunately, by monitoring simultaneous and quantitative changes in RNA concentration of thousands of genes under various experimental conditions, DNA microarray technology produced a large number of gene expression data [22, 23]. These gene expression data provide potential insights into the dynamics of PPI networks. Thus, the key step of identifying protein complexes from dynamic PPI networks is how to construct nearly real PPI networks using gene expression data. During a whole cell cycle, protein is not always active all the time. To construct the dynamic PPI network, it requires determining the so-called active time point at which protein exhibits activity. According to the periodicity of gene expression, De Lichtenberg et al. [24] constructed dynamic PPI networks over the yeast mitotic cell cycle by determining active time points of each protein. A protein is considered to be active when its level of gene expression exceeds a specified threshold. Tang et al. [22] used a recommended threshold to filter nonactive protein over three successive metabolic cycles and then constructed a time-course protein interaction network (TC-PIN). Instead of using a global threshold, Wang et al. [23] presented a three-sigma method, which uses the sum of the gene expression mean and three standard deviations as a threshold, to determine active time points of each protein, and constructed dynamic protein interaction networks (DPIN) and identified complexes from DPIN. Some swarm intelligence-based methods [25–29] also exploit the three-sigma method to construct dynamic PPI networks and identify protein complexes. Based on the three-sigma method, Zhang et al. [30] calculated the active probability of each protein at different time point to determine the active time point of each protein and constructed dynamic probabilistic protein interaction networks (DPPN). Furthermore, OU-Yang et al. [31] proposed a time smooth overlapping complexes detection (TS-OCD) model to construct dynamic PPI networks to detect temporal protein complexes. Shen et al. [32] used the deviation degree method to construct a Time-Evolving PIN (TEPIN) to detect temporal protein complexes. By adopting a dynamic model-based method to filter the noisy data from gene expression profiles, Xiao et al. [21] proposed ak-sigma method to determine whether a protein at a time point is active and constructed a noise-filtered active protein interaction network (NF-APIN) to detect protein complexes. The fore-mentioned methods mainly consider how to construct the dynamic PPI networks and then apply existing identification method to find protein complexes from the constructed dynamic PPI networks.Furthermore, some researchers have not only investigated how to construct the dynamic PPI networks but also designed identifying methods to find protein complexes from the constructed dynamic PPI networks. By combining the active probability of proteins and Pearson correlation coefficient of PPIs with static PPI networks, Zhang et al. [33] constructed dynamic PPI networks and proposed a protein complex prediction method. Based on the neighbor affinity and dynamic protein-protein interaction network, DPC-NADPIN method [34] selects the proteins with a high clustering coefficient and their neighbors to consolidate into an initial cluster and iteratively expands the neighbor proteins to the cluster to form a protein complex. TS-OCD method [31] captures the temporal feature of networks between consecutive time points and detects temporal protein complexes from the constructed dynamic PPI networks. Shen et al. [35] proposed a method called DCA (Dynamic Core-Attachment), which uses three-sigma method to construct dynamic PPI network integrating the inherent organizations of protein complexes and applies an outward expanding strategy to identify protein complexes with the characteristic of core-attachment structure. All four above-mentioned works identify protein complexes by constructing dynamic PPI networks using gene expression data and topological features of PPI networks.We observed that all the existing methods determine active time point of proteins by a conservative and relative high threshold. This leads to losing dynamic information of gene with expression value that is lower than the specified threshold. In this paper, we first exploited the undulating degree above the base level of gene expression instead of the gene expression level to determine the active time point of a protein and constructed temporal PPI networks (TPNs) by protein interaction data and gene expression data. We then proposed a method which not only converts TPNs into temporal interval PPI networks (TI-PINs) but also identifies more colocalized, coexpressed, and functionally significant protein complexes from the constructed TI-PINs by multisource biological data. Finally, we evaluated our constructed TI-PINs and other dynamic PPI networks and compared our proposed identification method with four other competing methods.


## 2. Methods

In this section, we describe how to construct temporal interval PPI networks (TI-PINs) and identify protein complexes from TI-PINs.


### 2.1. Preliminary

Let a graphG=(V,E) represent a static protein-protein interaction network (SPIN), whereV is a set of nodes (proteins) andN=V,E is a set of edges (protein-protein interactions), ande(i,j) denotes the edge between nodesi andj, wherei,j=1, 2, …,N. Let Sppi=(PP,s) denote a set of protein-protein interactions with reliability score, wherePP is a set of interacting protein pairs ands(x,y) denote the reliability score of the interacting protein pair (x,y) inPP. Thus, we useGW=(V,E,w) to denote the graphGweighted by Sppi, where the edge weightw(i,j) is defined as follows:(1)wi,j=si,j,ifi,j∈PP,ei,j∈E1,ifi,j∉PP,ei,j∈Ei,j=1,2,…,N.Furthermore, matrixAN×N is used to represent the reliability score matrix ofGW, where the element ai,j of AN×N is defined as follows:(2)ai,j=wi,j,ifei,j∈E0ifei,j∉Ei,j=1,2,…,N.Ifai,j≥r, we define the edge e(i,j) as ar-reliable link between nodesi andj, wherer is a given reliability threshold and r∈1,2,…,999 [36].LetGEN×T denote the matrix of gene expression ofN proteins acrossT time points. For a genei, let evi,t represent the expression value of genei at timet and gepi=gepit∣t=1,…,T denote the gene expression pattern of genei, where gepi(t)=evi,t-ev_mini/ev_maxi-ev_mini, ev_mini⁡=mint=1T⁡evi,t, and ev_maxi⁡=maxt=1T⁡evi,t,i=1,2,…,N,t=1,…,T.In fact, gepi is composed ofTnormalized gene expression values. The normalized gene expression data can be used to measure the undulating degree above the base level of gene expression during a whole cell cycle.


### 2.2. Temporal PPI Networks

When a protein is involved in a specific biological process, the expression data of the protein-coding gene exhibits the undulation above the base level of the gene expression during the biological process. If the normalized expression value of geneiexceeds a specified threshold at a certain time point, we call that the product of genei is activated at this time point. Let api(t) denote the active state of proteiniat time pointt, if proteini is active, api(t)=1, otherwise, api(t)=0,i=1,...,N, andt=1,...,T. For a given active thresholdφ, api(t) is defined as follows:(3)apit=1,ifgepit≥φ0,ifgepit<φ,i=1,…,N,andt=1,…,T.Obviously, a lower active thresholdφpreserves more gene dynamical information. The best active thresholdφwill be discussed in the section “The effect of active threshold”.In order to model the dynamics of active proteins mentioned above, the dynamical PPI network is introduced. In the following, we discuss how to construct temporal PPI networks (TPNs) by incorporating time-course gene expression data into static PPI network SPIN. LetTPNt =(Vt, Et) denote a temporal PPI network at time pointt, where Vt and Et is the set of proteins and the set of interactions between active proteins at time pointt, respectively,t=1, 2, …,T. We use DAt to represent the reliability score matrix of TPNt, where element dai,jt in DAt is computed as follows:(4)dai,jt=apit×apjt×ai,j,i,j=1,…,N,andt=1,2,…,T


### 2.3. Temporal Interval PPI Networks

A protein complex is corresponding to a subgraph in PPI network. To represent the subgraph of a protein complex which appears in several successive temporal PPI networks, we introduce temporal interval PPI networks (TI-PINs). A temporal interval PPI network (TI-PIN) can be generated by merging several successive temporal PPI networks (TPNs). GivenTPNt =(Vt, Et),t=1,...,T, let TI-PINtlow,ttop and Btlow,ttop denote the temporal interval PPI network and its reliability score matrix from tlow to ttop, respectively, where tlow and ttop are two time points and 1 ≤tlow≤ttop≤T. TI-PINtlow,ttop and element bi,jtlow,ttop in Btlow,ttop are defined as follows:(5)TI-PINtlow,ttop=Vtlow,ttop,Etlow,ttop,Vtlow,ttop=⋂t=tlowttopVt,Etlow,ttop=⋂t=tlowttopEt,1≤tlow≤ttop≤T(6)bi,jtlow,ttop=dai,jt,if1≤tlow=t=ttop≤Tmin⁡bi,jtlow,ttop-1,bi,jtlow+1,ttop,if1≤tlow<ttop≤T,i,j=1,2,…,NObviously, if 1 ≤tlow= t =ttop≤ T, then bi,jtlow,ttop=bi,jt,t=dai,jt, namely, TI-PINt,tis the same as TPNt. If 1 ≤tlow<ttop≤T, thenTI-PINtlow,ttop is newly constructed by TPNt, tlow ≤ t ≤ ttop. Here, letl=ttop-tlow+1 denote the temporal interval length. Figure 1 shows the generation of TI-PINtlow,ttop by merging the successive temporal PPI networks (TPNs) from tlow to ttop. From Figure 1, we can see thatT TPNs can generate T·(T-1)/2 TI-PINs.Figure 1
GeneratingTI-PINtlow,ttopby merging the successive temporal PPI networks TPNs from tlow to ttop. For example,TI-PIN5,9 is generated by merging TPNs from time point 5 to time point 9. TI-PINs in the triangle of red dash lines are generated by TPNs in the rectangle of red dash lines. A TI-PINt1,t2 corresponds to a temporal interval (t1,t2), where 1 ≤t1 ≤t2 ≤T= 12.For given time pointstlow and ttop, and tlow<ttop, if the PPI subgraph Gpc of a protein complex appears in all TPNtlow,TPNtlow+1,…, and TPNttop, then Gpc also appears in all TI-PINt1,t2,t1 ≤t2 andt1,t2=tlow, tlow+1,..., and ttop. Because the number of TI-PINt1,t2 is larger than the number of TPNt, the chance of exactly identifying the protein complex from TI-PINt1,t2 is higher than that from TPNt, wheret1 ≤t2 andt,t1,t2=tlow, tlow+1,..., ttop.


### 2.4. Identification Method

In this section, we introduce the concepts of the joint colocalization condition, the joint coexpression condition, the GO-based functional similarity between proteins, and the expanding cluster condition and then present our identification method.


#### 2.4.1. Joint Colocalization Condition

To accomplish a specific biological process, some proteins physically interact with each other to form a protein complex at the same subcellular localization. Huh et al. [37] investigated the distribution of yeast proteins at different subcellular localization. Without loss of generality, we use yeast protein subcellular localization to illustrate the construction of joint colocalization condition of a protein complex. Yeast protein subcellular localization is classified into 22 categories shown in Table 1 [37]. Based on the subcellular localization category, a 22-dimension 0-1 vector is defined to represent the protein subcellular localization indicating the appearance of a protein during a whole cell cycle.Table 1
Subcellular localization category for yeast subcellular compartment.
No. subcellular localization category No. subcellular localization category No. subcellular localization category No. subcellular localization category 1 mitochondrion 7 ER 13 late Golgi 19 early Golgi 2 vacuole 8 nuclear periphery 14 peroxisome 20 lipid particle 3 spindle pole 9 endosome 15 actin 21 nucleus 4 cell periphery 10 bud neck 16 nucleolus 22 bud 5 punctate composite 11 microtubule 17 cytoplasm 6 vacuolar membrane 12 Golgi 18 ER to Golgi Note. No. is the subcellular localization category number.Given a proteinp, letLV(p) denote the localization vector of the proteinpand LVi(p) denote thei-th element ofLV(p),i=1,…, 22. If the proteinpis once localized at thei-th subcellular localization category in a whole cell cycle, LVi(p)=1, otherwise, LVi(p)=0,i=1,…, 22.Given a setPSofk proteins p1,p2,…,pk and LV(pj),j=1,…,k, letJLV(PS)= JLV1PS,JLV2PS,…,JLV22PS denote the joint localization vector ofPS, where JLVi(PS)= ∧j=1kLVi(pj),i=1,…,22, and “∧” is the logical AND operation on the elements among the localization vectors of proteins inPS. If all proteins inPS perform a specific function at thei-th subcellular localization category, then JLVi(PS)=1, otherwise, JLVi(PS)=0,i=1,…, 22. Obviously,JLV(PS) is also a 22-dimension 0-1 vector.Given a setPS of proteins and itsJLV(PS), letJC(PS)=∑i=122JLVi(PS) denote the joint colocalization count ofPS. Clearly,JC(PS) is the sum of all elements inJLV(PS). IfJC(PS)>0, there exists at least one subcellular localization category where all proteins inPS are jointly colocalized in a whole cell cycle. IfJC(PS)=0, all proteins inPS are not jointly colocalized at any subcellular localization category in a whole cell cycle. We define “JC(PS)>0” as the joint colocalization condition.


#### 2.4.2. Joint Coexpression Condition

There exists a correlation between gene expression level and protein activity [38]. The subunits in a permanent complex are coexpressed [39]. That suggests analyzing gene coexpression can reveal the potential interaction between active proteins to some extent.Given a setGS ofk genes g1,g2,…,gk and the normalized gene expression valuegepi(t) of geneiat time pointt,t=1,…,T,i=1,…,k, we use JGEGS=JGEGSt∣t=1,…,T to denote the joint gene expression profile ofGS, where JGEGS(t)=∏i=1kgepi(t) and “Π” is the multiplication operation on the expression pattern values amongk genes. In essence, we can generate JGEGS(t) by calculating the product of the normalized expression values ofk genes inGS at time pointt,t=1,...,T.To measure the joint coexpression level ofGS, we useJQ(GS)=1/T∑t=1TJGEGS(t) to denote the joint coexpression quantity ofGS. IfJQ(GS)≥γ, all genes inGS are jointly coexpressed, where γ is the given threshold. We define “JQ(GS)≥γ” as the joint coexpression condition.When the temporal interval length isl, we usel+4 successive expression data to analyze the joint coexpression condition. We set a time window, which coversl+4 successive time points, on the normalized expression data. If the current temporal interval is (tlow, ttop), the time window coversl+4 time points including tlow-2, tlow-1, tlow,..., ttop, ttop+1, and ttop+2. If tlow<3, the time window consists of the following time points: 1, 2,..., ttop, ttop+1, and ttop+2. If ttop>T-2, the time window consists of the following time points: tlow-2, tlow-1, tlow,...,T-1, andT.


#### 2.4.3. The GO-Based Functional Similarity between Proteins

Ontology provides well-defined, structured, and computable semantics of domain knowledge [40]. Because of the need for consistent description related to genes and gene products across species, gene ontology GO has been launched by a collaborative effort to build complete ontologies in the biological domain [41]. GO terms include biological process (BP), molecular function (MF), and cellular component (CC). BP is referred to as a biological objective to which the gene or gene product contributes. MF is defined as the biochemical activity of a gene product. And CC is referred to as the place in the cell where a gene product is active [42]. These terms are semantically and hierarchically organized into a directed acyclic graph (DAG).Semantic similarity is a function to measure closeness in meaning between ontological terms [43]. The GO semantic similarity score can be applied to quantify functional similarity between proteins. We compute the GO term based functional similarity simgo(P1,P2) between two proteinsP1 andP2 by formula (7) [44, 45].(7)simgoP1,P2=∑i=1mSimgo1,i,ST2+∑j=1nSimgo2,j,ST1m+nwhereST1=go1,1,go1,2,…,go1,m is a term set annotating proteinP1,ST2=go2,1,go2,2,…,go2,n is a term set annotating proteinP2, andSim(go1,i,ST2) andSim(go2,j,ST1) are computed by formula (8).(8)Simgo,ST=maxj=1ksimgo,gojwherego denotes a GO term,ST=go1,go2,…,gok denotes a set ofk GO terms, andsim(go, goj) is computed by formula (9).(9)simgo1,go2=e-c1l·ec2h-e-c2hec2h+e-c2h·ec3d-e-c3dec3d+e-c3dwherego1 andgo2 are two different GO terms,ldenotes the sum of the lengths of the shortest paths frommica togo1 and frommica togo2,handd represent the depth and the information content ofmica, respectively, and c1=0.2, c2=0.3, c3=30, whilemica is referred to as the maximum informative common ancestor of two termsgo1 andgo2 in a DAG [44].Correspondingly, we use formulas (7)-(9) to calculate the MF term based similarity simmf(P1,P2), the CC term based similarity simcc(P1,P2), and the BP term based similarity simbp(P1,P2) between proteinsP1 andP2, respectively. The values of simmf(P1,P2), simcc(P1,P2), and simbp(P1,P2) range from 0.0 to 1.0. The larger these values are, the more similar proteinsP1 andP2 are. If simmf(P1,P2)≥ω, proteinsP1 andP2 are judged to be similar based on the MF term, whereωis a given threshold. Similarly, if simcc(P1,P2)≥σ and simbp(P1,P2)≥θ, proteinsP1 andP2 are judged to be similar based on the CC term and the BP term, respectively, whereσ andθare given thresholds.


#### 2.4.4. Expanding Cluster Condition

It is well known that members of a protein complex are similar to each other in functionality. In order to use the seed expanding strategy to mine a functional aggregation cluster from a PPI network, we devise an expanding cluster condition to judge whether a protein is functionally similar to a protein cluster (PC). Our method uses the expanding cluster condition to iteratively add the functionally similar proteins into the protein clusterPC to generate candidate protein complexes with functional homogeneity.Given a protein clusterPC and a proteinu, the CC term based minimal similarityCC(PC,u), the MF term based minimal similarityMF(PC,u), and the BP term based minimal similarityBP(PC,u) betweenPC andu are defined by formulas (10), (11), and (12), respectively.(10)CCPC,u=min⁡simccu,v∣au,v≥r,v∈PC(11)MFPC,u=min⁡simmfu,v∣au,v≥r,v∈PC(12)BPPC,u=min⁡simbpu,v∣au,v≥r,v∈PCwherer is a given reliability threshold.To judge whetherCC(PC,u),MF(PC,u), andBP(PC,u) exceed their specified thresholdsσ,ω, andθ, respectively, we define three Boolean variablesbcc,bmf, andbbp as follows:(13)bcc=true,ifCCPC,u≥σfalse,otherwise(14)bmf=true,ifMFPC,u≥ωfalse,otherwise(15)bbp=true,ifBPPC,u≥θfalse,otherwiseIf at least two out of three Boolean variablesbcc,bmf, andbbp are “true” at the same time, the value ofEC(PC,u) in formula (16) will become “true”. This means that the proteinu is similar with the protein clusterPCin at least two aspects. Therefore, the proteinucan be added into the protein clusterPC. We define “EC(PC,u)=true” as the expanding cluster condition.(16)ECPC,u=bcc∧bmf∨bcc∧bbp∨bmf∧bbp


#### 2.4.5. Algorithm

The main idea of our algorithm is to iteratively construct temporal interval PPI network (TI-PIN) from time pointt1 to time pointt2, TI-PINt1,t2 and identify protein complexes from TI-PINt1,t2, 1 ≤t1 ≤t2 ≤T. To construct different temporal interval TI-PINs, our algorithm dynamically constructs TI-PINs in a bottom-up approach as shown in Figure 1. Firstly, the TI-PINs of temporal interval lengthl=1 are constructed. Next, the TI-PINs of temporal interval lengthl=2 are constructed, and so on. In Figure 1, the direction of arrow indicates the order of constructing TI-PINs. To identify a protein cluster, our algorithm initializes a protein cluster by selecting a node not being a member of any identified protein cluster, and successively checks the joint colocalization condition, the joint coexpression condition, and the expanding cluster condition to determine whether to add the adjacent nodes into the protein cluster, and terminates until no nodes around the protein cluster satisfy all three above-mentioned conditions. By repeating the identifying process of a protein cluster, different protein clusters (PCs) are identified one by one from the constructed TI-PINs. We call our algorithm as ICJointLE-DPN (Identifying proteincomplexes with the features of joint colocalization and joint coexpression from Dynamic Protein Networks). Algorithm 1 describes ICJointLE-DPN in detail.Algorithm 1:ICJointLE-DPN.
Input:Reliability-scored PPI data set GW=(V,E,w), N×T gene expression matrix GEN×T. Output:Candidate Protein Complex set CPCs. Begin 1.CPCs←Φ; 2.for  l=1 to Tdo 3.for  t2=T to lstep -1  do 4.t1 = t2 -l+1; 5.   constructTI-PINt1,t2; 6.   agglomerate the jointly co-localized, jointly co-expressed, functionally similar proteins to identify all protein clusters PCs one by one from the constructed TI-PINt1,t2; 7.  CPCs←CPCs∪PCs; 8.end for 9.end for 10. Remove the protein complexes of size 1 in CPCs; 11. Post-processCPCs to ensure that no duplicate protein complexes appear in the CPCs. End.By converting temporal PPI networks TPNs into temporal interval PPI networks TI-PINs, the constructed TI-PINs preserve only interactions lasting over the temporal interval. Besides, the amount of the constructed TI-PINs is more than that of TPNs. So, our constructed TI-PINs can offer more opportunities to accurately identify more protein complexes.Now we analyze the time complexity of ICJointLE-DPN. Consider Algorithm1, ICJointLE-DPN dynamically constructs TI-PINs. ForT time points, ICJointLE-DPN can constructT∙(T+1)/2 TI-PINs. For each constructed TI-PIN, there are at mostN protein nodes, whereN is the total number of protein nodes in the constructed TI-PIN. For each protein node not being a member of any identified protein cluster, ICJointLE-DPN selects this protein node as an initial protein cluster and expands the protein cluster by checkingN-1 other protein nodes. The time complexity of identifying protein complexes from each constructed TI-PIN isO(N∙(N-1)), namely,O(N2). Therefore, the time complexity of ICJointLE-DPN isO(N2∙T∙(T+1)/2)=O((N∙T)2).In the following section, we evaluate our constructed TI-PINs and other dynamic PPI networks and compare our proposed identification method with other competing methods.


## 2.1. Preliminary

Let a graphG=(V,E) represent a static protein-protein interaction network (SPIN), whereV is a set of nodes (proteins) andN=V,E is a set of edges (protein-protein interactions), ande(i,j) denotes the edge between nodesi andj, wherei,j=1, 2, …,N. Let Sppi=(PP,s) denote a set of protein-protein interactions with reliability score, wherePP is a set of interacting protein pairs ands(x,y) denote the reliability score of the interacting protein pair (x,y) inPP. Thus, we useGW=(V,E,w) to denote the graphGweighted by Sppi, where the edge weightw(i,j) is defined as follows:(1)wi,j=si,j,ifi,j∈PP,ei,j∈E1,ifi,j∉PP,ei,j∈Ei,j=1,2,…,N.Furthermore, matrixAN×N is used to represent the reliability score matrix ofGW, where the element ai,j of AN×N is defined as follows:(2)ai,j=wi,j,ifei,j∈E0ifei,j∉Ei,j=1,2,…,N.Ifai,j≥r, we define the edge e(i,j) as ar-reliable link between nodesi andj, wherer is a given reliability threshold and r∈1,2,…,999 [36].LetGEN×T denote the matrix of gene expression ofN proteins acrossT time points. For a genei, let evi,t represent the expression value of genei at timet and gepi=gepit∣t=1,…,T denote the gene expression pattern of genei, where gepi(t)=evi,t-ev_mini/ev_maxi-ev_mini, ev_mini⁡=mint=1T⁡evi,t, and ev_maxi⁡=maxt=1T⁡evi,t,i=1,2,…,N,t=1,…,T.In fact, gepi is composed ofTnormalized gene expression values. The normalized gene expression data can be used to measure the undulating degree above the base level of gene expression during a whole cell cycle.


## 2.2. Temporal PPI Networks

When a protein is involved in a specific biological process, the expression data of the protein-coding gene exhibits the undulation above the base level of the gene expression during the biological process. If the normalized expression value of geneiexceeds a specified threshold at a certain time point, we call that the product of genei is activated at this time point. Let api(t) denote the active state of proteiniat time pointt, if proteini is active, api(t)=1, otherwise, api(t)=0,i=1,...,N, andt=1,...,T. For a given active thresholdφ, api(t) is defined as follows:(3)apit=1,ifgepit≥φ0,ifgepit<φ,i=1,…,N,andt=1,…,T.Obviously, a lower active thresholdφpreserves more gene dynamical information. The best active thresholdφwill be discussed in the section “The effect of active threshold”.In order to model the dynamics of active proteins mentioned above, the dynamical PPI network is introduced. In the following, we discuss how to construct temporal PPI networks (TPNs) by incorporating time-course gene expression data into static PPI network SPIN. LetTPNt =(Vt, Et) denote a temporal PPI network at time pointt, where Vt and Et is the set of proteins and the set of interactions between active proteins at time pointt, respectively,t=1, 2, …,T. We use DAt to represent the reliability score matrix of TPNt, where element dai,jt in DAt is computed as follows:(4)dai,jt=apit×apjt×ai,j,i,j=1,…,N,andt=1,2,…,T


## 2.3. Temporal Interval PPI Networks

A protein complex is corresponding to a subgraph in PPI network. To represent the subgraph of a protein complex which appears in several successive temporal PPI networks, we introduce temporal interval PPI networks (TI-PINs). A temporal interval PPI network (TI-PIN) can be generated by merging several successive temporal PPI networks (TPNs). GivenTPNt =(Vt, Et),t=1,...,T, let TI-PINtlow,ttop and Btlow,ttop denote the temporal interval PPI network and its reliability score matrix from tlow to ttop, respectively, where tlow and ttop are two time points and 1 ≤tlow≤ttop≤T. TI-PINtlow,ttop and element bi,jtlow,ttop in Btlow,ttop are defined as follows:(5)TI-PINtlow,ttop=Vtlow,ttop,Etlow,ttop,Vtlow,ttop=⋂t=tlowttopVt,Etlow,ttop=⋂t=tlowttopEt,1≤tlow≤ttop≤T(6)bi,jtlow,ttop=dai,jt,if1≤tlow=t=ttop≤Tmin⁡bi,jtlow,ttop-1,bi,jtlow+1,ttop,if1≤tlow<ttop≤T,i,j=1,2,…,NObviously, if 1 ≤tlow= t =ttop≤ T, then bi,jtlow,ttop=bi,jt,t=dai,jt, namely, TI-PINt,tis the same as TPNt. If 1 ≤tlow<ttop≤T, thenTI-PINtlow,ttop is newly constructed by TPNt, tlow ≤ t ≤ ttop. Here, letl=ttop-tlow+1 denote the temporal interval length. Figure 1 shows the generation of TI-PINtlow,ttop by merging the successive temporal PPI networks (TPNs) from tlow to ttop. From Figure 1, we can see thatT TPNs can generate T·(T-1)/2 TI-PINs.Figure 1
GeneratingTI-PINtlow,ttopby merging the successive temporal PPI networks TPNs from tlow to ttop. For example,TI-PIN5,9 is generated by merging TPNs from time point 5 to time point 9. TI-PINs in the triangle of red dash lines are generated by TPNs in the rectangle of red dash lines. A TI-PINt1,t2 corresponds to a temporal interval (t1,t2), where 1 ≤t1 ≤t2 ≤T= 12.For given time pointstlow and ttop, and tlow<ttop, if the PPI subgraph Gpc of a protein complex appears in all TPNtlow,TPNtlow+1,…, and TPNttop, then Gpc also appears in all TI-PINt1,t2,t1 ≤t2 andt1,t2=tlow, tlow+1,..., and ttop. Because the number of TI-PINt1,t2 is larger than the number of TPNt, the chance of exactly identifying the protein complex from TI-PINt1,t2 is higher than that from TPNt, wheret1 ≤t2 andt,t1,t2=tlow, tlow+1,..., ttop.


## 2.4. Identification Method

In this section, we introduce the concepts of the joint colocalization condition, the joint coexpression condition, the GO-based functional similarity between proteins, and the expanding cluster condition and then present our identification method.


### 2.4.1. Joint Colocalization Condition

To accomplish a specific biological process, some proteins physically interact with each other to form a protein complex at the same subcellular localization. Huh et al. [37] investigated the distribution of yeast proteins at different subcellular localization. Without loss of generality, we use yeast protein subcellular localization to illustrate the construction of joint colocalization condition of a protein complex. Yeast protein subcellular localization is classified into 22 categories shown in Table 1 [37]. Based on the subcellular localization category, a 22-dimension 0-1 vector is defined to represent the protein subcellular localization indicating the appearance of a protein during a whole cell cycle.Table 1
Subcellular localization category for yeast subcellular compartment.
No. subcellular localization category No. subcellular localization category No. subcellular localization category No. subcellular localization category 1 mitochondrion 7 ER 13 late Golgi 19 early Golgi 2 vacuole 8 nuclear periphery 14 peroxisome 20 lipid particle 3 spindle pole 9 endosome 15 actin 21 nucleus 4 cell periphery 10 bud neck 16 nucleolus 22 bud 5 punctate composite 11 microtubule 17 cytoplasm 6 vacuolar membrane 12 Golgi 18 ER to Golgi Note. No. is the subcellular localization category number.Given a proteinp, letLV(p) denote the localization vector of the proteinpand LVi(p) denote thei-th element ofLV(p),i=1,…, 22. If the proteinpis once localized at thei-th subcellular localization category in a whole cell cycle, LVi(p)=1, otherwise, LVi(p)=0,i=1,…, 22.Given a setPSofk proteins p1,p2,…,pk and LV(pj),j=1,…,k, letJLV(PS)= JLV1PS,JLV2PS,…,JLV22PS denote the joint localization vector ofPS, where JLVi(PS)= ∧j=1kLVi(pj),i=1,…,22, and “∧” is the logical AND operation on the elements among the localization vectors of proteins inPS. If all proteins inPS perform a specific function at thei-th subcellular localization category, then JLVi(PS)=1, otherwise, JLVi(PS)=0,i=1,…, 22. Obviously,JLV(PS) is also a 22-dimension 0-1 vector.Given a setPS of proteins and itsJLV(PS), letJC(PS)=∑i=122JLVi(PS) denote the joint colocalization count ofPS. Clearly,JC(PS) is the sum of all elements inJLV(PS). IfJC(PS)>0, there exists at least one subcellular localization category where all proteins inPS are jointly colocalized in a whole cell cycle. IfJC(PS)=0, all proteins inPS are not jointly colocalized at any subcellular localization category in a whole cell cycle. We define “JC(PS)>0” as the joint colocalization condition.


### 2.4.2. Joint Coexpression Condition

There exists a correlation between gene expression level and protein activity [38]. The subunits in a permanent complex are coexpressed [39]. That suggests analyzing gene coexpression can reveal the potential interaction between active proteins to some extent.Given a setGS ofk genes g1,g2,…,gk and the normalized gene expression valuegepi(t) of geneiat time pointt,t=1,…,T,i=1,…,k, we use JGEGS=JGEGSt∣t=1,…,T to denote the joint gene expression profile ofGS, where JGEGS(t)=∏i=1kgepi(t) and “Π” is the multiplication operation on the expression pattern values amongk genes. In essence, we can generate JGEGS(t) by calculating the product of the normalized expression values ofk genes inGS at time pointt,t=1,...,T.To measure the joint coexpression level ofGS, we useJQ(GS)=1/T∑t=1TJGEGS(t) to denote the joint coexpression quantity ofGS. IfJQ(GS)≥γ, all genes inGS are jointly coexpressed, where γ is the given threshold. We define “JQ(GS)≥γ” as the joint coexpression condition.When the temporal interval length isl, we usel+4 successive expression data to analyze the joint coexpression condition. We set a time window, which coversl+4 successive time points, on the normalized expression data. If the current temporal interval is (tlow, ttop), the time window coversl+4 time points including tlow-2, tlow-1, tlow,..., ttop, ttop+1, and ttop+2. If tlow<3, the time window consists of the following time points: 1, 2,..., ttop, ttop+1, and ttop+2. If ttop>T-2, the time window consists of the following time points: tlow-2, tlow-1, tlow,...,T-1, andT.


### 2.4.3. The GO-Based Functional Similarity between Proteins

Ontology provides well-defined, structured, and computable semantics of domain knowledge [40]. Because of the need for consistent description related to genes and gene products across species, gene ontology GO has been launched by a collaborative effort to build complete ontologies in the biological domain [41]. GO terms include biological process (BP), molecular function (MF), and cellular component (CC). BP is referred to as a biological objective to which the gene or gene product contributes. MF is defined as the biochemical activity of a gene product. And CC is referred to as the place in the cell where a gene product is active [42]. These terms are semantically and hierarchically organized into a directed acyclic graph (DAG).Semantic similarity is a function to measure closeness in meaning between ontological terms [43]. The GO semantic similarity score can be applied to quantify functional similarity between proteins. We compute the GO term based functional similarity simgo(P1,P2) between two proteinsP1 andP2 by formula (7) [44, 45].(7)simgoP1,P2=∑i=1mSimgo1,i,ST2+∑j=1nSimgo2,j,ST1m+nwhereST1=go1,1,go1,2,…,go1,m is a term set annotating proteinP1,ST2=go2,1,go2,2,…,go2,n is a term set annotating proteinP2, andSim(go1,i,ST2) andSim(go2,j,ST1) are computed by formula (8).(8)Simgo,ST=maxj=1ksimgo,gojwherego denotes a GO term,ST=go1,go2,…,gok denotes a set ofk GO terms, andsim(go, goj) is computed by formula (9).(9)simgo1,go2=e-c1l·ec2h-e-c2hec2h+e-c2h·ec3d-e-c3dec3d+e-c3dwherego1 andgo2 are two different GO terms,ldenotes the sum of the lengths of the shortest paths frommica togo1 and frommica togo2,handd represent the depth and the information content ofmica, respectively, and c1=0.2, c2=0.3, c3=30, whilemica is referred to as the maximum informative common ancestor of two termsgo1 andgo2 in a DAG [44].Correspondingly, we use formulas (7)-(9) to calculate the MF term based similarity simmf(P1,P2), the CC term based similarity simcc(P1,P2), and the BP term based similarity simbp(P1,P2) between proteinsP1 andP2, respectively. The values of simmf(P1,P2), simcc(P1,P2), and simbp(P1,P2) range from 0.0 to 1.0. The larger these values are, the more similar proteinsP1 andP2 are. If simmf(P1,P2)≥ω, proteinsP1 andP2 are judged to be similar based on the MF term, whereωis a given threshold. Similarly, if simcc(P1,P2)≥σ and simbp(P1,P2)≥θ, proteinsP1 andP2 are judged to be similar based on the CC term and the BP term, respectively, whereσ andθare given thresholds.


### 2.4.4. Expanding Cluster Condition

It is well known that members of a protein complex are similar to each other in functionality. In order to use the seed expanding strategy to mine a functional aggregation cluster from a PPI network, we devise an expanding cluster condition to judge whether a protein is functionally similar to a protein cluster (PC). Our method uses the expanding cluster condition to iteratively add the functionally similar proteins into the protein clusterPC to generate candidate protein complexes with functional homogeneity.Given a protein clusterPC and a proteinu, the CC term based minimal similarityCC(PC,u), the MF term based minimal similarityMF(PC,u), and the BP term based minimal similarityBP(PC,u) betweenPC andu are defined by formulas (10), (11), and (12), respectively.(10)CCPC,u=min⁡simccu,v∣au,v≥r,v∈PC(11)MFPC,u=min⁡simmfu,v∣au,v≥r,v∈PC(12)BPPC,u=min⁡simbpu,v∣au,v≥r,v∈PCwherer is a given reliability threshold.To judge whetherCC(PC,u),MF(PC,u), andBP(PC,u) exceed their specified thresholdsσ,ω, andθ, respectively, we define three Boolean variablesbcc,bmf, andbbp as follows:(13)bcc=true,ifCCPC,u≥σfalse,otherwise(14)bmf=true,ifMFPC,u≥ωfalse,otherwise(15)bbp=true,ifBPPC,u≥θfalse,otherwiseIf at least two out of three Boolean variablesbcc,bmf, andbbp are “true” at the same time, the value ofEC(PC,u) in formula (16) will become “true”. This means that the proteinu is similar with the protein clusterPCin at least two aspects. Therefore, the proteinucan be added into the protein clusterPC. We define “EC(PC,u)=true” as the expanding cluster condition.(16)ECPC,u=bcc∧bmf∨bcc∧bbp∨bmf∧bbp


### 2.4.5. Algorithm

The main idea of our algorithm is to iteratively construct temporal interval PPI network (TI-PIN) from time pointt1 to time pointt2, TI-PINt1,t2 and identify protein complexes from TI-PINt1,t2, 1 ≤t1 ≤t2 ≤T. To construct different temporal interval TI-PINs, our algorithm dynamically constructs TI-PINs in a bottom-up approach as shown in Figure 1. Firstly, the TI-PINs of temporal interval lengthl=1 are constructed. Next, the TI-PINs of temporal interval lengthl=2 are constructed, and so on. In Figure 1, the direction of arrow indicates the order of constructing TI-PINs. To identify a protein cluster, our algorithm initializes a protein cluster by selecting a node not being a member of any identified protein cluster, and successively checks the joint colocalization condition, the joint coexpression condition, and the expanding cluster condition to determine whether to add the adjacent nodes into the protein cluster, and terminates until no nodes around the protein cluster satisfy all three above-mentioned conditions. By repeating the identifying process of a protein cluster, different protein clusters (PCs) are identified one by one from the constructed TI-PINs. We call our algorithm as ICJointLE-DPN (Identifying proteincomplexes with the features of joint colocalization and joint coexpression from Dynamic Protein Networks). Algorithm 1 describes ICJointLE-DPN in detail.Algorithm 1:ICJointLE-DPN.
Input:Reliability-scored PPI data set GW=(V,E,w), N×T gene expression matrix GEN×T. Output:Candidate Protein Complex set CPCs. Begin 1.CPCs←Φ; 2.for  l=1 to Tdo 3.for  t2=T to lstep -1  do 4.t1 = t2 -l+1; 5.   constructTI-PINt1,t2; 6.   agglomerate the jointly co-localized, jointly co-expressed, functionally similar proteins to identify all protein clusters PCs one by one from the constructed TI-PINt1,t2; 7.  CPCs←CPCs∪PCs; 8.end for 9.end for 10. Remove the protein complexes of size 1 in CPCs; 11. Post-processCPCs to ensure that no duplicate protein complexes appear in the CPCs. End.By converting temporal PPI networks TPNs into temporal interval PPI networks TI-PINs, the constructed TI-PINs preserve only interactions lasting over the temporal interval. Besides, the amount of the constructed TI-PINs is more than that of TPNs. So, our constructed TI-PINs can offer more opportunities to accurately identify more protein complexes.Now we analyze the time complexity of ICJointLE-DPN. Consider Algorithm1, ICJointLE-DPN dynamically constructs TI-PINs. ForT time points, ICJointLE-DPN can constructT∙(T+1)/2 TI-PINs. For each constructed TI-PIN, there are at mostN protein nodes, whereN is the total number of protein nodes in the constructed TI-PIN. For each protein node not being a member of any identified protein cluster, ICJointLE-DPN selects this protein node as an initial protein cluster and expands the protein cluster by checkingN-1 other protein nodes. The time complexity of identifying protein complexes from each constructed TI-PIN isO(N∙(N-1)), namely,O(N2). Therefore, the time complexity of ICJointLE-DPN isO(N2∙T∙(T+1)/2)=O((N∙T)2).In the following section, we evaluate our constructed TI-PINs and other dynamic PPI networks and compare our proposed identification method with other competing methods.


## 2.4.1. Joint Colocalization Condition

To accomplish a specific biological process, some proteins physically interact with each other to form a protein complex at the same subcellular localization. Huh et al. [37] investigated the distribution of yeast proteins at different subcellular localization. Without loss of generality, we use yeast protein subcellular localization to illustrate the construction of joint colocalization condition of a protein complex. Yeast protein subcellular localization is classified into 22 categories shown in Table 1 [37]. Based on the subcellular localization category, a 22-dimension 0-1 vector is defined to represent the protein subcellular localization indicating the appearance of a protein during a whole cell cycle.Table 1
Subcellular localization category for yeast subcellular compartment.
No. subcellular localization category No. subcellular localization category No. subcellular localization category No. subcellular localization category 1 mitochondrion 7 ER 13 late Golgi 19 early Golgi 2 vacuole 8 nuclear periphery 14 peroxisome 20 lipid particle 3 spindle pole 9 endosome 15 actin 21 nucleus 4 cell periphery 10 bud neck 16 nucleolus 22 bud 5 punctate composite 11 microtubule 17 cytoplasm 6 vacuolar membrane 12 Golgi 18 ER to Golgi Note. No. is the subcellular localization category number.Given a proteinp, letLV(p) denote the localization vector of the proteinpand LVi(p) denote thei-th element ofLV(p),i=1,…, 22. If the proteinpis once localized at thei-th subcellular localization category in a whole cell cycle, LVi(p)=1, otherwise, LVi(p)=0,i=1,…, 22.Given a setPSofk proteins p1,p2,…,pk and LV(pj),j=1,…,k, letJLV(PS)= JLV1PS,JLV2PS,…,JLV22PS denote the joint localization vector ofPS, where JLVi(PS)= ∧j=1kLVi(pj),i=1,…,22, and “∧” is the logical AND operation on the elements among the localization vectors of proteins inPS. If all proteins inPS perform a specific function at thei-th subcellular localization category, then JLVi(PS)=1, otherwise, JLVi(PS)=0,i=1,…, 22. Obviously,JLV(PS) is also a 22-dimension 0-1 vector.Given a setPS of proteins and itsJLV(PS), letJC(PS)=∑i=122JLVi(PS) denote the joint colocalization count ofPS. Clearly,JC(PS) is the sum of all elements inJLV(PS). IfJC(PS)>0, there exists at least one subcellular localization category where all proteins inPS are jointly colocalized in a whole cell cycle. IfJC(PS)=0, all proteins inPS are not jointly colocalized at any subcellular localization category in a whole cell cycle. We define “JC(PS)>0” as the joint colocalization condition.


## 2.4.2. Joint Coexpression Condition

There exists a correlation between gene expression level and protein activity [38]. The subunits in a permanent complex are coexpressed [39]. That suggests analyzing gene coexpression can reveal the potential interaction between active proteins to some extent.Given a setGS ofk genes g1,g2,…,gk and the normalized gene expression valuegepi(t) of geneiat time pointt,t=1,…,T,i=1,…,k, we use JGEGS=JGEGSt∣t=1,…,T to denote the joint gene expression profile ofGS, where JGEGS(t)=∏i=1kgepi(t) and “Π” is the multiplication operation on the expression pattern values amongk genes. In essence, we can generate JGEGS(t) by calculating the product of the normalized expression values ofk genes inGS at time pointt,t=1,...,T.To measure the joint coexpression level ofGS, we useJQ(GS)=1/T∑t=1TJGEGS(t) to denote the joint coexpression quantity ofGS. IfJQ(GS)≥γ, all genes inGS are jointly coexpressed, where γ is the given threshold. We define “JQ(GS)≥γ” as the joint coexpression condition.When the temporal interval length isl, we usel+4 successive expression data to analyze the joint coexpression condition. We set a time window, which coversl+4 successive time points, on the normalized expression data. If the current temporal interval is (tlow, ttop), the time window coversl+4 time points including tlow-2, tlow-1, tlow,..., ttop, ttop+1, and ttop+2. If tlow<3, the time window consists of the following time points: 1, 2,..., ttop, ttop+1, and ttop+2. If ttop>T-2, the time window consists of the following time points: tlow-2, tlow-1, tlow,...,T-1, andT.


## 2.4.3. The GO-Based Functional Similarity between Proteins

Ontology provides well-defined, structured, and computable semantics of domain knowledge [40]. Because of the need for consistent description related to genes and gene products across species, gene ontology GO has been launched by a collaborative effort to build complete ontologies in the biological domain [41]. GO terms include biological process (BP), molecular function (MF), and cellular component (CC). BP is referred to as a biological objective to which the gene or gene product contributes. MF is defined as the biochemical activity of a gene product. And CC is referred to as the place in the cell where a gene product is active [42]. These terms are semantically and hierarchically organized into a directed acyclic graph (DAG).Semantic similarity is a function to measure closeness in meaning between ontological terms [43]. The GO semantic similarity score can be applied to quantify functional similarity between proteins. We compute the GO term based functional similarity simgo(P1,P2) between two proteinsP1 andP2 by formula (7) [44, 45].(7)simgoP1,P2=∑i=1mSimgo1,i,ST2+∑j=1nSimgo2,j,ST1m+nwhereST1=go1,1,go1,2,…,go1,m is a term set annotating proteinP1,ST2=go2,1,go2,2,…,go2,n is a term set annotating proteinP2, andSim(go1,i,ST2) andSim(go2,j,ST1) are computed by formula (8).(8)Simgo,ST=maxj=1ksimgo,gojwherego denotes a GO term,ST=go1,go2,…,gok denotes a set ofk GO terms, andsim(go, goj) is computed by formula (9).(9)simgo1,go2=e-c1l·ec2h-e-c2hec2h+e-c2h·ec3d-e-c3dec3d+e-c3dwherego1 andgo2 are two different GO terms,ldenotes the sum of the lengths of the shortest paths frommica togo1 and frommica togo2,handd represent the depth and the information content ofmica, respectively, and c1=0.2, c2=0.3, c3=30, whilemica is referred to as the maximum informative common ancestor of two termsgo1 andgo2 in a DAG [44].Correspondingly, we use formulas (7)-(9) to calculate the MF term based similarity simmf(P1,P2), the CC term based similarity simcc(P1,P2), and the BP term based similarity simbp(P1,P2) between proteinsP1 andP2, respectively. The values of simmf(P1,P2), simcc(P1,P2), and simbp(P1,P2) range from 0.0 to 1.0. The larger these values are, the more similar proteinsP1 andP2 are. If simmf(P1,P2)≥ω, proteinsP1 andP2 are judged to be similar based on the MF term, whereωis a given threshold. Similarly, if simcc(P1,P2)≥σ and simbp(P1,P2)≥θ, proteinsP1 andP2 are judged to be similar based on the CC term and the BP term, respectively, whereσ andθare given thresholds.


## 2.4.4. Expanding Cluster Condition

It is well known that members of a protein complex are similar to each other in functionality. In order to use the seed expanding strategy to mine a functional aggregation cluster from a PPI network, we devise an expanding cluster condition to judge whether a protein is functionally similar to a protein cluster (PC). Our method uses the expanding cluster condition to iteratively add the functionally similar proteins into the protein clusterPC to generate candidate protein complexes with functional homogeneity.Given a protein clusterPC and a proteinu, the CC term based minimal similarityCC(PC,u), the MF term based minimal similarityMF(PC,u), and the BP term based minimal similarityBP(PC,u) betweenPC andu are defined by formulas (10), (11), and (12), respectively.(10)CCPC,u=min⁡simccu,v∣au,v≥r,v∈PC(11)MFPC,u=min⁡simmfu,v∣au,v≥r,v∈PC(12)BPPC,u=min⁡simbpu,v∣au,v≥r,v∈PCwherer is a given reliability threshold.To judge whetherCC(PC,u),MF(PC,u), andBP(PC,u) exceed their specified thresholdsσ,ω, andθ, respectively, we define three Boolean variablesbcc,bmf, andbbp as follows:(13)bcc=true,ifCCPC,u≥σfalse,otherwise(14)bmf=true,ifMFPC,u≥ωfalse,otherwise(15)bbp=true,ifBPPC,u≥θfalse,otherwiseIf at least two out of three Boolean variablesbcc,bmf, andbbp are “true” at the same time, the value ofEC(PC,u) in formula (16) will become “true”. This means that the proteinu is similar with the protein clusterPCin at least two aspects. Therefore, the proteinucan be added into the protein clusterPC. We define “EC(PC,u)=true” as the expanding cluster condition.(16)ECPC,u=bcc∧bmf∨bcc∧bbp∨bmf∧bbp


## 2.4.5. Algorithm

The main idea of our algorithm is to iteratively construct temporal interval PPI network (TI-PIN) from time pointt1 to time pointt2, TI-PINt1,t2 and identify protein complexes from TI-PINt1,t2, 1 ≤t1 ≤t2 ≤T. To construct different temporal interval TI-PINs, our algorithm dynamically constructs TI-PINs in a bottom-up approach as shown in Figure 1. Firstly, the TI-PINs of temporal interval lengthl=1 are constructed. Next, the TI-PINs of temporal interval lengthl=2 are constructed, and so on. In Figure 1, the direction of arrow indicates the order of constructing TI-PINs. To identify a protein cluster, our algorithm initializes a protein cluster by selecting a node not being a member of any identified protein cluster, and successively checks the joint colocalization condition, the joint coexpression condition, and the expanding cluster condition to determine whether to add the adjacent nodes into the protein cluster, and terminates until no nodes around the protein cluster satisfy all three above-mentioned conditions. By repeating the identifying process of a protein cluster, different protein clusters (PCs) are identified one by one from the constructed TI-PINs. We call our algorithm as ICJointLE-DPN (Identifying proteincomplexes with the features of joint colocalization and joint coexpression from Dynamic Protein Networks). Algorithm 1 describes ICJointLE-DPN in detail.Algorithm 1:ICJointLE-DPN.
Input:Reliability-scored PPI data set GW=(V,E,w), N×T gene expression matrix GEN×T. Output:Candidate Protein Complex set CPCs. Begin 1.CPCs←Φ; 2.for  l=1 to Tdo 3.for  t2=T to lstep -1  do 4.t1 = t2 -l+1; 5.   constructTI-PINt1,t2; 6.   agglomerate the jointly co-localized, jointly co-expressed, functionally similar proteins to identify all protein clusters PCs one by one from the constructed TI-PINt1,t2; 7.  CPCs←CPCs∪PCs; 8.end for 9.end for 10. Remove the protein complexes of size 1 in CPCs; 11. Post-processCPCs to ensure that no duplicate protein complexes appear in the CPCs. End.By converting temporal PPI networks TPNs into temporal interval PPI networks TI-PINs, the constructed TI-PINs preserve only interactions lasting over the temporal interval. Besides, the amount of the constructed TI-PINs is more than that of TPNs. So, our constructed TI-PINs can offer more opportunities to accurately identify more protein complexes.Now we analyze the time complexity of ICJointLE-DPN. Consider Algorithm1, ICJointLE-DPN dynamically constructs TI-PINs. ForT time points, ICJointLE-DPN can constructT∙(T+1)/2 TI-PINs. For each constructed TI-PIN, there are at mostN protein nodes, whereN is the total number of protein nodes in the constructed TI-PIN. For each protein node not being a member of any identified protein cluster, ICJointLE-DPN selects this protein node as an initial protein cluster and expands the protein cluster by checkingN-1 other protein nodes. The time complexity of identifying protein complexes from each constructed TI-PIN isO(N∙(N-1)), namely,O(N2). Therefore, the time complexity of ICJointLE-DPN isO(N2∙T∙(T+1)/2)=O((N∙T)2).In the following section, we evaluate our constructed TI-PINs and other dynamic PPI networks and compare our proposed identification method with other competing methods.


## 3. Experiments and Results

In this section, we first introduce the testing data sets and the benchmark data. Subsequently, we describe metrics evaluating the quality of identified protein complexes. Finally, we present the experimental results and comparative analysis.


### 3.1. Experimental Dataset

To construct temporal interval PPI networks (TI-PINs), we selected three yeast PPI data sets. The first one, downloaded from the STRING database V10 version [36], consists of 6418 proteins and 939998 interactions with reliability score. The second one containing 5811 proteins and 256516 interactions was downloaded from the BioGrid database 3.4.128 version [46]. The last one, containing 5022 proteins and 22381 interactions, was downloaded from the DIP database with the release date 2015/07/01[47]. According to formula (1), we used reliability scores annotating interactions in STRING to score the interactions shared in STRING and BioGrid/DIP.Furthermore, we selected two yeast gene expression data sets to conduct the comparative experiment. One data set, GSE3431 [48], is extracted from the file GDS2267_full.soft which was acquired with access number GDS2267 on http://www.ncbi.nlm.nih.gov/sites/GDSbrowser. GSE3431 is an expression profile of yeast by Affymetrix Yeast Genome S98 Array over three successive metabolic cycles. GSE3431 contains 36 raw gene expression data gathered at 25-minute interval. LetT1,T2,..., andT36 denote the 36 successive time points, thus we can calculate the average valueave_gei of three raw gene expression data at three time points Ti, Ti+12, and Ti+24 for each gene in GSE3431. The average valueave_gei is used to represent thei-th gene expression value,i=1, 2,..., 12. We used the 12 gene expression values for each gene to analyze joint coexpression condition and construct TI-PINs for GSE3431. Another data set GSE4987 [49] is composed of gene expression data of wild type W303a cells, which are sampled at 5-minute interval over two hours per cell cycle across two cell cycles. GSE4987 contains 50 raw gene expression data across two cell cycles, where there are 25 raw gene expression data per cell cycle. Similarly, we calculated 25 gene expression values for each gene in GSE4987, and used the 25 gene expression values for each gene to analyze joint coexpression condition and construct TI-PINs for GSE4987.In addition, we used the yeast-related protein localization data [37], downloaded from http://yeastgfp.yeastgenome.org, to analyze joint colocalization condition. The GO term annotations of the yeast-related proteins were downloaded from http://www.ncbi.nlm.nih.gov/geo/query/acc.cgi?acc=GSE3431. We used the GO term annotations to calculate the GO term based functional similarity between proteins. The known complexes set CYC2008 containing 408 manually curated heterometric protein complexes was downloaded from http://wodaklab.org/cyc2008/ [50].


### 3.2. Evaluation Metrics

Comparing identified complexes with known ones is a commonly used evaluation. There are several statistical matching-based metrics, which evaluate the quality of identified complexes and the performance of identification methods. The biological relevance-based metrics, which are independent of the known complexes, are used to evaluate the biological significance of identified complexes.


#### 3.2.1. The Statistical Matching-Based Metrics

If an identified complex and a known complex overlap each other, there exist common proteins between them. The overlapping score between an identified complexicand a known complexkc,OS(ic,kc), is calculated as follows [4]:(17)OSic,kc=Vic∩Vkc2Vic×Vkcwhere Vic and Vkc are the protein set ofic and the protein set ofkc respectively. IfOS(ic,kc)≥λ,icis matched withkc, where the thresholdλ is usually set to 0.2 [4, 11]. Particularly,OS(ic,kc)=1 indicates thatic is completely matched withkc.LetIC be the set of complexes identified by computational method andKC be the set of the known complexes. Then letMicrepresent the number of identified complexes which matches at least one known complex inKC, andMkcdenote the number of known complexes which matches at least one identified complex inIC.Mic andMkc are defined as follows [4]:(18)Mic=ic∣ic∈IC,∃kc∈KC,OSic,kc≥λ(19)Mkc=kc∣kc∈KC,∃ic∈IC,OSic,kc≥λWe evaluate the quality of identified complexes by precision (prec), recall(rec), and f-measure (fm) [51].(20)prec=MicIC(21)rec=MkcKC(22)fm=2×prec×recprec+recFrac is defined as the fraction of matched complexes, which measures the percentage of known complexes matched with identified complexes [5]. In fact,Frac is equivalent torec.The maximum matching ratio (MMR) [5] is based on a maximal one-to-one mapping between identified complex and known complex, and it measures accuracy that the identified complexes can represent the known complexes.MMR is calculated as follows [5]:(23)MMR=∑i=1nmax⁡OSkci,icj∣j=1,…,mnwhere kci is thei-th known complex,i=1,...,n, andn= KC, and icj is thej-th identified complex,j=1,...,m andm= IC.Letni be the number of proteins in thei-th known complex and tij be the number of common proteins between thei-th known complex and thej-th identified complex,i=1,…,n, andj=1,…,m. Sensitivity (Sn), positive predictive value (PPV), and geometric mean (Acc) ofSn andPPV[51] are used to assess the accuracy of identification methods.Sn,PPV, andAcc are computed by formulas (24)-(26).(24)Sn=∑i=1nmax⁡tij∣j=1,2,…,m∑i=1nni(25)PPV=∑j=1mmax⁡tij∣i=1,2,…,n∑i=1n∑j=1mtij(26)Acc=Sn×PPVAs a result, the performance of identification method is evaluated by the comprehensive scoreFAM, which is calculated by formula (27) [5].(27)FAM=Frac+Acc+MMRObviously,FAM is a metric measuring statistical match and is mainly used to statistically evaluate the identification accuracy.Let #PMbe the number of identified complexes that match with known complexes exactly. In fact, #PM is a metric for evaluating the degree of exact match between the identified complexes and known complexes.In the following, we will illustrate how to use both #PM andFAM to comprehensively compare the quality of two sets of identified complexes via analyzing the relative performance of these two sets of identified complexes.For two sets of identified complexes with metrics #PM andFAM,S1 with #PM1 andFAM1 andS2 with #PM2 andFAM2, letG1,2 denote the geometric mean of the relative performances ofS1 andS2, andG1,2 is calculated as follows:(28)G1,2=#PM1#PM2×FAM1FAM2=#PM1×FAM1#PM2×FAM2IfG1,2> 1, then the quality ofS1 will be superior to that ofS2 in terms of the product of #PM andFAM; otherwise, the quality ofS2 will be superior to that ofS1 in terms of the product of #PM andFAM. Hence, whether the quality of a set of identified complexes is superior to that of another set of identified complexes can be judged in terms of the product of #PM andFAM. In essence, we treat the product of #PM andFAMas a comprehensive score of exact match and statistical match. So, in our experiments, we chose the product of #PM andFAM, #PM×FAM, as the major metric to comprehensively evaluate the quality of identified complexes.


#### 3.2.2. The Biological Relevance-Based Metrics

We noticed that the known complexes are generally incomplete [52]. Even though an identified complex does not match with any known complex, it may be an uncharacterized but valid complex [5]. A protein complex tends to be responsible for a specific biological process or molecular function [53]. Hence, it is necessary for evaluating biological relevance to analyze the over-expression of an identified protein complex.The GO term based over-expression analysis for biological process and molecular function can be used to reveal functional homogeneity of proteins in a complex to some extent [5]. For a PPI network containingN proteins, we useK to denote the total number of the termX-annotated proteins in the PPI network. For a given complex containing ns proteins, thep-valueof this complex is defined as the probability that the number of termX-annotated proteins in a protein set of size ns is not less than ks, where ks is the number of the termX-annotated proteins in this complex [54]. Thep-value is computed as follows [54]:(29)p-value=1-∑i=0ks-1N-Kns-iKiNns=∑i=ksnsN-Kns-iKiNnsWe used the open source software GO::TermFinder [55] to calculate thep-value of an identified complex.Ifp-value<ψ, we call that the termX-annotated proteins enrich the complex atψ-level [54], whereψis a given threshold. If the termX-annotated proteins enrich a complex at the level ofψ=0.01 [54], this complex will has significantly biological function and be called significant complex [5]. The over-expression score of a set of identified protein complexes is defined as the ratio of the number of significant protein complexes to the total number of protein complexes in the set. We can evaluate the biological relevance of a set of identified protein complexes by calculating its over-expression score.


### 3.3. Experimental Results

Firstly, we evaluated the effect of active thresholdφ on the quality of protein complexes identified from temporal PPI networks (TPNs). Secondly, we assessed the protein complexes identified from temporal interval PPI networks (TI-PINs). Finally, we compared our method ICJointLE-DPN with Zhang’s method [33], DPC-NADPIN [34], TS-OCD [31], and DCA [35].


#### 3.3.1. The Effect of Active Threshold

Here we first constructed different temporal PPI networks (TPNs) by combining three yeast PPI data sets (STRING, BioGrid, and DIP) with two yeast gene expression data sets (GSE3431 and GSE4987). And then we evaluated the quality of the complexes identified from these different TPNs. Figure2 shows the variation curves of value #PM×FAM of complexes identified from different constructed TPNs with the changingφ.Figure 2
Plot of value of #PM×FAMof complexes identified from the constructed TPNs by integrating gene expression data into yeast PPI data with respect to value ofφ.(a) Plot of value of #PM×FAMof complexes identified from the constructed TPNs by integrating GSE3431 into STRING, BioGrid, and DIP, respectively, with respect to value ofφ. (b) Plot of value of #PM×FAMof complexes identified from the constructed TPNs by integrating GSE4987 into STRING, BioGrid, and DIP, respectively, with respect to value ofφ.
(a) (b)From Figure2(a) we can see that for GSE3431, the value of #PM×FAM of the complexes identified from the constructed TPNs is the largest whenφ=0.01 for DIP andφ=0.1 for STRING and BioGrid respectively. At the meantime, from Figure 2(b), we can also see that for GSE4987, the value of #PM×FAMis the largest whenφ=0.05 for DIP, and the value of #PM×FAMis the largest whenφ=0.2 for STRING and BioGrid. Hence, in the following experiments, these values ofφ, shown in Table 2, are used to construct different TPNs for different combination of yeast expression data sets and yeast PPI data sets.Table 2
Setting values ofφ for different combination of yeast gene expression data sets and yeast PPI data sets.
Yeast expression data sets Yeast PPI data sets φ GSE3431 STRING 0.1 BioGrid 0.1 DIP 0.01  GSE4987 STRING 0.2 BioGrid 0.2 DIP 0.05


#### 3.3.2. Setting of Parameters for ICJointLE-DPN

In our experiments, we empirically adjusted the value of parametersσ,ω, andθ to enable ICJointLE-DPN to perform well. We adjusted the value of parametersσ,ω, andθfrom 0.1 to 0.9 by increment 0.1 through several experiments respectively, and set these parameters to the appropriate values.Table3 shows the values of four parameters for algorithm ICJointLE-DPN with different combination of yeast gene expression data sets and yeast PPI data sets.Table 3
Value of parametersr, σ, ω, and θ for ICJointLE-DPN.
Yeast expression data sets Yeast PPI data sets r σ ω θ GSE3431 STRING 999 0.7 0.6 0.1 BioGrid 999 0.7 0.6 0.1 DIP 990 0.7 0.1 0.3  GSE4987 STRING 999 0.7 0.6 0.1 BioGrid 999 0.7 0.6 0.1 DIP 990 0.7 0.1 0.3


#### 3.3.3. Evaluating Identified Complexes

To evaluate the quality of complexes identified by our method ICJointLE-DPN, we first constructed TPNs and TI-PINs. And then we executed algorithm ICJointLE-DPN to identify complexes from SPIN, TPNs, and TI-PINs respectively. Finally, we compared the quality of the complexes identified from SPIN, TPNs, and TI-PINs respectively in terms of value of #PM×FAM, which is shown in Table 4.Table 4
Values of #PM×FAM of complexes identified from SPIN, TPNs, and TI-PINs.
Yeast expression data sets Yeast PPI networks #PM×FAM STRING BioGrid DIP GSE3431 SPIN 356.54 337.93 282.01 TPNs 433.68 415.28 347.72 TI-PINs 441.38 423.30 356.69  GSE4987 SPIN 338.49 334.74 277.48 TPNs 424.25 416.00 343.00 TI-PINs 426.60 420.18 345.02As seen in Table4, we can find that for the same yeast PPI data set, the values of #PM×FAM resulting from both TPNs and TI-PINs are apparently larger than that resulting from SPIN. This indicates that identifying protein complexes from dynamic PPI networks can improve the quality of identified complexes. From Table 4, we can also see that the value of #PM×FAMresulting from TI-PINs is larger than that from TPNs. It means that identifying protein complexes from TI-PINs can further enhance the quality of identified complexes. As mentioned in the section “temporal interval PPI networks”, the use of TI-PINs constructed by several successive TPNs can provide more opportunities to accurately identify more protein complexes.To further illustrate the effect of our constructed TI-PINs, we ran our algorithm ICJointLE-DPN to identify complexes from TI-PINs and other existing dynamic PPI networks respectively. The experimental results are shown in Figure3.Figure 3
Comparison of values of #PM×FAMof complexes identified by ICJointLE-DPN from different dynamic PPI networks. (a) GSE3431 and (b) GSE4987 are integrated into STRING, BioGrid, and DIP, respectively, to construct six types of dynamic protein interaction networks.
(a) (b)We can see from Figure3 that no matter which yeast PPI data set is integrated with either GSE3431 or GSE4987 to construct TI-PINs, the value of #PM×FAMof complexes identified by ICJointLE-DPN from the constructed TI-PINs is apparently larger than that from other dynamic PPI networks. Such results may partly be attribute to using the relatively low active thresholdφ. In addition, by preserving continuous interactions, our constructed TI-PINs can indeed offer more opportunities to identify more protein complexes accurately.As a result, our constructed TI-PINs have more contributions to identification of protein complexes than other dynamic PPI networks such as TEPIN, DPIN, NF-APIN, DPPN, and TC-PINs.


#### 3.3.4. Comparing Identification Methods

In order to evaluate the performance of the identification methods, we compared our method ICJointLE-DPN to three other competing methods Zhang’s method [33], DPC-NADPIN [34], TS-OCD [31], and DCA[35]. As described in the section “Expanding cluster condition”, in our method, only those PPIs with reliability score not lower than reliability thresholdr are used to identify protein complexes. For fair comparison, we removed those PPIs with reliability score lower than reliability thresholdr in three yeast PPI data sets before executing four other competing methods. For DPC-NADPIN method, no parameters need to be set. Zhang’s method uses two parametersPre_threshandComplex_threshwhose default values are 0.5 and 0.1. For DCA, we set parameters to the recommended values α=0.6, β=0.55, and γ=1.4. The setting of nine parameters used in TS-OCD method is shown in Table 5.Table 5
Setting parameters for TS-OCD method.
Parameters Repeat_times tau delta T K lambda beta iter rho value 1 0.3 0.3 12 1000 0.0625 16 20 0.000001By analyzing known complexes in CYC2008, we found that the number of the complexes of size two to six exceeds 84% of the total number of known complexes. To evaluate the ability of identifying complexes of size two to six, Table6 shows the distribution of the size of the complexes identified exactly by five methods.Table 6
Distribution of the size of the exactly identified complexes.
Yeast expression data sets Yeast PPI Data sets Methods The number of the exactly identified complexes Total Size 2 3 4 5 6 7 8 9 10 12 14 15 GSE3431 STRING ICJointLE-DPN  112 44 17 7 4 1 3 1 0 1 0 0 190 Zhang’s method  53 19 9 5 2 1 2 0 0 1 0 0 92 DPC-NADPIN  0 18 10 4 0 1 0 0 0 1 0 0 34 TS-OCD  0 5 7 3 1 1 1 0 0 1 1 0 20 DCA  0 4 3 0 0 0 0 0 0 0 0 0 7 BioGrid ICJointLE-DPN  113 42 15 6 4 0 1 2 1 1 0 0 185 Zhang’s method  56 20 10 5 3 1 2 0 0 1 0 0 98 DPC-NADPIN  0 20 11 4 1 1 1 0 0 1 0 0 39 TS-OCD  0 19 7 4 4 2 3 0 0 1 0 1 41 DCA  0 4 3 1 0 0 0 0 0 0 0 0 8 DIP ICJointLE-DPN  111 41 11 4 2 1 1 2 0 1 0 0 174 Zhang’s method  65 17 7 2 1 1 1 0 0 0 0 0 94 DPC-NADPIN  0 11 6 2 1 1 1 1 0 0 0 0 23 TS-OCD  0 4 5 0 1 1 0 0 0 1 0 0 12 DCA  0 3 5 1 0 0 0 0 0 0 0 0 9  GSE4987 STRING ICJointLE-DPN  107 45 17 6 5 0 2 1 1 0 1 0 185 Zhang’s method  52 21 12 4 3 2 2 0 0 0 0 1 97 DPC-NADPIN  0 3 1 2 0 0 0 0 0 0 0 0 6 TS-OCD  0 2 2 4 3 1 2 0 1 0 0 0 15 DCA  0 2 2 1 1 0 0 0 0 0 0 0 6 BioGrid ICJointLE-DPN  111 46 16 4 4 0 1 3 2 0 0 0 187 Zhang’s method  59 22 13 4 3 2 1 0 0 0 0 0 104 DPC-NADPIN  0 4 2 2 0 0 0 0 0 0 0 0 8 TS-OCD  0 16 7 5 5 2 2 0 1 0 1 0 39 DCA  0 2 3 2 1 0 1 0 0 0 0 0 9 DIP ICJointLE-DPN  110 40 13 4 2 1 1 2 1 0 0 0 174 Zhang’s method  69 20 8 3 3 2 1 0 0 0 0 0 106 DPC-NADPIN  0 4 2 0 0 0 0 0 0 0 0 0 6 TS-OCD  0 8 3 2 2 1 0 0 0 0 0 0 16 DCA  0 5 3 2 1 0 0 0 0 0 0 0 11From Table6, we can see that our method ICJointLE-DPN has stronger ability of exactly identifying the complexes of size two to six than other four competing methods. Especially, DPC-NADPIN, TS-OCD, and DCA fail to identify any complexes of size two.To evaluate the overall performance of five competing methods, we reported the statistical matching-based metrics of the identified complexes in Table7.Table 7
Statistical matching-based metrics of the complexes identified by five competing methods.
Yeast expression data sets Yeast PPI data sets Methods #PM fm Frac Acc MMR FAM #PM×FAM GSE3431 STRING ICJointLE-DPN 190 0.71 0.95 0.75 0.75 2.45 465.50 Zhang’s method 92 0.63 0.86 0.80 0.59 2.25 207.00 DPC-NADPIN 34 0.71 0.77 0.71 0.48 1.96 66.64 TS-OCD 20 0.55 0.46 0.68 0.30 1.45 29.00 DCA 7 0.55 0.51 0.57 0.27 1.35 9.45 BioGrid ICJointLE-DPN 185 0.72 0.93 0.80 0.73 2.46 455.10 Zhang’s method 98 0.63 0.85 0.78 0.58 2.21 216.58 DPC-NADPIN 39 0.71 0.75 0.72 0.48 1.94 75.66 TS-OCD 41 0.66 0.65 0.73 0.43 1.81 74.21 DCA 8 0.55 0.51 0.56 0.27 1.34 10.72 DIP ICJointLE-DPN 174 0.69 0.85 0.70 0.68 2.23 388.02 Zhang’s method 94 0.67 0.76 0.71 0.52 1.99 187.06 DPC-NADPIN 23 0.63 0.55 0.67 0.35 1.57 36.11 TS-OCD 12 0.39 0.27 0.54 0.18 1.00 12.00 DCA 9 0.48 0.36 0.55 0.21 1.12 10.08  GSE4987 STRING ICJointLE-DPN 185 0.60 0.95 0.72 0.75 2.42 447.70 Zhang’s method 97 0.64 0.91 0.79 0.62 2.32 225.04 DPC-NADPIN 6 0.52 0.56 0.59 0.30 1.46 8.76 TS-OCD 15 0.55 0.53 0.68 0.34 1.56 23.4 DCA 6 0.61 0.70 0.64 0.37 1.71 10.26 BioGrid ICJointLE-DPN 187 0.67 0.93 0.76 0.74 2.43 454.41 Zhang’s method 104 0.63 0.90 0.78 0.63 2.31 240.24 DPC-NADPIN 8 0.54 0.55 0.60 0.13 1.45 11.6 TS-OCD 39 0.66 0.68 0.74 0.46 1.88 73.32 DCA 9 0.62 0.68 0.65 0.36 1.69 15.17 DIP ICJointLE-DPN 174 0.67 0.86 0.68 0.68 2.22 386.28 Zhang’s method 106 0.67 0.83 0.74 0.58 2.15 227.9 DPC-NADPIN 6 0.44 0.36 0.53 0.21 1.10 6.60 TS-OCD 16 0.41 0.29 0.54 0.20 1.04 16.64 DCA 11 0.58 0.50 0.63 0.29 1.42 15.62From Table7, we can see that our method ICJointLE-DPN outperforms the other four competing methods in terms of#PM,Frac,MMR,FAM, and#PM×FAM. We also see that, concerningfm, ICJointLE-DPN obtains almost all the largest values except for one among five competing methods, and with regard toAcc, ICJointLE-DPN is ranked top two. Overall, our method ICJointLE-DPN can not only identify complexes accurately but also identify more complexes exactly matched with known complexes from TI-PINs.Now we give two examples related to the complexes identified from dynamical PPI networks which are constructed via incorporating GSE3431 into DIP. Figure4 illustrates the matching example between nuclear exosome complex and the complexes identified by five competing methods.Figure 4
The complexes identified by five competing methods. (a) The No. 396 complex identified by TSOCD and the No. 901 complex identified by ICJointLE-DPN both match with nuclear exosome complex exactly. (b) The No. 829 complex is incorrectly identified by Zhang's method by not including the four proteins outside the ellipse. (c) The No. 1929 complex identified by DPC-NADPIN by wrongly including the yellow-colored YNL189W and excluding YHR081W. (d) DCA identified the No. 55 complex wrongly with the inclusion of three yellow-colored proteins.
(a)
TSOCD, ICJointLE-DPN (b)
Zhang’s method (c)
DPC-NADPIN (d)
DCAAs can be seen from Figure4(a), TSOCD and ICJointLE-DPN can identify nuclear exosome complex exactly. Zhang’s method misses four proteins outside the ellipse in Figure 4(b). DPC-NADPIN wrongly identifies the yellow-colored YNL189W and misses YHR081W outside the ellipse in Figure 4(c). DCA wrongly identifies three yellow-colored proteins in Figure 4(d).Similarly, Figure5 shows the matching example between COMA complex and the complexes identified by five competing methods.Figure 5
The complexes identified by five competing methods. (a) The No. 1935 complex identified by ICJointLE-DPN misses YBR211C outside the ellipse. (b) The No. 123 complex identified by TSOCD and the No. 137 complex identified by Zhang's method incorrectly contain the yellow-colored YBR107C and omit YBR211C outside the ellipse. (c) The No. 159 complex identified by DPC-NADPIN wrongly includes the yellow-colored YKL049C and omits YBR211C outside the ellipse. (d) The No. 433 complex identified by DCA wrongly includes the yellow-colored YGR140W.
(a)
ICJointLE-DPN (b)
TSOCD, Zhang’s method (c)
DPC-NADPIN (d)
DCAFrom Figure5, we can see that our method ICJointLE-DPN fails to identify COMA complex exactly due to missing YBR211C outside the ellipse in Figure 5(a). TSOCD and Zhang’s method wrongly identify the yellow-colored YBR107C and miss YBR211C outside the ellipse in Figure 5(b), these two methods are unable to detect COMA complex exactly. Likewise, owing to wrongly identifying the yellow-colored YKL049C and missing YBR211C outside the ellipse in Figure 5(c), DPC-NADPIN fails to find COMA complex exactly. We can also see from Figure 5(d) that DCA is unsuccessful in detecting the COMA complex due to wrongly identifying the yellow-colored YGR140W.To evaluate the functional enrichment of identified complexes, we compared our method ICJointLE-DPN to other four competing methods with respect to biological process (BP) enrichment analysis. For complexes identified by ICJointLE-DPN from different TI-PINs, their raw data of BP enrichment analyses and their results of significant statistics are presented in Supplementary Materials (Availablehere). Table 8 shows the proportion of the complexes that are significantly enriched by BP term-annotated proteins, where #ICis the total number of identified complexes, #SCdenotes the number of identified complexes with significant enrichment.Table 8
Proportion of the complexes enriched significantly by BP term-annotated proteins.
Yeast expression data sets Yeast PPI data sets Methods #IC #SC % of significant (size≤6) % of significant (6<size<20) % of significant (size≥20) GSE3431 STRING ICJointLE-DPN 5137 4873 93.33% 100.00% 100.00% Zhang’s method 1117 1013 88.56% 100.00% 100.00% DPC-NADPIN 6464 6439 98.88% 99.94% 100.00% TS-OCD 1175 1157 97.26% 100.00% 100.00% DCA 1261 1261 100.00% 100.00% 100.00% BioGrid ICJointLE-DPN 4896 4559 90.69% 100.00% 100.00% Zhang’s method 1074 974 88.73% 100.00% 100.00% DPC-NADPIN 5437 5420 99.16% 100.00% 100.00% TS-OCD 1784 1749 96.56% 100.00% 100.00% DCA 1201 1199 98.45% 100.00% 100.00% DIP ICJointLE-DPN 4398 4118 91.42% 100.00% 100.00% Zhang’s method 836 725 85.18% 100.00% 100.00% DPC-NADPIN 3019 3007 99.24% 100.00% 100.00% TS-OCD 439 434 98.50% 100.00% 100.00% DCA 595 595 100.00% 100.00% 100.00%  GSE4987 STRING ICJointLE-DPN 12283 11913 95.34% 99.97% 100.00% Zhang’s method 1863 1712 89.36% 100.00% 100.00% DPC-NADPIN 4509 4498 99.45% 100.00% 100.00% TS-OCD 2302 2266 97.26% 100.00% 100.00% DCA 3212 3204 98.84% 99.94% 100.00% BioGrid ICJointLE-DPN 10558 10100 93.25% 100.00% 100.00% Zhang’s method 1821 1660 88.75% 100.00% 100.00% DPC-NADPIN 3657 3641 99.15% 100.00% 100.00% TS-OCD 3354 3295 97.12% 100.00% 100.00% DCA 2686 2678 98.46% 99.60% 100.00% DIP ICJointLE-DPN 8745 8359 92.86% 100.00% 100.00% Zhang’s method 1343 1177 85.76% 100.00% 100.00% DPC-NADPIN 6464 1668 99.66% 100.00% 100.00% TS-OCD 734 721 97.68% 100.00% 100.00% DCA 1269 1266 99.27% 100.00% 100.00%As seen from Table8, for five competing methods, their identified complexes of size larger than 6 are almost biologically significant except for the four italic cases. From Table 8, we can also see that for the significant enrichment of identified complexes of size not larger than 6, our method performs slightly weaker than DPC-NADPIN, TS-OCD, and DCA but stronger than Zhang’s method.In summary, our proposed identification method overall outperforms other four competing methods in terms of the number of identified complexes exactly matched with known complexes#PM, the fraction of known complexes matched with identified complexesFRAC, maximum matching ratioMMR, comprehensive scoreFAM, and the product of#PMandFAM. Concerning the significant enrichment, five competing methods overall perform well when they identify complexes of size larger than 6; when identifying complexes of size not larger than 6, our proposed method performs slightly weaker than DPC-NADPIN, TS-OCD, and DCA but stronger than Zhang’s method.


## 3.1. Experimental Dataset

To construct temporal interval PPI networks (TI-PINs), we selected three yeast PPI data sets. The first one, downloaded from the STRING database V10 version [36], consists of 6418 proteins and 939998 interactions with reliability score. The second one containing 5811 proteins and 256516 interactions was downloaded from the BioGrid database 3.4.128 version [46]. The last one, containing 5022 proteins and 22381 interactions, was downloaded from the DIP database with the release date 2015/07/01[47]. According to formula (1), we used reliability scores annotating interactions in STRING to score the interactions shared in STRING and BioGrid/DIP.Furthermore, we selected two yeast gene expression data sets to conduct the comparative experiment. One data set, GSE3431 [48], is extracted from the file GDS2267_full.soft which was acquired with access number GDS2267 on http://www.ncbi.nlm.nih.gov/sites/GDSbrowser. GSE3431 is an expression profile of yeast by Affymetrix Yeast Genome S98 Array over three successive metabolic cycles. GSE3431 contains 36 raw gene expression data gathered at 25-minute interval. LetT1,T2,..., andT36 denote the 36 successive time points, thus we can calculate the average valueave_gei of three raw gene expression data at three time points Ti, Ti+12, and Ti+24 for each gene in GSE3431. The average valueave_gei is used to represent thei-th gene expression value,i=1, 2,..., 12. We used the 12 gene expression values for each gene to analyze joint coexpression condition and construct TI-PINs for GSE3431. Another data set GSE4987 [49] is composed of gene expression data of wild type W303a cells, which are sampled at 5-minute interval over two hours per cell cycle across two cell cycles. GSE4987 contains 50 raw gene expression data across two cell cycles, where there are 25 raw gene expression data per cell cycle. Similarly, we calculated 25 gene expression values for each gene in GSE4987, and used the 25 gene expression values for each gene to analyze joint coexpression condition and construct TI-PINs for GSE4987.In addition, we used the yeast-related protein localization data [37], downloaded from http://yeastgfp.yeastgenome.org, to analyze joint colocalization condition. The GO term annotations of the yeast-related proteins were downloaded from http://www.ncbi.nlm.nih.gov/geo/query/acc.cgi?acc=GSE3431. We used the GO term annotations to calculate the GO term based functional similarity between proteins. The known complexes set CYC2008 containing 408 manually curated heterometric protein complexes was downloaded from http://wodaklab.org/cyc2008/ [50].


## 3.2. Evaluation Metrics

Comparing identified complexes with known ones is a commonly used evaluation. There are several statistical matching-based metrics, which evaluate the quality of identified complexes and the performance of identification methods. The biological relevance-based metrics, which are independent of the known complexes, are used to evaluate the biological significance of identified complexes.


### 3.2.1. The Statistical Matching-Based Metrics

If an identified complex and a known complex overlap each other, there exist common proteins between them. The overlapping score between an identified complexicand a known complexkc,OS(ic,kc), is calculated as follows [4]:(17)OSic,kc=Vic∩Vkc2Vic×Vkcwhere Vic and Vkc are the protein set ofic and the protein set ofkc respectively. IfOS(ic,kc)≥λ,icis matched withkc, where the thresholdλ is usually set to 0.2 [4, 11]. Particularly,OS(ic,kc)=1 indicates thatic is completely matched withkc.LetIC be the set of complexes identified by computational method andKC be the set of the known complexes. Then letMicrepresent the number of identified complexes which matches at least one known complex inKC, andMkcdenote the number of known complexes which matches at least one identified complex inIC.Mic andMkc are defined as follows [4]:(18)Mic=ic∣ic∈IC,∃kc∈KC,OSic,kc≥λ(19)Mkc=kc∣kc∈KC,∃ic∈IC,OSic,kc≥λWe evaluate the quality of identified complexes by precision (prec), recall(rec), and f-measure (fm) [51].(20)prec=MicIC(21)rec=MkcKC(22)fm=2×prec×recprec+recFrac is defined as the fraction of matched complexes, which measures the percentage of known complexes matched with identified complexes [5]. In fact,Frac is equivalent torec.The maximum matching ratio (MMR) [5] is based on a maximal one-to-one mapping between identified complex and known complex, and it measures accuracy that the identified complexes can represent the known complexes.MMR is calculated as follows [5]:(23)MMR=∑i=1nmax⁡OSkci,icj∣j=1,…,mnwhere kci is thei-th known complex,i=1,...,n, andn= KC, and icj is thej-th identified complex,j=1,...,m andm= IC.Letni be the number of proteins in thei-th known complex and tij be the number of common proteins between thei-th known complex and thej-th identified complex,i=1,…,n, andj=1,…,m. Sensitivity (Sn), positive predictive value (PPV), and geometric mean (Acc) ofSn andPPV[51] are used to assess the accuracy of identification methods.Sn,PPV, andAcc are computed by formulas (24)-(26).(24)Sn=∑i=1nmax⁡tij∣j=1,2,…,m∑i=1nni(25)PPV=∑j=1mmax⁡tij∣i=1,2,…,n∑i=1n∑j=1mtij(26)Acc=Sn×PPVAs a result, the performance of identification method is evaluated by the comprehensive scoreFAM, which is calculated by formula (27) [5].(27)FAM=Frac+Acc+MMRObviously,FAM is a metric measuring statistical match and is mainly used to statistically evaluate the identification accuracy.Let #PMbe the number of identified complexes that match with known complexes exactly. In fact, #PM is a metric for evaluating the degree of exact match between the identified complexes and known complexes.In the following, we will illustrate how to use both #PM andFAM to comprehensively compare the quality of two sets of identified complexes via analyzing the relative performance of these two sets of identified complexes.For two sets of identified complexes with metrics #PM andFAM,S1 with #PM1 andFAM1 andS2 with #PM2 andFAM2, letG1,2 denote the geometric mean of the relative performances ofS1 andS2, andG1,2 is calculated as follows:(28)G1,2=#PM1#PM2×FAM1FAM2=#PM1×FAM1#PM2×FAM2IfG1,2> 1, then the quality ofS1 will be superior to that ofS2 in terms of the product of #PM andFAM; otherwise, the quality ofS2 will be superior to that ofS1 in terms of the product of #PM andFAM. Hence, whether the quality of a set of identified complexes is superior to that of another set of identified complexes can be judged in terms of the product of #PM andFAM. In essence, we treat the product of #PM andFAMas a comprehensive score of exact match and statistical match. So, in our experiments, we chose the product of #PM andFAM, #PM×FAM, as the major metric to comprehensively evaluate the quality of identified complexes.


### 3.2.2. The Biological Relevance-Based Metrics

We noticed that the known complexes are generally incomplete [52]. Even though an identified complex does not match with any known complex, it may be an uncharacterized but valid complex [5]. A protein complex tends to be responsible for a specific biological process or molecular function [53]. Hence, it is necessary for evaluating biological relevance to analyze the over-expression of an identified protein complex.The GO term based over-expression analysis for biological process and molecular function can be used to reveal functional homogeneity of proteins in a complex to some extent [5]. For a PPI network containingN proteins, we useK to denote the total number of the termX-annotated proteins in the PPI network. For a given complex containing ns proteins, thep-valueof this complex is defined as the probability that the number of termX-annotated proteins in a protein set of size ns is not less than ks, where ks is the number of the termX-annotated proteins in this complex [54]. Thep-value is computed as follows [54]:(29)p-value=1-∑i=0ks-1N-Kns-iKiNns=∑i=ksnsN-Kns-iKiNnsWe used the open source software GO::TermFinder [55] to calculate thep-value of an identified complex.Ifp-value<ψ, we call that the termX-annotated proteins enrich the complex atψ-level [54], whereψis a given threshold. If the termX-annotated proteins enrich a complex at the level ofψ=0.01 [54], this complex will has significantly biological function and be called significant complex [5]. The over-expression score of a set of identified protein complexes is defined as the ratio of the number of significant protein complexes to the total number of protein complexes in the set. We can evaluate the biological relevance of a set of identified protein complexes by calculating its over-expression score.


## 3.2.1. The Statistical Matching-Based Metrics

If an identified complex and a known complex overlap each other, there exist common proteins between them. The overlapping score between an identified complexicand a known complexkc,OS(ic,kc), is calculated as follows [4]:(17)OSic,kc=Vic∩Vkc2Vic×Vkcwhere Vic and Vkc are the protein set ofic and the protein set ofkc respectively. IfOS(ic,kc)≥λ,icis matched withkc, where the thresholdλ is usually set to 0.2 [4, 11]. Particularly,OS(ic,kc)=1 indicates thatic is completely matched withkc.LetIC be the set of complexes identified by computational method andKC be the set of the known complexes. Then letMicrepresent the number of identified complexes which matches at least one known complex inKC, andMkcdenote the number of known complexes which matches at least one identified complex inIC.Mic andMkc are defined as follows [4]:(18)Mic=ic∣ic∈IC,∃kc∈KC,OSic,kc≥λ(19)Mkc=kc∣kc∈KC,∃ic∈IC,OSic,kc≥λWe evaluate the quality of identified complexes by precision (prec), recall(rec), and f-measure (fm) [51].(20)prec=MicIC(21)rec=MkcKC(22)fm=2×prec×recprec+recFrac is defined as the fraction of matched complexes, which measures the percentage of known complexes matched with identified complexes [5]. In fact,Frac is equivalent torec.The maximum matching ratio (MMR) [5] is based on a maximal one-to-one mapping between identified complex and known complex, and it measures accuracy that the identified complexes can represent the known complexes.MMR is calculated as follows [5]:(23)MMR=∑i=1nmax⁡OSkci,icj∣j=1,…,mnwhere kci is thei-th known complex,i=1,...,n, andn= KC, and icj is thej-th identified complex,j=1,...,m andm= IC.Letni be the number of proteins in thei-th known complex and tij be the number of common proteins between thei-th known complex and thej-th identified complex,i=1,…,n, andj=1,…,m. Sensitivity (Sn), positive predictive value (PPV), and geometric mean (Acc) ofSn andPPV[51] are used to assess the accuracy of identification methods.Sn,PPV, andAcc are computed by formulas (24)-(26).(24)Sn=∑i=1nmax⁡tij∣j=1,2,…,m∑i=1nni(25)PPV=∑j=1mmax⁡tij∣i=1,2,…,n∑i=1n∑j=1mtij(26)Acc=Sn×PPVAs a result, the performance of identification method is evaluated by the comprehensive scoreFAM, which is calculated by formula (27) [5].(27)FAM=Frac+Acc+MMRObviously,FAM is a metric measuring statistical match and is mainly used to statistically evaluate the identification accuracy.Let #PMbe the number of identified complexes that match with known complexes exactly. In fact, #PM is a metric for evaluating the degree of exact match between the identified complexes and known complexes.In the following, we will illustrate how to use both #PM andFAM to comprehensively compare the quality of two sets of identified complexes via analyzing the relative performance of these two sets of identified complexes.For two sets of identified complexes with metrics #PM andFAM,S1 with #PM1 andFAM1 andS2 with #PM2 andFAM2, letG1,2 denote the geometric mean of the relative performances ofS1 andS2, andG1,2 is calculated as follows:(28)G1,2=#PM1#PM2×FAM1FAM2=#PM1×FAM1#PM2×FAM2IfG1,2> 1, then the quality ofS1 will be superior to that ofS2 in terms of the product of #PM andFAM; otherwise, the quality ofS2 will be superior to that ofS1 in terms of the product of #PM andFAM. Hence, whether the quality of a set of identified complexes is superior to that of another set of identified complexes can be judged in terms of the product of #PM andFAM. In essence, we treat the product of #PM andFAMas a comprehensive score of exact match and statistical match. So, in our experiments, we chose the product of #PM andFAM, #PM×FAM, as the major metric to comprehensively evaluate the quality of identified complexes.


## 3.2.2. The Biological Relevance-Based Metrics

We noticed that the known complexes are generally incomplete [52]. Even though an identified complex does not match with any known complex, it may be an uncharacterized but valid complex [5]. A protein complex tends to be responsible for a specific biological process or molecular function [53]. Hence, it is necessary for evaluating biological relevance to analyze the over-expression of an identified protein complex.The GO term based over-expression analysis for biological process and molecular function can be used to reveal functional homogeneity of proteins in a complex to some extent [5]. For a PPI network containingN proteins, we useK to denote the total number of the termX-annotated proteins in the PPI network. For a given complex containing ns proteins, thep-valueof this complex is defined as the probability that the number of termX-annotated proteins in a protein set of size ns is not less than ks, where ks is the number of the termX-annotated proteins in this complex [54]. Thep-value is computed as follows [54]:(29)p-value=1-∑i=0ks-1N-Kns-iKiNns=∑i=ksnsN-Kns-iKiNnsWe used the open source software GO::TermFinder [55] to calculate thep-value of an identified complex.Ifp-value<ψ, we call that the termX-annotated proteins enrich the complex atψ-level [54], whereψis a given threshold. If the termX-annotated proteins enrich a complex at the level ofψ=0.01 [54], this complex will has significantly biological function and be called significant complex [5]. The over-expression score of a set of identified protein complexes is defined as the ratio of the number of significant protein complexes to the total number of protein complexes in the set. We can evaluate the biological relevance of a set of identified protein complexes by calculating its over-expression score.


## 3.3. Experimental Results

Firstly, we evaluated the effect of active thresholdφ on the quality of protein complexes identified from temporal PPI networks (TPNs). Secondly, we assessed the protein complexes identified from temporal interval PPI networks (TI-PINs). Finally, we compared our method ICJointLE-DPN with Zhang’s method [33], DPC-NADPIN [34], TS-OCD [31], and DCA [35].


### 3.3.1. The Effect of Active Threshold

Here we first constructed different temporal PPI networks (TPNs) by combining three yeast PPI data sets (STRING, BioGrid, and DIP) with two yeast gene expression data sets (GSE3431 and GSE4987). And then we evaluated the quality of the complexes identified from these different TPNs. Figure2 shows the variation curves of value #PM×FAM of complexes identified from different constructed TPNs with the changingφ.Figure 2
Plot of value of #PM×FAMof complexes identified from the constructed TPNs by integrating gene expression data into yeast PPI data with respect to value ofφ.(a) Plot of value of #PM×FAMof complexes identified from the constructed TPNs by integrating GSE3431 into STRING, BioGrid, and DIP, respectively, with respect to value ofφ. (b) Plot of value of #PM×FAMof complexes identified from the constructed TPNs by integrating GSE4987 into STRING, BioGrid, and DIP, respectively, with respect to value ofφ.
(a) (b)From Figure2(a) we can see that for GSE3431, the value of #PM×FAM of the complexes identified from the constructed TPNs is the largest whenφ=0.01 for DIP andφ=0.1 for STRING and BioGrid respectively. At the meantime, from Figure 2(b), we can also see that for GSE4987, the value of #PM×FAMis the largest whenφ=0.05 for DIP, and the value of #PM×FAMis the largest whenφ=0.2 for STRING and BioGrid. Hence, in the following experiments, these values ofφ, shown in Table 2, are used to construct different TPNs for different combination of yeast expression data sets and yeast PPI data sets.Table 2
Setting values ofφ for different combination of yeast gene expression data sets and yeast PPI data sets.
Yeast expression data sets Yeast PPI data sets φ GSE3431 STRING 0.1 BioGrid 0.1 DIP 0.01  GSE4987 STRING 0.2 BioGrid 0.2 DIP 0.05


### 3.3.2. Setting of Parameters for ICJointLE-DPN

In our experiments, we empirically adjusted the value of parametersσ,ω, andθ to enable ICJointLE-DPN to perform well. We adjusted the value of parametersσ,ω, andθfrom 0.1 to 0.9 by increment 0.1 through several experiments respectively, and set these parameters to the appropriate values.Table3 shows the values of four parameters for algorithm ICJointLE-DPN with different combination of yeast gene expression data sets and yeast PPI data sets.Table 3
Value of parametersr, σ, ω, and θ for ICJointLE-DPN.
Yeast expression data sets Yeast PPI data sets r σ ω θ GSE3431 STRING 999 0.7 0.6 0.1 BioGrid 999 0.7 0.6 0.1 DIP 990 0.7 0.1 0.3  GSE4987 STRING 999 0.7 0.6 0.1 BioGrid 999 0.7 0.6 0.1 DIP 990 0.7 0.1 0.3


### 3.3.3. Evaluating Identified Complexes

To evaluate the quality of complexes identified by our method ICJointLE-DPN, we first constructed TPNs and TI-PINs. And then we executed algorithm ICJointLE-DPN to identify complexes from SPIN, TPNs, and TI-PINs respectively. Finally, we compared the quality of the complexes identified from SPIN, TPNs, and TI-PINs respectively in terms of value of #PM×FAM, which is shown in Table 4.Table 4
Values of #PM×FAM of complexes identified from SPIN, TPNs, and TI-PINs.
Yeast expression data sets Yeast PPI networks #PM×FAM STRING BioGrid DIP GSE3431 SPIN 356.54 337.93 282.01 TPNs 433.68 415.28 347.72 TI-PINs 441.38 423.30 356.69  GSE4987 SPIN 338.49 334.74 277.48 TPNs 424.25 416.00 343.00 TI-PINs 426.60 420.18 345.02As seen in Table4, we can find that for the same yeast PPI data set, the values of #PM×FAM resulting from both TPNs and TI-PINs are apparently larger than that resulting from SPIN. This indicates that identifying protein complexes from dynamic PPI networks can improve the quality of identified complexes. From Table 4, we can also see that the value of #PM×FAMresulting from TI-PINs is larger than that from TPNs. It means that identifying protein complexes from TI-PINs can further enhance the quality of identified complexes. As mentioned in the section “temporal interval PPI networks”, the use of TI-PINs constructed by several successive TPNs can provide more opportunities to accurately identify more protein complexes.To further illustrate the effect of our constructed TI-PINs, we ran our algorithm ICJointLE-DPN to identify complexes from TI-PINs and other existing dynamic PPI networks respectively. The experimental results are shown in Figure3.Figure 3
Comparison of values of #PM×FAMof complexes identified by ICJointLE-DPN from different dynamic PPI networks. (a) GSE3431 and (b) GSE4987 are integrated into STRING, BioGrid, and DIP, respectively, to construct six types of dynamic protein interaction networks.
(a) (b)We can see from Figure3 that no matter which yeast PPI data set is integrated with either GSE3431 or GSE4987 to construct TI-PINs, the value of #PM×FAMof complexes identified by ICJointLE-DPN from the constructed TI-PINs is apparently larger than that from other dynamic PPI networks. Such results may partly be attribute to using the relatively low active thresholdφ. In addition, by preserving continuous interactions, our constructed TI-PINs can indeed offer more opportunities to identify more protein complexes accurately.As a result, our constructed TI-PINs have more contributions to identification of protein complexes than other dynamic PPI networks such as TEPIN, DPIN, NF-APIN, DPPN, and TC-PINs.


### 3.3.4. Comparing Identification Methods

In order to evaluate the performance of the identification methods, we compared our method ICJointLE-DPN to three other competing methods Zhang’s method [33], DPC-NADPIN [34], TS-OCD [31], and DCA[35]. As described in the section “Expanding cluster condition”, in our method, only those PPIs with reliability score not lower than reliability thresholdr are used to identify protein complexes. For fair comparison, we removed those PPIs with reliability score lower than reliability thresholdr in three yeast PPI data sets before executing four other competing methods. For DPC-NADPIN method, no parameters need to be set. Zhang’s method uses two parametersPre_threshandComplex_threshwhose default values are 0.5 and 0.1. For DCA, we set parameters to the recommended values α=0.6, β=0.55, and γ=1.4. The setting of nine parameters used in TS-OCD method is shown in Table 5.Table 5
Setting parameters for TS-OCD method.
Parameters Repeat_times tau delta T K lambda beta iter rho value 1 0.3 0.3 12 1000 0.0625 16 20 0.000001By analyzing known complexes in CYC2008, we found that the number of the complexes of size two to six exceeds 84% of the total number of known complexes. To evaluate the ability of identifying complexes of size two to six, Table6 shows the distribution of the size of the complexes identified exactly by five methods.Table 6
Distribution of the size of the exactly identified complexes.
Yeast expression data sets Yeast PPI Data sets Methods The number of the exactly identified complexes Total Size 2 3 4 5 6 7 8 9 10 12 14 15 GSE3431 STRING ICJointLE-DPN  112 44 17 7 4 1 3 1 0 1 0 0 190 Zhang’s method  53 19 9 5 2 1 2 0 0 1 0 0 92 DPC-NADPIN  0 18 10 4 0 1 0 0 0 1 0 0 34 TS-OCD  0 5 7 3 1 1 1 0 0 1 1 0 20 DCA  0 4 3 0 0 0 0 0 0 0 0 0 7 BioGrid ICJointLE-DPN  113 42 15 6 4 0 1 2 1 1 0 0 185 Zhang’s method  56 20 10 5 3 1 2 0 0 1 0 0 98 DPC-NADPIN  0 20 11 4 1 1 1 0 0 1 0 0 39 TS-OCD  0 19 7 4 4 2 3 0 0 1 0 1 41 DCA  0 4 3 1 0 0 0 0 0 0 0 0 8 DIP ICJointLE-DPN  111 41 11 4 2 1 1 2 0 1 0 0 174 Zhang’s method  65 17 7 2 1 1 1 0 0 0 0 0 94 DPC-NADPIN  0 11 6 2 1 1 1 1 0 0 0 0 23 TS-OCD  0 4 5 0 1 1 0 0 0 1 0 0 12 DCA  0 3 5 1 0 0 0 0 0 0 0 0 9  GSE4987 STRING ICJointLE-DPN  107 45 17 6 5 0 2 1 1 0 1 0 185 Zhang’s method  52 21 12 4 3 2 2 0 0 0 0 1 97 DPC-NADPIN  0 3 1 2 0 0 0 0 0 0 0 0 6 TS-OCD  0 2 2 4 3 1 2 0 1 0 0 0 15 DCA  0 2 2 1 1 0 0 0 0 0 0 0 6 BioGrid ICJointLE-DPN  111 46 16 4 4 0 1 3 2 0 0 0 187 Zhang’s method  59 22 13 4 3 2 1 0 0 0 0 0 104 DPC-NADPIN  0 4 2 2 0 0 0 0 0 0 0 0 8 TS-OCD  0 16 7 5 5 2 2 0 1 0 1 0 39 DCA  0 2 3 2 1 0 1 0 0 0 0 0 9 DIP ICJointLE-DPN  110 40 13 4 2 1 1 2 1 0 0 0 174 Zhang’s method  69 20 8 3 3 2 1 0 0 0 0 0 106 DPC-NADPIN  0 4 2 0 0 0 0 0 0 0 0 0 6 TS-OCD  0 8 3 2 2 1 0 0 0 0 0 0 16 DCA  0 5 3 2 1 0 0 0 0 0 0 0 11From Table6, we can see that our method ICJointLE-DPN has stronger ability of exactly identifying the complexes of size two to six than other four competing methods. Especially, DPC-NADPIN, TS-OCD, and DCA fail to identify any complexes of size two.To evaluate the overall performance of five competing methods, we reported the statistical matching-based metrics of the identified complexes in Table7.Table 7
Statistical matching-based metrics of the complexes identified by five competing methods.
Yeast expression data sets Yeast PPI data sets Methods #PM fm Frac Acc MMR FAM #PM×FAM GSE3431 STRING ICJointLE-DPN 190 0.71 0.95 0.75 0.75 2.45 465.50 Zhang’s method 92 0.63 0.86 0.80 0.59 2.25 207.00 DPC-NADPIN 34 0.71 0.77 0.71 0.48 1.96 66.64 TS-OCD 20 0.55 0.46 0.68 0.30 1.45 29.00 DCA 7 0.55 0.51 0.57 0.27 1.35 9.45 BioGrid ICJointLE-DPN 185 0.72 0.93 0.80 0.73 2.46 455.10 Zhang’s method 98 0.63 0.85 0.78 0.58 2.21 216.58 DPC-NADPIN 39 0.71 0.75 0.72 0.48 1.94 75.66 TS-OCD 41 0.66 0.65 0.73 0.43 1.81 74.21 DCA 8 0.55 0.51 0.56 0.27 1.34 10.72 DIP ICJointLE-DPN 174 0.69 0.85 0.70 0.68 2.23 388.02 Zhang’s method 94 0.67 0.76 0.71 0.52 1.99 187.06 DPC-NADPIN 23 0.63 0.55 0.67 0.35 1.57 36.11 TS-OCD 12 0.39 0.27 0.54 0.18 1.00 12.00 DCA 9 0.48 0.36 0.55 0.21 1.12 10.08  GSE4987 STRING ICJointLE-DPN 185 0.60 0.95 0.72 0.75 2.42 447.70 Zhang’s method 97 0.64 0.91 0.79 0.62 2.32 225.04 DPC-NADPIN 6 0.52 0.56 0.59 0.30 1.46 8.76 TS-OCD 15 0.55 0.53 0.68 0.34 1.56 23.4 DCA 6 0.61 0.70 0.64 0.37 1.71 10.26 BioGrid ICJointLE-DPN 187 0.67 0.93 0.76 0.74 2.43 454.41 Zhang’s method 104 0.63 0.90 0.78 0.63 2.31 240.24 DPC-NADPIN 8 0.54 0.55 0.60 0.13 1.45 11.6 TS-OCD 39 0.66 0.68 0.74 0.46 1.88 73.32 DCA 9 0.62 0.68 0.65 0.36 1.69 15.17 DIP ICJointLE-DPN 174 0.67 0.86 0.68 0.68 2.22 386.28 Zhang’s method 106 0.67 0.83 0.74 0.58 2.15 227.9 DPC-NADPIN 6 0.44 0.36 0.53 0.21 1.10 6.60 TS-OCD 16 0.41 0.29 0.54 0.20 1.04 16.64 DCA 11 0.58 0.50 0.63 0.29 1.42 15.62From Table7, we can see that our method ICJointLE-DPN outperforms the other four competing methods in terms of#PM,Frac,MMR,FAM, and#PM×FAM. We also see that, concerningfm, ICJointLE-DPN obtains almost all the largest values except for one among five competing methods, and with regard toAcc, ICJointLE-DPN is ranked top two. Overall, our method ICJointLE-DPN can not only identify complexes accurately but also identify more complexes exactly matched with known complexes from TI-PINs.Now we give two examples related to the complexes identified from dynamical PPI networks which are constructed via incorporating GSE3431 into DIP. Figure4 illustrates the matching example between nuclear exosome complex and the complexes identified by five competing methods.Figure 4
The complexes identified by five competing methods. (a) The No. 396 complex identified by TSOCD and the No. 901 complex identified by ICJointLE-DPN both match with nuclear exosome complex exactly. (b) The No. 829 complex is incorrectly identified by Zhang's method by not including the four proteins outside the ellipse. (c) The No. 1929 complex identified by DPC-NADPIN by wrongly including the yellow-colored YNL189W and excluding YHR081W. (d) DCA identified the No. 55 complex wrongly with the inclusion of three yellow-colored proteins.
(a)
TSOCD, ICJointLE-DPN (b)
Zhang’s method (c)
DPC-NADPIN (d)
DCAAs can be seen from Figure4(a), TSOCD and ICJointLE-DPN can identify nuclear exosome complex exactly. Zhang’s method misses four proteins outside the ellipse in Figure 4(b). DPC-NADPIN wrongly identifies the yellow-colored YNL189W and misses YHR081W outside the ellipse in Figure 4(c). DCA wrongly identifies three yellow-colored proteins in Figure 4(d).Similarly, Figure5 shows the matching example between COMA complex and the complexes identified by five competing methods.Figure 5
The complexes identified by five competing methods. (a) The No. 1935 complex identified by ICJointLE-DPN misses YBR211C outside the ellipse. (b) The No. 123 complex identified by TSOCD and the No. 137 complex identified by Zhang's method incorrectly contain the yellow-colored YBR107C and omit YBR211C outside the ellipse. (c) The No. 159 complex identified by DPC-NADPIN wrongly includes the yellow-colored YKL049C and omits YBR211C outside the ellipse. (d) The No. 433 complex identified by DCA wrongly includes the yellow-colored YGR140W.
(a)
ICJointLE-DPN (b)
TSOCD, Zhang’s method (c)
DPC-NADPIN (d)
DCAFrom Figure5, we can see that our method ICJointLE-DPN fails to identify COMA complex exactly due to missing YBR211C outside the ellipse in Figure 5(a). TSOCD and Zhang’s method wrongly identify the yellow-colored YBR107C and miss YBR211C outside the ellipse in Figure 5(b), these two methods are unable to detect COMA complex exactly. Likewise, owing to wrongly identifying the yellow-colored YKL049C and missing YBR211C outside the ellipse in Figure 5(c), DPC-NADPIN fails to find COMA complex exactly. We can also see from Figure 5(d) that DCA is unsuccessful in detecting the COMA complex due to wrongly identifying the yellow-colored YGR140W.To evaluate the functional enrichment of identified complexes, we compared our method ICJointLE-DPN to other four competing methods with respect to biological process (BP) enrichment analysis. For complexes identified by ICJointLE-DPN from different TI-PINs, their raw data of BP enrichment analyses and their results of significant statistics are presented in Supplementary Materials (Availablehere). Table 8 shows the proportion of the complexes that are significantly enriched by BP term-annotated proteins, where #ICis the total number of identified complexes, #SCdenotes the number of identified complexes with significant enrichment.Table 8
Proportion of the complexes enriched significantly by BP term-annotated proteins.
Yeast expression data sets Yeast PPI data sets Methods #IC #SC % of significant (size≤6) % of significant (6<size<20) % of significant (size≥20) GSE3431 STRING ICJointLE-DPN 5137 4873 93.33% 100.00% 100.00% Zhang’s method 1117 1013 88.56% 100.00% 100.00% DPC-NADPIN 6464 6439 98.88% 99.94% 100.00% TS-OCD 1175 1157 97.26% 100.00% 100.00% DCA 1261 1261 100.00% 100.00% 100.00% BioGrid ICJointLE-DPN 4896 4559 90.69% 100.00% 100.00% Zhang’s method 1074 974 88.73% 100.00% 100.00% DPC-NADPIN 5437 5420 99.16% 100.00% 100.00% TS-OCD 1784 1749 96.56% 100.00% 100.00% DCA 1201 1199 98.45% 100.00% 100.00% DIP ICJointLE-DPN 4398 4118 91.42% 100.00% 100.00% Zhang’s method 836 725 85.18% 100.00% 100.00% DPC-NADPIN 3019 3007 99.24% 100.00% 100.00% TS-OCD 439 434 98.50% 100.00% 100.00% DCA 595 595 100.00% 100.00% 100.00%  GSE4987 STRING ICJointLE-DPN 12283 11913 95.34% 99.97% 100.00% Zhang’s method 1863 1712 89.36% 100.00% 100.00% DPC-NADPIN 4509 4498 99.45% 100.00% 100.00% TS-OCD 2302 2266 97.26% 100.00% 100.00% DCA 3212 3204 98.84% 99.94% 100.00% BioGrid ICJointLE-DPN 10558 10100 93.25% 100.00% 100.00% Zhang’s method 1821 1660 88.75% 100.00% 100.00% DPC-NADPIN 3657 3641 99.15% 100.00% 100.00% TS-OCD 3354 3295 97.12% 100.00% 100.00% DCA 2686 2678 98.46% 99.60% 100.00% DIP ICJointLE-DPN 8745 8359 92.86% 100.00% 100.00% Zhang’s method 1343 1177 85.76% 100.00% 100.00% DPC-NADPIN 6464 1668 99.66% 100.00% 100.00% TS-OCD 734 721 97.68% 100.00% 100.00% DCA 1269 1266 99.27% 100.00% 100.00%As seen from Table8, for five competing methods, their identified complexes of size larger than 6 are almost biologically significant except for the four italic cases. From Table 8, we can also see that for the significant enrichment of identified complexes of size not larger than 6, our method performs slightly weaker than DPC-NADPIN, TS-OCD, and DCA but stronger than Zhang’s method.In summary, our proposed identification method overall outperforms other four competing methods in terms of the number of identified complexes exactly matched with known complexes#PM, the fraction of known complexes matched with identified complexesFRAC, maximum matching ratioMMR, comprehensive scoreFAM, and the product of#PMandFAM. Concerning the significant enrichment, five competing methods overall perform well when they identify complexes of size larger than 6; when identifying complexes of size not larger than 6, our proposed method performs slightly weaker than DPC-NADPIN, TS-OCD, and DCA but stronger than Zhang’s method.


## 3.3.1. The Effect of Active Threshold

Here we first constructed different temporal PPI networks (TPNs) by combining three yeast PPI data sets (STRING, BioGrid, and DIP) with two yeast gene expression data sets (GSE3431 and GSE4987). And then we evaluated the quality of the complexes identified from these different TPNs. Figure2 shows the variation curves of value #PM×FAM of complexes identified from different constructed TPNs with the changingφ.Figure 2
Plot of value of #PM×FAMof complexes identified from the constructed TPNs by integrating gene expression data into yeast PPI data with respect to value ofφ.(a) Plot of value of #PM×FAMof complexes identified from the constructed TPNs by integrating GSE3431 into STRING, BioGrid, and DIP, respectively, with respect to value ofφ. (b) Plot of value of #PM×FAMof complexes identified from the constructed TPNs by integrating GSE4987 into STRING, BioGrid, and DIP, respectively, with respect to value ofφ.
(a) (b)From Figure2(a) we can see that for GSE3431, the value of #PM×FAM of the complexes identified from the constructed TPNs is the largest whenφ=0.01 for DIP andφ=0.1 for STRING and BioGrid respectively. At the meantime, from Figure 2(b), we can also see that for GSE4987, the value of #PM×FAMis the largest whenφ=0.05 for DIP, and the value of #PM×FAMis the largest whenφ=0.2 for STRING and BioGrid. Hence, in the following experiments, these values ofφ, shown in Table 2, are used to construct different TPNs for different combination of yeast expression data sets and yeast PPI data sets.Table 2
Setting values ofφ for different combination of yeast gene expression data sets and yeast PPI data sets.
Yeast expression data sets Yeast PPI data sets φ GSE3431 STRING 0.1 BioGrid 0.1 DIP 0.01  GSE4987 STRING 0.2 BioGrid 0.2 DIP 0.05


## 3.3.2. Setting of Parameters for ICJointLE-DPN

In our experiments, we empirically adjusted the value of parametersσ,ω, andθ to enable ICJointLE-DPN to perform well. We adjusted the value of parametersσ,ω, andθfrom 0.1 to 0.9 by increment 0.1 through several experiments respectively, and set these parameters to the appropriate values.Table3 shows the values of four parameters for algorithm ICJointLE-DPN with different combination of yeast gene expression data sets and yeast PPI data sets.Table 3
Value of parametersr, σ, ω, and θ for ICJointLE-DPN.
Yeast expression data sets Yeast PPI data sets r σ ω θ GSE3431 STRING 999 0.7 0.6 0.1 BioGrid 999 0.7 0.6 0.1 DIP 990 0.7 0.1 0.3  GSE4987 STRING 999 0.7 0.6 0.1 BioGrid 999 0.7 0.6 0.1 DIP 990 0.7 0.1 0.3


## 3.3.3. Evaluating Identified Complexes

To evaluate the quality of complexes identified by our method ICJointLE-DPN, we first constructed TPNs and TI-PINs. And then we executed algorithm ICJointLE-DPN to identify complexes from SPIN, TPNs, and TI-PINs respectively. Finally, we compared the quality of the complexes identified from SPIN, TPNs, and TI-PINs respectively in terms of value of #PM×FAM, which is shown in Table 4.Table 4
Values of #PM×FAM of complexes identified from SPIN, TPNs, and TI-PINs.
Yeast expression data sets Yeast PPI networks #PM×FAM STRING BioGrid DIP GSE3431 SPIN 356.54 337.93 282.01 TPNs 433.68 415.28 347.72 TI-PINs 441.38 423.30 356.69  GSE4987 SPIN 338.49 334.74 277.48 TPNs 424.25 416.00 343.00 TI-PINs 426.60 420.18 345.02As seen in Table4, we can find that for the same yeast PPI data set, the values of #PM×FAM resulting from both TPNs and TI-PINs are apparently larger than that resulting from SPIN. This indicates that identifying protein complexes from dynamic PPI networks can improve the quality of identified complexes. From Table 4, we can also see that the value of #PM×FAMresulting from TI-PINs is larger than that from TPNs. It means that identifying protein complexes from TI-PINs can further enhance the quality of identified complexes. As mentioned in the section “temporal interval PPI networks”, the use of TI-PINs constructed by several successive TPNs can provide more opportunities to accurately identify more protein complexes.To further illustrate the effect of our constructed TI-PINs, we ran our algorithm ICJointLE-DPN to identify complexes from TI-PINs and other existing dynamic PPI networks respectively. The experimental results are shown in Figure3.Figure 3
Comparison of values of #PM×FAMof complexes identified by ICJointLE-DPN from different dynamic PPI networks. (a) GSE3431 and (b) GSE4987 are integrated into STRING, BioGrid, and DIP, respectively, to construct six types of dynamic protein interaction networks.
(a) (b)We can see from Figure3 that no matter which yeast PPI data set is integrated with either GSE3431 or GSE4987 to construct TI-PINs, the value of #PM×FAMof complexes identified by ICJointLE-DPN from the constructed TI-PINs is apparently larger than that from other dynamic PPI networks. Such results may partly be attribute to using the relatively low active thresholdφ. In addition, by preserving continuous interactions, our constructed TI-PINs can indeed offer more opportunities to identify more protein complexes accurately.As a result, our constructed TI-PINs have more contributions to identification of protein complexes than other dynamic PPI networks such as TEPIN, DPIN, NF-APIN, DPPN, and TC-PINs.


## 3.3.4. Comparing Identification Methods

In order to evaluate the performance of the identification methods, we compared our method ICJointLE-DPN to three other competing methods Zhang’s method [33], DPC-NADPIN [34], TS-OCD [31], and DCA[35]. As described in the section “Expanding cluster condition”, in our method, only those PPIs with reliability score not lower than reliability thresholdr are used to identify protein complexes. For fair comparison, we removed those PPIs with reliability score lower than reliability thresholdr in three yeast PPI data sets before executing four other competing methods. For DPC-NADPIN method, no parameters need to be set. Zhang’s method uses two parametersPre_threshandComplex_threshwhose default values are 0.5 and 0.1. For DCA, we set parameters to the recommended values α=0.6, β=0.55, and γ=1.4. The setting of nine parameters used in TS-OCD method is shown in Table 5.Table 5
Setting parameters for TS-OCD method.
Parameters Repeat_times tau delta T K lambda beta iter rho value 1 0.3 0.3 12 1000 0.0625 16 20 0.000001By analyzing known complexes in CYC2008, we found that the number of the complexes of size two to six exceeds 84% of the total number of known complexes. To evaluate the ability of identifying complexes of size two to six, Table6 shows the distribution of the size of the complexes identified exactly by five methods.Table 6
Distribution of the size of the exactly identified complexes.
Yeast expression data sets Yeast PPI Data sets Methods The number of the exactly identified complexes Total Size 2 3 4 5 6 7 8 9 10 12 14 15 GSE3431 STRING ICJointLE-DPN  112 44 17 7 4 1 3 1 0 1 0 0 190 Zhang’s method  53 19 9 5 2 1 2 0 0 1 0 0 92 DPC-NADPIN  0 18 10 4 0 1 0 0 0 1 0 0 34 TS-OCD  0 5 7 3 1 1 1 0 0 1 1 0 20 DCA  0 4 3 0 0 0 0 0 0 0 0 0 7 BioGrid ICJointLE-DPN  113 42 15 6 4 0 1 2 1 1 0 0 185 Zhang’s method  56 20 10 5 3 1 2 0 0 1 0 0 98 DPC-NADPIN  0 20 11 4 1 1 1 0 0 1 0 0 39 TS-OCD  0 19 7 4 4 2 3 0 0 1 0 1 41 DCA  0 4 3 1 0 0 0 0 0 0 0 0 8 DIP ICJointLE-DPN  111 41 11 4 2 1 1 2 0 1 0 0 174 Zhang’s method  65 17 7 2 1 1 1 0 0 0 0 0 94 DPC-NADPIN  0 11 6 2 1 1 1 1 0 0 0 0 23 TS-OCD  0 4 5 0 1 1 0 0 0 1 0 0 12 DCA  0 3 5 1 0 0 0 0 0 0 0 0 9  GSE4987 STRING ICJointLE-DPN  107 45 17 6 5 0 2 1 1 0 1 0 185 Zhang’s method  52 21 12 4 3 2 2 0 0 0 0 1 97 DPC-NADPIN  0 3 1 2 0 0 0 0 0 0 0 0 6 TS-OCD  0 2 2 4 3 1 2 0 1 0 0 0 15 DCA  0 2 2 1 1 0 0 0 0 0 0 0 6 BioGrid ICJointLE-DPN  111 46 16 4 4 0 1 3 2 0 0 0 187 Zhang’s method  59 22 13 4 3 2 1 0 0 0 0 0 104 DPC-NADPIN  0 4 2 2 0 0 0 0 0 0 0 0 8 TS-OCD  0 16 7 5 5 2 2 0 1 0 1 0 39 DCA  0 2 3 2 1 0 1 0 0 0 0 0 9 DIP ICJointLE-DPN  110 40 13 4 2 1 1 2 1 0 0 0 174 Zhang’s method  69 20 8 3 3 2 1 0 0 0 0 0 106 DPC-NADPIN  0 4 2 0 0 0 0 0 0 0 0 0 6 TS-OCD  0 8 3 2 2 1 0 0 0 0 0 0 16 DCA  0 5 3 2 1 0 0 0 0 0 0 0 11From Table6, we can see that our method ICJointLE-DPN has stronger ability of exactly identifying the complexes of size two to six than other four competing methods. Especially, DPC-NADPIN, TS-OCD, and DCA fail to identify any complexes of size two.To evaluate the overall performance of five competing methods, we reported the statistical matching-based metrics of the identified complexes in Table7.Table 7
Statistical matching-based metrics of the complexes identified by five competing methods.
Yeast expression data sets Yeast PPI data sets Methods #PM fm Frac Acc MMR FAM #PM×FAM GSE3431 STRING ICJointLE-DPN 190 0.71 0.95 0.75 0.75 2.45 465.50 Zhang’s method 92 0.63 0.86 0.80 0.59 2.25 207.00 DPC-NADPIN 34 0.71 0.77 0.71 0.48 1.96 66.64 TS-OCD 20 0.55 0.46 0.68 0.30 1.45 29.00 DCA 7 0.55 0.51 0.57 0.27 1.35 9.45 BioGrid ICJointLE-DPN 185 0.72 0.93 0.80 0.73 2.46 455.10 Zhang’s method 98 0.63 0.85 0.78 0.58 2.21 216.58 DPC-NADPIN 39 0.71 0.75 0.72 0.48 1.94 75.66 TS-OCD 41 0.66 0.65 0.73 0.43 1.81 74.21 DCA 8 0.55 0.51 0.56 0.27 1.34 10.72 DIP ICJointLE-DPN 174 0.69 0.85 0.70 0.68 2.23 388.02 Zhang’s method 94 0.67 0.76 0.71 0.52 1.99 187.06 DPC-NADPIN 23 0.63 0.55 0.67 0.35 1.57 36.11 TS-OCD 12 0.39 0.27 0.54 0.18 1.00 12.00 DCA 9 0.48 0.36 0.55 0.21 1.12 10.08  GSE4987 STRING ICJointLE-DPN 185 0.60 0.95 0.72 0.75 2.42 447.70 Zhang’s method 97 0.64 0.91 0.79 0.62 2.32 225.04 DPC-NADPIN 6 0.52 0.56 0.59 0.30 1.46 8.76 TS-OCD 15 0.55 0.53 0.68 0.34 1.56 23.4 DCA 6 0.61 0.70 0.64 0.37 1.71 10.26 BioGrid ICJointLE-DPN 187 0.67 0.93 0.76 0.74 2.43 454.41 Zhang’s method 104 0.63 0.90 0.78 0.63 2.31 240.24 DPC-NADPIN 8 0.54 0.55 0.60 0.13 1.45 11.6 TS-OCD 39 0.66 0.68 0.74 0.46 1.88 73.32 DCA 9 0.62 0.68 0.65 0.36 1.69 15.17 DIP ICJointLE-DPN 174 0.67 0.86 0.68 0.68 2.22 386.28 Zhang’s method 106 0.67 0.83 0.74 0.58 2.15 227.9 DPC-NADPIN 6 0.44 0.36 0.53 0.21 1.10 6.60 TS-OCD 16 0.41 0.29 0.54 0.20 1.04 16.64 DCA 11 0.58 0.50 0.63 0.29 1.42 15.62From Table7, we can see that our method ICJointLE-DPN outperforms the other four competing methods in terms of#PM,Frac,MMR,FAM, and#PM×FAM. We also see that, concerningfm, ICJointLE-DPN obtains almost all the largest values except for one among five competing methods, and with regard toAcc, ICJointLE-DPN is ranked top two. Overall, our method ICJointLE-DPN can not only identify complexes accurately but also identify more complexes exactly matched with known complexes from TI-PINs.Now we give two examples related to the complexes identified from dynamical PPI networks which are constructed via incorporating GSE3431 into DIP. Figure4 illustrates the matching example between nuclear exosome complex and the complexes identified by five competing methods.Figure 4
The complexes identified by five competing methods. (a) The No. 396 complex identified by TSOCD and the No. 901 complex identified by ICJointLE-DPN both match with nuclear exosome complex exactly. (b) The No. 829 complex is incorrectly identified by Zhang's method by not including the four proteins outside the ellipse. (c) The No. 1929 complex identified by DPC-NADPIN by wrongly including the yellow-colored YNL189W and excluding YHR081W. (d) DCA identified the No. 55 complex wrongly with the inclusion of three yellow-colored proteins.
(a)
TSOCD, ICJointLE-DPN (b)
Zhang’s method (c)
DPC-NADPIN (d)
DCAAs can be seen from Figure4(a), TSOCD and ICJointLE-DPN can identify nuclear exosome complex exactly. Zhang’s method misses four proteins outside the ellipse in Figure 4(b). DPC-NADPIN wrongly identifies the yellow-colored YNL189W and misses YHR081W outside the ellipse in Figure 4(c). DCA wrongly identifies three yellow-colored proteins in Figure 4(d).Similarly, Figure5 shows the matching example between COMA complex and the complexes identified by five competing methods.Figure 5
The complexes identified by five competing methods. (a) The No. 1935 complex identified by ICJointLE-DPN misses YBR211C outside the ellipse. (b) The No. 123 complex identified by TSOCD and the No. 137 complex identified by Zhang's method incorrectly contain the yellow-colored YBR107C and omit YBR211C outside the ellipse. (c) The No. 159 complex identified by DPC-NADPIN wrongly includes the yellow-colored YKL049C and omits YBR211C outside the ellipse. (d) The No. 433 complex identified by DCA wrongly includes the yellow-colored YGR140W.
(a)
ICJointLE-DPN (b)
TSOCD, Zhang’s method (c)
DPC-NADPIN (d)
DCAFrom Figure5, we can see that our method ICJointLE-DPN fails to identify COMA complex exactly due to missing YBR211C outside the ellipse in Figure 5(a). TSOCD and Zhang’s method wrongly identify the yellow-colored YBR107C and miss YBR211C outside the ellipse in Figure 5(b), these two methods are unable to detect COMA complex exactly. Likewise, owing to wrongly identifying the yellow-colored YKL049C and missing YBR211C outside the ellipse in Figure 5(c), DPC-NADPIN fails to find COMA complex exactly. We can also see from Figure 5(d) that DCA is unsuccessful in detecting the COMA complex due to wrongly identifying the yellow-colored YGR140W.To evaluate the functional enrichment of identified complexes, we compared our method ICJointLE-DPN to other four competing methods with respect to biological process (BP) enrichment analysis. For complexes identified by ICJointLE-DPN from different TI-PINs, their raw data of BP enrichment analyses and their results of significant statistics are presented in Supplementary Materials (Availablehere). Table 8 shows the proportion of the complexes that are significantly enriched by BP term-annotated proteins, where #ICis the total number of identified complexes, #SCdenotes the number of identified complexes with significant enrichment.Table 8
Proportion of the complexes enriched significantly by BP term-annotated proteins.
Yeast expression data sets Yeast PPI data sets Methods #IC #SC % of significant (size≤6) % of significant (6<size<20) % of significant (size≥20) GSE3431 STRING ICJointLE-DPN 5137 4873 93.33% 100.00% 100.00% Zhang’s method 1117 1013 88.56% 100.00% 100.00% DPC-NADPIN 6464 6439 98.88% 99.94% 100.00% TS-OCD 1175 1157 97.26% 100.00% 100.00% DCA 1261 1261 100.00% 100.00% 100.00% BioGrid ICJointLE-DPN 4896 4559 90.69% 100.00% 100.00% Zhang’s method 1074 974 88.73% 100.00% 100.00% DPC-NADPIN 5437 5420 99.16% 100.00% 100.00% TS-OCD 1784 1749 96.56% 100.00% 100.00% DCA 1201 1199 98.45% 100.00% 100.00% DIP ICJointLE-DPN 4398 4118 91.42% 100.00% 100.00% Zhang’s method 836 725 85.18% 100.00% 100.00% DPC-NADPIN 3019 3007 99.24% 100.00% 100.00% TS-OCD 439 434 98.50% 100.00% 100.00% DCA 595 595 100.00% 100.00% 100.00%  GSE4987 STRING ICJointLE-DPN 12283 11913 95.34% 99.97% 100.00% Zhang’s method 1863 1712 89.36% 100.00% 100.00% DPC-NADPIN 4509 4498 99.45% 100.00% 100.00% TS-OCD 2302 2266 97.26% 100.00% 100.00% DCA 3212 3204 98.84% 99.94% 100.00% BioGrid ICJointLE-DPN 10558 10100 93.25% 100.00% 100.00% Zhang’s method 1821 1660 88.75% 100.00% 100.00% DPC-NADPIN 3657 3641 99.15% 100.00% 100.00% TS-OCD 3354 3295 97.12% 100.00% 100.00% DCA 2686 2678 98.46% 99.60% 100.00% DIP ICJointLE-DPN 8745 8359 92.86% 100.00% 100.00% Zhang’s method 1343 1177 85.76% 100.00% 100.00% DPC-NADPIN 6464 1668 99.66% 100.00% 100.00% TS-OCD 734 721 97.68% 100.00% 100.00% DCA 1269 1266 99.27% 100.00% 100.00%As seen from Table8, for five competing methods, their identified complexes of size larger than 6 are almost biologically significant except for the four italic cases. From Table 8, we can also see that for the significant enrichment of identified complexes of size not larger than 6, our method performs slightly weaker than DPC-NADPIN, TS-OCD, and DCA but stronger than Zhang’s method.In summary, our proposed identification method overall outperforms other four competing methods in terms of the number of identified complexes exactly matched with known complexes#PM, the fraction of known complexes matched with identified complexesFRAC, maximum matching ratioMMR, comprehensive scoreFAM, and the product of#PMandFAM. Concerning the significant enrichment, five competing methods overall perform well when they identify complexes of size larger than 6; when identifying complexes of size not larger than 6, our proposed method performs slightly weaker than DPC-NADPIN, TS-OCD, and DCA but stronger than Zhang’s method.


## 4. Conclusions

Gene expression data contains temporal information of protein activity. By integrating gene expression data into PPI data to determine active time point of interacting proteins, we exploited temporal dynamics of proteins to construct temporal PPI networks TPNs. In order to accurately identify more protein complexes, we further converted TPNs into temporal interval PPI networks TI-PINs. The experimental results confirmed that our constructed TI-PINs have more contributions to identification of protein complex than TEPIN (Time-Evolving PIN), DPIN (dynamic protein interaction networks), NF-APIN (noise-filtered active protein interaction networks), DPPN (dynamic probabilistic protein interaction networks), and TC-PIN (time-course protein interaction networks).Based on our constructed TI-PINs, we devised a novel method ICJointLE-DPN which uses multisource biological data to identify protein complexes. First, our proposed method employs protein localization data to analyze the joint colocalization condition to judge whether a group of proteins is of joint colocalization. Secondly, our proposed method uses gene expression data to analyze the joint coexpression condition to judge whether a group of proteins is of joint coexpression. Thirdly, our method exploits three types of similarity to analyze the expanding cluster condition to judge whether a group of proteins is of functional homogeneity. As a result, by combining these three conditions, our proposed method can accurately identify more protein complexes from TI-PINs than other four competing methods Zhang’s method, DPC-NADPIN, TS-OCD, and DCA.Identifying protein complexes from dynamic PPI networks remains to be a challenging work in postgenomic era. In cell system, protein activity and protein-protein interaction have dynamical characteristics. Hence, it is important for identifying protein complexes to construct dynamic PPI networks close to reality. Due to the limited gene expression samples and failure to capture some transient interactions, it is difficult to construct dynamic PPI networks completely expressing protein interactions in cell system. Although many works have made to construct effective dynamic PPI networks to identify protein complexes, the efforts on constructing nearly real PPI networks will still be encouraged. In addition, it is also important to design an effective method to identify protein complexes from dynamic PPI networks. To find protein complexes with biological relevance by computational approach, multisource biological data should be used to identify protein complexes from dynamic PPI networks. As seen from Table8, some protein complexes of size not larger than 6 identified by our method are not significant enough in biological meaning. This suggests that more other biological data should be integrated into protein complex identification. In future work, we will further investigate the integration of more biological data into our method in order to not only identify protein complexes more accurately but also improve the significant enrichment of the identified protein complexes of size not larger than 6.



---

*Source: 3726721-2019-08-21.xml*