LoTo: a graphlet based method for the comparison of local topology between gene regulatory networks

Abstract

One of the main challenges of the post-genomic era is the understanding of how gene expression is controlled. Changes in gene expression lay behind diverse biological phenomena such as development, disease and the adaptation to different environmental conditions. Despite the availability of well-established methods to identify these changes, tools to discern how gene regulation is orchestrated are still required. The regulation of gene expression is usually depicted as a Gene Regulatory Network (GRN) where changes in the network structure (i.e., network topology) represent adjustments of gene regulation. Like other networks, GRNs are composed of basic building blocks; small induced subgraphs called graphlets. Here we present LoTo, a novel method that using Graphlet Based Metrics (GBMs) identifies topological variations between different states of a GRN. Under our approach, different states of a GRN are analyzed to determine the types of graphlet formed by all triplets of nodes in the network. Subsequently, graphlets occurring in a state of the network are compared to those formed by the same three nodes in another version of the network. Once the comparisons are performed, LoTo applies metrics from binary classification problems calculated on the existence and absence of graphlets to assess the topological similarity between both network states. Experiments performed on randomized networks demonstrate that GBMs are more sensitive to topological variation than the same metrics calculated on single edges. Additional comparisons with other common metrics demonstrate that our GBMs are capable to identify nodes whose local topology changes between different states of the network. Notably, due to the explicit use of graphlets, LoTo captures topological variations that are disregarded by other approaches. LoTo is freely available as an online web server at http://dlab.cl/loto.

Keywords: Differential analysis; Gene Regulatory Network; Graphlet; Metric.

Figure 1. All possible realizations of three node graphlets that can be defined in LoTo.

The direction of edges indicate the sense of the transcriptional regulation. Black edges denote true interactions, and red-dashed edges depict false ones. In this definition, true and false edges are given equal relevance. Adapted from Milo et al. (2002).

Figure 2. Comparison between single-edge and GBMs.

For each randomization procedure, average values over 1 × 10³ replicas for single-edge (solid blue line) and graphlet-based (solid red line) F1 and MCC are shown at different percentages of randomization. (A and B) Show F1 for SWAP and REMO randomizations respectively; and (C and D) show MCC for the SWAP and REMO cases respectively.

Figure 3. Contribution of each graphlet type to F1 and MCC GBMs on the two randomization procedures of the E. coli reference network.

For each randomization procedure, the plots show the contribution of each graphlet type to the averaged values of each metric over the 1 × 10³ replicas. The X-axis indicates the percentage of randomization, ranging from total randomization on the lefthand side to no variation on the right side. The Y-axis indicates the contribution of each graphlet type to the metric in the form of a percentage. (A) shows F1 for the SWAP randomization, and (B) F1 for the REMO randomizations respectively; and (C and D), MCC for the SWAP and REMO cases, respectively.

Figure 4. ompR subnetwork.

Subnetwork formed by all graphlets in which ompR participates (red colored node) showing the comparison between wild-type and the ompR knock-out GRNs. The subnetwork elements are displayed using different colors for TF-coding genes and effector genes. TP elements are those present in both networks being compared, FN are network elements present only in the wild-type network and FP are those elements present only in the ompR network. The small insert represent the subnetwork formed by only direct neighbors of ompR in the comparison using the same coloring scheme.