TY  - JOUR
A1  - Omranian, Sara
A1  - Angeleska, Angela
A1  - Nikoloski, Zoran
T1  - Efficient and accurate identification of protein complexes from protein-protein interaction networks based on the clustering coefficient
JF  - Computational and structural biotechnology journal
N2  - Identification of protein complexes from protein-protein interaction (PPI) networks is a key problem in PPI mining, solved by parameter-dependent approaches that suffer from small recall rates. Here we introduce GCC-v, a family of efficient, parameter-free algorithms to accurately predict protein complexes using the (weighted) clustering coefficient of proteins in PPI networks. Through comparative analyses with gold standards and PPI networks from Escherichia coli, Saccharomyces cerevisiae, and Homo sapiens, we demonstrate that GCC-v outperforms twelve state-of-the-art approaches for identification of protein complexes with respect to twelve performance measures in at least 85.71% of scenarios. We also show that GCC-v results in the exact recovery of similar to 35% of protein complexes in a pan-plant PPI network and discover 144 new protein complexes in Arabidopsis thaliana, with high support from GO semantic similarity. Our results indicate that findings from GCC-v are robust to network perturbations, which has direct implications to assess the impact of the PPI network quality on the predicted protein complexes. (C) 2021 The Author(s). Published by Elsevier B.V. on behalf of Research Network of Computational and Structural Biotechnology.
KW  - Protein complexes
KW  - Protein-protein interaction
KW  - Network clustering
KW  - Species comparison
Y1  - 2021
U6  - https://doi.org/10.1016/j.csbj.2021.09.014
SN  - 2001-0370
VL  - 19
SP  - 5255
EP  - 5263
PB  - Elsevier
CY  - Amsterdam
ER  - 
TY  - JOUR
A1  - Angeleska, Angela
A1  - Omranian, Sara
A1  - Nikoloski, Zoran
T1  - Coherent network partitions
BT  - Characterizations with cographs and prime graphs
JF  - Theoretical computer science : the journal of the EATCS
N2  - We continue to study coherent partitions of graphs whereby the vertex set is partitioned into subsets that induce biclique spanned subgraphs. The problem of identifying the minimum number of edges to obtain biclique spanned connected components (CNP), called the coherence number, is NP-hard even on bipartite graphs. Here, we propose a graph transformation geared towards obtaining an O (log n)-approximation algorithm for the CNP on a bipartite graph with n vertices. The transformation is inspired by a new characterization of biclique spanned subgraphs. In addition, we study coherent partitions on prime graphs, and show that finding coherent partitions reduces to the problem of finding coherent partitions in a prime graph. Therefore, these results provide future directions for approximation algorithms for the coherence number of a given graph.
KW  - Graph partitions
KW  - Network clustering
KW  - Cographs
KW  - Coherent partition
KW  - Prime graphs
Y1  - 2021
U6  - https://doi.org/10.1016/j.tcs.2021.10.002
SN  - 0304-3975
VL  - 894
SP  - 3
EP  - 11
PB  - Elsevier
CY  - Amsterdam [u.a.]
ER  - 
TY  - JOUR
A1  - Omranian, Sara
A1  - Angeleska, Angela
A1  - Nikoloski, Zoran
T1  - PC2P
BT  - parameter-free network-based prediction of protein complexes
JF  - Bioinformatics
N2  - Motivation: 
Prediction of protein complexes from protein-protein interaction (PPI) networks is an important problem in systems biology, as they control different cellular functions. The existing solutions employ algorithms for network community detection that identify dense subgraphs in PPI networks. However, gold standards in yeast and human indicate that protein complexes can also induce sparse subgraphs, introducing further challenges in protein complex prediction. 

Results: 
To address this issue, we formalize protein complexes as biclique spanned subgraphs, which include both sparse and dense subgraphs. We then cast the problem of protein complex prediction as a network partitioning into biclique spanned subgraphs with removal of minimum number of edges, called coherent partition. Since finding a coherent partition is a computationally intractable problem, we devise a parameter-free greedy approximation algorithm, termed Protein Complexes from Coherent Partition (PC2P), based on key properties of biclique spanned subgraphs. Through comparison with nine contenders, we demonstrate that PC2P: (i) successfully identifies modular structure in networks, as a prerequisite for protein complex prediction, (ii) outperforms the existing solutions with respect to a composite score of five performance measures on 75% and 100% of the analyzed PPI networks and gold standards in yeast and human, respectively, and (iii,iv) does not compromise GO semantic similarity and enrichment score of the predicted protein complexes. Therefore, our study demonstrates that clustering of networks in terms of biclique spanned subgraphs is a promising framework for detection of complexes in PPI networks.
Y1  - 2021
U6  - https://doi.org/10.1093/bioinformatics/btaa1089
SN  - 1367-4811
VL  - 37
IS  - 1
SP  - 73
EP  - 81
PB  - Oxford Univ. Press
CY  - Oxford
ER  -