Premium
Identification of conserved protein modules from multiple organisms using transitive closure and cliques in protein interaction networks
Author(s) -
Ye Yong,
Ding Chris,
Holbrook Stephen R
Publication year - 2006
Publication title -
the faseb journal
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.709
H-Index - 277
eISSN - 1530-6860
pISSN - 0892-6638
DOI - 10.1096/fasebj.20.4.a530-b
Subject(s) - transitive closure , transitive relation , computer science , computational biology , graph , theoretical computer science , biology , archaea , genome , gene , genetics , combinatorics , mathematics
To identify modules in protein interaction networks as densely connected subgraphs, we have developed a new transitive closure method to overcome the typical sparse interaction problem and have introduced an effective quadratic programming clique finding algorithm. Together these new methods can effectively detect a large number of densely connected subgraphs as cliques in weighted interaction networks. Transitive closure helps to detect more, larger and denser cliques. From sets of protein modules (cliques) identified in multiple organisms, we have developed a systematic framework to determine conserved modules across several organisms using protein homology and graph comparison. We have also developed methods to integrate different types of data (protein interaction, gene expression, protein complex etc.) into a single interaction graph. We applied this approach to the archaeal genomes Sulfolobus tokodaii, Pyrococcus furiosus DSM 3638 and Halobacterium sp NRC_1. Experimental results show that our algorithm successfully identified hundreds of cliques for each of these organisms. We also found that 5% to 15% of the cliques are conserved among these three and other archaea, bacteria and yeast. Their physical and biological significance are verified by experimental and annotation data. This research is funded by a grant from the US Department of Energy, Office of Biological Energy Research, contract no. DE‐AC03‐76SF00098.