Gradually Expanding Dense Neighborhoods (GENA) is proposed for the computational prediction of protein complexes from weighted protein interaction networks.

GENA permits the participation of proteins to multiple complexes in agreement with the underlying cell mechanisms.

GENA outperformed three of the state of the art algorithms for predicting protein complexes in experiments with datasets from yeast and human organisms.

Downstream analysis of the resulted clusters revealed functional homogeneity between the proteins of the same cluster.

Significantly altered network modules were detected when GENA was applied to two co-expression networks: one generated from Parkinson patients and one from healthy individuals.