{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,13]],"date-time":"2025-09-13T16:19:30Z","timestamp":1757780370638},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"published-print":{"date-parts":[[2006,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:sec>\n            <jats:title>Background<\/jats:title>\n            <jats:p>Most cellular processes are carried out by multi-protein complexes, groups of proteins that bind together to perform a specific task. Some proteins form stable complexes, while other proteins form transient associations and are part of several complexes at different stages of a cellular process. A better understanding of this higher-order organization of proteins into overlapping complexes is an important step towards unveiling functional and evolutionary mechanisms behind biological networks.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>We propose a new method for identifying and representing overlapping protein complexes (or larger units called <jats:italic>functional groups<\/jats:italic>) within a protein interaction network. We develop a graph-theoretical framework that enables automatic construction of such representation. We illustrate the effectiveness of our method by applying it to TNF<jats:italic>\u03b1<\/jats:italic>\/NF-<jats:italic>\u03ba<\/jats:italic> B and pheromone signaling pathways.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Conclusion<\/jats:title>\n            <jats:p>The proposed representation helps in understanding the transitions between functional groups and allows for tracking a protein's path through a cascade of functional groups. Therefore, depending on the nature of the network, our representation is capable of elucidating temporal relations between functional groups. Our results show that the proposed method opens a new avenue for the analysis of protein interaction networks.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/1748-7188-1-7","type":"journal-article","created":{"date-parts":[[2006,4,27]],"date-time":"2006-04-27T07:22:12Z","timestamp":1146122532000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":23,"title":["Decomposition of overlapping protein complexes: A graph theoretical method for analyzing static and dynamic protein associations"],"prefix":"10.1186","volume":"1","author":[{"given":"Elena","family":"Zotenko","sequence":"first","affiliation":[]},{"given":"Katia S","family":"Guimar\u00e3es","sequence":"additional","affiliation":[]},{"given":"Raja","family":"Jothi","sequence":"additional","affiliation":[]},{"given":"Teresa M","family":"Przytycka","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2006,4,26]]},"reference":[{"key":"7_CR1","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1038\/35001009","volume":"403","author":"P Uetz","year":"2000","unstructured":"Uetz P, Giot L, Cagney G, Mansfield T, Judson R, Knight J, Lockshon D, Narayan V, Srinivasan M, Pochart P: A comprehensive analysis of protein-protein interactions in Saccharomyces cerevisiae. Nature. 2000, 403: 623-627. 10.1038\/35001009","journal-title":"Nature"},{"key":"7_CR2","doi-asserted-by":"publisher","first-page":"4569","DOI":"10.1073\/pnas.061034498","volume":"98","author":"T Ito","year":"2001","unstructured":"Ito T, Chiba T, Ozawa R, Yoshida M, Hattori M, Sakaki Y: A comprehensive two-hybrid analysis to explore the yeast protein interactome. Proc Natl Acad Sci U S A. 2001, 98: 4569-74. 10.1073\/pnas.061034498","journal-title":"Proc Natl Acad Sci U S A"},{"key":"7_CR3","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1038\/415180a","volume":"415","author":"Y Ho","year":"2002","unstructured":"Ho Y, Gruhler A, Heilbut A, Bader G, Moore L, Adams S, Millar A, Taylor P, Bennett K, Boutilier K: Systematic identification of protein complexes in Saccharomyces cerevisiae by mass spectrometry. Nature. 2002, 415: 180-183. 10.1038\/415180a","journal-title":"Nature"},{"key":"7_CR4","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1038\/415141a","volume":"415","author":"A Gavin","year":"2002","unstructured":"Gavin A, Bosche M, Krause R, Grandi P, Marzioch M, Bauer A, Schultz J, Rick J, Michon A, Cruciat C: Functional organization of the yeast proteome by systematic analysis of protein complexes. Nature. 2002, 415: 141-147. 10.1038\/415141a","journal-title":"Nature"},{"key":"7_CR5","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1038\/ncb1086","volume":"6","author":"T Bouwmeester","year":"2004","unstructured":"Bouwmeester T, Bauch A, Ruffner H, Angrand P, Bergamini G, Croughton K, Cruciat C, Eberhard D, Gagneur J, Ghidelli S: A physical and functional map of the human TNF-alpha\/NF-kappaB signal transduction pathway. Nature Cell Biology. 2004, 6: 97-105. 10.1038\/ncb1086","journal-title":"Nature Cell Biology"},{"key":"7_CR6","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1126\/science.286.5439.509","volume":"286","author":"A Barabasi","year":"1999","unstructured":"Barabasi A, Albert R: Emergence of scaling in random networks. Science. 1999, 286: 509-512. 10.1126\/science.286.5439.509","journal-title":"Science"},{"issue":"18","key":"7_CR7","doi-asserted-by":"publisher","first-page":"3508","DOI":"10.1093\/bioinformatics\/bth436","volume":"20","author":"N Przulj","year":"2004","unstructured":"Przulj N, Corneil D, Jurisica I: Modeling interactome: scale-free or geometric?. Bioinformatics. 2004, 20 (18): 3508-3515. 10.1093\/bioinformatics\/bth436","journal-title":"Bioinformatics"},{"key":"7_CR8","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/j.compbiolchem.2004.07.001","volume":"28","author":"T Przytycka","year":"2004","unstructured":"Przytycka T, Yu Y: Scale-free networks versus evolutionary drift. Comput Biol Chem. 2004, 28: 257-264. 10.1016\/j.compbiolchem.2004.07.001","journal-title":"Comput Biol Chem"},{"key":"7_CR9","doi-asserted-by":"publisher","first-page":"C47","DOI":"10.1038\/35011540","volume":"402","author":"LH Hartwell","year":"1999","unstructured":"Hartwell LH, Hopfield JJ, Leibler S, Murray AW: From molecular to modular cell biology. Nature. 1999, 402: C47-C52. 10.1038\/35011540","journal-title":"Nature"},{"key":"7_CR10","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1186\/1471-2105-4-2","volume":"4","author":"G Bader","year":"2003","unstructured":"Bader G, Hogue C: An automated method for finding molecular complexes in large protein interaction networks. BMC Bioinformatics. 2003, 4: 2. 10.1186\/1471-2105-4-2","journal-title":"BMC Bioinformatics"},{"key":"7_CR11","doi-asserted-by":"publisher","first-page":"1128","DOI":"10.1073\/pnas.0237338100","volume":"100","author":"A Rives","year":"2003","unstructured":"Rives A, Galitski T: Modular organization of cellular networks. Proc Natl Acad Sci U S A. 2003, 100: 1128-33. 10.1073\/pnas.0237338100","journal-title":"Proc Natl Acad Sci U S A"},{"issue":"9","key":"7_CR12","doi-asserted-by":"publisher","first-page":"2443","DOI":"10.1093\/nar\/gkg340","volume":"31","author":"D Bu","year":"2003","unstructured":"Bu D, Zhao Y, Cai L, Xue H, Zhu X, Lu H, Zhang J, Sun S, Ling L, Zhang N, Li G, Chen R: Topological structure analysis of the protein-protein interaction network in budding yeast. Nucleic Acids Research. 2003, 31 (9): 2443-2450. 10.1093\/nar\/gkg340","journal-title":"Nucleic Acids Research"},{"key":"7_CR13","doi-asserted-by":"publisher","first-page":"12123","DOI":"10.1073\/pnas.2032324100","volume":"100","author":"V Spirin","year":"2003","unstructured":"Spirin V, Mirny L: Protein complexes and functional modules in molecular networks. Proc Natl Acad Sci U S A. 2003, 100: 12123-12128. 10.1073\/pnas.2032324100","journal-title":"Proc Natl Acad Sci U S A"},{"key":"7_CR14","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1186\/1471-2105-3-34","volume":"3","author":"M Steffen","year":"2002","unstructured":"Steffen M, Petti A, Aach J, D'haeseleer P, Church G: Automated modelling of signal transduction networks. BMC Bioinformatics. 2002, 3: 34. 10.1186\/1471-2105-3-34","journal-title":"BMC Bioinformatics"},{"key":"7_CR15","doi-asserted-by":"publisher","first-page":"6283","DOI":"10.1093\/nar\/gkg838","volume":"31","author":"S Tornow","year":"2003","unstructured":"Tornow S, Mewes HW: Functional modules by relating protein interaction networks and gene expression. Nucleic Acids Research. 2003, 31: 6283-6289. 10.1093\/nar\/gkg838","journal-title":"Nucleic Acids Research"},{"issue":"8","key":"7_CR16","doi-asserted-by":"publisher","first-page":"R57","DOI":"10.1186\/gb-2004-5-8-r57","volume":"5","author":"J Gagneur","year":"2004","unstructured":"Gagneur J, Krause R, Bouwmeester T, Casari G: Modular decomposition of protein-protein interaction networks. Genome Biology. 2004, 5 (8): R57. 10.1186\/gb-2004-5-8-r57","journal-title":"Genome Biology"},{"key":"7_CR17","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0095-8956(74)90094-X","volume":"16","author":"F Gavril","year":"1974","unstructured":"Gavril F: The intersection graphs of subtrees in trees are exactly the chordal graphs. Journal of Combinatorial Theory (B). 1974, 16: 47-56. 10.1016\/0095-8956(74)90094-X.","journal-title":"Journal of Combinatorial Theory (B)"},{"key":"7_CR18","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"MC Golumbic","year":"1980","unstructured":"Golumbic MC: Algorithmic Graph Theory and Perfect Graphs. 1980, Academic Press, New York"},{"key":"7_CR19","volume-title":"Tech rep","author":"R Shamir","year":"1994","unstructured":"Shamir R: Advanced topics in graph theory. Tech rep. 1994, Tel-Aviv University"},{"key":"7_CR20","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/0166-218X(81)90013-5","volume":"3","author":"D Corneil","year":"1981","unstructured":"Corneil D, Perl Y, Stewart L: Complement reducible graphs. Discrete Applied Mathematics. 1981, 3: 163-174. 10.1016\/0166-218X(81)90013-5.","journal-title":"Discrete Applied Mathematics"},{"key":"7_CR21","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1093\/nar\/30.1.31","volume":"30","author":"H Mewes","year":"2002","unstructured":"Mewes H, Frishman D, Guldener U, Mannhaupt G, Mayer K, Mokrejs M, Morgenstern B, Munsterkotter M, Rudd S, Weil B: MIPS: a database for genomes and protein sequences. Nucleic Acids Research. 2002, 30: 31-34. 10.1093\/nar\/30.1.31","journal-title":"Nucleic Acids Research"},{"issue":"5701","key":"7_CR22","doi-asserted-by":"publisher","first-page":"1508","DOI":"10.1126\/science.1104568","volume":"306","author":"Y Wang","year":"2004","unstructured":"Wang Y, Dohlman H: Pheromone signaling mechanisms in yeast: a prototypical sex machine. Science. 2004, 306 (5701): 1508-1509. 10.1126\/science.1104568","journal-title":"Science"},{"key":"7_CR23","doi-asserted-by":"publisher","first-page":"3076","DOI":"10.1128\/MCB.13.5.3076","volume":"13","author":"K Irie","year":"1993","unstructured":"Irie K, Takase M, Lee K, Levin D, Araki H, Matsumoto K, Oshima Y: MKK1 and MKK2, which encode Saccharomyces cerevisiae mitogen-activated protein kinase-kinase homologs, function in the pathway mediated by protein kinase C. Mol Cell Biol. 1993, 13: 3076-3083.","journal-title":"Mol Cell Biol"},{"issue":"5710","key":"7_CR24","doi-asserted-by":"publisher","first-page":"687","DOI":"10.1126\/science.1109500","volume":"307","author":"E Elion","year":"2005","unstructured":"Elion E, Qi M, Chen W: SIGNAL TRANSDUCTION: Signaling Specificity in Yeast. Science. 2005, 307 (5710): 687-688. 10.1126\/science.1109500","journal-title":"Science"},{"key":"7_CR25","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/0020-0190(89)90070-7","volume":"31","author":"C Ho","year":"1989","unstructured":"Ho C, Lee R: Counting clique trees and computing perfect elimination schemes in parallel. Information Processing Letters. 1989, 31: 61-68. 10.1016\/0020-0190(89)90070-7.","journal-title":"Information Processing Letters"},{"key":"7_CR26","volume-title":"Parametrized Complexity","author":"R Downey","year":"1997","unstructured":"Downey R, Fellows M: Parametrized Complexity. 1997, Springer-Verlag"},{"key":"7_CR27","first-page":"47","volume":"2","author":"V Batagelj","year":"1998","unstructured":"Batagelj V, Mrvar A: Pajek \u2013 Program for large network analysis. Connections. 1998, 2: 47-57.","journal-title":"Connections"}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1748-7188-1-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,31]],"date-time":"2021-08-31T21:42:17Z","timestamp":1630446137000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/1748-7188-1-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,4,26]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2006,12]]}},"alternative-id":["7"],"URL":"https:\/\/doi.org\/10.1186\/1748-7188-1-7","relation":{},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,4,26]]},"assertion":[{"value":"14 February 2006","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 April 2006","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 April 2006","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"7"}}