Network Analysis Tools (NeAT)

Category Cross-Omics>Pathway Analysis/Tools

Abstract The Network Analysis Tools (NeAT) provide a user-friendly web access to a collection of modular tools for the analysis of networks (graphs) and clusters (e.g. microarray clusters, functional classes, etc.).

The first set of tools supports basic operations on graphs (comparison between two graphs, a neighborhood of a set of input nodes, path finding and graph randomization).

Another set of programs makes the connection between networks and clusters (graph-based clustering, cliques’ discovery and mapping of clusters onto a network).

The toolbox also includes programs for detecting significant intersections between clusters/classes (e.g. clusters of co-expression versus functional classes of genes)

.

NeAT are designed to cope with large datasets and provide a flexible toolbox for analyzing 'biological networks' stored in various databases (protein interactions, regulation and metabolism) or obtained from high- throughput experiments (two-hybrid, mass-spectrometry and microarrays).

The web interface interconnects the programs in predefined analysis flows, enabling you to address a series of questions about your networks of interest.

Each tool can also be used separately by entering custom data for a specific analysis. NeAT can also be used as a web service (SOAP/WSDL interface), in order to design programmatic workflows and integrate them with other available resources.

NeAT tools can be broadly grouped into three (3) categories: 1) network tools - perform various operations on one or several graphs; 2) cluster tools -are mainly dedicated to comparisons between clusters; and 3) network-clusters tools - make the connection between networks and clusters.

1) NeAT Network tools --

Network topology - Several statistics have been defined to characterize global topological properties of a network. It has been shown that these topological properties distinguish biological networks from random networks.

Noticeably, it is often stated that the distribution of degree (the number of edges connected per nodes) follows a power-law distribution.

The program graph-topology computes the degree of each node of a graph, which can then be analyzed either as a full result table or visualized as an XY plot.

Graph-topology also computes the betweenness (i.e. the proportion of 'shortest' going through a node) and the closeness (i.e. the mean shortest distance of a node to all others) of each node in the network.

Node neighborhood - Starting from one or several nodes of interest, the program graph-neighbours collects neighbor nodes up to a user- specified distance.

Neighborhood analysis can be (for example) applied to predict the function of an unknown polypeptide by collecting its neighbors with known function in a protein interaction network (guilty by association).

Network comparison - The program compare-graphs computes the intersection, the union and/or the difference between two input networks and estimates the statistical significance of the overlap.

Evaluation of predicted networks using receiver operating characteristic (ROC) curves - The program roc-stats is typically used as a post analysis program after a network comparison between predicted and annotated networks.

It takes as input a set of scored results associated with validation status (positives or negatives) and computes, for each threshold on the score, the derived statistics: true positive rate (TPR, also called ‘sensitivity’), positive predictive value (PPV), false positive rate (FPR) and accuracy.

Path finding in a network (Pathfinder) - The NeAT interface includes a general k-shortest path finding algorithm that supports searches from a set of (one or several) source nodes to a set of target nodes. Node weights can either be specified in the input graph or computed automatically according to node degree.

Network randomization and alteration - The program random-graph supports different procedures to randomize a network, which can then be submitted to the same workflows in the same way as a real biological network. Random graphs can be generated from scratch, according to an Erdös-Renyi model.

Alternatively, random graphs can be generated by permuting the edges between the nodes of a given input graph. This randomization preserves the degree of each node.

A third mode of randomization preserves the degree distribution of the input graph, without preserving the degree of individual nodes.

Another tool, alter-graph, performs a partial randomization of a given input graph, by combining two operations: random addition and/or deletion of nodes and/or edges.

Altered graphs are particularly useful for studying the robustness of procedures for the presence of noise (node/edge additions) or for missing information (node/edge deletions).

Network display - NeAT includes a tool called display-graph, which can generate static images of an input network. NeAT can also load a network directly into the VisANT (see G6G Abstract Number 20338) graph editor via the Java Web Start process.

For more advanced visualization facilities, the manufacturer recommends specialized 'graph editors' such as, yED Graph Editor and Cytoscape (see G6G Abstract Number 20092).

For this purpose, the tool convert-graph permits you to export any network resulting from NeAT to the Graph Markup Language (GML) format which is supported by both these editors.

2) NeAT Cluster tools --

NeAT also presents a series of tools which allows you to study clusters or classification (functional classes).

For example, the program compare-classes can be used to study the process of - [if among the clusters of highly connected nodes extracted from a graph via some clustering algorithm, some overlap with biological relevant classes (e.g. Gene Ontology classes) exists].

This program also allows you to create a contingency table that can be further analyzed via the contingency-stats application.

3) NeAT Network-clusters tools --

Network clustering - The graph-based clustering algorithms Markov cluster (MCL) and Restricted Neighborhood Search Clustering Algorithm (RNSC) have been shown to obtain good performances for extracting protein complexes from ‘protein interaction networks’.

These algorithms can deal with large graphs and are very efficient in time. For these reasons, the manufacturer has included them in the NeAT tool suite. Moreover, NeAT also includes a tool that discovers Cliques (a fully connected set of nodes) in networks.

From partitions to fuzzy clusters - Some graph-based clustering algorithms support multiple assignment and non-assigned nodes (i.e. fuzzy clustering), but the tuning of their parameters is sometimes delicate and the results can sometimes be weaker than those of a partitioning algorithm.

To keep the best of both worlds, an approach is to first run a partitioning algorithm and to post process its results by measuring a posteriori, the membership between each node and each cluster of the partition.

The membership of a node to a cluster is the proportion of edges from this node that reach that cluster. If the graph is weighted, the membership can take edge weights into account.

This two-step approach has been used to perform a 'reticulate classification' of phages and detect mosaic phages resulting from fusions between other phage genomes.

The program graph-cluster-membership takes as input a graph and a clustering result, and returns a node/cluster table indicating the degree of membership of each node to each cluster.

On the NeAT site, clustering results can be automatically launched from the graph-cluster-membership form. Graph-cluster-membership can also be easily adapted to be combined with other graph-based clustering algorithms.

System Requirements

Web-based.

Manufacturer

Manufacturer Web Site NeAT

Price Contact manufacturer.

G6G Abstract Number 20501

G6G Manufacturer Number 104121