SiDeS was developed by M. Koyuturk, A. Grama, and W. Szpankowski at the Parallel and Distributed Systems Lab of the Computer Science Department at Purdue University. It is based on the RECOMB 2006 paper "Assessing significance of connectivity and conservation in protein interaction networks" by Mehmet Koyuturk, Ananth Grama and Wojciech Szpankowski, which is on the statistical analysis of the behavior of subgraph density in large networks [1].

SiDeS implements the HCS algorithm [2], which is modified to incorporate the above-mentioned statistical results in evaluating the adequacy of the density of a subgraph to be considered a "cluster". The basic building block of this heuristics is a simple min-cut algorithm [3]. Implementation of the Cytoscape [4] plug-in, particularly the user interface, is based on the implementation of the MCODE [5] plug-in, which also targets identification of dense subgraphs in biological networks, and is also publicly available.

References

[1] M. Koyuturk, A. Grama, and W. Szpankowski, Assessing significance of connectivity and conservation in protein interaction networks. In A. Apostolico et al. (Eds.): 10th International Conference on Research in Computational Molecular Biology (RECOMB'06), LNBI 3909, pp. 45-59, 2006.

[2] E. Hartuv and R. Shamir. A clustering algorithm based on graph connectivity. Information Processing Letters, 76:171.181, 2000.

[3] M. Stoer and F. Wagner. A simple min-cut algorithm. Journal of ACM, 44(4):585.591, 1997.

[4] P. Shannon, A. Markiel, O. Ozier, N. S. Baliga, J. T. Wang, D. Ramage, N. Amin, B. Schwikowski, and T. Ideker. Cytoscape: A software environment for integrated models of biomolecular interaction networks. Genome Research, 13(11):2498-504, 2003.

[5] G. D. Bader and C. W. V. Hogue. An automated method for finding molecular complexes in large protein interaction networks. BMC Bioinformatics, 4(2), 2003.