Gram - A Graph Motif solver =========================== This file describes the installation, usage, and limitations of Gram. Gram is the graph motif solver accompanying the paper - Nadja Betzler, René van Bevern, Michael R. Fellows, Christian Komusiewicz, and Rolf Niedermeier: "Parameterized Algorithmics for Finding Connected Motifs in Biological Networks" It has been tested on: * Debian GNU/Linux (x86_64) 5.0 with GCC 4.3.2 * Arch Linux (x86_64) with GCC 4.5 * Mac OS X 10.5 with GCC 4.2 The current version of Gram can always be found on http://theinf1.informatik.uni-jena.de/graph-motif/ 0. Requirements / Installation ------------------------------ Gram needs the Boost Library in version 1.36 or higher, including the Boost Graph Library. It is available from http://www.boost.org. Compiling Gram has been tested with the GNU build system. For windows system, the GNU build system including GNU make and GNU Bash is available from http://www.mingw.org Note that GNU Make is available as the "gmake" command on non-gnu Unix systems. If all requirements are met, compiling Gram should work as follows: In the directory that this README file is in, execute: ./configure make (or gmake) and if you want to install Gram system-wide, execute as root: make install (or gmake install) Otherwise, you find the "Gram" executable in the src/ directory. Compiler optimization may yield a significant speedup for Gram. For example, running CXXFLACS="-O3 -mtune=athon64" ./configure instead of plain "./configure" yields a factor-8 speedup on our test-hardware. 1. Usage -------- Call Gram like gram -e 0.1 file.dot Herein, -e 0.1 denotes the probability of error and is an optional parameter. Per default, 0.1 is used as maximum error probability. The input graph is given as "file.dot" here. If replaced by "-", a graph is read from standard input. For the used file format, refer to Section 3 (File Format). Gram then searches for an occurrence of a motif M that contains all colors that are assigned to some vertex in the given input graph. It outputs a maximum set of connected vertices that are an occurrence of a submotif of M. If there are multiple such maximum connected vertex sets, the one that has the spanning tree of maximum weight is output. Because of data reduction rules, Gram does in general not output motif occurrences containing only a single vertex. Observe that every query allows for a motif occurrence of only one vertex. Thus, these are "trivial" solutions. If only trivial solutions exist, Gram may output "no nontrivial motif occurrence found". In this case, the maximum set of connected vertices that are an occurrence of a submotif of M has size 1 and every vertex of the input graph is an occurrence. 2. Random Number Generator Initialization ----------------------------------------- If you use Gram on a system that provides /dev/urandom, a value from this device is used as seed for the randon number generator. Otherwise, the system time in seconds is used as seed. Thus, beware of rapidly solving the same graph motif instances in a short time interval, because the same seed for the random number generator is being used every time. 3. File Format and Limitations on Input --------------------------------------- Input graphs should be given in graphviz format. For example, see the file "examplegraph.dot" that is distributed with Gram. Each edge must have a "weight" attribute that gives the weight of an edge. Each vertex must have a "colorlist" attribute that gives a list of colors for this vertex. This list is binary coded as a 64bit integer. That is, if a vertex has the color list "0,1,3,5,7", this is encoded as 2^0 + 2^1 + 2^3 + 2^5 + 2^7 and the according entry for vertex number 16 is: 16 [colorlist="171"] This encoding of color sets is for speed reasons, as it easily allows the enumeration of subsets. However, it has the limitation that the largest color in use can have the number 63. So a graph motif instance with more than 32 colors cannot be solved because another colors are used for color coding. Vertices must have integer names. 4. Example run / Explaining output ---------------------------------- Consider the following execution step: Input: gram examplegraph.dot Output with explaining comments: colorful motif size : 6 This line shows the size of the motif of which an occurrence is sought. maximum error probability : 0.1 random seed : 35715 Shows the seed that has been used to initialize the random number generator. It can be used to reproduce a specific run of Gram by initializing the random number generator to this value. recoloring tries used : 1 Number of recoloring trials for color coding. The lower, the better. solution size : 6 The size of the found motif occurrence. Here, we have a perfect match. solution vertices : 1335 2420 2740 362 525 1428 The vertices that constitue the solution set, if the solution size is at least two. Otherwise, no vertices might be output, but every vertex is a solution vertex. 5. Terms of Usage ----------------- (C) 2008-2010 René van Bevern Gram is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. Gram is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with Gram. If not, see . -- Jun 2nd 2010, René van Bevern