Efficient Algorithms for Detecting Signaling Pathways in Protein Interaction Networks
Authors:
- 1 March 2006
- journal article
- Published by SAGE Publications in Journal of Computational Biology
- Vol. 13 (2) , 133-144
Abstract
The interpretation of large-scale protein network data depends on our ability to identify significant substructures in the data, a computationally intensive task. Here we adapt and extend efficient techniques for finding paths and trees in graphs to the problem of identifying pathways in protein interaction networks. We present linear-time algorithms for finding paths and trees in networks under several biologically motivated constraints. We apply our methodology to search for protein pathways in the yeast protein-protein interaction network. We demonstrate that our algorithm is capable of reconstructing known signaling pathways and identifying functionally enriched paths and trees in an unsupervised manner. The algorithm is very efficient, computing optimal paths of length 8 within minutes and paths of length 10 in about three hours.Keywords
This publication has 15 references indexed in Scilit:
- Conserved patterns of protein interaction in multiple speciesProceedings of the National Academy of Sciences, 2005
- Whole-genome annotation by using evidence integration in functional-linkage networksProceedings of the National Academy of Sciences, 2004
- MIPS: analysis and annotation of proteins from whole genomesNucleic Acids Research, 2004
- Gaining confidence in high-throughput protein interaction networksNature Biotechnology, 2003
- Conserved pathways within bacteria and yeast as revealed by global protein network alignmentProceedings of the National Academy of Sciences, 2003
- The Stanford Microarray Database: data access and quality assessment toolsNucleic Acids Research, 2003
- Comparative assessment of large-scale data sets of protein–protein interactionsNature, 2002
- DIP, the Database of Interacting Proteins: a research tool for studying cellular networks of protein interactionsNucleic Acids Research, 2002
- Pattern and Timing of Gene Duplication in Animal GenomesGenome Research, 2001
- Color-codingJournal of the ACM, 1995