QPath: a method for querying pathways in a protein-protein interaction network. Results: We present a comprehensive framework for protein network searches using pathway queries. Given a linear query pathway and a network of interest, our algorithm, QPath, efficiently searches the network for homologous pathways, allowing both insertions and deletions of proteins in the identified pathways. Matched pathways are automatically scored according to their variation from the query pathway in terms of the protein insertions and deletions they employ, the sequence similarity of their constituent proteins to the query proteins, and the reliability of their constituent interactions. We applied QPath to systematically infer protein pathways in fly using an extensive collection of 271 putative pathways from yeast. QPath identified 69 conserved pathways whose members were both functionally enriched and coherently expressed. The resulting pathways tended to preserve the function of the original query pathways, allowing us to derive a first annotated map of conserved protein pathways in fly. Conclusion: Pathway homology searches using QPath provide a powerful approach for identifying biologically significant pathways and inferring their function. The growing amounts of protein interactions in public databases underscore the importance of our network querying framework for mining protein network data.

References in zbMATH (referenced in 11 articles )

Showing results 1 to 11 of 11.
Sorted by year (citations)

  1. Rubert, Diego P.; Araujo, Eloi; Stefanes, Marco A.; Stoye, Jens; Martinez, Fábio V.: Searching and inferring colorful topological motifs in vertex-colored graphs (2020)
  2. Pinter, Ron Y.; Shachnai, Hadas; Zehavi, Meirav: Improved parameterized algorithms for network query problems (2019)
  3. Aliakbarpour, Maryam; Biswas, Amartya Shankha; Gouleakis, Themis; Peebles, John; Rubinfeld, Ronitt; Yodpinyanee, Anak: Sublinear-time algorithms for counting star subgraphs via edge sampling (2018)
  4. Zehavi, Meirav: Parameterized algorithms for the module motif problem (2016)
  5. Pinter, Ron Y.; Shachnai, Hadas; Zehavi, Meirav: Partial information network queries (2015)
  6. Pinter, Ron Y.; Zehavi, Meirav: Algorithms for topology-free and alignment network queries (2014)
  7. Downey, Rodney G.; Thilikos, Dimitrios M.: Confronting intractability via parameters (2011)
  8. Dogrusöz, Ugur; Cetintas, Ahmet; Demir, Emek; Babur, Ozgun: Algorithms for effective querying of compound graph-based pathway databases (2009) ioport
  9. Hüffner, Falk; Wernicke, Sebastian; Zichner, Thomas: Algorithm engineering for color-coding with applications to signaling pathway detection (2008)
  10. Bebek, Gurkan; Yang, Jiong: Pathfinder: Mining signal transduction pathway segments from protein-protein interaction networks (2007) ioport
  11. Shlomi, Tomer; Segal, Daniel; Ruppin, Eytan; Sharan, Roded: Qpath: a method for querying pathways in a protein-protein interaction network (2006) ioport