Decomposition of overlapping protein complexes: A graph theoretical method for analyzing static and dynamic protein associations

Elena Zotenko¹^,2 , Katia S Guimarães¹^,3 , Raja Jothi¹ and Teresa M Przytycka¹

¹National Center for Biotechnology Information, National Library of Medicine, National Institutes of Health, Bethesda, USA

²Department of Computer Science, University of Maryland, College Park, USA

³Center of Informatics, Federal University of Pernambuco, Recife, Brazil

author email corresponding author email

Algorithms for Molecular Biology 2006, 1:7doi:10.1186/1748-7188-1-7


Published:	26 April 2006

Abstract

Background

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.

Results

We propose a new method for identifying and representing overlapping protein complexes (or larger units called functional groups) 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α/NF-κB and pheromone signaling pathways.

Conclusion

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.