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 - Omranian, Sara A1 - Nikoloski, Zoran A1 - Grimm, Dominik G. T1 - Computational identification of protein complexes from network interactions: Present state, challenges, and the way forward BT - present state, challenges, and the way forward JF - Computational and structural biotechnology journal N2 - Physically interacting proteins form macromolecule complexes that drive diverse cellular processes. Advances in experimental techniques that capture interactions between proteins provide us with protein-protein interaction (PPI) networks from several model organisms. These datasets have enabled the prediction and other computational analyses of protein complexes. Here we provide a systematic review of the state-of-the-art algorithms for protein complex prediction from PPI networks proposed in the past two decades. The existing approaches that solve this problem are categorized into three groups, including: cluster-quality-based, node affinity-based, and network embedding-based approaches, and we compare and contrast the advantages and disadvantages. We further include a comparative analysis by computing the performance of eighteen methods based on twelve well-established performance measures on four widely used benchmark protein-protein interaction networks. Finally, the limitations and drawbacks of both, current data and approaches, along with the potential solutions in this field are discussed, with emphasis on the points that pave the way for future research efforts in this field. (c) 2022 The Author(s). Published by Elsevier B.V. on behalf of Research Network of Computational and Structural Biotechnology. This is an open access article under the CC BY license (http://creativecommons. org/licenses/by/4.0/). KW - Protein Complex Prediction KW - Protein-Protein interaction network KW - Network KW - Clustering Algorithms KW - Network embedding Y1 - 2022 U6 - https://doi.org/10.1016/j.csbj.2022.05.049 SN - 2001-0370 VL - 20 SP - 2699 EP - 2712 PB - Research Network of Computational and Structural Biotechnology (RNCSB) CY - Gotenburg 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 - GEN A1 - Omranian, Sara A1 - Nikoloski, Zoran T1 - CUBCO+: prediction of protein complexes based on min-cut network partitioning into biclique spanned subgraphs T2 - Zweitveröffentlichungen der Universität Potsdam : Mathematisch-Naturwissenschaftliche Reihe N2 - High-throughput proteomics approaches have resulted in large-scale protein–protein interaction (PPI) networks that have been employed for the prediction of protein complexes. However, PPI networks contain false-positive as well as false-negative PPIs that affect the protein complex prediction algorithms. To address this issue, here we propose an algorithm called CUBCO+ that: (1) employs GO semantic similarity to retain only biologically relevant interactions with a high similarity score, (2) based on link prediction approaches, scores the false-negative edges, and (3) incorporates the resulting scores to predict protein complexes. Through comprehensive analyses with PPIs from Escherichia coli, Saccharomyces cerevisiae, and Homo sapiens, we show that CUBCO+ performs as well as the approaches that predict protein complexes based on recently introduced graph partitions into biclique spanned subgraphs and outperforms the other state-of-the-art approaches. Moreover, we illustrate that in combination with GO semantic similarity, CUBCO+ enables us to predict more accurate protein complexes in 36% of the cases in comparison to CUBCO as its predecessor. T3 - Zweitveröffentlichungen der Universität Potsdam : Mathematisch-Naturwissenschaftliche Reihe - 1315 KW - Protein complexes KW - Protein–protein interaction KW - Network clustering KW - Species comparison Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-586863 SN - 1866-8372 IS - 1315 ER - TY - JOUR A1 - Omranian, Sara A1 - Nikoloski, Zoran T1 - CUBCO+: prediction of protein complexes based on min-cut network partitioning into biclique spanned subgraphs JF - Applied Network Science N2 - High-throughput proteomics approaches have resulted in large-scale protein–protein interaction (PPI) networks that have been employed for the prediction of protein complexes. However, PPI networks contain false-positive as well as false-negative PPIs that affect the protein complex prediction algorithms. To address this issue, here we propose an algorithm called CUBCO+ that: (1) employs GO semantic similarity to retain only biologically relevant interactions with a high similarity score, (2) based on link prediction approaches, scores the false-negative edges, and (3) incorporates the resulting scores to predict protein complexes. Through comprehensive analyses with PPIs from Escherichia coli, Saccharomyces cerevisiae, and Homo sapiens, we show that CUBCO+ performs as well as the approaches that predict protein complexes based on recently introduced graph partitions into biclique spanned subgraphs and outperforms the other state-of-the-art approaches. Moreover, we illustrate that in combination with GO semantic similarity, CUBCO+ enables us to predict more accurate protein complexes in 36% of the cases in comparison to CUBCO as its predecessor. KW - Protein complexes KW - Protein–protein interaction KW - Network clustering KW - Species comparison Y1 - 2022 U6 - https://doi.org/10.1007/s41109-022-00508-5 SN - 2364-8228 VL - 7 PB - Springer International Publishing CY - Cham ER - TY - THES A1 - Omranian, Sara T1 - Novel algorithms for prediction of protein complexes from protein-protein interacton networks Y1 - 2022 ER -