BACKGROUND
understanding the structural and functional architecture of the cell has been a fundamental task for systems biology  <cit> .
as vital macromolecules, proteins do not act individually, but work by interacting with other partners  <cit> .
almost all of the functional processes within a cell are carried out by protein complexes which are formed by interacting proteins  <cit> .
therefore, detecting protein complexes from protein-protein interaction  data is crucial for elucidating the modular structure within cells  <cit> .
in recent years, high-throughput screening  techniques have been designed to detect protein-protein interactions, e.g., yeast two-hybrid   <cit>  and tandem affinity purification/mass spectrometry   <cit> .
such hts techniques have already generated a large amount of ppi data, which facilitate the development of computational methods for protein complex detection .
generally, computational methods for protein complex detection utilize two types of data, namely, the binary protein interaction data detected by hts techniques such as y2h method, and the data for co-complex interactions among proteins  <cit>  from tap experiments.
here, we denote the above two types of data as ppi data and tap data respectively.
ppi data is usually modeled as a graph  where nodes represent proteins and edges represent protein interactions.
a number of graph clustering algorithms have been proposed for detecting protein complexes from ppi networks, such as mcode  <cit> , cfinder  <cit> , mcl  <cit> , rnsc  <cit> , coach  <cit>  and clusterone  <cit> .
on the other hand, raw data from tap experiments is a list of bait proteins along with their corresponding prey proteins that they pulled out , which could be modeled as a bipartite graph .
several algorithms have been proposed to identify protein complexes from tap data as well .
a common strategy is to first define affinity scores between proteins based on the purification records  <cit>  and then convert the tap data to a ppi network by using a threshold method to keep those reliable interactions for further analysis.
since convert the original tap data into a binary ppi network not only introduces errors but also loses useful information in the raw data  <cit> , another alternative strategy is to detect complexes from the tap data directly, such as cachet  <cit> .
as diverse sources of protein interaction data are available, data integration becomes a common methodology to reduce the noise in ppi and tap data   <cit>  and to improve the coverage  for protein complex detection.
for example, decaff  <cit>  exploited the gene ontology  annotations to assess the reliability of ppi data and then detected protein complexes from the refined ppi data; matisse  <cit>  and cmbi  <cit>  integrated gene expression data with ppi data to increase the confidence of interactions for protein complex detection.
intehc  <cit>  integrated four data sources  and significantly improved the complex detection.
in particular, intehc calculated a score matrix for each of the four data sources and took their weighted sum, which relies on additional supervision information to learn a weight for each data source, as an integrated matrix.
however, due to noise in different data sources, the direct fusion of several original datasets may exacerbate the problems of noise.
moreover, how to correctly estimate the co-complex relationships between proteins based on their functional annotations and gene expression profiles is still an open problem.
nevertheless, with various methods proposed for protein complex detection, we are thus able to generate a series of clustering results for each type of data.
clearly, given one type of data, each method has its own advantages and limitations in capturing co-complex relationships between proteins  <cit> .
ensemble clustering, which exploits the complementary nature of individual methods by leveraging their clustering outputs, is thus promising to improve the detection for protein complexes  <cit> .
particularly, ensemble clustering methods usually first reconstruct a consensus matrix  which shows the co-complex propensity among proteins from a series of clustering results and then apply a specific algorithm  <cit>  to detect protein complexes from the consensus matrix.
however, the consensus network, based solely on the result-level integration , may miss the underlying complex information which exist in other types of data.
it is thus necessary to combine the consensus matrices derived from multiple types of data to generate a more comprehensive and reliable co-complex similarity matrix, which may facilitate the detection of protein complexes.
different from y2h experiments that are prone to identify direct physical interactions, tap experiments already provide useful information about protein complexes and tap data describe the co-complex propensity among proteins.
however, as tap data cannot be converted into co-complex interactions in a straightforward manner, several scoring methods have been proposed to estimate the affinity scores between proteins based on the purification records  provided by tap data, such as c2s scores  <cit> .
as such, we are able to integrate heterogeneous matrices, i.e., the consensus matrices derived from different types of data and the co-complex score matrices derived from tap data, to better understand the co-complex relationships among proteins.
however, as these heterogeneous matrices may have different scales, noise rates and importance levels, focusing only on common patterns can miss valuable complementary information.
it would be challenging to merge them into a final co-complex matrix automatically in an unsupervised manner.
in addition, once we obtain the integrated matrix, it is still difficult for us to design an efficient algorithm to detect overlapping complexes from this integrated matrix.
to address the above challenges, we propose a novel two-layer integrative complex detection  model to predict protein complexes as shown in fig.
<dig>  which leverages the information from both clustering results and raw data sources.
in the first layer integration, we utilize an ensemble method to construct consensus matrices for different types of data to measure the co-complex propensities between proteins based on various clustering results.
in the second layer integration, we combine the consensus matrices derived from different types of data with the score matrix derived from tap data and obtain an integrated similarity network via a similarity network fusion  method.
snf is an iterative process to fuse heterogeneous networks or matrices by capturing both shared and complementary information among them  <cit> .
finally, a novel graph regularized doubly stochastic matrix decomposition model is proposed to detect overlapping protein complexes from the integrated similarity network.
we have conducted comprehensive experiments to evaluate the performance of our proposed tincd algorithm.
a comprehensive comparison with  <dig> existing methods shows that our two-layer integration strategy generates protein complexes with better coverage and accuracy.
all the experimental results and code can be downloaded from https://github.com/oyl-cityu/tincd.
fig.
<dig> schematic overview of our proposed tincd model.
tincd first constructs two consensus matrices  and c
) based on the complex knowledge discovered by various graph clustering algorithms from ppi and tap data.
second, a similarity network fusion  strategy is employed by tincd to combine these two consensus matrices with the score matrix obtained from tap data ) to obtain a final co-complex score matrix.
finally, a novel graph regularized doubly stochastic matrix decomposition model is proposed to detect overlapping protein complexes from the final score matrix
methods
in this section, we describe our tincd model as shown in fig.
<dig> in details.
we first demonstrate the two-layer integration and then present the graph regularized doubly stochastic matrix decomposition algorithm for protein complex detection.
first layer integration: result-level integration via ensemble clustering
as diverse types of data are available and various computational methods have been designed to detect protein complexes from them, we are thus able to generate a series of base clustering results .
a straightforward way to measure the co-complex affinities among proteins is to build the consensus matrices by integrating the above abundant clustering results.
suppose all the data sources used in this study cover n proteins and we have obtained np clustering results which are generated by applying np different methods on a specific type of data.
here, a clustering result refers to a set of clusters generated by a certain method.
a consensus matrix c is a n×n matrix.
in c, the entry cij is the number of clustering results where the proteins i and j are assigned to the same cluster, divided by the number of clustering results np.
as such, each entry cij indicates the probabilities that protein i and j are involving in the same complexes.
if protein i is not assigned to any clusters or is not included in the m-th data source, the i-th row and i-th column of c are set to zero.
note that the coverage and quality of different data sources would be different.
we thus build a corresponding consensus matrix independently for each type of data.
in this study, we focus on two data sources, namely, ppi data and tap data.
therefore, the consensus matrices corresponding to these two types of data are denoted by c and c respectively .
second layer integration: integrating heterogeneous co-complex matrices via similarity network fusion
unlike ppi data, the tap data is designed to capture the co-complex relationships between proteins.
in addition to the above consensus matrices, we also calculate an affinity score matrix to capture the co-complex relationships directly from the tap data .
for tap data, several scoring methods have been proposed to measure the affinity between proteins based on the purification records  <cit> .
for example, c2s method  <cit>  has been recently developed for measuring the co-complex relationships among proteins.
in this paper, we further process the c2s scores by discarding the negative scores  and taking exponential transformation for the positive scores , and generate a matrix c. assume that c2sij is the original score between the proteins i and j, cij is our refined score as follows.
cij=1−exp,ifc2sij> <dig> ,ifc2sij≤ <dig>
let c  denote all the consensus matrices from the ensemble clustering and the score matrix derived from the tap data .
all of these m matrices describe the co-complex similarities among proteins, but in different scales and with different noise rates.
we next introduce the similarity network fusion  method  <cit>  to integrate these m heterogeneous matrices.
after defining similarity matrices c, the normalized weight matrices a are defined in eq.
.
the normalization here is free of the scale of self-similarity in the diagonal entries and avoids numerical instabilities and it satisfies ∑jaij= <dig>
aij=cij2∑v≠icivifj≠i, <dig> ifj=i
local neighborhoods are further exploited to measure the local affinities among proteins.
let vi denote the l  nearest neighbors of protein i in the matrix c .
to measure the local affinity, the local kernel matrix b is defined in eq.
.
by this operation, the l most similar proteins for each protein are kept and those neighbors with low similarities are filtered out.
therefore, b captures the local structure of similarity network corresponding to c. overall, a carries the full information about the similarity of each protein to all the others, while b only encodes the similarity to nearby proteins.
bij=cij∑v∈vicivifj∈vi, <dig> otherwise
let wt=0=a represent the initial status matrices at t= <dig>  snf is an iterative process to update the status matrix w in eq.
as follows:
wt+1=b×1m−1∑v≠mwt×bt.
another way to think of the updating rule  is:
wt+1=∑h∈vi∑l∈vjbi,h×1m−1∑v≠mwth,l×bj,l.
note vi represents the neighborhood of protein i in matrix c .
if proteins i and j have common neighbors in c or their neighbors in c have high similarity scores in other similarity matrices, their co-complex similarity will be augmented through these cross diffusion processes and vice versa.
therefore, even if protein i and j are not very similar in one data type, their similarity can be expressed in other data types, and this similarity information can be propagated through the fusion process.
we perform normalization on wt+ <dig> as in eq.
after each iteration  <cit> .
after t steps  are converged), we can automatically obtain the integrated similarity matrix w that fuses all these heterogeneous matrices in eq.
where m is  <dig>  since a is normalized and b retains the local similarities , the cross diffusion processes in eq.
are free of the scale and robust to the noise.
hence, the final similarity scores encoded in w would be more comprehensive and reliable.
w=1m∑m=1mwt.
detecting protein complexes via graph regularized doubly stochastic matrix decomposition model
in the above sections, we obtain the integrated similarity matrix w via a two-layer integration framework.
next, we present the graph regularized doubly stochastic matrix decomposition model to detect protein complexes from w.
model formulation
our objective is to infer p from w, which is the probability of assigning protein i to the predicted k-th complex.
if we cluster all proteins into k complexes, the complex assigning probabilities represent the single-step random walk probabilities from proteins to complexes.
without preference to any particular proteins, we impose uniform prior p=1/n over the proteins.
in this way, the reversed random walk probabilities can be calculated by the bayes formula:
p=pp∑z=1npp=p∑z=1np.
taking into account the probability of two-step random walks from protein i to protein j via all complexes:
p=∑k=1kpp=∑k=1kpp∑z=1np.
this probability defines the similarity between two proteins, Ŵij=p, according to their memberships with respect to all complexes.
note that w represents the observed similarity between proteins that arise from their co-complex relationships, the learning target is to find a good approximation between w and Ŵ. in this study, we use generalized kullback-leibler  divergence, which is suitable for the approximation w≈Ŵ, to measure the difference between Ŵ and w  <cit> .
the objective function is defined as the following optimization problem:
minθ≥0dkl=∑ijwijlogwijwij^−wij+Ŵij.s.t.∑k=1kθik= <dig> i= <dig> …,n.
where θik=p and Ŵij=∑k=1kθikθjk∑z=1nθzk.
moreover, as each element wij of the similarity matrix w reflect the observed co-complex similarity between protein i and j, protein pairs with high value of wij are supposed to have similar propensities to be involved in the same complexes.
as a popular manifold learning method, graph laplacian is widely used in semi-supervised learning to enforce smooth regularization for nodes with high similarities  <cit> .
given the similarity matrix w, the laplacian regularizer for the value of θ is defined as follows:
r=12∑i=1n∑j=1nwij∑k=1kθik−θjk2=trθtdθ−trθtwθ.
where tr denotes the trace of a matrix and d is a diagonal matrix defined by dii=∑j=1nwij.
by minimizing r, we wish the co-complex relationships inherent in w could transfer to the estimator of θ.
graph regularized doubly stochastic matrix decomposition model
taking into account the above two factors in eqs.
and , and dropping those constants, we present a novel graph regularized doubly stochastic matrix decomposition model with the following objective function:
minθ≥0j=∑ij−wijlogwij^+Ŵij+λtr−trs.t.∑k=1kθik= <dig> i= <dig> …,n.
where λ≥ <dig> is the tradeoff parameter that controls the balance between the two factors.
since the above objective function  is non-convex, we employ a relaxed majorization-minimization algorithm to find a good local minima  <cit> .
the update rule for θ is shown in algorithm ??.
please refer to additional file  <dig> for more details.
since the optimal solution θ^ik is a continuous value which describes the probability of assigning protein i to the predicted k-th complex, we need to discretize θ^ into a final protein-complex assignment matrix θ⋆.
in this study, to get overlapping protein complexes, for each protein i, we first sort θ^ik, k= <dig> …,k in descending order, then we retain the top ki complexes if the gap between the ki-th and -th element is the largest.
θik⋆= <dig> if k belongs to the top ki complexes, and θik⋆= <dig> otherwise.
here, θik⋆= <dig> represents protein i is assigned to the predicted k-th complex while θik⋆= <dig> indicates protein i does not belong to the predicted k-th complex.
in this study, we only consider predicted complexes with at least three proteins  <cit> .
RESULTS
in this section, we first introduce the experiment settings, i.e., experiment data and evaluation metrics.
then, we demonstrate an extensive comparison study between our proposed tincd method and various existing approaches for protein complex detection.
experiment data and evaluation metrics
in this study, two types of data  for yeast have been employed for evaluating the performance of various complex detection methods.
the binary ppi data is downloaded from the dip database  <cit> , which involves with  <dig>  interactions among  <dig>  proteins.
in addition, we consolidate the data from both  <cit>  and  <cit>  as our tap data, which consist of  <dig>  purifications involving  <dig>  bait proteins and  <dig>  prey proteins.
overall, the ppi data and tap data cover  <dig>  proteins.
we employ  <dig> benchmark complex sets as gold-standard to evaluate the complexes predicted by various methods, namely cyc <dig>  <cit> , mips  <cit>  and sgd  <cit> .
in particular, cyc <dig> consists of  <dig> complexes, mips with  <dig> and sgd with  <dig>  respectively.
for all the reference sets, to avoid selection bias, we filter out the proteins that are not involved in the input ppi and tap data.
moreover, we only consider complexes with at least  <dig> proteins as suggested by nepusz et al.
<cit> .
we utilize the sensitivity , positive predictive value , accuracy   <cit>  and frac  <cit>  to evaluate the predicted protein complexes.
given a benchmark complex xi and a predicted complex yj, the sn and ppv are defined in eq.
, and accuracy is the geometric mean of sn and ppv.
using accuracy is better than sn and ppv individually, as it can provide a balanced view of the prediction performance.
sn=∑imaxjti,j∑i|xi|,ppv=∑jmaxiti,j∑j|∪i|,accuracy=sn×ppv
where ti,j is the number of proteins shared by xi and yj, i.e., |xi∩yj|.
fraction of matched complexes   <cit>  is an indicator for prediction coverage, which measures the percentage of benchmark complexes that are matched by the predicted complexes.
given xi and yj, we consider them to be matching if |xi∩yj|2|xi||yj|≥ω .
frac is defined in eq.
, where x is the set of benchmark complexes and q is the set of predicted complexes.
frac=xi|xi∈x∧∃yj∈q,yjmatchesxi|x|.
parameter settings
there are two parameters k and λ in our model, where k is the number of possible complexes and λ controls the effects of the laplacian regularizer.
since we usually do not have any prior knowledge about the number of complexes in real-world situations, it is hard to decide the value of k. fortunately, we have introduced a graph regularization to force proteins with high co-complex similarity scores to have similar memberships.
by controlling the effect of this regularization term, we may be able to filter out the irrelevant dimensions of θ. if so, we can fit our model with a large value of k as our model is able to determine the number of complexes adaptively.
therefore, to test how these two parameters affect the performance of our model, we have performed the sensitivity studies.
particularly, we consider all combinations of the following values: { <dig> ,2500} for k and {2− <dig> − <dig> …,27} for λ, and assess how well the complexes predicted by our model match with reference sets.
the performance of tincd is measured by accuracy with respect to mips gold standard.
as shown in fig.
<dig>  for a fixed value of k, as the value of λ increases, the value of accuracy fluctuates slightly in the beginning and then increases steadily until converge.
overall, tincd obtains competitive accuracy scores when λ∈ <cit> .
on the other hand, when the value of λ is less than  <dig>  the larger the value of k, the worse the effect of tincd.
we can also find that with the increase of the value of λ, the influence of k is waning.
a possible reason would be that we use graph regularization to force proteins with high co-complex similarity scores to have similar memberships.
when the value of λ is large enough, irrelevant latent indexes always obtain lower associations.
therefore, tincd is not very sensitive to the value of k when λ is large enough.
in this case, the value of k could be relatively large since irrelevant clusters will be automatically filtered out.
based on the above sensitivity analysis as shown in fig.
<dig>  k= <dig> and λ= <dig> would be the optimal setting for parameters k and λ on mips data.
to avoid overestimating the performance of tincd, we will also set k= <dig> and λ= <dig> as the default values on other benchmark sets .
fig.
<dig> the effect of λ and k. performance of tincd on protein complex detection with different values of λ and k measured by accuracy with respect to mips gold standard.
the x-axis denotes the value of logλ, the y-axis denotes the value of accuracy
similarity network fusion  vs. matrix averaging
in the experiments, the consensus matrices are built via integrating various base clustering results from ppi data and tap data.
in particular,  <dig> state-of-the-art approaches are applied to ppi data to generate complexes, including cfinder  <cit> , cmc  <cit> , coach  <cit> , clusterone  <cit> , dpclus  <cit> , ipca  <cit> , mcl  <cit> , mcode  <cit> , rnsc  <cit> , rrw  <cit>  and spici  <cit> .
in this study, optimal parameters are set for cfinder, cmc, coach, dpclus, ipca, mcl, mcode, rrw and spici to generate their best results while clusterone and rnsc have used the default parameters set by the authors.
for detailed parameter settings of these algorithms, please refer to additional file  <dig>  the consensus matrix based on these  <dig> base clustering solutions is denoted as p. we also collect the complexes predicted from tap data by  <dig> existing methods, including bt  <cit> , c2s  <cit> , cachet  <cit> , hart  <cit>  and pu  <cit> .
protein complexes predicted by these  <dig> methods are downloaded from http://www.ntu.edu.sg/home/zhengjie/data/intehc/.
the consensus matrix based on these  <dig> solutions for tap data is denoted as t. in addition, p+t denotes the combination of two consensus matrices p and t. snf is thus applied to integrate the c2s matrix with the consensus matrices .
in addition, a natural way to integrate these matrices is to take an average for them, and we denote this method as matrix averaging.
next, we will take matrix averaging as baseline and compare it with the snf method.
fig.
<dig> snf vs. matrix averaging.
performance of snf and matrix averaging in terms of a
accuracy and b frac with respect to cyc2008
moreover, we have two observations by comparing the performance of different consensus matrices as shown in fig.
<dig>
firstly, integrated with c2s matrix via snf, the consensus matrix p performs much better than t. for example with reference data cyc <dig>  c2s+p and c2s+t obtain comparable accuracy, while c2s+p has a higher frac than c2s+t .
the rationale behind this finding would be that t is redundant with c2s to some extent , while p complements c2s well  to achieve better performance.
secondly, by adding t to c2s+p, c2s+p+t achieves better performance than c2s+p.
comparing c2s+p with respect to cyc <dig>  the accuracy of c2s+p+t is increased by  <dig>  % from  <dig>  to  <dig>  while its frac is increased by  <dig>  % from  <dig>  to  <dig> .
as shown in additional file  <dig>  both accuracy and frac of c2s+p+t are improved on sgd benchmark complexes, i.e., the accuracy improves by  <dig>  % from  <dig>  to  <dig>  and the frac increases by  <dig>  % from  <dig>  to  <dig> .
overall, we would think that c2s+p+t performs better than c2s+p and c2s+t, and our tincd refers to the clustering over c2s+p+t thereafter.
clustering the integrated matrix
once we obtained the integrated matrix , we are able to apply various clustering methods to generate protein complexes in our framework, e.g., nonnegative matrix factorization  and agglomerative hierarchical clustering .
since the integrated matrix corresponds to a weighted network, and only few methods can deal with large scale weighted networks.
in this section, we will compare our proposed graph regularized doubly stochastic matrix decomposition model with nmf, hc, clusterone and spici.
all of these four algorithms are able to detect complexes from weighted ppi networks directly and output the results in a reasonable time.
in particular, nmf is a popular clustering algorithm which can be related to a generalized form of many clustering methods   <cit> .
in this study, nmf is solved by dtu:toolbox  <cit>  via multiplicative update method.
for hc, it first considers all singleton proteins as initial clusters, then it iteratively merges two clusters with the highest similarity in each iteration.
the iterative algorithm terminates when quality function of the detected clusters has achieved its maximal value.
similar to  <cit> , three quality functions are used to measure the quality of a set of clusters, the corresponding results are thus denoted by hc-q <dig>  hc-q <dig> and hc-q <dig> respectively.
for more details about these three quality functions, please refer to  <cit> .
for a fair comparison, optimal parameters are set for these four algorithms to generate its best results .
fig.
<dig> clustering the integrated matrix.
accuracy and frac of tincd, nmf, hierarchical clustering with  <dig> different quality functions , clusterone and spici with respect to cyc2008
comparisons with base clustering solutions
as introduced above, we collected  <dig> base solutions  to generate protein complexes.
next, we compare tincd with these  <dig> base solutions in terms of their accuracy and frac over  <dig> benchmark complex sets.
table  <dig> comparison between tincd and state-of-the-art methods with respect to cyc2008
an observation in table  <dig> is that  <dig> base solutions for tap data are much better than those  <dig> base solutions for ppi data.
the consensus matrix p generated by these weaker base solutions for ppi data, however, performs much better than t as shown in fig.
<dig>  this observation highlights once again that the consensus matrix p from ppi data is a good complement to c2s score matrix for protein complex detection.
comparison with ensemble clustering
we further compared tincd with ec-bnmf , which generated ensemble clusters from the above  <dig> base clustering solutions.
for a fair comparison, optimal parameters are set for ec-bnmf to generate its best results.
for detailed parameter settings of ec-bnmf, please refer to additional file  <dig>  figure  <dig> shows the accuracy and frac of tincd and ec-bnmf with respect to cyc <dig>
fig.
<dig> comparison with ensemble clustering.
accuracy and frac of tincd and ec-bnmf with respect to cyc2008
in fig.
<dig>  tincd achieves higher accuracy than ec-bnmf .
in addition, tincd achieves a frac  <dig> , which is  <dig>  % higher than ec-bnmf .
hence, tincd outperforms the ensemble clustering method ec-bnmf in terms of both accuracy and frac .
comparison with data integration techniques
in addition to ensemble clustering techniques which integrate clustering results, another type of integrative techniques aims to integrate diverse data sources for protein complex detection.
for example, cmbi integrates ppi data, gene expression profiles and essential protein information to detect protein complexes, while intehc integrates ppi data, tap data, gene expression profiles and gene ontology annotations for protein complex prediction.
next, we compare our tincd with data integration techniques cmbi and intehc.
protein complexes predicted by cmbi and intehc are downloaded from http://www.ntu.edu.sg/home/zhengjie/data/intehc/.
fig.
<dig> comparison with data integration techniques.
accuracy and frac of cmbi, intehc and tincd with respect to cyc2008
intehc integrates various data sources and utilizes some supervision information to assign them different weights according to their importance.
among various raw data sources, tincd integrates only the c2s scores with consensus matrices in an unsupervised manner and thus is more preferable.
the overall better results achieved by tincd in the more challenging unsupervised setting demonstrate that tincd is able to achieve better frac , at the same time to maintain a high accuracy.
in the future, it would be promising if we integrate more data sources  into our tincd framework.
a case study: the fbp degradation complexfig.
<dig> examples of benchmark protein complexes predicted more accurately by tincd.
the fbp degradation complex as detected by different computational methods.
the shadow area shows the complex predicted by each method, red circle nodes represent subunits of the fbp degradation complex in cyc <dig>  and blue rectangle nodes represent proteins belong to other complexes.
in addition, dash lines represent physical interactions and solid lines refer to the pairs with positive c2s scores
discussions and
CONCLUSIONS
in this work, we have proposed a novel two-layer integration framework tincd to identify protein complexes.
first, tincd constructs consensus matrices for proteins and measures their co-complex propensity based on the complex knowledge discovered by various graph clustering results.
second, a similarity network fusion  strategy is employed by tincd to combine consensus matrices and score matrix obtained from tap data to obtain a final co-complex score matrix.
finally, a novel graph regularized doubly stochastic matrix decomposition model is proposed to detect overlapping protein complexes from the final score matrix.
experiment comparisons show that tincd significantly outperforms  <dig> existing state-of-the-art protein complex identification methods in terms of accuracy and frac.
in addition, our model is a flexible and generic framework, which allows us to include more data sources  by simple matrix operations.
when evaluating the predicted clusters over a reference set, other commonly used evaluation metrics include sensitivity, specificity and f-measure.
the detailed definition of these three measures and the evaluation results of various algorithms in terms of these three measures are listed in additional file  <dig>  as shown in table  <dig>  our tincd predicts  <dig>  complexes covering  <dig>  proteins, which is very close to the size of input data with  <dig>  proteins.
we note that the data set used in our study contains  <dig>  proteins, while the three gold standard sets  cover  <dig> ,  <dig>  and  <dig>  proteins.
that is, the gold standard sets are far from complete.
thus, most of our predicted complexes are not able to match the benchmark complexes and tincd achieves a low specificity .
however, predicted protein complexes that do not match with reference complexes are not necessarily undesired results and they would probably be novel protein complexes  <cit> .
therefore, optimizing specificity and f-measure will somehow prevent us from detecting novel complexes.
on the other hand, as discussed in  <cit> , accuracy and frac are more suitable to evaluate the performance of an overlapping protein complex detection algorithm.
furthermore, we also analyze the importance of an individual base clustering solution for tincd, and investigate the correlation between the number of base clustering solutions and the performance of tincd.
however, since tincd not only perform result-level integration, but also perform data-level integration, as shown in additional file 1: table s <dig>  the effect of removing a base solution in result-level integration will be attenuated by the further operations in data-level integration.
as shown in additional file 1: table s <dig>  the performance of tincd does not change a lot when the consensus matrix of ppi data are constructed using  <dig> base clustering solutions.
thus, the correlation between the number of methods and the performance of tincd depends on the quality of the used methods.
ideally, we would think that we are able to construct more accurate consensus matrices and tincd can generate more accurate prediction results, provided that more base clustering solutions with good performance are available.
in summary, compared with existing methods, our model has the advantages as follows.
our tincd model, leveraging the information from both the clustering results and raw data sources, generates more comprehensive and reliable results.
the similarity network fusion  model, integrating heterogeneous matrices into a final co-complex score matrix, is free of scale and robust to the noise in the data.
the graph regularized doubly stochastic matrix decomposition model considers the sparse similarities and thus ensures relatively balanced clusters.
tincd generates the overlapping protein complexes, which clearly reflect the biological reality on proteins’ multi-functional roles.
finally, tincd is unsupervised and is thus generic enough for the integration of different types of data sources.
the computational complexity for updating θ in algorithm  <dig> is o, where e is the number of non-zero items in w, n is the number of proteins in the data and k is the pre-defined number of complexes.
therefore the overall time cost of the graph regularized doubly stochastic matrix decomposition model is okiter), where iter is the number of iterations.
in the experiments, we implement the algorithm using matlab in a laptop with intel  <dig> cpu  and  <dig> gb ram.
the time cost of calculating the final co-complex score matrix is at most  <dig> seconds .
each update of θ costs at most  <dig> seconds and the entire estimation takes less than  <dig>  seconds when the maximum number of iterations is set to  <dig>  frankly, our tincd has a relatively higher computational cost compared with some base solutions.
however, we would think that the running time for tincd is still affordable for the following reasons.
first, our primary task is to predict protein complexes with better accuracy and coverage.
to achieve this goal, we integrate multiple data sources for clustering and it makes sense that we will higher computational cost as a sacrifice.
second, as discussed in  <cit> , in the context of understanding and exploiting the structure of ppi networks, cluster analysis is usually used as an “offline” process to provide a comprehensive set of clustering results.
it is thus acceptable that “offline”, processes have longer running time.
third, ppi data is indeed growing in recent years.
the computing power of hardware  is also under a rapid development.
moreover, we can also consider to parallelize the integration process for speedup.
regarding the future works, we plan to design an algorithm that could incorporate other data sources   <cit>  in addition to protein interaction data for protein complex detection.
we would expect higher prediction accuracy by considering more features for proteins.
availability of supporting data
the datasets supporting the results of this article are included within its additional files.
all the experimental results and code can be downloaded from https://github.com/oyl-cityu/tincd.
additional file
additional file  <dig>
supplementary figures and text.
this section provides the supplementary figures referred in the main text and some text which describes the detailed inference of the solution to tincd and several biological case studies.
competing interests
the authors declare that they have no competing interests.
authors’ contributions
loy conceived and designed the study, performed the statistical analysis and drafted the manuscript.
mw conceived of the study, and participated in its design and coordination and helped to draft the manuscript.
xfz participated in the design of the study, performed the statistical analysis and helped to revise the manuscript.
dqd participated in the design of the study and helped to revise the manuscript.
xll participated in the design of the study and helped to revise the manuscript.
hy participated in the design of the study and helped to revise the manuscript.
all authors read and approved the final manuscript.

 understanding the structural and functional architecture of the cell has been a fundamental task for systems biology. as vital macromolecules, proteins do not act individually, but work by interacting with other partners. almost all of the functional processes within a cell are carried out by protein complexes which are formed by interacting proteins. therefore, detecting protein complexes from protein-protein interaction data is crucial for elucidating the modular structure within cells. in recent years, high-throughput screening techniques have been designed to detect protein-protein interactions, e.g., yeast two-hybrid and tandem affinity purification/mass spectrometry. such hts techniques have already generated a large amount of ppi data, which facilitate the development of computational methods for protein complex detection. generally, computational methods for protein complex detection utilize two types of data, namely, the binary protein interaction data detected by hts techniques such as y2h method, and the data for co-complex interactions among proteins from tap experiments. here, we denote the above two types of data as ppi data and tap data respectively. ppi data is usually modeled as a graph where nodes represent proteins and edges represent protein interactions. a number of graph clustering algorithms have been proposed for detecting protein complexes from ppi networks, such as mcode, cfinder, mcl, rnsc, coach and clusterone. on the other hand, raw data from tap experiments is a list of bait proteins along with their corresponding prey proteins that they pulled out, which could be modeled as a bipartite graph. several algorithms have been proposed to identify protein complexes from tap data as well. a common strategy is to first define affinity scores between proteins based on the purification records and then convert the tap data to a ppi network by using a threshold method to keep those reliable interactions for further analysis. since convert the original tap data into a binary ppi network not only introduces errors but also loses useful information in the raw data, another alternative strategy is to detect complexes from the tap data directly, such as cachet. as diverse sources of protein interaction data are available, data integration becomes a common methodology to reduce the noise in ppi and tap data and to improve the coverage for protein complex detection. for example, decaff exploited the gene ontology annotations to assess the reliability of ppi data and then detected protein complexes from the refined ppi data; matisse and cmbi integrated gene expression data with ppi data to increase the confidence of interactions for protein complex detection. intehc integrated four data sources and significantly improved the complex detection. in particular, intehc calculated a score matrix for each of the four data sources and took their weighted sum, which relies on additional supervision information to learn a weight for each data source, as an integrated matrix. however, due to noise in different data sources, the direct fusion of several original datasets may exacerbate the problems of noise. moreover, how to correctly estimate the co-complex relationships between proteins based on their functional annotations and gene expression profiles is still an open problem. nevertheless, with various methods proposed for protein complex detection, we are thus able to generate a series of clustering results for each type of data. clearly, given one type of data, each method has its own advantages and limitations in capturing co-complex relationships between proteins. ensemble clustering, which exploits the complementary nature of individual methods by leveraging their clustering outputs, is thus promising to improve the detection for protein complexes. particularly, ensemble clustering methods usually first reconstruct a consensus matrix which shows the co-complex propensity among proteins from a series of clustering results and then apply a specific algorithm to detect protein complexes from the consensus matrix. however, the consensus network, based solely on the result-level integration, may miss the underlying complex information which exist in other types of data. it is thus necessary to combine the consensus matrices derived from multiple types of data to generate a more comprehensive and reliable co-complex similarity matrix, which may facilitate the detection of protein complexes. different from y2h experiments that are prone to identify direct physical interactions, tap experiments already provide useful information about protein complexes and tap data describe the co-complex propensity among proteins. however, as tap data cannot be converted into co-complex interactions in a straightforward manner, several scoring methods have been proposed to estimate the affinity scores between proteins based on the purification records provided by tap data, such as c2s scores. as such, we are able to integrate heterogeneous matrices, i.e., the consensus matrices derived from different types of data and the co-complex score matrices derived from tap data, to better understand the co-complex relationships among proteins. however, as these heterogeneous matrices may have different scales, noise rates and importance levels, focusing only on common patterns can miss valuable complementary information. it would be challenging to merge them into a final co-complex matrix automatically in an unsupervised manner. in addition, once we obtain the integrated matrix, it is still difficult for us to design an efficient algorithm to detect overlapping complexes from this integrated matrix. to address the above challenges, we propose a novel two-layer integrative complex detection model to predict protein complexes as shown in fig. which leverages the information from both clustering results and raw data sources. in the first layer integration, we utilize an ensemble method to construct consensus matrices for different types of data to measure the co-complex propensities between proteins based on various clustering results. in the second layer integration, we combine the consensus matrices derived from different types of data with the score matrix derived from tap data and obtain an integrated similarity network via a similarity network fusion method. snf is an iterative process to fuse heterogeneous networks or matrices by capturing both shared and complementary information among them. finally, a novel graph regularized doubly stochastic matrix decomposition model is proposed to detect overlapping protein complexes from the integrated similarity network. we have conducted comprehensive experiments to evaluate the performance of our proposed tincd algorithm. a comprehensive comparison with existing methods shows that our two-layer integration strategy generates protein complexes with better coverage and accuracy. all the experimental results and code can be downloaded from https://github.com/oyl-cityu/tincd. fig. schematic overview of our proposed tincd model. tincd first constructs two consensus matrices and c ) based on the complex knowledge discovered by various graph clustering algorithms from ppi and tap data. second, a similarity network fusion strategy is employed by tincd to combine these two consensus matrices with the score matrix obtained from tap data ) to obtain a final co-complex score matrix. finally, a novel graph regularized doubly stochastic matrix decomposition model is proposed to detect overlapping protein complexes from the final score matrix methods in this section, we describe our tincd model as shown in fig. in details. we first demonstrate the two-layer integration and then present the graph regularized doubly stochastic matrix decomposition algorithm for protein complex detection. first layer integration: result-level integration via ensemble clustering as diverse types of data are available and various computational methods have been designed to detect protein complexes from them, we are thus able to generate a series of base clustering results. a straightforward way to measure the co-complex affinities among proteins is to build the consensus matrices by integrating the above abundant clustering results. suppose all the data sources used in this study cover n proteins and we have obtained np clustering results which are generated by applying np different methods on a specific type of data. here, a clustering result refers to a set of clusters generated by a certain method. a consensus matrix c is a n×n matrix. in c, the entry cij is the number of clustering results where the proteins i and j are assigned to the same cluster, divided by the number of clustering results np. as such, each entry cij indicates the probabilities that protein i and j are involving in the same complexes. if protein i is not assigned to any clusters or is not included in the m-th data source, the i-th row and i-th column of c are set to zero. note that the coverage and quality of different data sources would be different. we thus build a corresponding consensus matrix independently for each type of data. in this study, we focus on two data sources, namely, ppi data and tap data. therefore, the consensus matrices corresponding to these two types of data are denoted by c and c respectively. second layer integration: integrating heterogeneous co-complex matrices via similarity network fusion unlike ppi data, the tap data is designed to capture the co-complex relationships between proteins. in addition to the above consensus matrices, we also calculate an affinity score matrix to capture the co-complex relationships directly from the tap data. for tap data, several scoring methods have been proposed to measure the affinity between proteins based on the purification records. for example, c2s method has been recently developed for measuring the co-complex relationships among proteins. in this paper, we further process the c2s scores by discarding the negative scores and taking exponential transformation for the positive scores, and generate a matrix c. assume that c2sij is the original score between the proteins i and j, cij is our refined score as follows. cij=1−exp,ifc2sij>,ifc2sij≤ let c denote all the consensus matrices from the ensemble clustering and the score matrix derived from the tap data. all of these m matrices describe the co-complex similarities among proteins, but in different scales and with different noise rates. we next introduce the similarity network fusion method to integrate these m heterogeneous matrices. after defining similarity matrices c, the normalized weight matrices a are defined in eq.. the normalization here is free of the scale of self-similarity in the diagonal entries and avoids numerical instabilities and it satisfies ∑jaij= aij=cij2∑v≠icivifj≠i, ifj=i local neighborhoods are further exploited to measure the local affinities among proteins. let vi denote the l nearest neighbors of protein i in the matrix c. to measure the local affinity, the local kernel matrix b is defined in eq.. by this operation, the l most similar proteins for each protein are kept and those neighbors with low similarities are filtered out. therefore, b captures the local structure of similarity network corresponding to c. overall, a carries the full information about the similarity of each protein to all the others, while b only encodes the similarity to nearby proteins. bij=cij∑v∈vicivifj∈vi, otherwise let wt=0=a represent the initial status matrices at t= snf is an iterative process to update the status matrix w in eq. as follows: wt+1=b×1m−1∑v≠mwt×bt. another way to think of the updating rule is: wt+1=∑h∈vi∑l∈vjbi,h×1m−1∑v≠mwth,l×bj,l. note vi represents the neighborhood of protein i in matrix c. if proteins i and j have common neighbors in c or their neighbors in c have high similarity scores in other similarity matrices, their co-complex similarity will be augmented through these cross diffusion processes and vice versa. therefore, even if protein i and j are not very similar in one data type, their similarity can be expressed in other data types, and this similarity information can be propagated through the fusion process. we perform normalization on wt+ as in eq. after each iteration. after t steps are converged), we can automatically obtain the integrated similarity matrix w that fuses all these heterogeneous matrices in eq. where m is since a is normalized and b retains the local similarities, the cross diffusion processes in eq. are free of the scale and robust to the noise. hence, the final similarity scores encoded in w would be more comprehensive and reliable. w=1m∑m=1mwt. detecting protein complexes via graph regularized doubly stochastic matrix decomposition model in the above sections, we obtain the integrated similarity matrix w via a two-layer integration framework. next, we present the graph regularized doubly stochastic matrix decomposition model to detect protein complexes from w. model formulation our objective is to infer p from w, which is the probability of assigning protein i to the predicted k-th complex. if we cluster all proteins into k complexes, the complex assigning probabilities represent the single-step random walk probabilities from proteins to complexes. without preference to any particular proteins, we impose uniform prior p=1/n over the proteins. in this way, the reversed random walk probabilities can be calculated by the bayes formula: p=pp∑z=1npp=p∑z=1np. taking into account the probability of two-step random walks from protein i to protein j via all complexes: p=∑k=1kpp=∑k=1kpp∑z=1np. this probability defines the similarity between two proteins, Ŵij=p, according to their memberships with respect to all complexes. note that w represents the observed similarity between proteins that arise from their co-complex relationships, the learning target is to find a good approximation between w and Ŵ. in this study, we use generalized kullback-leibler divergence, which is suitable for the approximation w≈Ŵ, to measure the difference between Ŵ and w. the objective function is defined as the following optimization problem: minθ≥0dkl=∑ijwijlogwijwij^−wij+Ŵij.s.t.∑k=1kθik= i= …,n. where θik=p and Ŵij=∑k=1kθikθjk∑z=1nθzk. moreover, as each element wij of the similarity matrix w reflect the observed co-complex similarity between protein i and j, protein pairs with high value of wij are supposed to have similar propensities to be involved in the same complexes. as a popular manifold learning method, graph laplacian is widely used in semi-supervised learning to enforce smooth regularization for nodes with high similarities. given the similarity matrix w, the laplacian regularizer for the value of θ is defined as follows: r=12∑i=1n∑j=1nwij∑k=1kθik−θjk2=trθtdθ−trθtwθ. where tr denotes the trace of a matrix and d is a diagonal matrix defined by dii=∑j=1nwij. by minimizing r, we wish the co-complex relationships inherent in w could transfer to the estimator of θ. graph regularized doubly stochastic matrix decomposition model taking into account the above two factors in eqs. and, and dropping those constants, we present a novel graph regularized doubly stochastic matrix decomposition model with the following objective function: minθ≥0j=∑ij−wijlogwij^+Ŵij+λtr−trs.t.∑k=1kθik= i= …,n. where λ≥ is the tradeoff parameter that controls the balance between the two factors. since the above objective function is non-convex, we employ a relaxed majorization-minimization algorithm to find a good local minima. the update rule for θ is shown in algorithm??. please refer to additional file for more details. since the optimal solution θ^ik is a continuous value which describes the probability of assigning protein i to the predicted k-th complex, we need to discretize θ^ into a final protein-complex assignment matrix θ⋆. in this study, to get overlapping protein complexes, for each protein i, we first sort θ^ik, k= …,k in descending order, then we retain the top ki complexes if the gap between the ki-th and -th element is the largest. θik⋆= if k belongs to the top ki complexes, and θik⋆= otherwise. here, θik⋆= represents protein i is assigned to the predicted k-th complex while θik⋆= indicates protein i does not belong to the predicted k-th complex. in this study, we only consider predicted complexes with at least three proteins.  in this section, we first introduce the experiment settings, i.e., experiment data and evaluation metrics. then, we demonstrate an extensive comparison study between our proposed tincd method and various existing approaches for protein complex detection. experiment data and evaluation metrics in this study, two types of data for yeast have been employed for evaluating the performance of various complex detection methods. the binary ppi data is downloaded from the dip database, which involves with interactions among proteins. in addition, we consolidate the data from both and as our tap data, which consist of purifications involving bait proteins and prey proteins. overall, the ppi data and tap data cover proteins. we employ benchmark complex sets as gold-standard to evaluate the complexes predicted by various methods, namely cyc, mips and sgd. in particular, cyc consists of complexes, mips with and sgd with respectively. for all the reference sets, to avoid selection bias, we filter out the proteins that are not involved in the input ppi and tap data. moreover, we only consider complexes with at least proteins as suggested by nepusz et al.. we utilize the sensitivity, positive predictive value, accuracy and frac to evaluate the predicted protein complexes. given a benchmark complex xi and a predicted complex yj, the sn and ppv are defined in eq., and accuracy is the geometric mean of sn and ppv. using accuracy is better than sn and ppv individually, as it can provide a balanced view of the prediction performance. sn=∑imaxjti,j∑i|xi|,ppv=∑jmaxiti,j∑j|∪i|,accuracy=sn×ppv where ti,j is the number of proteins shared by xi and yj, i.e., |xi∩yj|. fraction of matched complexes is an indicator for prediction coverage, which measures the percentage of benchmark complexes that are matched by the predicted complexes. given xi and yj, we consider them to be matching if |xi∩yj|2|xi||yj|≥ω. frac is defined in eq., where x is the set of benchmark complexes and q is the set of predicted complexes. frac=xi|xi∈x∧∃yj∈q,yjmatchesxi|x|. parameter settings there are two parameters k and λ in our model, where k is the number of possible complexes and λ controls the effects of the laplacian regularizer. since we usually do not have any prior knowledge about the number of complexes in real-world situations, it is hard to decide the value of k. fortunately, we have introduced a graph regularization to force proteins with high co-complex similarity scores to have similar memberships. by controlling the effect of this regularization term, we may be able to filter out the irrelevant dimensions of θ. if so, we can fit our model with a large value of k as our model is able to determine the number of complexes adaptively. therefore, to test how these two parameters affect the performance of our model, we have performed the sensitivity studies. particularly, we consider all combinations of the following values: {,2500} for k and {2− − …,27} for λ, and assess how well the complexes predicted by our model match with reference sets. the performance of tincd is measured by accuracy with respect to mips gold standard. as shown in fig. for a fixed value of k, as the value of λ increases, the value of accuracy fluctuates slightly in the beginning and then increases steadily until converge. overall, tincd obtains competitive accuracy scores when λ∈. on the other hand, when the value of λ is less than the larger the value of k, the worse the effect of tincd. we can also find that with the increase of the value of λ, the influence of k is waning. a possible reason would be that we use graph regularization to force proteins with high co-complex similarity scores to have similar memberships. when the value of λ is large enough, irrelevant latent indexes always obtain lower associations. therefore, tincd is not very sensitive to the value of k when λ is large enough. in this case, the value of k could be relatively large since irrelevant clusters will be automatically filtered out. based on the above sensitivity analysis as shown in fig. k= and λ= would be the optimal setting for parameters k and λ on mips data. to avoid overestimating the performance of tincd, we will also set k= and λ= as the default values on other benchmark sets. fig. the effect of λ and k. performance of tincd on protein complex detection with different values of λ and k measured by accuracy with respect to mips gold standard. the x-axis denotes the value of logλ, the y-axis denotes the value of accuracy similarity network fusion vs. matrix averaging in the experiments, the consensus matrices are built via integrating various base clustering results from ppi data and tap data. in particular, state-of-the-art approaches are applied to ppi data to generate complexes, including cfinder, cmc, coach, clusterone, dpclus, ipca, mcl, mcode, rnsc, rrw and spici. in this study, optimal parameters are set for cfinder, cmc, coach, dpclus, ipca, mcl, mcode, rrw and spici to generate their best results while clusterone and rnsc have used the default parameters set by the authors. for detailed parameter settings of these algorithms, please refer to additional file the consensus matrix based on these base clustering solutions is denoted as p. we also collect the complexes predicted from tap data by existing methods, including bt, c2s, cachet, hart and pu. protein complexes predicted by these methods are downloaded from http://www.ntu.edu.sg/home/zhengjie/data/intehc/. the consensus matrix based on these solutions for tap data is denoted as t. in addition, p+t denotes the combination of two consensus matrices p and t. snf is thus applied to integrate the c2s matrix with the consensus matrices. in addition, a natural way to integrate these matrices is to take an average for them, and we denote this method as matrix averaging. next, we will take matrix averaging as baseline and compare it with the snf method. fig. snf vs. matrix averaging. performance of snf and matrix averaging in terms of a accuracy and b frac with respect to cyc2008 moreover, we have two observations by comparing the performance of different consensus matrices as shown in fig. firstly, integrated with c2s matrix via snf, the consensus matrix p performs much better than t. for example with reference data cyc c2s+p and c2s+t obtain comparable accuracy, while c2s+p has a higher frac than c2s+t. the rationale behind this finding would be that t is redundant with c2s to some extent, while p complements c2s well to achieve better performance. secondly, by adding t to c2s+p, c2s+p+t achieves better performance than c2s+p. comparing c2s+p with respect to cyc the accuracy of c2s+p+t is increased by % from to while its frac is increased by % from to. as shown in additional file both accuracy and frac of c2s+p+t are improved on sgd benchmark complexes, i.e., the accuracy improves by % from to and the frac increases by % from to. overall, we would think that c2s+p+t performs better than c2s+p and c2s+t, and our tincd refers to the clustering over c2s+p+t thereafter. clustering the integrated matrix once we obtained the integrated matrix, we are able to apply various clustering methods to generate protein complexes in our framework, e.g., nonnegative matrix factorization and agglomerative hierarchical clustering. since the integrated matrix corresponds to a weighted network, and only few methods can deal with large scale weighted networks. in this section, we will compare our proposed graph regularized doubly stochastic matrix decomposition model with nmf, hc, clusterone and spici. all of these four algorithms are able to detect complexes from weighted ppi networks directly and output the results in a reasonable time. in particular, nmf is a popular clustering algorithm which can be related to a generalized form of many clustering methods. in this study, nmf is solved by dtu:toolbox via multiplicative update method. for hc, it first considers all singleton proteins as initial clusters, then it iteratively merges two clusters with the highest similarity in each iteration. the iterative algorithm terminates when quality function of the detected clusters has achieved its maximal value. similar to, three quality functions are used to measure the quality of a set of clusters, the corresponding results are thus denoted by hc-q hc-q and hc-q respectively. for more details about these three quality functions, please refer to. for a fair comparison, optimal parameters are set for these four algorithms to generate its best results. fig. clustering the integrated matrix. accuracy and frac of tincd, nmf, hierarchical clustering with different quality functions, clusterone and spici with respect to cyc2008 comparisons with base clustering solutions as introduced above, we collected base solutions to generate protein complexes. next, we compare tincd with these base solutions in terms of their accuracy and frac over benchmark complex sets. table comparison between tincd and state-of-the-art methods with respect to cyc2008 an observation in table is that base solutions for tap data are much better than those base solutions for ppi data. the consensus matrix p generated by these weaker base solutions for ppi data, however, performs much better than t as shown in fig. this observation highlights once again that the consensus matrix p from ppi data is a good complement to c2s score matrix for protein complex detection. comparison with ensemble clustering we further compared tincd with ec-bnmf, which generated ensemble clusters from the above base clustering solutions. for a fair comparison, optimal parameters are set for ec-bnmf to generate its best results. for detailed parameter settings of ec-bnmf, please refer to additional file figure shows the accuracy and frac of tincd and ec-bnmf with respect to cyc fig. comparison with ensemble clustering. accuracy and frac of tincd and ec-bnmf with respect to cyc2008 in fig. tincd achieves higher accuracy than ec-bnmf. in addition, tincd achieves a frac, which is % higher than ec-bnmf. hence, tincd outperforms the ensemble clustering method ec-bnmf in terms of both accuracy and frac. comparison with data integration techniques in addition to ensemble clustering techniques which integrate clustering results, another type of integrative techniques aims to integrate diverse data sources for protein complex detection. for example, cmbi integrates ppi data, gene expression profiles and essential protein information to detect protein complexes, while intehc integrates ppi data, tap data, gene expression profiles and gene ontology annotations for protein complex prediction. next, we compare our tincd with data integration techniques cmbi and intehc. protein complexes predicted by cmbi and intehc are downloaded from http://www.ntu.edu.sg/home/zhengjie/data/intehc/. fig. comparison with data integration techniques. accuracy and frac of cmbi, intehc and tincd with respect to cyc2008 intehc integrates various data sources and utilizes some supervision information to assign them different weights according to their importance. among various raw data sources, tincd integrates only the c2s scores with consensus matrices in an unsupervised manner and thus is more preferable. the overall better results achieved by tincd in the more challenging unsupervised setting demonstrate that tincd is able to achieve better frac, at the same time to maintain a high accuracy. in the future, it would be promising if we integrate more data sources into our tincd framework. a case study: the fbp degradation complexfig. examples of benchmark protein complexes predicted more accurately by tincd. the fbp degradation complex as detected by different computational methods. the shadow area shows the complex predicted by each method, red circle nodes represent subunits of the fbp degradation complex in cyc and blue rectangle nodes represent proteins belong to other complexes. in addition, dash lines represent physical interactions and solid lines refer to the pairs with positive c2s scores discussions and  in this work, we have proposed a novel two-layer integration framework tincd to identify protein complexes. first, tincd constructs consensus matrices for proteins and measures their co-complex propensity based on the complex knowledge discovered by various graph clustering results. second, a similarity network fusion strategy is employed by tincd to combine consensus matrices and score matrix obtained from tap data to obtain a final co-complex score matrix. finally, a novel graph regularized doubly stochastic matrix decomposition model is proposed to detect overlapping protein complexes from the final score matrix. experiment comparisons show that tincd significantly outperforms existing state-of-the-art protein complex identification methods in terms of accuracy and frac. in addition, our model is a flexible and generic framework, which allows us to include more data sources by simple matrix operations. when evaluating the predicted clusters over a reference set, other commonly used evaluation metrics include sensitivity, specificity and f-measure. the detailed definition of these three measures and the evaluation results of various algorithms in terms of these three measures are listed in additional file as shown in table our tincd predicts complexes covering proteins, which is very close to the size of input data with proteins. we note that the data set used in our study contains proteins, while the three gold standard sets cover, and proteins. that is, the gold standard sets are far from complete. thus, most of our predicted complexes are not able to match the benchmark complexes and tincd achieves a low specificity. however, predicted protein complexes that do not match with reference complexes are not necessarily undesired results and they would probably be novel protein complexes. therefore, optimizing specificity and f-measure will somehow prevent us from detecting novel complexes. on the other hand, as discussed in, accuracy and frac are more suitable to evaluate the performance of an overlapping protein complex detection algorithm. furthermore, we also analyze the importance of an individual base clustering solution for tincd, and investigate the correlation between the number of base clustering solutions and the performance of tincd. however, since tincd not only perform result-level integration, but also perform data-level integration, as shown in additional file 1: table s the effect of removing a base solution in result-level integration will be attenuated by the further operations in data-level integration. as shown in additional file 1: table s the performance of tincd does not change a lot when the consensus matrix of ppi data are constructed using base clustering solutions. thus, the correlation between the number of methods and the performance of tincd depends on the quality of the used methods. ideally, we would think that we are able to construct more accurate consensus matrices and tincd can generate more accurate prediction results, provided that more base clustering solutions with good performance are available. in summary, compared with existing methods, our model has the advantages as follows. our tincd model, leveraging the information from both the clustering results and raw data sources, generates more comprehensive and reliable results. the similarity network fusion model, integrating heterogeneous matrices into a final co-complex score matrix, is free of scale and robust to the noise in the data. the graph regularized doubly stochastic matrix decomposition model considers the sparse similarities and thus ensures relatively balanced clusters. tincd generates the overlapping protein complexes, which clearly reflect the biological reality on proteins’ multi-functional roles. finally, tincd is unsupervised and is thus generic enough for the integration of different types of data sources. the computational complexity for updating θ in algorithm is o, where e is the number of non-zero items in w, n is the number of proteins in the data and k is the pre-defined number of complexes. therefore the overall time cost of the graph regularized doubly stochastic matrix decomposition model is okiter), where iter is the number of iterations. in the experiments, we implement the algorithm using matlab in a laptop with intel cpu and gb ram. the time cost of calculating the final co-complex score matrix is at most seconds. each update of θ costs at most seconds and the entire estimation takes less than seconds when the maximum number of iterations is set to frankly, our tincd has a relatively higher computational cost compared with some base solutions. however, we would think that the running time for tincd is still affordable for the following reasons. first, our primary task is to predict protein complexes with better accuracy and coverage. to achieve this goal, we integrate multiple data sources for clustering and it makes sense that we will higher computational cost as a sacrifice. second, as discussed in, in the context of understanding and exploiting the structure of ppi networks, cluster analysis is usually used as an “offline” process to provide a comprehensive set of clustering results. it is thus acceptable that “offline”, processes have longer running time. third, ppi data is indeed growing in recent years. the computing power of hardware is also under a rapid development. moreover, we can also consider to parallelize the integration process for speedup. regarding the future works, we plan to design an algorithm that could incorporate other data sources in addition to protein interaction data for protein complex detection. we would expect higher prediction accuracy by considering more features for proteins. availability of supporting data the datasets supporting the results of this article are included within its additional files. all the experimental results and code can be downloaded from https://github.com/oyl-cityu/tincd. additional file additional file supplementary figures and text. this section provides the supplementary figures referred in the main text and some text which describes the detailed inference of the solution to tincd and several biological case studies. competing interests the authors declare that they have no competing interests. authors’ contributions loy conceived and designed the study, performed the statistical analysis and drafted the manuscript. mw conceived of the study, and participated in its design and coordination and helped to draft the manuscript. xfz participated in the design of the study, performed the statistical analysis and helped to revise the manuscript. dqd participated in the design of the study and helped to revise the manuscript. xll participated in the design of the study and helped to revise the manuscript. hy participated in the design of the study and helped to revise the manuscript. all authors read and approved the final manuscript. 
