Graph theory primer

Aim

In this blogpost, I will review foundational concepts underlying co-occurrence networks and apply them to visualize a drinking water metagenome dataset.

Scope

The information discussed in the “Background” section is in part a summary of the “Graph Theory for Data Science” workshop series taught by Stanford University PhD student Julia Olivieri, as a part of Women in data science workshop series. Her workshops are available on youtube and consist of the three parts:

• Part I: What is a graph and What Can We Do With It?

• Part II: Graph Algorithms: Traversing the tree and beyond

• Part III: Characterizing Graphs in the Real World

In May 2019, I was one of the workshop organizers for Meta-omics in Environmental Engineering Research at the Association of Environmental Engineering and Science Professors (AEESP) conference. The slides I presented there are shared within this post as well.

Additionally, the plugging CoNet in the Cytoscape application will be used to infer associations between metagenome assembled genomes (MAGs) from drinking water systems.

The main objective of this post is to use R packages to describe and visualize the network.

Background

Graphs are structures that represent relationships between things.

The formal definition of a graph, G is

\[ G = (v,E) \]

the set of vertices, v (i.e., nodes), and edges, E (i.e., links) such that v is finite and non-empty and each element of E is a two-element subset of v.

In order to describe the topology of the graph we rely on different scores. Centrality measures, for example, are useful to determine the importance of nodes and edges compared to the remaining components of the graph.

There are multiple types of graphs that we might be familiarized with. For example, phylogenetic trees show ancestral relationships between taxa, chemical structures show connection between molecules, and co-occurrence networks are representations of the relationships between biological entities within a context. In this post, I will be describing the co-ocurrence network of metagenomes from drinking water systems.

There are a few tools at our disposal for co-occurrence inference from sequencing data, but I’m more familiar with CoNet. This tool detects non-random patterns of co-occurrence in presence/absence and abundance data based on user selected thresholds.

The general workflow is:

1. Preprocessing

   raw data matrix is processed by removing rare taxa, and normalizing counts

2. Edge score computation

   pairwise scoring using a range of measures (i.e., ensemble method) to capture different types of relationships

3. Significance assessment

   Computation of p-value using a Z-test, comparing the permutation distribution mean given the bootstrap distribution

CoNet runs on command line and as a Cytoscape plugin, there is also an R implementation, but is not on CRAN or continuously maintained.

Libraries

library(tidyverse)
library(visNetwork)
library(igraph)

Data wrangling

The tables resulting from the CoNet workflow require minimal wrangling. Here’s a sneak peak of the node and edge tables, respectively.

## # A tibble: 6 x 2
##   id      value
##   <chr>   <dbl>
## 1 DW01178    22
## 2 DW01233    20
## 3 DW01231    20
## 4 DW01139    20
## 5 DW01202    19
## 6 DW01177    18

## # A tibble: 6 x 5
##   from    to      weight interactionType color  
##   <chr>   <chr>    <dbl> <chr>           <chr>  
## 1 DW01142 DW01102      0 copresence      #00b300
## 2 DW01132 DW01177      0 copresence      #00b300
## 3 DW01235 DW01225      0 copresence      #00b300
## 4 DW01178 DW01202      0 copresence      #00b300
## 5 DW01233 DW01138      0 copresence      #00b300
## 6 DW00423 DW00424      0 copresence      #00b300

Analyses

A high level summary of network metrics are shown below:

For a comprehensive description of metrics and their interpretation, take a look a this site.

Let’s see what the network looks like!

In this network, positive and negative type interactions are colored green and red, respectively.

I’ve also created this shiny app to play with the network’s layout. Take a look!

From the network graph we can see that there are two large components (or clusters), in fact 71.12% of the MAGs are part of those clusters.

We will now hone in on these nodes by creating two connected sub-graphs.

As discussed in the ?? section, we can use centrality measures to describe node importance.

The MAGs with largest degrees correspond to DW01178 and DW00270, DW00626 in cluster 1 and 2, respectively. However, we know that degree alone is not the best metric for node importance. Let’s take a look at global metrics of centrality.

The highest ranking MAGs for each metric in terms of centrality are

Further, higher level metrics for both subgraphs are provided below.