Dataset Information

Functionally guided alignment of protein interaction networks for module detection.

ABSTRACT:

Motivation

Functional module detection within protein interaction networks is a challenging problem due to the sparsity of data and presence of errors. Computational techniques for this task range from purely graph theoretical approaches involving single networks to alignment of multiple networks from several species. Current network alignment methods all rely on protein sequence similarity to map proteins across species.

Results

Here we carry out network alignment using a protein functional similarity measure. We show that using functional similarity to map proteins across species improves network alignment in terms of functional coherence and overlap with experimentally verified protein complexes. Moreover, the results from functional similarity-based network alignment display little overlap (<15%) with sequence similarity-based alignment. Our combined approach integrating sequence and function-based network alignment alongside graph clustering properties offers a 200% increase in coverage of experimental datasets and comparable accuracy to current network alignment methods.

Availability

Program binaries and source code is freely available at http://www.stats.ox.ac.uk/research/bioinfo/resources.

Supplementary information

Supplementary data are available at Bioinformatics online.

SUBMITTER: Ali W

PROVIDER: S-EPMC2778333 | biostudies-literature | 2009 Dec

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

Functionally guided alignment of protein interaction networks for module detection.

Ali Waqar W Deane Charlotte M CM

Bioinformatics (Oxford, England) 20091001 23

<h4>Motivation</h4>Functional module detection within protein interaction networks is a challenging problem due to the sparsity of data and presence of errors. Computational techniques for this task range from purely graph theoretical approaches involving single networks to alignment of multiple networks from several species. Current network alignment methods all rely on protein sequence similarity to map proteins across species.<h4>Results</h4>Here we carry out network alignment using a protein ...[more]

PMID: 19797409

Similar Datasets

Project description:MotivationIdentifying 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.ResultsIn 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 implementationAll data and code are available at http://www.cse.usf.edu/~xqian/fmi/slcp2hop/.

Dataset Information

Functionally guided alignment of protein interaction networks for module detection.

Motivation

Results

Availability

Supplementary information

Publications

Functionally guided alignment of protein interaction networks for module detection.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets