title: Characterization of known protein complexes using k-connectivity and other topological measures.
abstract: Many protein complexes are densely packed, so proteins within complexes often interact with several other proteins in the complex. Steric constraints prevent most proteins from simultaneously binding more than a handful of other proteins, regardless of the number of proteins in the complex. Because of this, as complex size increases, several measures of the complex decrease within protein-protein interaction networks. However, k-connectivity, the number of vertices or edges that need to be removed in order to disconnect a graph, may be consistently high for protein complexes. The property of k-connectivity has been little used previously in the investigation of protein-protein interactions. To understand the discriminative power of k-connectivity and other topological measures for identifying unknown protein complexes, we characterized these properties in known Saccharomyces cerevisiae protein complexes in networks generated both from highly accurate X-ray crystallography experiments which give an accurate model of each complex, and also as the complexes appear in high-throughput yeast 2-hybrid studies in which new complexes may be discovered. We also computed these properties for appropriate random subgraphs.We found that clustering coefficient, mutual clustering coefficient, and k-connectivity are better indicators of known protein complexes than edge density, degree, or betweenness. This suggests new directions for future protein complex-finding algorithms.
authors.affiliation: Department of Computer Science, University of Colorado, Boulder CO, 80302, USA.
authors.forename: Suzanne R
authors.initials: SR
authors.lastname: Gallagher
authors.affiliation: Department of Computer Science, University of Colorado, Boulder CO, 80302, USA.
authors.forename: Debra S
authors.initials: DS
authors.lastname: Goldberg
keywords: Complex size; Protein folding; Protein-protein interaction; Saccharomyces cerevisiae; X-ray crystallography