{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,7]],"date-time":"2025-11-07T08:51:19Z","timestamp":1762505479619},"reference-count":35,"publisher":"Oxford University Press (OUP)","issue":"14","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009,7,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: The large, complex networks of interactions between proteins provide a lens through which one can examine the structure and function of biological systems. Previous analyses of these continually growing networks have primarily followed either of two approaches: large-scale statistical analysis of holistic network properties, or small-scale analysis of local topological features. Meanwhile, investigation of meso-scale network structure (above that of individual functional modules, while maintaining the significance of individual proteins) has been hindered by the computational complexity of structural search in networks. Examining protein\u2013protein interaction (PPI) networks at the meso-scale may provide insights into the presence and form of relationships between individual protein complexes and functional modules.<\/jats:p>\n               <jats:p>Results: In this article, we present an efficient algorithm for performing sub-graph isomorphism queries on a network and show its computational advantage over previous methods. We also present a novel application of this form of topological search which permits analysis of a network's structure at a scale between that of individual functional modules and that of network-wide properties. This analysis provides support for the presence of hierarchical modularity in the PPI network of Saccharomyces cerevisiae.<\/jats:p>\n               <jats:p>Contact: \u00a0ying.liu@utdallas.edu<\/jats:p>","DOI":"10.1093\/bioinformatics\/btp297","type":"journal-article","created":{"date-parts":[[2009,5,16]],"date-time":"2009-05-16T00:14:09Z","timestamp":1242432849000},"page":"1814-1821","source":"Crossref","is-referenced-by-count":12,"title":["Structure discovery in PPI networks using pattern-based network decomposition"],"prefix":"10.1093","volume":"25","author":[{"given":"Philip","family":"Bachman","sequence":"first","affiliation":[{"name":"1 Department of Computer Science and 2 Department of Molecular Biology, University of Texas at Dallas, Richardson, TX 75083-0688"}]},{"given":"Ying","family":"Liu","sequence":"additional","affiliation":[{"name":"1 Department of Computer Science and 2 Department of Molecular Biology, University of Texas at Dallas, Richardson, TX 75083-0688"},{"name":"1 Department of Computer Science and 2 Department of Molecular Biology, University of Texas at Dallas, Richardson, TX 75083-0688"}]}],"member":"286","published-online":{"date-parts":[[2009,5,15]]},"reference":[{"key":"2023013112050140500_B1","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1038\/nature01511","article-title":"Mass spectrometry-based proteomics","volume":"422","author":"Aebersold","year":"2003","journal-title":"Nature"},{"key":"2023013112050140500_B2","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1038\/35019019","article-title":"Error and attack tolerance of complex networks","volume":"406","author":"Albert","year":"2000","journal-title":"Nature"},{"key":"2023013112050140500_B3","first-page":"171","article-title":"Canonical labeling of graphs","volume-title":"Proceedings of the fifteenth annual ACM symposium on Theory of computing.","author":"Babai","year":"1983"},{"key":"2023013112050140500_B4","doi-asserted-by":"crossref","first-page":"991","DOI":"10.1038\/nbt1002-991","article-title":"Analyzing yeast protein-protein interaction data obtained from different sources","volume":"20","author":"Bader","year":"2002","journal-title":"Nat. Biotechnol."},{"key":"2023013112050140500_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 networks","volume":"4","author":"Bader","year":"2003","journal-title":"BMC Bioinformatics"},{"key":"2023013112050140500_B6","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1145\/1150402.1150418","article-title":"Nemofinder: Dissecting genome-wide protein-protein interactions with meso-scale network motifs","volume-title":"Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Datamining.","author":"Chen","year":"2006"},{"key":"2023013112050140500_B7","first-page":"149","article-title":"An improved algorithm for matching large graphs","volume-title":"Proceedings of the 3rd IAPR-TC15 Workshop on Graph-based Representations in Pattern Recognition, Cuen.","author":"Cordella","year":"2001"},{"key":"2023013112050140500_B8","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":"2023013112050140500_B9","doi-asserted-by":"crossref","first-page":"5391","DOI":"10.1111\/j.1742-4658.2005.04973.x","article-title":"High-throughput two-hybrid analysis: the promise and the peril","volume":"272","author":"Fields","year":"2005","journal-title":"FEBS J"},{"key":"2023013112050140500_B10","first-page":"92","article-title":"Network motif discovery using subgraph enumeration and symmetry-breaking","volume-title":"Proceedings of the 11th Annual International Conference on Research in Computational Molecular Biology, RECOMB 2007.","author":"Grochow","year":"2007"},{"key":"2023013112050140500_B11","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1038\/ng873","article-title":"Topological and causal structure of the yeast transcriptional regulatory network","volume":"31","author":"Guelzim","year":"2002","journal-title":"Nat. Genet."},{"key":"2023013112050140500_B12","doi-asserted-by":"crossref","first-page":"651","DOI":"10.1038\/35036627","article-title":"The large-scale organization of metabolic networks","volume":"407","author":"Jeong","year":"2000","journal-title":"Nature"},{"key":"2023013112050140500_B13","doi-asserted-by":"crossref","first-page":"031909","DOI":"10.1103\/PhysRevE.70.031909","article-title":"Topological generalizations of network motifs","volume":"70","author":"Kashtan","year":"2004","journal-title":"Phys. Rev. E"},{"key":"2023013112050140500_B14","doi-asserted-by":"crossref","first-page":"360","DOI":"10.1109\/TCBB.2006.55","article-title":"Motif search in graphs: Application to metabolic networks","volume":"3","author":"Lacroix","year":"2006","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"2023013112050140500_B15","first-page":"45","article-title":"Practical graph isomorphism","volume":"30","author":"McKay","year":"1981","journal-title":"Congressus Numerantium"},{"key":"2023013112050140500_B16","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1006\/jagm.1997.0898","article-title":"Isomorph-free exhaustive generation","volume":"26","author":"McKay","year":"1998","journal-title":"J. Algorithms"},{"key":"2023013112050140500_B17","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1093\/nar\/30.1.31","article-title":"Mips: a database for genomes and protein sequences","volume":"30","author":"Mewes","year":"2002","journal-title":"Nucleic Acids Res."},{"key":"2023013112050140500_B18","doi-asserted-by":"crossref","first-page":"824","DOI":"10.1126\/science.298.5594.824","article-title":"Network motifs: Simple building blocks of complex networks","volume":"298","author":"Milo","year":"2002","journal-title":"Science"},{"key":"2023013112050140500_B19","doi-asserted-by":"crossref","first-page":"814","DOI":"10.1038\/nature03607","article-title":"Uncovering the overlapping community structure of complex networks in nature and society","volume":"435","author":"Palla","year":"2005","journal-title":"Nature"},{"key":"2023013112050140500_B20","doi-asserted-by":"crossref","first-page":"e177","DOI":"10.1093\/bioinformatics\/btl301","article-title":"Biological network comparison using graphlet degree distribution","volume":"23","author":"Pr\u017eulj","year":"2007","journal-title":"Bioinformatics"},{"key":"2023013112050140500_B21","doi-asserted-by":"crossref","first-page":"3508","DOI":"10.1093\/bioinformatics\/bth436","article-title":"Modeling interactome: scale-free or geometric","volume":"20","author":"Pr\u017eulj","year":"2004","journal-title":"Bioinformatics"},{"key":"2023013112050140500_B22","doi-asserted-by":"crossref","first-page":"974","DOI":"10.1093\/bioinformatics\/btl030","article-title":"Efficient estimation of graphlet frequency distributions in protein-protein interaction networks","volume":"22","author":"Pr\u017eulj","year":"2006","journal-title":"Bioinformatics"},{"key":"2023013112050140500_B23","doi-asserted-by":"crossref","first-page":"1128","DOI":"10.1073\/pnas.0237338100","article-title":"Modular organization of cellular networks","volume":"100","author":"Rives","year":"2003","journal-title":"PNAS"},{"key":"2023013112050140500_B24","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1093\/nar\/gkh086","article-title":"The database of interacting proteins: 2004 update","volume":"32","author":"Salwinski","year":"2004","journal-title":"Nucleic Acids Res."},{"key":"2023013112050140500_B25","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1038\/msb4100129","article-title":"Network-based prediction of protein function","volume":"3","author":"Sharan","year":"2007","journal-title":"Mol. Syst. Biol."},{"key":"2023013112050140500_B26","doi-asserted-by":"crossref","first-page":"12123","DOI":"10.1073\/pnas.2032324100","article-title":"Protein complexes and functional modules in molecular networks","volume":"100","author":"Spirin","year":"2003","journal-title":"PNAS"},{"key":"2023013112050140500_B27","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1038\/35065725","article-title":"Exploring complex networks","volume":"410","author":"Strogatz","year":"2001","journal-title":"Nature"},{"key":"2023013112050140500_B28","article-title":"A combined experimental and computational strategy to define protein interaction networks for peptide recognition modules","volume":"10","author":"Tong","year":"2001","journal-title":"Sciencexpress"},{"key":"2023013112050140500_B29","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1109\/TCBB.2006.51","article-title":"Efficient detection of network motifs","volume":"3","author":"Wernicke","year":"2006","journal-title":"IEEE\/ACM Trans. Comput. Biol."},{"key":"2023013112050140500_B30","doi-asserted-by":"crossref","first-page":"444","DOI":"10.1002\/pmic.200400962","article-title":"Peeling the yeast protein network","volume":"5","author":"Wuchty","year":"2005","journal-title":"Proteomics"},{"key":"2023013112050140500_B31","doi-asserted-by":"crossref","first-page":"176","DOI":"10.1038\/ng1242","article-title":"Evolutionary conservation of motif constituents in the yeast protein interactino network","volume":"35","author":"Wuchty","year":"2003","journal-title":"Nat. Genet."},{"key":"2023013112050140500_B32","doi-asserted-by":"crossref","first-page":"5934","DOI":"10.1073\/pnas.0306752101","article-title":"Network motifs in integrated cellular networks of transcription-regulation and protein\u2013protein interaction","volume":"101","author":"Yeger-Lotem","year":"2004","journal-title":"PNAS"},{"key":"2023013112050140500_B33","doi-asserted-by":"crossref","first-page":"928","DOI":"10.1002\/pmic.200300636","article-title":"Functional and topological characterization of protein interaction networks","volume":"4","author":"Yook","year":"2004","journal-title":"Proteomics"},{"key":"2023013112050140500_B34","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1186\/jbiol23","article-title":"Motifs, themes and thematic maps of an integrated saccharomyces cerevisiae interaction network","volume":"4","author":"Zhang","year":"2005","journal-title":"J. Biol."},{"key":"2023013112050140500_B35","doi-asserted-by":"crossref","first-page":"046117","DOI":"10.1103\/PhysRevE.71.046117","article-title":"Information-theoretic approach to network modularity","volume":"71","author":"Ziv","year":"2005","journal-title":"Phys. Rev. E"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/25\/14\/1814\/48993185\/bioinformatics_25_14_1814.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/25\/14\/1814\/48993185\/bioinformatics_25_14_1814.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T21:19:39Z","timestamp":1675199979000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/25\/14\/1814\/224366"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,5,15]]},"references-count":35,"journal-issue":{"issue":"14","published-print":{"date-parts":[[2009,7,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btp297","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2009,7,15]]},"published":{"date-parts":[[2009,5,15]]}}}