{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,31]],"date-time":"2026-01-31T06:21:22Z","timestamp":1769840482849,"version":"3.49.0"},"reference-count":55,"publisher":"Oxford University Press (OUP)","issue":"1","license":[{"start":{"date-parts":[[2021,1,8]],"date-time":"2021-01-08T00:00:00Z","timestamp":1610064000000},"content-version":"vor","delay-in-days":7,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"European Union\u2019s Horizon 2020 research and innovation programme","award":["739582"],"award-info":[{"award-number":["739582"]}]},{"DOI":"10.13039\/100014137","name":"FPA","doi-asserted-by":"publisher","award":["664620"],"award-info":[{"award-number":["664620"]}],"id":[{"id":"10.13039\/100014137","id-type":"DOI","asserted-by":"publisher"}]},{"name":"European Union\u2019s Horizon 2020 research and innovation program","award":["739582"],"award-info":[{"award-number":["739582"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,4,9]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>Prediction of protein complexes from protein\u2013protein 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.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>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.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and implementation<\/jats:title>\n                  <jats:p>https:\/\/github.com\/SaraOmranian\/PC2P.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Supplementary information<\/jats:title>\n                  <jats:p>Supplementary data are available at Bioinformatics online.<\/jats:p>\n               <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btaa1089","type":"journal-article","created":{"date-parts":[[2020,12,22]],"date-time":"2020-12-22T12:21:23Z","timestamp":1608639683000},"page":"73-81","source":"Crossref","is-referenced-by-count":30,"title":["PC2P: parameter-free network-based prediction of protein complexes"],"prefix":"10.1093","volume":"37","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0539-5609","authenticated-orcid":false,"given":"Sara","family":"Omranian","sequence":"first","affiliation":[{"name":"Bioinformatics, Institute of Biochemistry and Biology, University of Potsdam , 14476 Potsdam, Germany"},{"name":"Systems Biology and Mathematical Modeling, Max Planck Institute of Molecular Plant Physiology , 14476 Potsdam, Germany"}]},{"given":"Angela","family":"Angeleska","sequence":"additional","affiliation":[{"name":"Mathematics Department, University of Tampa , Tampa, FL 33606, USA"}]},{"given":"Zoran","family":"Nikoloski","sequence":"additional","affiliation":[{"name":"Bioinformatics, Institute of Biochemistry and Biology, University of Potsdam , 14476 Potsdam, Germany"},{"name":"Systems Biology and Mathematical Modeling, Max Planck Institute of Molecular Plant Physiology , 14476 Potsdam, Germany"},{"name":"Bioinformatic Department, Centre of Plant Systems Biology and Biotechnology (CPSBB) , 4000 Plovdiv, Bulgaria"}]}],"member":"286","published-online":{"date-parts":[[2021,1,8]]},"reference":[{"key":"2023051510470485500_btaa1089-B1","doi-asserted-by":"crossref","first-page":"1021","DOI":"10.1093\/bioinformatics\/btl039","article-title":"CFinder: locating cliques and overlapping modules in biological networks","volume":"22","author":"Adamcsek","year":"2006","journal-title":"Bioinformatics"},{"key":"2023051510470485500_btaa1089-B2","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1002\/jgt.3190050108","article-title":"A graph and its complement with specified properties. IV. Counting self-complementary blocks","volume":"5","author":"Akiyama","year":"1981","journal-title":"J. Graph Theory"},{"key":"2023051510470485500_btaa1089-B3","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1016\/j.dam.2019.02.048","article-title":"Coherent network partitions","volume":"266","author":"Angeleska","year":"2019","journal-title":"Discrete Appl. Math"},{"key":"2023051510470485500_btaa1089-B4","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1038\/75556","article-title":"Gene ontology: tool for the unification of biology. The Gene Ontology Consortium","volume":"25","author":"Ashburner","year":"2000","journal-title":"Nat. Genet"},{"key":"2023051510470485500_btaa1089-B5","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1186\/1471-2105-4-2","article-title":"An automated method for finding molecular complexes in large protein interaction networks","volume":"4","author":"Bader","year":"2003","journal-title":"BMC Bioinformatics"},{"key":"2023051510470485500_btaa1089-B6","doi-asserted-by":"crossref","first-page":"570","DOI":"10.1046\/j.1432-1033.2003.03428.x","article-title":"Affinity purification-mass spectrometry","volume":"270","author":"Bauer","year":"2003","journal-title":"Eur. J. Biochem"},{"key":"2023051510470485500_btaa1089-B7","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1109\/TKDE.2007.190689","article-title":"On modularity clustering","volume":"20","author":"Brandes","year":"2008","journal-title":"IEEE Trans. Knowl. Data Eng"},{"key":"2023051510470485500_btaa1089-B8","doi-asserted-by":"crossref","first-page":"488","DOI":"10.1186\/1471-2105-7-488","article-title":"Evaluation of clustering algorithms for protein\u2013protein interaction networks","volume":"7","author":"Broh\u00e9e","year":"2006","journal-title":"BMC Bioinformatics"},{"key":"2023051510470485500_btaa1089-B9","doi-asserted-by":"crossref","first-page":"1460","DOI":"10.3390\/molecules23061460","article-title":"Detection of protein complexes based on penalized matrix decomposition in a sparse protein\u2013protein interaction network","volume":"23","author":"Cao","year":"2018","journal-title":"Molecules (Basel, Switzerland"},{"key":"2023051510470485500_btaa1089-B10","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1186\/1471-2105-8-265","article-title":"Semantic integration to identify overlapping functional modules in protein interaction networks","volume":"8","author":"Cho","year":"2007","journal-title":"BMC Bioinformatics"},{"key":"2023051510470485500_btaa1089-B11","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1074\/mcp.M600381-MCP200","article-title":"Toward a comprehensive atlas of the physical interactome of Saccharomyces cerevisiae","volume":"6","author":"Collins","year":"2007","journal-title":"Mol. Cell. Proteomics"},{"key":"2023051510470485500_btaa1089-B12","doi-asserted-by":"crossref","first-page":"1575","DOI":"10.1093\/nar\/30.7.1575","article-title":"An efficient algorithm for large-scale detection of protein families","volume":"30","author":"Enright","year":"2002","journal-title":"Nucleic Acids Res"},{"key":"2023051510470485500_btaa1089-B13","doi-asserted-by":"crossref","first-page":"286","DOI":"10.1016\/0168-9525(90)90012-U","article-title":"The two-hybrid system: an assay for protein\u2013protein interactions","volume":"10","author":"Fields","year":"1994","journal-title":"Trends Genet"},{"key":"2023051510470485500_btaa1089-B14","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1080\/15427951.2004.10129093","article-title":"Graph clustering and minimum cut trees","volume":"1","author":"Flake","year":"2004","journal-title":"Internet Math"},{"key":"2023051510470485500_btaa1089-B15","first-page":"972","article-title":"Clustering by passing messages between data points","volume":"315","author":"Frey","year":"2007","journal-title":"Am. Assoc. Adv. Sci"},{"key":"2023051510470485500_btaa1089-B16","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1186\/1471-2105-8-166","article-title":"GOSim \u2013 an R-package for computation of information theoretic GO similarities between terms and gene products","volume":"8","author":"Fr\u00f6hlich","year":"2007","journal-title":"BMC Bioinformatics"},{"key":"2023051510470485500_btaa1089-B17","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1111\/j.1365-313X.2007.03214.x","article-title":"Technical Advance: split luciferase complementation assay to study protein\u2013protein interactions in Arabidopsis protoplasts","volume":"52","author":"Fujikawa","year":"2007","journal-title":"Plant J"},{"key":"2023051510470485500_btaa1089-B18","doi-asserted-by":"crossref","first-page":"631","DOI":"10.1038\/nature04532","article-title":"Proteome survey reveals modularity of the yeast cell machinery","volume":"440","author":"Gavin","year":"2006","journal-title":"Nature"},{"key":"2023051510470485500_btaa1089-B19","doi-asserted-by":"crossref","first-page":"D559","DOI":"10.1093\/nar\/gky973","article-title":"CORUM: the comprehensive resource of mammalian protein complexes\u20142019","volume":"47","author":"Giurgiu","year":"2019","journal-title":"Nucleic Acids Res"},{"key":"2023051510470485500_btaa1089-B20","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1137\/0109047","article-title":"Multi-terminal network flows","volume":"9","author":"Gomory","year":"1961","journal-title":"J. Soc. Ind. Appl. Math"},{"key":"2023051510470485500_btaa1089-B21","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1186\/1752-0509-4-129","article-title":"Protein complex prediction based on k-connected subgraphs in protein interaction network","volume":"4","author":"Habibi","year":"2010","journal-title":"BMC Syst. Biol"},{"key":"2023051510470485500_btaa1089-B22","doi-asserted-by":"crossref","first-page":"204","DOI":"10.1186\/1471-2105-15-204","article-title":"Detecting protein complexes in protein interaction networks using a ranking algorithm with a refined merging procedure","volume":"15","author":"Hanna","year":"2014","journal-title":"BMC Bioinformatics"},{"key":"2023051510470485500_btaa1089-B23","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/S0020-0190(00)00142-3","article-title":"A clustering algorithm based on graph connectivity","volume":"76","author":"Hartuv","year":"2000","journal-title":"Inf. Process. Lett"},{"key":"2023051510470485500_btaa1089-B24","doi-asserted-by":"crossref","first-page":"D577","DOI":"10.1093\/nar\/gkm909","article-title":"Gene Ontology annotations at SGD: new data sources and annotation methods","volume":"36","author":"Hong","year":"2007","journal-title":"Nucleic Acids Res"},{"key":"2023051510470485500_btaa1089-B25","first-page":"143","volume-title":"Connectivity","author":"Kammer","year":"2004"},{"key":"2023051510470485500_btaa1089-B26","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1002\/net.3230230604","article-title":"Finding all minimum-size separating vertex sets in a graph","volume":"23","author":"Kanevsky","year":"1993","journal-title":"Networks"},{"key":"2023051510470485500_btaa1089-B27","doi-asserted-by":"crossref","first-page":"637","DOI":"10.1038\/nature04670","article-title":"Global landscape of protein complexes in the yeast Saccharomyces cerevisiae","volume":"440","author":"Krogan","year":"2006","journal-title":"Nature"},{"key":"2023051510470485500_btaa1089-B28","doi-asserted-by":"crossref","first-page":"18001","DOI":"10.1209\/0295-5075\/90\/18001","article-title":"Modularity measure of networks with overlapping communities","volume":"90","author":"L\u00e1z\u00e1r","year":"2010","journal-title":"EPL (Europhys. Lett.)"},{"key":"2023051510470485500_btaa1089-B29","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1007\/978-1-4939-7033-9_17","volume-title":"Bacterial Protein Secretion Systems: Methods and Protocols","author":"Lin","year":"2017"},{"key":"2023051510470485500_btaa1089-B30","doi-asserted-by":"crossref","first-page":"1891","DOI":"10.1093\/bioinformatics\/btp311","article-title":"Complex discovery from weighted PPI networks","volume":"25","author":"Liu","year":"2009","journal-title":"Bioinformatics"},{"key":"2023051510470485500_btaa1089-B31","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1038\/s41598-019-49225-7","article-title":"CDAP: an online package for evaluation of complex detection methods","volume":"9","author":"Maddi","year":"2019","journal-title":"Sci. Rep"},{"key":"2023051510470485500_btaa1089-B32","doi-asserted-by":"crossref","first-page":"3247","DOI":"10.1038\/s41598-017-03268-w","article-title":"Discovering overlapped protein complexes from weighted PPI networks by removing inter-module hubs","volume":"7","author":"Maddi","year":"2017","journal-title":"Sci. Rep"},{"key":"2023051510470485500_btaa1089-B33","doi-asserted-by":"crossref","first-page":"1588","DOI":"10.1074\/mcp.RA119.001400","article-title":"A label-free mass spectrometry method to predict endogenous protein complex composition","volume":"18","author":"McBride","year":"2019","journal-title":"Mol. Cell. Proteomics"},{"key":"2023051510470485500_btaa1089-B34","doi-asserted-by":"crossref","first-page":"D651","DOI":"10.1093\/nar\/gkn870","article-title":"PIPs: human protein\u2013protein interaction prediction database","volume":"37","author":"McDowall","year":"2009","journal-title":"Nucleic Acids Res"},{"key":"2023051510470485500_btaa1089-B35","doi-asserted-by":"crossref","first-page":"41D","DOI":"10.1093\/nar\/gkh092","article-title":"MIPS: analysis and annotation of proteins from whole genomes","volume":"32","author":"Mewes","year":"2004","journal-title":"Nucleic Acids Res"},{"key":"2023051510470485500_btaa1089-B37","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1038\/nmeth.1938","article-title":"Detecting overlapping protein complexes in protein\u2013protein interaction networks","volume":"9","author":"Nepusz","year":"2012","journal-title":"Nat. Methods"},{"key":"2023051510470485500_btaa1089-B38","doi-asserted-by":"crossref","first-page":"1027","DOI":"10.1101\/gad.14.9.1027","article-title":"Protein\u2013protein interaction define specificity in signal transduction","volume":"14","author":"Pawson","year":"2000","journal-title":"Genes Dev"},{"key":"2023051510470485500_btaa1089-B39","doi-asserted-by":"crossref","first-page":"372","DOI":"10.1186\/s12859-016-1191-6","article-title":"Protein complex prediction for large protein\u2013protein interaction networks with the Core&Peel method","volume":"17","author":"Pellegrini","year":"2016","journal-title":"BMC Bioinformatics"},{"key":"2023051510470485500_btaa1089-B41","doi-asserted-by":"crossref","first-page":"825","DOI":"10.1093\/nar\/gkn1005","article-title":"Up-to-date catalogues of yeast protein complexes","volume":"37","author":"Pu","year":"2009","journal-title":"Nucleic Acids Res"},{"key":"2023051510470485500_btaa1089-B42","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1038\/nbt.2831","article-title":"The binary protein\u2013protein interaction landscape of Escherichia coli","volume":"32","author":"Rajagopala","year":"2014","journal-title":"Nat. Biotechnol"},{"key":"2023051510470485500_btaa1089-B43","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1146\/annurev.biochem.78.082307.091526","article-title":"Regulation and cellular roles of ubiquitin-specific deubiquitinating enzymes","volume":"78","author":"Reyes-Turcu","year":"2009","journal-title":"Annu. Rev. Biochem"},{"key":"2023051510470485500_btaa1089-B44","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1186\/s12859-018-2017-5","article-title":"Improving prediction of heterodimeric protein complexes using combination with pairwise kernel","volume":"19","author":"Ruan","year":"2018","journal-title":"BMC Bioinformatics"},{"key":"2023051510470485500_btaa1089-B45","doi-asserted-by":"crossref","first-page":"S5","DOI":"10.1186\/1477-5956-9-S1-S5","article-title":"Protein complex detection with semi-supervised learning in protein interaction networks","volume":"9","author":"Shi","year":"2011","journal-title":"Proteome Sci"},{"key":"2023051510470485500_btaa1089-B46","doi-asserted-by":"crossref","first-page":"2590","DOI":"10.1016\/j.febslet.2015.04.026","article-title":"Methods for protein complex prediction and their contributions towards understanding the organisation, function and dynamics of complexes","volume":"589","author":"Srihari","year":"2015","journal-title":"FEBS Lett"},{"key":"2023051510470485500_btaa1089-B47","doi-asserted-by":"crossref","first-page":"286","DOI":"10.1504\/IJBRA.2012.048962","article-title":"Employing functional interactions for characterisation and detection of sparse complexes from yeast PPI networks","volume":"8","author":"Srihari","year":"2012","journal-title":"Int. J. Bioinf. Res. Appl"},{"key":"2023051510470485500_btaa1089-B48","doi-asserted-by":"crossref","first-page":"1230002","DOI":"10.1142\/S021972001230002X","article-title":"A survey of computational methods for protein complex prediction from protein interaction networks","volume":"11","author":"Srihari","year":"2013","journal-title":"J. Bioinf. Comput. Biol"},{"key":"2023051510470485500_btaa1089-B49","doi-asserted-by":"crossref","first-page":"D535","DOI":"10.1093\/nar\/gkj109","article-title":"BioGRID: a general repository for interaction datasets","volume":"34","author":"Stark","year":"2006","journal-title":"Nucleic Acids Res"},{"key":"2023051510470485500_btaa1089-B50","volume-title":"Nat. Commun.,","author":"Sweetlove","year":"2018"},{"key":"2023051510470485500_btaa1089-B51","doi-asserted-by":"crossref","first-page":"D447","DOI":"10.1093\/nar\/gku1003","article-title":"STRING v10: protein\u2013protein interaction networks, integrated over the tree of life","volume":"43","author":"Szklarczyk","year":"2015","journal-title":"Nucleic Acids Res"},{"key":"2023051510470485500_btaa1089-B52","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1186\/s12859-018-2309-9","article-title":"Predicting overlapping protein complexes based on core-attachment and a local modularity structure","volume":"19","author":"Wang","year":"2018","journal-title":"BMC Bioinformatics"},{"key":"2023051510470485500_btaa1089-B53","doi-asserted-by":"crossref","first-page":"1531","DOI":"10.1093\/bib\/bbz085","article-title":"A comprehensive review and evaluation of computational methods for identifying protein complexes from protein\u2013protein interaction networks","volume":"21","author":"Wu","year":"2020","journal-title":"Brief. Bioinf"},{"key":"2023051510470485500_btaa1089-B54","doi-asserted-by":"crossref","first-page":"S13","DOI":"10.1186\/1752-0509-6-S2-S13","article-title":"Supervised maximum-likelihood weighting of composite protein networks for complex prediction","volume":"6","author":"Yong","year":"2012","journal-title":"BMC Syst. Biol"},{"key":"2023051510470485500_btaa1089-B55","doi-asserted-by":"crossref","first-page":"S3","DOI":"10.1186\/1752-0509-8-S5-S3","article-title":"Discovery of small protein complexes from PPI networks with size-specific supervised weighting","volume":"8","author":"Yong","year":"2014","journal-title":"BMC Syst. Biol"},{"key":"2023051510470485500_btaa1089-B56","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1089\/omi.2011.0118","article-title":"clusterProfiler: an R package for comparing biological themes among gene clusters","volume":"16","author":"Yu","year":"2012","journal-title":"OMICS J. Integrative Biol"},{"key":"2023051510470485500_btaa1089-B57","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1016\/j.ygeno.2019.01.011","article-title":"Protein complex prediction: a survey","volume":"112","author":"Zahiri","year":"2020","journal-title":"Genomics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btaa1089\/35906237\/btaa1089.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/37\/1\/73\/50321358\/btaa1089.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/37\/1\/73\/50321358\/btaa1089.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,15]],"date-time":"2023-05-15T10:49:20Z","timestamp":1684147760000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/37\/1\/73\/6069560"}},"subtitle":[],"editor":[{"given":"Pier Luigi","family":"Martelli","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2021,1,1]]},"references-count":55,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,4,9]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btaa1089","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2021,1,1]]},"published":{"date-parts":[[2021,1,1]]}}}