article

Transitive closure and metric inequality of weighted graphs: detecting protein interaction modules using cliques

Authors:

Stephen R. HolbrookAuthors Info & Claims

International Journal of Data Mining and Bioinformatics, Volume 1, Issue 2

Pages 162 - 177

https://doi.org/10.1504/IJDMB.2006.010854

Published: 01 September 2006 Publication History

Abstract

We study transitivity properties of edge weights in complex networks. We show that enforcing transitivity leads to a transitivity inequality which is equivalent to ultra-metric inequality. This can be used to define transitive closure on weighted undirected graphs, which can be computed using a modified Floyd-Warshall algorithm. These new concepts are extended to dissimilarity graphs and triangle inequalities. From this, we extend the clique concept from unweighted graph to weighted graph. We outline several applications and present results of detecting protein functional modules in a protein interaction network.

References

[1]

Bader, G.D. and Hogue, C.W.V. (2002) 'Analyzing yeast protein-protein interaction data obtained from different sources', Nature Biotechnology, Vol. 20, pp. 991-997.

Crossref

Google Scholar

[2]

Ding, C., He, X., Meraz, R. and Holbrook, S. (2004) 'A unified representation for multiprotein complex data for modeling protein interaction networks', Proteins: Structure, Function, and Bioinformatics, Vol. 57, pp. 99-108.

Crossref

Google Scholar

[3]

Gavin, A.C., Bosche, M., Krause, R., Grandi, P., Marzioch, M., Bauer, A., Schultz, J., Rick, J.M., Michon, A.M., Cruciat, C.M., Remor, M., Hofert, C., Schelder, M., Brajenovic, M., Ruffner, H., Merino, A., Klein, K., Hudak, M., Dickson, D., Rudi, T., Gnau, V., Bauch, A., Bastuck, S., Huhse, B., Leutwein, C., Heurtier, M.A., Copley, R.R., Edelmann, A., Querfurth, E., Rybin, V., Drewes, G., Raida, M., Bouwmeester, T., Bork, P., Seraphin, B., Kuster, B., Neubauer, G. and Superti-Furga, G. (2002) 'Functional organization of the yeast proteome by systematic analysis of protein complexes', Nature, Vol. 415, pp. 141-147.

Crossref

Google Scholar

[4]

Hastie, T., Tibshirani, R. and Friedman, J. (2001) Elements of Statistical Learning, Springer Verlag, New York, Berlin, Heidelberg.

Google Scholar

[5]

Ho, Y., Gruhler, A., Heilbut, A., Bader, G.D., Moore, L., Adams, S.L., Millar, A., Taylor, P., Bennett, K., Boutilier, K., Yang, L., Wolting, C., Donaldson, I., Schandorff, S., Shewnarane, J., Vo, M., Taggart, J., Goudreault, M., Muskat, B., Alfarano, C., Dewar, D., Lin, Z., Michalickova, K., Willems, A.R., Sassi, H., Nielsen, P.A., Rasmussen, K.J., Andersen, J.R., Johansen, L.E., Hansen, L.H., Jespersen, H., Podtelejnikov, A., Nielsen, E., Crawford, J., Poulsen, V., Sorensen, B.D., Matthiesen, J., Hendrickson, R.C., Gleeson, F., Pawson, T., Moran, M.F., Durocher, D., Mann, M., Hogue, C.W., Figeys, D. and Tyers, M. (2002) 'Systematic identification of protein complexes in saccharomyces cerevisiae by mass spectrometry', Nature, Vol. 415, pp. 180-193.

Crossref

Google Scholar

[6]

Ito, T., Chiba, T., Ozawa, R., Yoshida, M., Hattori, M. and Sakaki, Y. (2001) 'A comprehensive two hybrid analysis to explore the yeast protein interactome', Proc. Natl. Acad. Sci., Vol. 98, No. 8, pp. 4569-4574.

Crossref

Google Scholar

[7]

Motzkin, T. and Straus, E. (1965) 'Maxima for graphs and a new proof of a theorem of turan', Canad. J. Math., Vol. 17, pp. 533-540.

Crossref

Google Scholar

[8]

Pelillo, M., Siddiqi, K. and Zucker, S. (1999) 'Matching hierarchical structures using association graphs', IEEE. Trans. on Pattern Analysis and Machine Intelligence, Vol. 21, pp. 1105-1120.

Digital Library

Google Scholar

[9]

Tibshirani, R. (1996) 'Regression shrinkage and selection via the LASSO', J. Royal. Statist. Soc B., Vol. 58, pp. 267-288.

Crossref

Google Scholar

[10]

Uetz, P., Giot, L., Cagney, G., Mansfield, T.A., Judson, R.S., Knight, J.R., Lockshon, D., Narayan, V., Srinivasan, M., Pochart, P., Qureshi-Emili, A., Li, Y., Godwin, B., Conover, D., Kalbfleisch, T., Vijayadamodar, G., Yang, M., Johnston, M., Fields, S. and Rothberg, J.M. (2000) 'A comprehensive analysis of protein-protein interactions in saccharomyces cerevisiae', Nature, Vol. 403, No. 6770, pp. 623-627.

