NetMatch is a Cytoscape plugin to query networks for patterns

TableOfContents

Many biological systems arise from complex interactions between components (people, organisms, cells, proteins, DNA, RNA and small molecules). Such networks are naturally modeled as large graphs, which can be analyzed using graph theoretical techniques. Locating subgraphs matching a specific topology is useful to find higher-order connectivity motifs of networks that may have functional relevance in the modeled biological system. In cell biology, it may be of interest to see whether the connectivity of genes of one functional type is similar to some characteristic shape, like a feed-forward loop. In epidemiology, acquaintance graphs between people may characterize specific patterns of disease outbreaks and can be used to optimize vaccine delivery. A query to NetMatch is a graph, some of whose elements are constants and some are wildcards (which can match an unspecified number of elements). The query results are subgraphs of the original graph connected in the same way as the query graph. NetMatch provides an efficient graph matching algorithm with extensions to handle multiple labels per node, multiple edges between pairs of nodes, and approximate queries. NetMatch has been implemented as a plugin for Cytoscape, an open source software platform for network visualization and analysis that is extensible through a straightforward plug-in architecture, allowing rapid development of additional features.

attachment:netmatch.jpg

NetMatch supports subgraph matching queries against a target network, previously loaded into the Cytoscape workspace. Approximate queries are special subgraphs that may contain: (a) nodes and edges labeled with a special wildcard symbol ?, which can match any single value of a user specified node or edge attribute; (b) approximate paths, which are paths of length <= n or >=n, where n is a positive integer, that can connect two nodes. NetMatch handles target and query graphs with multi-edges (more than one edge between two nodes), loops (edges starting and ending at the same node), and a list of attributes for each edge and node. The searching (matching) process is carried out by using the state space representation where a state is a partial mapping and a transition between two states corresponds to the addition of a new pair of matched graph nodes. The aim of the matching process is the determination of a mapping, which is a bijection, and consists of a set of node pairs covering all the query graph nodes. When a pair of nodes is added to the partial mapping, consistency conditions are checked. Such consistency rules allow the pruning of the search space, reducing significantly the computational cost of the matching process. Approximate query graphs are handled by first independently processing all maximal specified subparts and then joining in all possible ways the results of the subqueries. The joining process connects the subparts by all paths satisfying the approximate paths present in the query. NetMatch can be set to interpret labeled/unlabeled, directed/undirected networks. Users can express queries in NetMatch by (a) loading from an existing file, (b) importing from the Cytoscape workspace, (c) drawing using the NetMatch query drawing tool.

The query drawing tool allows multiple node and edge attributes, zooming, moving and resizing operations, and exports drawing results directly to NetMatch. It also has a predefined set of frequently used network motifs for convenience. The matching results are shown in NetMatch along with images of matched subnetworks and match information. Clicking on one particular match will highlight its position in the target network in the Cytoscape main view. Any matched subnetwork can be saved and further analyzed and manipulated as a separate network in the Cytoscape workspace, using standard Cytoscape features.

Installation

Download the plugin from the following URL:

http://alpha.dmi.unict.it/~ctnyu/netmatch.html or http://baderlab.org/Software/NetMatch

Copy the jar file in the Cytoscape plugins directory. When Cytoscape starts, all the plugins contained in this directory will be loaded. The plugin will be available from the Cytoscape "Plugins" item menu (see figure).

attachment:cyt1.jpg

Usage

Load a Network and/or a Query From Cytoscape

The Cytoscape "File" item menu allows loading networks or queries. Two choices are possible: "Import/network..." or "Open". Moreover, by selecting "Import/Node Attributes..." and "Import/Edge Attributes...", nodes and edges attributes files can be associated with a network. See the main Cytoscape documentation for more information and to find other ways of loading networks into Cytoscape.

Queries can be also defined with the NetMatch Query Tool (see "query drawing tool" help page).

attachment:load.jpg

NetMatch Options

Once networks and/or queries are loaded, these will be available through the NetMatch plug-in when executed.

Several options are be available:

attachment:properties.jpg

attachment:query.jpg

attachment:net.jpg

attachment:multip2.jpg

attachment:options.jpg

View Results

The right top panel shows for each occurrence of the query in the network:

attachment:res.jpg

Clicking on one such match, its nodes in the network (shown in the Cytoscape desktop) are selected (highlighted). If "Create a new child network" is checked and a match result is clicked then a new network containing the query is created and displayed in the Cytoscape window. The "Save" button stores information of query results in a text file.

When more than 500 matches are found, it can be time consuming to display all results. In this case, NetMatch asks if the user wants to display all results, display only the text results or don’t show results (in order to refine the search).

The lower right panel shows a log of match.

attachment:log.jpg

Query Drawing

A query drawing tool is launched by "Query/Draw". It allows the user to draw exact and approximate queries. An approximate query contains unspecified node labels and edge labels, paths of length greater than one (specified as an attribute of the path connector).

attachment:d.jpg

Palette Toolbar

attachment:select.jpg Select: Move and resize a selected node or edge.

