Gram is a tool for topology-free querying of protein-protein interaction networks or for finding reaction motifs in metabolic networks. It solves the following NP-hard problem:
That is, we search for a connected subgraph of G such that the color-sets of the vertices of the subgraph have all colors from M and such that each vertex of the subgraph can be assigned a distinct color from M that also belongs to its color-set. Gram outputs a maximum set of connected vertices that are an occurrence of a submotif of M.
With an error probability of 0.1%, Gram solves problem instances with motif sizes up to 13 within milliseconds on a standard desktop computer—almost independently from the size of the input graph. This is achieved by using a probabilistic fixed-parameter algorithm from
Nadja Betzler, Michael R. Fellows, Christian Komusiewicz, and Rolf Niedermeier:
Parameterized algorithms and hardness results for some graph motif problems.
This paper also contains information on the possible use cases of Gram. A journal version of this paper will contain benchmark results for Gram on popular protein-protein interaction networks such as the Yeast network.
Gram is implemented in about 1000 lines of C++ using the Boost Graph Library. On the one hand, the efficiency of Gram is due to the use of efficient set representations that allow rapid iteration over a set's subsets of given size. On the other hand, Gram employs a heuristics that significantly reduces the error probability. This heuristics is described in
Sharon Bruckner, Falk Hüffner, Richard M. Karp, Ron Shamir, and Roded Sharan:
Topology-free querying of protein interaction networks.
The current version of Gram including an installation and usage manual can always be found at the Institut für Informatik, Friedrich-Schiller-Universität Jena.
Gram has been tested on Debian GNU/Linux 5.0 "Lenny", and on Mac OS X 10.5.
© 2010 René van Bevern. Last modified 2010-07-29.