We present a new image co-segmentation framework to simultaneously segment multiple images by formulating the co-segmentation problem as a multiple graph clustering problem. For each image, we first construct a corresponding segment graph by extracting superpixels as vertices and assigning edge weights between superpixels according to their feature and spatial proximity. To integrate the related information across images, we further compose a similarity graph across all constructed segment graphs, in which edges capture the similarity among superpixels across images. We propose to solve the co-segmentation problem by applying an alternating random walk strategy on both the segment graphs and the similarity graph to borrow strengths across images for better segmentation. The common objects shared in images can be identified by finding low conductance sets based on the transition probability matrix of the alternating random walk on these graphs. Experiments on iCoseg and a sequence of echocardiac images demonstrate that our novel formulation yields promising results and performs better than image segmentation on individual images separately.

Identification of functional modules in protein protein interaction (PPI) networks may help better understand cell functions. Many existing computational methods focus on identifying modules based on either individual PPI networks or protein sequence similarities within the species. As both interaction data and sequence similarities may not be either complete or accurate with respect to revealing protein functionalities, we propose a joint clustering framework based on block modeling to integrate the available information across different species to utilize both protein interaction data and sequence similarities. The motivation is to borrow strengths from multiple data sources for more accurate module identification as evolutionally different species may share similar cellular organization. Our blockmodel joint clustering enables the identification of not only densely connected modules but also those modules containing proteins with similar interaction patterns to the rest of the networks. We develop a simulated annealing (SA) algorithm based on Potts-Models for the blockmodel problem to solve the non-convex combinatorial optimization. Our method is validated using synthetic networks as well as yeast and fruit fly PPI networks. The experimental results conclude that joint clustering outperforms clustering of individual networks separately.

MOTIVATION: Identifying functional modules in protein-protein interaction (PPI) networks may shed light on cellular functional organization and thereafter underlying cellular mechanisms. Many existing module identification algorithms aim to detect densely connected groups of proteins as potential modules. However, based on this simple topological criterion of 'higher than expected connectivity', those algorithms may miss biologically meaningful modules of functional significance, in which proteins have similar interaction patterns to other proteins in networks but may not be densely connected to each other. A few blockmodel module identification algorithms have been proposed to address the problem but the lack of global optimum guarantee and the prohibitive computational complexity have been the bottleneck of their applications in real-world large-scale PPI networks. RESULTS: In this article, we propose a novel optimization formulation LCP(2) (low two-hop conductance sets) using the concept of Markov random walk on graphs, which enables simultaneous identification of both dense and sparse modules based on protein interaction patterns in given networks through searching for LCP(2) by random walk. A spectral approximate algorithm SLCP(2) is derived to identify non-overlapping functional modules. Based on a bottom-up greedy strategy, we further extend LCP(2) to a new algorithm (greedy algorithm for LCP(2)) GLCP(2) to identify overlapping functional modules. We compare SLCP(2) and GLCP(2) with a range of state-of-the-art algorithms on synthetic networks and real-world PPI networks. The performance evaluation based on several criteria with respect to protein complex prediction, high level Gene Ontology term prediction and especially sparse module detection, has demonstrated that our algorithms based on searching for LCP(2) outperform all other compared algorithms. AVAILABILITY AND IMPLEMENTATION: All data and code are available at http://www.cse.usf.edu/~xqian/fmi/slcp2hop/.

Functional module identification in biological networks may provide new insights into the complex interactions among biomolecules for a better understanding of cellular functional organization. Most of existing functional module identification methods are based on the optimization of network modularity and cluster networks into groups of nodes within which there are a higher-than-expectation number of edges. However, module identification simply based on this topological criterion may not discover certain kinds of biologically meaningful modules within which nodes are sparsely connected but have similar interaction patterns with the rest of the network. In order to unearth more biologically meaningful functional modules, we propose a novel efficient convex programming algorithm based on the subgradient method with heuristic path generation to solve the problem in a recently proposed framework of blockmodel module identification. We have implemented our algorithm for large-scale protein-protein interaction (PPI) networks, including Saccharomyces cerevisia and Homo sapien PPI networks collected from the Database of Interaction Proteins (DIP) and Human Protein Reference Database (HPRD). Our experimental results have shown that our algorithm achieves comparable network clustering performance in comparison to the more time-consuming simulated annealing (SA) optimization. Furthermore, preliminary results for identifying fine-grained functional modules in both biological networks and the comparison with the commonly adopted Markov Clustering (MCL) algorithm have demonstrated the potential of our algorithm to discover new types of modules, within which proteins are sparsely connected but with significantly enriched biological functionalities.