graph-prac.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Graphical analysis of protein interactions in yeast\n",
    "\n",
    "The aim of this practical is to examine some uses of graphical analysis in a biological setting. The analyses are identical to those demonstrated in the London Tube Graph examples in the introduction to systems biology lecture.\n",
    "\n",
    "The approaches we saw in the London Tube Map example involved visual examination of the coloured nodes and edges of the graph. For large biological (or other) graphs, this is not feasible. The graph we will be looking at today is shown here.\n",
    "\n",
    "![Yeast PIN showing node degree](yeast-pin.png)\n",
    "\n",
    "Questions to be answered for the assignment are written in **bold**. Answers are to be written in the blank cells immediately below the question and the assignment should be submitted as a Notebook file with the name `graph-prac-aNNNNNNN.ipynb` where aNNNNNNN is your a-number (jupyter: File → Download as → Notebook (.ipynb) when you have written your answers). This file should be packaged into a zip file called `graph-prac-aNNNNNNN.zip` with no other files. A cover sheet will not be necessary for submission. Submit via MyUni.\n",
    "\n",
    "The assignment is due Monday 27nd October before 5pm ACDT.\n",
    "\n",
    "### Programming language\n",
    "\n",
    "The practical uses the [Go programming language](https://golang.org/). Go is a statically typed, compiled language, but we will be using it through an interactive environment called Jupyter. This tries to make Go behave as an interpretted language, and this may cause some problems at some stages. If you have any problems, please ask the demonstrators for help.\n",
    "\n",
    "### Setting up the package imports\n",
    "\n",
    "Go modularises code into packages (much the same way as other languages, though different languages will use different terms for the same concept). Go packages must be imported before they can be used. In a compiled Go program this *must* happen at the beginning of a source code file, though in jupyter, this is not strictly necessary.\n",
    "\n",
    "The packages that we will use are for printing, `\"fmt\"`, logging errors, `\"log\"`, and performing the graph analyses, `\"github.com/kortschak/graphprac\"`. The first two packages are provided with the language and the last is a small package that wraps graph routines made available through the graph packages of the https://gonum.org project, [`graph/...`](https://godoc.org/gonum.org/v1/gonum/graph/)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import (\n",
    "    \"fmt\"\n",
    "    \"log\"\n",
    "\n",
    "    \"github.com/kortschak/graphprac\"\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The documentation for the `\"github.com/kortschak/graphprac\"` package is available from the godoc.org website: http://godoc.org/github.com/kortschak/graphprac. You can click on links on the documentation page to see the source of the functions and to link to the definitions of types and externally provided functions. This is an excellent way to get to understand the code.\n",
    "\n",
    "The routines wrapped by the `\"github.com/kortschak/graphprac\"` are in [`graph/network`](https://godoc.org/gonum.org/v1/gonum/graph/network) and [`graph/community`](https://godoc.org/gonum.org/v1/gonum/graph/community).\n",
    "\n",
    "### Read in a graph\n",
    "\n",
    "The graph is from a [data set](http://vlado.fmf.uni-lj.si/pub/networks/data/bio/Yeast/Yeast.htm) used in an analysis of topological structure in the yeast protein interaction network (DOI:[10.1093/nar/gkg340](https://doi.org/10.1093/nar/gkg340))."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "infile := \"YeastL.dot\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "g, err := graphprac.NewGraph(infile)\n",
    "if err != nil {\n",
    "    log.Fatalf(\"failed to read graph: %v\", err)\n",
    "}\n",
    "{\n",
    "    fmt.Printf(\"G has %d nodes and %d edges.\\n\", g.Nodes().Len(), g.Edges().Len())\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Notice that the number of nodes agrees with the data set summary linked above, but the number of edges disagrees. Suggest why this might be.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Examining the nodes\n",
    "\n",
    "There is no `head` function in Go (we could write one, but the code is short, so there is no need).\n",
    "\n",
    "The following code loops over the first 10 elements of the nodes slice (essentially an array - there are differences in Go, but that is not important here) and prints out the node value stored in `n`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for _, n := range graphprac.NodesOf(g)[:10] {\n",
    "    fmt.Println(n)\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that running this multiple times will result in different sets of nodes being printed as the nodes returned by `g.Nodes()` are selected in a random order, so the first ten will differ. Try this out.\n",
    "\n",
    "**Why is it not important that a node list be returned in a specific order?**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Network analysis\n",
    "\n",
    "We are going to look at nodes that have a high connectivity or potential for information flow through the network.\n",
    "\n",
    "Two measures that we can use to do this (*very roughly*) are node betweenness centrality and PageRank.\n",
    "\n",
    "The routines provided in the `graphprac` package write their analysis results into the graph that is provided as a parameter. This is not how we normally do this kind of analysis, but it makes the practical simpler.\n",
    "\n",
    "The writing into the graph is done via a set of attributes that have names that can be queried using the functions in the package."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**How can an attribute be queried?**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Use an example to demonstrate.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The first analysis is for node betweenness of G."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "graphprac.Betweenness(g)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "nodes, err := graphprac.NodesByAttribute(\"betweenness\", g)\n",
    "if err != nil {\n",
    "    log.Fatalf(\"failed to obtain nodes: %v\", err)\n",
    "}\n",
    "for _, n := range nodes[:10] {\n",
    "    attr := n.Attributes\n",
    "    fmt.Printf(\"%s %s -- %s\\n\", n.Name, attr.Get(\"betweenness\"), attr.Get(\"desc\"))\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**If you rerun the code block above, does the order/set of nodes change like in the previous example? Why?**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next we perform a PageRank analysis of G. There are two additional parameters here, `damp` and `tol`.\n",
    "\n",
    "**What is the purpose of these two parameters? _Hint: You will need to read about PageRank._**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "graphprac.PageRank(g, 0.85, 1e-4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we print out the ten highest ranked nodes and keep the highest ranked node of all."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "nodes, err := graphprac.NodesByAttribute(\"rank\", g)\n",
    "if err != nil {\n",
    "    log.Fatalf(\"failed to obtain nodes: %v\", err)\n",
    "}\n",
    "bestRank := nodes[0]\n",
    "for _, n := range nodes[:10] {\n",
    "    attr := n.Attributes\n",
    "    fmt.Printf(\"%s %s -- %s\\n\", n.Name, attr.Get(\"rank\"), attr.Get(\"desc\"))\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Look at the two sets of highest ranked nodes from the betweenness and PageRank analyses. How well do they agree? How does this situation compare to the case of the London Tube Graph example? Why do you think this is?**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The next step is to identify sets of nodes that interact more strongly within the set than they do between sets. These sets are called communities.\n",
    "\n",
    "![Modular graph showing communities](http://journals.plos.org/ploscompbiol/article/figure/image?size=large&id=10.1371/journal.pcbi.1000190.g004 \"Müller-Linow et al PLoS Comp Biol 2008:e1000190\")\n",
    "\n",
    "The `graphprac.Communities` function takes a single extra parameter, `resolution`. We are using a resolution of 5."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "graphprac.Communities(g, 5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we are going to identify the community that the highest PageRanked node is in. Note that the algorithm used to identify communities is a randomised algorithm, the [Louvain Algorithm](https://en.wikipedia.org/wiki/Louvain_Modularity), and so different runs will produce a different name for the community and may include slightly different community memberships.\n",
    "\n",
    "*Community detection is an NP-hard problem and the Louvain Algorithm gives us a reasonable approximation in reasonable time.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nodes, err := graphprac.NodesByAttribute(\"community\", g)\n",
    "if err != nil {\n",
    "    log.Fatalf(\"failed to get community: %v\", err)\n",
    "}\n",
    "comm := \"\"\n",
    "for _, n := range nodes {\n",
    "    attr := n.Attributes\n",
    "    if n.Name == bestRank.Name {\n",
    "        comm = attr.Get(\"community\")\n",
    "        break\n",
    "    }\n",
    "}\n",
    "{\n",
    "    fmt.Printf(\"%s is in community %s\\n\", bestRank.Name, comm)\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for _, n := range nodes {\n",
    "    attr := n.Attributes\n",
    "    if attr.Get(\"community\") == comm {\n",
    "        fmt.Printf(\"%s -- %s\\n\", n.Name, attr.Get(\"desc\"))\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**What are the functions of these proteins? Would you expect them to be in the same community? Hint:http://www.yeastgenome.org/**\n",
    "\n",
    "**What happens when you alter the resolution parameter to `graphprac.Communities`? Note here that there is another tool, Gephi, that performs community detection but inverts the meaning of the resolution parameter. Do not use their definition.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can render the graph visually using external tools provided by [GraphViz](https://www.graphviz.org/). The `graphprac.Induce` function produces a subgraph based on `g` that only includes nodes in `g` that are also in the `by` parameter (this is termed an [induced subgraph](https://en.wikipedia.org/wiki/Induced_subgraph)). `graphprac.Draw` then generates an SVG graphic rendering of the graph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "by := []*graphprac.Node{}\n",
    "for _, n := range nodes {\n",
    "    attr := n.Attributes\n",
    "    if attr.Get(\"community\") == comm {\n",
    "        by = append(by, n)\n",
    "    }\n",
    "}\n",
    "subgraph := graphprac.Induce(g, by)\n",
    "svg, err := graphprac.Draw(subgraph, \"fdp\")\n",
    "if err != nil {\n",
    "    fmt.Println(err)\n",
    "}\n",
    "display.SVG(svg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally we are going to look for potential targets to disrupt the function of this community. By looking for edges that have a high edge betweenness we may be able to identify candidates for molecular disruption.\n",
    "\n",
    "**Run the two code cells below and choose an interaction pair that looks like it might be a good candidate for a druggable target. Write the names of the two proteins you chose in the next cell.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Notice that the number of edges reported below is significantly higher than shown in the graph rendering above. Have a look at the source code associated with [`graphprac.Induce`](https://godoc.org/github.com/kortschak/graphprac#Induce) and explain why this is the case. Why might it be useful to be more inclusive in the case here of looking for druggable targets?**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "graphprac.EdgeBetweenness(g)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "edges, err := graphprac.EdgesByAttribute(\"edge_betweenness\", g)\n",
    "if err != nil {\n",
    "    log.Fatalf(\"failed to obtain nodes: %v\", err)\n",
    "}\n",
    "for _, e := range edges {\n",
    "    fattr := e.F.Attributes\n",
    "    tattr := e.T.Attributes\n",
    "    if fattr.Get(\"community\") != comm && tattr.Get(\"community\") != comm {\n",
    "        continue\n",
    "    }\n",
    "    attr := e.Attributes\n",
    "    fmt.Printf(\"%s--%s %s (%s--%s)\\n\", e.F.Name, e.T.Name, attr.Get(\"edge_betweenness\"), fattr.Get(\"desc\"), tattr.Get(\"desc\"))\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Write a page (~300 words) explaining why you chose the target you did and how it could potentially be investigated further. Give references for information you introduce.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Go",
   "language": "go",
   "name": "gophernotes"
  },
  "language_info": {
   "codemirror_mode": "",
   "file_extension": ".go",
   "mimetype": "",
   "name": "go",
   "nbconvert_exporter": "",
   "pygments_lexer": "",
   "version": "go1.14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}