QNet swMATH ID: 13845 Software Authors: Banu Dost; Tomer Shlomi; Nitin Gupta; Eytan Ruppin; Vineet Bafna; Roded Sharan Description: QNet: A Tool for Querying Protein Interaction Networks. Molecular interaction databases can be used to study the evolution of molecular pathways across species. Querying such pathways is a challenging computational problem, and recent efforts have been limited to simple queries (paths), or simple networks (forests). In this paper, we significantly extend the class of pathways that can be efficiently queried to the case of trees, and graphs of bounded treewidth. Our algorithm allows the identification of non-exact (homeomorphic) matches, exploiting the color coding technique of Alon et al. We implement a tool for tree queries, called QNet, and test its retrieval properties in simulations and on real network data. We show that QNet searches queries with up to 9 proteins in seconds on current networks, and outperforms sequence-based searches. We also use QNet to perform the first large scale cross-species comparison of protein complexes, by querying known yeast complexes against a fly protein interaction network. This comparison points to strong conservation between the two species, and underscores the importance of our tool in mining protein interaction networks. Homepage: http://link.springer.com/chapter/10.1007/978-3-540-71681-5_1 Related Software: QPath; MetaCyc; CPLEX; GO-TermFinder; SIMBio; GraMoFoNe; Kavosh; FANMOD; CIRCUS; Gravisto; PARAssign; WhatsHap; INDDGO; MetaCrop; BioMiner; Bioconductor; Numbat; MG-RAST; TreeWiz; igraph Cited in: 11 Publications all top 5 Cited by 27 Authors 6 Zehavi, Meirav 4 Shachnai, Hadas 3 Pinter, Ron Yair 1 Araújo, Elói 1 Bentert, Matthias 1 Hüffner, Falk 1 Keith, Jonathan M. 1 Lian, Xiang 1 Lokshtanov, Daniel 1 Martinez, Fábio Viduani 1 Misra, Pranabendu 1 Nichterlein, André 1 Niedermeier, Rolf 1 Panolan, Fahad 1 Rubert, Diego P. 1 Saurabh, Saket 1 Smirnov, Pavel V. 1 Stefanes, Marco A. 1 Stoye, Jens 1 van Bevern, René 1 Wang, Wei 1 Wernicke, Sebastian 1 Zhang, Huaming 1 Zhao, Dongyan 1 Zheng, Weiguo 1 Zichner, Thomas 1 Zou, Lei all top 5 Cited in 7 Serials 2 Algorithmica 2 Journal of Discrete Algorithms 1 Information Sciences 1 Journal of Computer and System Sciences 1 INFORMS Journal on Computing 1 Journal of Combinatorial Optimization 1 Methods in Molecular Biology Cited in 5 Fields 8 Combinatorics (05-XX) 8 Computer science (68-XX) 4 Biology and other natural sciences (92-XX) 1 General and overarching topics; collections (00-XX) 1 Operations research, mathematical programming (90-XX) Citations by Year