attachment:move.jpg Move: Selecting this button allows moving the entire query in the drawing window by clicking on it and dragging.

attachment:addnode.jpg Add Node: Selecting this button enables adding a new node to the drawing window by clicking on the drawing canvas. The default attribute is "Unlabeled". It is possible to change the attribute by clicking the node with right mouse button..

attachment:addloop.jpg Add Loop edge: Selecting this button allows adding a loop edge to an existing node. The default attribute is "Unlabeled". It is possible to change the attribute by clicking the edge with right mouse button. It is possible to add multi-loops from a node to another.

attachment:addedge.jpg Add Edge: Selecting this button enables adding a new edge to the drawing window by clicking on an existing node and to another one. The edge is directed. The default attribute is "Unlabeled". It is possible to change the attribute by clicking the edge with right mouse button. It is possible to add multi-edges from a node to another.

attachment:addpath.jpg Add approximate Path: Selecting this button it is possible to add an approximate path to the drawing window by clicking on an existing node and to another one. The default attribute is "?>0" (this means that the user wants an approximate path of length > 0). It is possible to change the attribute by clicking the edge with right mouse button. It is possible to add multi-paths from a node to another.

attachment:zoomin.jpg Zoom in: Click to zoom in on the drawing window.

attachment:zoomout.jpg Zoom out: Click to zoom out of the drawing window.

Motifs Toolbar

attachment:threechain.jpg Three Chain Motif: Selecting this button and clicking on the canvas adds a three chain motif to the drawing window.

attachment:feed.jpg Feed Forward Loop Motif: Selecting this button and clicking on the canvas adds a feed forward loop motif to the drawing window.

attachment:biparallel.jpg Bi-parallel Motif: Selecting this button and clicking on the canvas adds a bi-parallel motif to the drawing window.

attachment:bifan.jpg Bi-fan Motif: Selecting this button and clicking on the canvas adds a bi-fan motif to the drawing window by clicking on it.

Main Toolbar Buttons

attachment:new.gif Create a new query.

attachment:load.gif Load an existing query in sif format.

attachment:save.gif Save a Query. It automatically creates three files: a ".sif" file containing the query, a ".na" file containing node attributes and a ".ne" file containing edge attributes.

attachment:change.gif Change name of a query. This allows the drawn query to be renamed for ease of use in the main window. Otherwise, it will get a default name.

attachment:exit.gif Exit from query editor. If the query is not saved user will be prompted to save it.

attachment:clear.gif Clear drawing window. Press to clear the drawing window.

attachment:pass.gif Pass the query to NetMatch. The new query will be uploaded in the "Query Selection box" in NetMatch window. The drawing tool main windows can be closed or can be left opened for other modifications.

Modify Node/Edge Attributes or Delete

It is possible to edit a node, an edge or a path attribute by clicking on it with the right mouse button and then selecting the "Edit Attribute..." item menu.

attachment:edit.jpg

attachment:na.jpg

attachment:pa.jpg

Load/Save a query

attachment:menu.jpg

Using Wizard

  1. Start NetMatch in Wizard mode.

attachment:wiz1.jpg

  1. Select the target network.

attachment:wiz2.jpg

  1. Select nodes and edges attributes for the target network.

attachment:wiz3.jpg

  1. Select query network or draw a query.

attachment:wiz4.jpg

  1. Select nodes and edges attributes for the query. Notice that, if the query has been drawed with the query drawing tool, nodes and edges attributes will be those defined through the drawing tool.

attachment:wiz5.jpg

  1. The radio buttons (Labeled/Unlabeled) enable/disable nodes and edges labels usage (i.e. if the target network and/or query have labels and "Unlabeled" is selected these will be treated as an unlabeled networks).

attachment:wiz6.jpg

The radio buttons (Directed/Undirected) enable/disable edges direction for both query and target network (i.e. if "Undirected" is selected target network and query will be treated as an undirected graphs)

NetMatch by Example

Find all feed-forward loops in galFiltered.xgmml network

  1. Load GalFiltered.xgmml file from Cytoscape File menu (it is in sampleData directory).

attachment:load.jpg

  1. Run NetMatch.

attachment:cyt1.jpg

  1. Select drawing tool.

attachment:d.jpg

  1. Select "Feed Forward Loop" from the Motifs panel.

attachment:3.jpg

  1. Click on drawing canvas with left mouse button. This will add a Feed Forward loop.

attachment:sel.jpg

  1. Click on "Pass to NetMatch" button to upload the query to NetMatch main window. It is also possible to save the query or change its name. The drawing tool window can be closed or can be left opened for other modifications.

attachment:pass.gif attachment:4.jpg

  1. Make sure from the Query Properties box the new query (QE-unnamed_1) is selected.

attachment:attr5.jpg

  1. Make sure from the Network Properties box "Yeast Network (galfiltered.gml)" is selected.

attachment:attr6.jpg

  1. Click the "Go" button to start the matching.

attachment:options.jpg

  1. The result is showed in the upper left panel. By clicking on a match, the corresponding nodes and edges will be highlighted in the Cytoscape main window.

attachment:attr7.jpg