Crossref

Google Scholar

[11]

Wasserman, S. and Faust, K. (1994) Social Network Analysis, Cambridge University Press, Cambridge.

Google Scholar

[12]

Watts, D. and Strogatz, S. (1998) 'Collective dynamics of small world networks', Nature, Vol. 393, pp. 440-442.

Crossref

Google Scholar

[13]

Xiong, H., He, X., Ding, C., Zhang, Y., Kumar, V. and Holbrook, S. (2005) 'Identification of functional modules in protein complexes via hyperclique pattern discovery', Proc. Pacific Symposium on Biocomputing, pp. 221-232.

Google Scholar

Cited By

View all

Cao YChai MLi MJiang CKrause ABrunskill ECho KEngelhardt BSabato SScarlett J(2023)Efficient learning of mesh-based physical simulation with bi-stride multi-scale graph neural networkProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3618553(3541-3558)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.5555/3618408.3618553
Baral RIyengar SLi TZhu XBanaei-Kashani FHoel EGüting RTamassia RXiong L(2018)HiCaPSProceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/3274895.3274925(436-439)Online publication date: 6-Nov-2018
https://dl.acm.org/doi/10.1145/3274895.3274925
Yu ZLiu WLiu WYang YLi MKumar B(2016)On order-constrained transitive distance clusteringProceedings of the Thirtieth AAAI Conference on Artificial Intelligence10.5555/3016100.3016219(2293-2299)Online publication date: 12-Feb-2016
https://dl.acm.org/doi/10.5555/3016100.3016219
Show More Cited By

Transitive closure and metric inequality of weighted graphs: detecting protein interaction modules using cliques
1. Applied computing
  1. Life and medical sciences
2. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory

Recommendations

On the Maximum Number of Cliques in a Graph

A clique is a set of pairwise adjacent vertices in a graph. We determine the maximum number of cliques in a graph for the following graph classes: (1) graphs with n vertices and m edges; (2) graphs with n vertices, m edges, and maximum degree Δ; (3) d-...
Weighted domination in triangle-free graphs

A weighted graph (G,w) is a graph G together with a positive weight-function on its vertex set w: V(G) → R^>0. The weighted domination number γ_w(G) of (G,w) is the minimum weight w(D) = Σ_υ∈D w(υ) of a set D ⊆ V(G) such that every vertex x ∈ V(D) - D has ...
Finding cliques in protein interaction networks via transitive closure of a weighted graph
BIOKDD '05: Proceedings of the 5th international workshop on Bioinformatics

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. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image International Journal of Data Mining and Bioinformatics

International Journal of Data Mining and Bioinformatics Volume 1, Issue 2

September 2006

105 pages

ISSN:1748-5673

EISSN:1748-5681

Issue’s Table of Contents

Publisher

Inderscience Publishers

Geneva 15, Switzerland

Publication History

Published: 01 September 2006

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 04 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Cao YChai MLi MJiang CKrause ABrunskill ECho KEngelhardt BSabato SScarlett J(2023)Efficient learning of mesh-based physical simulation with bi-stride multi-scale graph neural networkProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3618553(3541-3558)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.5555/3618408.3618553
Baral RIyengar SLi TZhu XBanaei-Kashani FHoel EGüting RTamassia RXiong L(2018)HiCaPSProceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/3274895.3274925(436-439)Online publication date: 6-Nov-2018
https://dl.acm.org/doi/10.1145/3274895.3274925
Yu ZLiu WLiu WYang YLi MKumar B(2016)On order-constrained transitive distance clusteringProceedings of the Thirtieth AAAI Conference on Artificial Intelligence10.5555/3016100.3016219(2293-2299)Online publication date: 12-Feb-2016
https://dl.acm.org/doi/10.5555/3016100.3016219
Oliveira SSharma R(2016)Identification and prediction of functional protein modules using a bi-level community detection algorithmInternational Journal of Bioinformatics Research and Applications10.1504/IJBRA.2016.07712412:2(129-148)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1504/IJBRA.2016.077124
Yu ZLiu WLiu WPeng XHui ZKumar B(2015)Generalized transitive distance with minimum spanning random forestProceedings of the 24th International Conference on Artificial Intelligence10.5555/2832415.2832555(2205-2211)Online publication date: 25-Jul-2015
https://dl.acm.org/doi/10.5555/2832415.2832555
Zheng LLi TDing C(2014)A Framework for Hierarchical Ensemble ClusteringACM Transactions on Knowledge Discovery from Data10.1145/26113809:2(1-23)Online publication date: 23-Sep-2014
https://dl.acm.org/doi/10.1145/2611380
Geryk JSlanina F(2013)Modules in the metabolic network of E.coli with regulatory interactionsInternational Journal of Data Mining and Bioinformatics10.1504/IJDMB.2013.0555008:2(188-202)Online publication date: 1-Jul-2013
https://dl.acm.org/doi/10.1504/IJDMB.2013.055500

Abstract

References

Cited By

Recommendations

On the Maximum Number of Cliques in a Graph

Weighted domination in triangle-free graphs

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

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations