@article{OmranianAngeleskaNikoloski2021, author = {Omranian, Sara and Angeleska, Angela and Nikoloski, Zoran}, title = {Efficient and accurate identification of protein complexes from protein-protein interaction networks based on the clustering coefficient}, series = {Computational and structural biotechnology journal}, volume = {19}, journal = {Computational and structural biotechnology journal}, publisher = {Elsevier}, address = {Amsterdam}, issn = {2001-0370}, doi = {10.1016/j.csbj.2021.09.014}, pages = {5255 -- 5263}, year = {2021}, abstract = {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.}, language = {en} } @article{OmranianNikoloski2022, author = {Omranian, Sara and Nikoloski, Zoran}, title = {CUBCO+: prediction of protein complexes based on min-cut network partitioning into biclique spanned subgraphs}, series = {Applied Network Science}, volume = {7}, journal = {Applied Network Science}, publisher = {Springer International Publishing}, address = {Cham}, issn = {2364-8228}, doi = {10.1007/s41109-022-00508-5}, pages = {12}, year = {2022}, abstract = {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.}, language = {en} } @article{AngeleskaOmranianNikoloski2021, author = {Angeleska, Angela and Omranian, Sara and Nikoloski, Zoran}, title = {Coherent network partitions}, series = {Theoretical computer science : the journal of the EATCS}, volume = {894}, journal = {Theoretical computer science : the journal of the EATCS}, publisher = {Elsevier}, address = {Amsterdam [u.a.]}, issn = {0304-3975}, doi = {10.1016/j.tcs.2021.10.002}, pages = {3 -- 11}, year = {2021}, abstract = {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.}, language = {en} } @article{AngeleskaNikoloski2019, author = {Angeleska, Angela and Nikoloski, Zoran}, title = {Coherent network partitions}, series = {Discrete applied mathematics}, volume = {266}, journal = {Discrete applied mathematics}, publisher = {Elsevier}, address = {Amsterdam}, issn = {0166-218X}, doi = {10.1016/j.dam.2019.02.048}, pages = {283 -- 290}, year = {2019}, abstract = {Graph clustering is widely applied in the analysis of cellular networks reconstructed from large-scale data or obtained from experimental evidence. Here we introduce a new type of graph clustering based on the concept of coherent partition. A coherent partition of a graph G is a partition of the vertices of G that yields only disconnected subgraphs in the complement of G. The coherence number of G is then the size of the smallest edge cut inducing a coherent partition. A coherent partition of G is optimal if the size of the inducing edge cut is the coherence number of G. Given a graph G, we study coherent partitions and the coherence number in connection to (bi)clique partitions and the (bi)clique cover number. We show that the problem of finding the coherence number is NP-hard, but is of polynomial time complexity for trees. We also discuss the relation between coherent partitions and prominent graph clustering quality measures.}, language = {en} }