GraMoFoNe

GraMoFoNe, a Plugin for Cytoscape. GraMoFoNe (Graph Motif For Networks) is under GPL licence, written in Java 1.6 and developed as a plugin for Cytoscape. Cytoscape is an open-source software platform for network visualization and analysis, which supports the development of external plugin tools extending its functionality. Our plugin seeks for connected occurrences of a motif (set or multiset of proteins), given by the user, into a Protein-Protein Interaction network previously loaded into the Cytoscape workspace (many file format are supported). Similarity is measured among sequence-similarity via a Blastp analysis: proteins in the motif got different colors, proteins of the network are colored with the colors of motif proteins which are homologous. Note that a network node can have 0, 1 or more colors. GraMoFoNe allows deletions (proteins in the motif but not in the resulting connected subnetwork), and insertions (proteins in the results but not in the motif) of colored or uncolored network nodes. It uses an exact algorithm to perform this task. To this end, we choose to express our problem as a linear pseudo-boolean optimization problem (LPB), i.e. as a linear program whose variables are boolean. We choose Sat4JPseudo.