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:

List-Colored Graph Motif:
Input:
A graph G=(V,E) and a multiset of colors M, where each vertex v in V has assigned a set col(v) of colors.
Task:
Find maximum-cardinality sets S⊆V and M'⊆M such that the induced subgraph G[S] is connected and there is a one-to-one mapping f:S→M' such ∀v∈S:f(v)∈col(v).

That is, we search for a largest possible connected induced subgraph of G such that the color-sets of the vertices of the subgraph have precisely (also with respect to multiplicity) the colors of a subset M' of M.

Efficiency

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 using a the probabilistic fixed-parameter algorithms and heuristics described in

Nadja Betzler, René van Bevern, Michael R. Fellows, Christian Komusiewicz, and Rolf Niedermeier:
Parameterized Algorithmics for Finding Connected Motifs in Biological Networks.

This paper also contains information on the possible use cases and 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. Additionally to the above mentioned fixed-parameter algorithms, the efficiency of Gram relies on set representations that allow rapid iteration over a set's subsets of given size; moreover, Gram employs heuristics that significantly reduce the error probability. One of these heuristics is also described in

Sharon Bruckner, Falk Hüffner, Richard M. Karp, Ron Shamir, and Roded Sharan:
Topology-free querying of protein interaction networks.

Download

The current version of Gram including an installation and usage manual can always be found at Institut für Informatik, Friedrich-Schiller-Universität Jena.

Gram has been tested on Debian GNU/Linux 5.0 "Lenny", on Mac OS X 10.5., and on Arch Linux with GCC 4.5.

© 2010 René van Bevern. Last modified 2011-03-14.