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 is a challenging computational problem, and recent efforts have been limited simple queries (paths), or networks (forests). In this paper, we significantly extend class that efficiently queried case trees, graphs bounded treewidth. Our algorithm allows identification non-exact (homeomorphic) matches, exploiting color coding technique Alon et al. (1995). We implement tool for tree queries, called QNet, test its retrieval properties in simulations on real network data. show QNet searches with up nine proteins seconds current networks, outperforms sequence-based searches. also use perform first large-scale cross-species comparison protein complexes, by querying known yeast complexes against fly network. This points strong conservation between two species, underscores importance our mining networks.