extensive experimental results demonstrate that tincd performs much better than state-of-the-art complex detection techniques, including ensemble clustering and data integration techniques. finally, a novel graph regularized doubly stochastic matrix decomposition model is proposed to detect overlapping protein complexes from the integrated similarity network. protein complexes carry out nearly all signaling and functional processes within cells. the study of protein complexes is an effective strategy to analyze cellular functions and biological processes. with the increasing availability of proteomics data, various computational methods have recently been developed to predict protein complexes. in this paper, we develop a novel two-layer integrative complex detection model to detect protein complexes, leveraging the information from both clustering results and raw data sources. second, we combine these consensus matrices with the co-complex score matrix derived from tandem affinity purification/mass spectrometry data and obtain an integrated co-complex similarity network via an unsupervised metric fusion method. however, different computational methods are based on their own assumptions and designed to work on different data sources, and various biological screening methods have their unique experiment conditions, and are often different in scale and noise level. therefore, a single computational method on a specific data source is generally not able to generate comprehensive and reliable prediction results. in particular, we first integrate various clustering results to construct consensus matrices for proteins to measure their overall co-complex propensity.
 protein complexes carry out nearly all signaling and functional processes within cells. the study of protein complexes is an effective strategy to analyze cellular functions and biological processes. with the increasing availability of proteomics data, various computational methods have recently been developed to predict protein complexes. however, different computational methods are based on their own assumptions and designed to work on different data sources, and various biological screening methods have their unique experiment conditions, and are often different in scale and noise level. therefore, a single computational method on a specific data source is generally not able to generate comprehensive and reliable prediction results.  in this paper, we develop a novel two-layer integrative complex detection model to detect protein complexes, leveraging the information from both clustering results and raw data sources. in particular, we first integrate various clustering results to construct consensus matrices for proteins to measure their overall co-complex propensity. second, we combine these consensus matrices with the co-complex score matrix derived from tandem affinity purification/mass spectrometry data and obtain an integrated co-complex similarity network via an unsupervised metric fusion method. finally, a novel graph regularized doubly stochastic matrix decomposition model is proposed to detect overlapping protein complexes from the integrated similarity network.  extensive experimental results demonstrate that tincd performs much better than state-of-the-art complex detection techniques, including ensemble clustering and data integration techniques. electronic supplementary material the online version of this article contains supplementary material, which is available to authorized users. keywords protein complexprotein interaction dataco-complex matrixconsensus matrixmatrix fusionmatrix decompositionissue-copyright-statement© the author 2016 