NetMatch by Example

Find all "short" paths from proteins located in the plasma membrane to proteins in the nucleus in galfiltered.xgmml network

  1. Load GalFiltered.xgmml file from Cytoscape File menu (it is in sampleData directory).

attachment:load.jpg

  1. Run NetMatch.

attachment:cyt1.jpg

  1. Select drawing tool.

attachment:d.jpg

  1. Select "Add Node" from Palette Panel clicking on it with left mouse button.

attachment:node.jpg

  1. Add two nodes on drawing canvas (clicking with the left mouse button).

attachment:node2.jpg

  1. Change the attribute of the first node clicking on it with the right mouse button.

attachment:node3.jpg

  1. Set the attribute as "plasma membrane" (notice that the tool is case sensitive).

attachment:plasma.jpg

  1. In the same way, change the attribute of the second node in "nucleus".

attachment:plasma2.jpg

  1. Select "Add Path" from Palette Panel clicking on it with left mouse button.

attachment:plasma3.jpg

  1. Add the path clicking with the left button, first on "plasma membrane" node and then on "nucleus" node.

attachment:plasma4.jpg

  1. Change the attribute of the path clicking on it with the right mouse button.

attachment:plasma5.jpg

  1. Set the path attribute as "<4" (we want a path with length <4).

attachment:plasma6.jpg

  1. Click on "Pass to NetMatch" button to upload the query to NetMatch main window. It is also possible to save the query or change its name. The drawing tool window can be closed or can be left opened for other modifications.

attachment:pass.gif attachment:4.jpg

  1. Make sure from the Query Properties box the new query (QE-unnamed_1) is selected.

attachment:attr5.jpg

  1. Make sure from the Network Properties box "Yeast Network (galfiltered.gml)" is selected.

attachment:attr6.jpg

  1. Select from the Network Node Attribute menu the "GO Cellular Component" attribute.

attachment:plasma7.jpg

  1. Click the "Go" button to start the matching.

attachment:options.jpg

  1. The result is showed in the upper left panel. By clicking on a match, the corresponding nodes and edges will be highlighted in the Cytoscape main window.

attachment:plasma8.jpg

NetMatch by Example

Find all three-chain motifs in galfiltered.sif network where the genes are all significantly differentially expressed (Gal1RGsig < 0.01)

  1. Load GalFiltered.sif file from Cytoscape File menu (it is in sampleData directory).

attachment:load.jpg

  1. Load gene expression attributes "galExpData.pvals" file from Cytoscape File menu (it is in sampleData directory).

attachment:cyt3.jpg

  1. Run NetMatch.

attachment:cyt1.jpg

  1. Select drawing tool.

attachment:d.jpg

  1. Select "Three chain loop" from Motif Panel clicking on it with left mouse button.

attachment:tcm.jpg

  1. Add The Three Chain on drawing canvas (clicking with the left mouse button).

attachment:tcm2.jpg

  1. Change the attribute of the first node clicking on it with the right mouse button.

attachment:tcm3.jpg

  1. Set the attribute as "<0.01" (all nodes in the network having a value in the specified attribute <0.01 will match).

attachment:tcm4.jpg

  1. In the same way, change the attributes of the remaining nodes to "<0.01".

attachment:tcm5.jpg

  1. Click on the Pass to NetMatch button in order to upload the query to NetMatch main window. It is also possible to save the query or change its name. The drawing tool main windows can be closed or can be left opened for other modifications.

attachment:pass.gif attachment:4.jpg

  1. Make sure from the Query Properties box the new query (QE-unnamed_1) is selected.

attachment:tcm6.jpg

  1. Make sure from the Network Properties box "GalFiltered.sif" is selected.

attachment:tcm7.jpg

  1. Select from the Network Node Attribute menu the "gal1RGsig" attribute.

attachment:tcm8.jpg

  1. Click the "Go" button to start the matching.

attachment:options.jpg

  1. The result is showed in the upper left panel. By clicking on a match, the corresponding nodes and edges will be highlighted in the Cytoscape main window.

attachment:tcm9.jpg

Download

[attachment:netmatch.zip Download jar plugin, together with example data.]

Version 1.0.1 - 22/12/2006 Developed by:

A. Ferro, R. Giugno, G. Pigola, A. Pulvirenti, D. SkripinBR Department of Mathematics and Computer Science - University of CataniaBR Viale A. Doria 6, I-95125 Catania, Italy.BR email:{ferro,giugno,pigola,apulvirenti,skripin}@dmi.unict.it

G. BaderBR Banting and Best Department of Medical Research & Department of Medical Genetics and MicrobiologyBR University of TorontoBR 160 College St., Toronto, Ontario, Canada M5S 3E1BR e-mail:gary.bader @ utoronto.ca

D. ShashaBR Courant Institute of Mathematical Science - New York UniversityBR 251, Mercer Street, New York, NY 10012, U.S.A.BR email:shasha @ cs.nyu.edu

Software/NetMatch (last edited 2006-12-22 21:36:02 by GaryBader)

MoinMoin Appliance - Powered by TurnKey Linux