NetMatch

 
 

Introduction

 

The following help refers to Netmatch plug-in version 1.0.1. The current version (Netmatch 2.0) is developed as Cytoscape panel. Netmatch usage remains the same as in the past version except that the data are automatically acquired from Cytoscape main window. Moreover Netmatch 2.0 uses another algorithm for approximate paths which filters results considering only disjoint paths.

 

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.

 
 
Netmatch 1.0.1

 

 
Netmatch 2.0

 

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.