Algorithms and tools for protein-protein interaction networks clustering, with a special focus on population-based stochastic methods.
BACKGROUND
Protein-protein interaction (PPI) networks are powerful models to represent the pairwise protein interactions of the organisms. Clustering PPI networks can be useful for isolating groups of interacting proteins that participate in the same biological processes or that perform together specific biological functions. Evolutionary orthologies can be inferred this way, as well as functions and properties of yet uncharacterized proteins.


RESULTS
We present an overview of the main state-of-the-art clustering methods that have been applied to PPI networks over the past decade. We distinguish five specific categories of approaches, describe and compare their main features and then focus on one of them, i.e. population-based stochastic search. We provide an experimental evaluation, based on some validation measures widely used in the literature, of techniques in this class, that are as yet less explored than the others. In particular, we study how the capability of Genetic Algorithms (GAs) to extract clusters in PPI networks varies when different topology-based fitness functions are used, and we compare GAs with the main techniques in the other categories. The experimental campaign shows that predictions returned by GAs are often more accurate than those produced by the contestant methods. Interesting issues still remain open about possible generalizations of GAs allowing for cluster overlapping.


METHODS
We point out which methods and tools described here are publicly available.


BACKGROUND
simona.rombo@math.unipa.it


BACKGROUND
Supplementary data are available at Bioinformatics online.
Institute for High Performance Computing and Networking (ICAR), National Research Council of Italy (CNR), Via P. Bucci 41C, 87036 Rende (CS) and Department of Mathematics and Computer Science, University of Palermo, Via Archirafi 34, 90123 Palermo (PA), Italy.
Clara
C
Pizzuti
Simona E
SE
Rombo
D000465:Algorithms; D000818:Animals; D016000:Cluster Analysis; D006801:Humans; D025941:Protein Interaction Mapping / Q000379:methods*; D011506:Proteins / Q000235:genetics / Q000378:metabolism*
D011506:Proteins