Clustering and cross-talk in a yeast functional interaction network

Many different clustering algorithms have been applied to biological networks, with varying degrees of success. The output of a clustering algorithm may be hard to interpret in biological terms because such networks are often large and highly interconnected, with structural and functional modules overlapping to varying degrees. In this paper we describe an evolutionary network clustering algorithm specifically designed for the analysis of large, complex biological networks. It identifies variably sized, overlapping clusters of nodes. The identification of points of overlap between clusters facilitates the analysis of the biological nature of crosstalk between functional units in the network. We apply two variants of the algorithm (one using probabilistic weights on edges and one ignoring them) to a recently published network of functional gene interactions in the yeast Saccharomyces cerevisiae and assess the biological validity of the resulting clusters in terms of ontological similarity.