Finding cliques in protein interaction networks via transitive closure of a weighted graph

Chris Ding; Xiaofeng He; Hanchuan Peng

doi:10.1145/1134030.1134043

Finding cliques in protein interaction networks via transitive closure of a weighted graph

Chris Ding
, Xiaofeng He
, Hanchuan Peng

University of California at Berkeley

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

2 Scopus citations

Abstract

Finding protein functional modules in protein interaction networks amounts to finding densely connected subgraphs. Standard methods such as cliques and k-cores produce very small subgraphs due to highly sparse connections in most protein networks. Furthermore, standard methods are not applicable on weighted protein networks. We propose a method to identify cliques on weighted graphs. To overcome the sparsity problem, we introduce the concept of transitive closure on weighted graphs which is based on enforcing a transitive affinity inequality on the connection weights, and an algorithm to compute them. Using protein network from TAP-MS experiment on yeast, we discover a large number of cliques that are densely connected protein modules, with clear biological meanings as shown on Gene Ontology analysis.

Original language	English
Title of host publication	Proceedings of the 5th International Workshop on Bioinformatics, BIOKDD 2005
Pages	69-75
Number of pages	7
DOIs	https://doi.org/10.1145/1134030.1134043
State	Published - 2005
Externally published	Yes
Event	5th International Workshop on Bioinformatics, BIOKDD 2005 - In Conjunction with 11th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2005 - Chicago, IL, United States Duration: 21 Aug 2005 → 21 Aug 2005

Publication series

Name	Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

Conference

Conference	5th International Workshop on Bioinformatics, BIOKDD 2005 - In Conjunction with 11th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2005
Country/Territory	United States
City	Chicago, IL
Period	21/08/05 → 21/08/05

Access to Document

10.1145/1134030.1134043

Cite this

@inproceedings{fc763c35e01e45a09aacf71b25ea2379,

title = "Finding cliques in protein interaction networks via transitive closure of a weighted graph",

abstract = "Finding protein functional modules in protein interaction networks amounts to finding densely connected subgraphs. Standard methods such as cliques and k-cores produce very small subgraphs due to highly sparse connections in most protein networks. Furthermore, standard methods are not applicable on weighted protein networks. We propose a method to identify cliques on weighted graphs. To overcome the sparsity problem, we introduce the concept of transitive closure on weighted graphs which is based on enforcing a transitive affinity inequality on the connection weights, and an algorithm to compute them. Using protein network from TAP-MS experiment on yeast, we discover a large number of cliques that are densely connected protein modules, with clear biological meanings as shown on Gene Ontology analysis.",

author = "Chris Ding and Xiaofeng He and Hanchuan Peng",

year = "2005",

doi = "10.1145/1134030.1134043",

language = "英语",

isbn = "1595932135",

series = "Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining",

pages = "69--75",

booktitle = "Proceedings of the 5th International Workshop on Bioinformatics, BIOKDD 2005",

note = "5th International Workshop on Bioinformatics, BIOKDD 2005 - In Conjunction with 11th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2005 ; Conference date: 21-08-2005 Through 21-08-2005",

}

Ding, C, He, X & Peng, H 2005, Finding cliques in protein interaction networks via transitive closure of a weighted graph. in Proceedings of the 5th International Workshop on Bioinformatics, BIOKDD 2005. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 69-75, 5th International Workshop on Bioinformatics, BIOKDD 2005 - In Conjunction with 11th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2005, Chicago, IL, United States, 21/08/05. https://doi.org/10.1145/1134030.1134043

Finding cliques in protein interaction networks via transitive closure of a weighted graph. / Ding, Chris; He, Xiaofeng; Peng, Hanchuan.
Proceedings of the 5th International Workshop on Bioinformatics, BIOKDD 2005. 2005. p. 69-75 (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Finding cliques in protein interaction networks via transitive closure of a weighted graph

AU - Ding, Chris

AU - He, Xiaofeng

AU - Peng, Hanchuan

PY - 2005

Y1 - 2005

N2 - Finding protein functional modules in protein interaction networks amounts to finding densely connected subgraphs. Standard methods such as cliques and k-cores produce very small subgraphs due to highly sparse connections in most protein networks. Furthermore, standard methods are not applicable on weighted protein networks. We propose a method to identify cliques on weighted graphs. To overcome the sparsity problem, we introduce the concept of transitive closure on weighted graphs which is based on enforcing a transitive affinity inequality on the connection weights, and an algorithm to compute them. Using protein network from TAP-MS experiment on yeast, we discover a large number of cliques that are densely connected protein modules, with clear biological meanings as shown on Gene Ontology analysis.

AB - Finding protein functional modules in protein interaction networks amounts to finding densely connected subgraphs. Standard methods such as cliques and k-cores produce very small subgraphs due to highly sparse connections in most protein networks. Furthermore, standard methods are not applicable on weighted protein networks. We propose a method to identify cliques on weighted graphs. To overcome the sparsity problem, we introduce the concept of transitive closure on weighted graphs which is based on enforcing a transitive affinity inequality on the connection weights, and an algorithm to compute them. Using protein network from TAP-MS experiment on yeast, we discover a large number of cliques that are densely connected protein modules, with clear biological meanings as shown on Gene Ontology analysis.

UR - https://www.scopus.com/pages/publications/84885638908

U2 - 10.1145/1134030.1134043

DO - 10.1145/1134030.1134043

M3 - 会议稿件

AN - SCOPUS:84885638908

SN - 1595932135

SN - 9781595932136

T3 - Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

SP - 69

EP - 75

BT - Proceedings of the 5th International Workshop on Bioinformatics, BIOKDD 2005

T2 - 5th International Workshop on Bioinformatics, BIOKDD 2005 - In Conjunction with 11th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2005

Y2 - 21 August 2005 through 21 August 2005

ER -

Finding cliques in protein interaction networks via transitive closure of a weighted graph

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this