title: Efficient algorithms for detecting signaling pathways in protein interaction networks.
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.
authors.affiliation: Computer Science Division, University of California, Berkeley, 94720, USA.
authors.forename: Jacob
authors.initials: J
authors.lastname: Scott
authors.forename: Trey
authors.initials: T
authors.lastname: Ideker
authors.forename: Richard M
authors.initials: RM
authors.lastname: Karp
authors.forename: Roded
authors.initials: R
authors.lastname: Sharan
mesh_terms: D000465:Algorithms; D003198:Computer Simulation; D008954:Models, Biological; D011485:Protein Binding; D025941:Protein Interaction Mapping; D020543:Proteome / Q000378:metabolism; D012441:Saccharomyces cerevisiae / Q000378:metabolism; D029701:Saccharomyces cerevisiae Proteins / Q000737:chemistry* / Q000378:metabolism*; D015398:Signal Transduction
chemical_list: D020543:Proteome; D029701:Saccharomyces cerevisiae Proteins