Global network alignment using multiscale spectral signatures
Authors:
Open Access
- 9 October 2012
- journal article
- research article
- Published by Oxford University Press (OUP) in Bioinformatics
- Vol. 28 (23) , 3105-3114
Abstract
Motivation: Protein interaction networks provide an important system-level view of biological processes. One of the fundamental problems in biological network analysis is the global alignment of a pair of networks, which puts the proteins of one network into correspondence with the proteins of another network in a manner that conserves their interactions while respecting other evidence of their homology. By providing a mapping between the networks of different species, alignments can be used to inform hypotheses about the functions of unannotated proteins, the existence of unobserved interactions, the evolutionary divergence between the two species and the evolution of complexes and pathways. Results: We introduce GHOST, a global pairwise network aligner that uses a novel spectral signature to measure topological similarity between subnetworks. It combines a seed-and-extend global alignment phase with a local search procedure and exceeds state-of-the-art performance on several network alignment tasks. We show that the spectral signature used by GHOST is highly discriminative, whereas the alignments it produces are also robust to experimental noise. When compared with other recent approaches, we find that GHOST is able to recover larger and more biologically significant, shared subnetworks between species. Availability: An efficient and parallelized implementation of GHOST, released under the Apache 2.0 license, is available at http://cbcb.umd.edu/kingsford_group/ghost Contact:rob@cs.umd.eduKeywords
This publication has 42 references indexed in Scilit:
- A variable selection method for genome-wide association studiesBioinformatics, 2010
- Automatic Parameter Learning for Multiple Local Network AlignmentJournal of Computational Biology, 2009
- IsoRankN: spectral methods for global alignment of multiple protein networksBioinformatics, 2009
- Global alignment of protein–protein interaction networks by graph matching methodsBioinformatics, 2009
- Global alignment of multiple protein interaction networks with application to functional orthology detectionProceedings of the National Academy of Sciences, 2008
- A Large Scale Analysis of Protein-Protein Interactions in the Nitrogen-fixing Bacterium Mesorhizobium lotiDNA Research, 2008
- Proteome survey reveals modularity of the yeast cell machineryNature, 2006
- Conserved patterns of protein interaction in multiple speciesProceedings of the National Academy of Sciences, 2005
- Basic Local Alignment Search ToolJournal of Molecular Biology, 1990
- A novel genetic system to detect protein–protein interactionsNature, 1989