Overview

In today’s workshop we will be looking to:

We will also see how to:

Networks

Networks are everywhere and they are formed by the interactions. Specifically, interactions between elements in a network. Those elements might be computers, if we’re thinking about the network of computers on campus, or they might be species in a complex ecosystem. Today, we’ll explore various networks we have available in biosciences.

Biological networks are often incomplete. Some networks are very complete, meaning we know all interactions, because we have designed them to be. Others, like interactions between organisms (microbes to macrobes) in coastal wetlands, may be severely underspecified - meaning we are missing many real interactions. As we add more layers of information to networks, we often change (sometimes drastically) the topology of a network.

Networks are useful tools to help us explain a complex world. Useful as networks are they not without faults. It is important to remember that our ideas about networks, and the theory and practice of analyzing them, are human inventions. Organisms in nature do not care about networks. Networks are an emergent property of organisms living their lives, day to day. Networks also imply something static about interactions. This can be very misleading, particularly in natural systems where species members or diets may be ephemeral (or short lived).

So, as we examine networks here or as you use them in your research, remain critical about what interactions in a network mean and whether the network being used is a fairly complete representation of possible interactions.

Ecological network databases

There are a wide variety ecological databases. Most public databases describe interactions of species in a given environment.

Here are a few:

The transition to public availability in ecological data is fairly new. As a result, many of these databases are underdeveloped compared to some of the extensive cellular pathway databases. However, there is a lot of interest in sharing these types of data in developing ecological models so there is rapid growth in ecological data sharing.

Pathway databases

Major sources of biological pathways are in cellular signaling, cellular metabolism, and nutrient cycling. We’ll focus on a couple of pathway databases.

Reactome

Take a look at the Pathway Browser.


Question

What kind of information do you find available for Homo sapiens? List 3 or 4.


BioCyc

Now, let’s take a look at BioCyc. In the search field, input “glycolysis”. Select “Glycolysis I”.


Question

Describe 3 types of information you could gather from this database entry?


Functional interacterion databases

There are many different types of interactions in a cell that result in changes in cellular behavior. Some of the primary ones that draw much biological interest are protein-protein interactions and protein-metabolite interactions. Here, we’ll examine a protein-protein interaction database, BioGRID.

BioGRID

BioGRID is a curated database of interactions defined by experiments and computation in published literature. There is also substantial integration into various comparative bioinformatics tools we have covered elsewhere in the course (NCBI Entrez, etc.).

Perform a search for human “ACE2”.


Question

Examine the Network of ACE2 interactions in humans. What are the known chemical interactions based on the BioGRID data?


Using R to analyze networks

There are a number of R packages to help you visualize and analyze data. There are also a growing number of interfaces that help you interact with large databases. We’ll explore a few here.

Beyond some of the basic functionality I will demonstrate here, there are number of great online resources. For example, check out the site put together by Katherine Ognyanova (https://kateto.net/networks-r-igraph/).

Our exercise will focus on analyzing networks from the Mangal database (https://mangal.io/).

library(rmangal)
library(igraph)

mgs <- search_datasets("Aspen Parkland") #search for datasets involving "Aspen Parkland" environments (these are data set from a marshland in southern Mantioba)

mgn <- get_collection(mgs) #download the networks from Mangal
class(mgn)
mgn

ig1 <- as.igraph(mgn[[3]]) #covert the Mangal data into igraph format for analysis with the igraph package / we'll focus on a large interaction dataset

Let’s look at what is in the graph (a.k.a. network). You will see it is a matrix.

head(ig1)

Question

What is your interpretation of the . and 1 values in this matrix? What are the rows and columns?


What the heck?! What do those numbers mean?! Great questions! Let’s see if we can figure this out. We’ll start by interrogating the original data we downloaded from Mangal.

mgn[[3]] #we chose the 3rd dataset from our query.

If we look in our Environment tab, we’ll see mgn is an Object variable meaning it has several types of information stored in it. To access the components of an object in R, we can use the $ after our variable name. Let’s try it!

In the space below, type mgn[[3]]$ and wait a second after the $ or press the down arrow key. You should see a dropdown menu appear full of variable names. These are the components of this object variable. Let’s access the nodes. I think we have our answer! Converting between data formats sometimes results in data loss as we see when we convert to the igraph format, above. In this case, the data is lost it is just associated with our igraph object a bit differently. We’ll see below.

mgn[[3]]$nodes

Now, let’s see our network!

plot(ig1)

The igraph package adds additional plotting capabilities for networks. We see, here, this is a little cumbersome looking using default settings. We can modify a variety of variables if want and those can be found in the igraph Help page.

Let’s start by changing our node labels to something useful.


vertLabels <- vertex_attr(ig1)$original_name #extract the original names from our data

plot(
  ig1,
  vertex.label=vertLabels
  )

An example that might make things look better.

plot(ig1,
     vertex.label=vertLabels,
     vertex.label.cex=0.2, # reduce label size on nodes (a.k.a. vertices)
     vertex.size=5, # make the vertices a little smaller
     edge.arrow.size=0, # since we might not know anything about directionality
     )

There are wide variety of approaches and metrics for understanding networks… in fact there are whole areas of math and computer science dedicated to it. We’ll just sample a few ideas here.

Maybe we want to try and identify clusters (or subnetworks). Here, we can use the number of interconnections between nodes as a metric to define clusters.

ceb <- cluster_edge_betweenness(as.undirected(ig1))

plot(ceb, 
     ig1,
     vertex.label=vertLabels,
     vertex.label.cex=0.2, # reduce label size on nodes (a.k.a. vertices)
     vertex.size=5, # make the vertices a little smaller
     edge.arrow.size=0, # since we might not know anything about directionality
     )

Or, we can use greedy algorithms to search for most “optimal” clusters. This is beyond our scope, I just want you to see there are different methods out there. As we can see, there are some different outcomes based on clustering approach.

cfg <- cluster_fast_greedy(as.undirected(ig1))

plot(cfg, 
     as.undirected(ig1),
     vertex.label=vertLabels,
     vertex.label.cex=0.2, # reduce label size on nodes (a.k.a. vertices)
     vertex.size=5, # make the vertices a little smaller
     edge.arrow.size=0, # since we might not know anything about directionality
)

There are number of other metrics that often used to describe networks.

Things like distance can tell us about how spread out elements of the network are. This calculates the number of edges that would need to be transversed to get from one point to another.

distances(ig1)
mean(distances(ig1)) # this reports the average distance between each node

We may also want to understand how many connections/interactions each node has, on average.

degree(ig1, mode="all")
hist(degree(ig1, mode="all"), # makes a simple histogram plot of these data
     main="Distribution of Node Connections",
     xlab="Number of connections at each node"
)

mean(degree(ig1, mode="all"))

As we can imagine, networks are everywhere. There is an extraordinary set of theory behind analyzing networks but it always requires deeper understanding the systems studied to interpret what these theoretical values and graphs mean in the real world.

LS0tCnRpdGxlOiAiTW9kdWxlIDExIFdvcmtzaG9wIEV4ZXJjaXNlcyIKb3V0cHV0OgogIGh0bWxfbm90ZWJvb2s6IGRlZmF1bHQKICB3b3JkX2RvY3VtZW50OiBkZWZhdWx0Ci0tLQoKIyBPdmVydmlldwoKSW4gdG9kYXkncyB3b3Jrc2hvcCB3ZSB3aWxsIGJlIGxvb2tpbmcgdG86CgotIEV4cGxvcmUgdmFyaW91cyBuZXR3b3JrIGRhdGFiYXNlcwoKV2Ugd2lsbCBhbHNvIHNlZSBob3cgdG86CgotIFVzZSBSIHRvIGFjY2VzcyBpbmZvcm1hdGlvbiBpbiBuZXR3b3JrIGRhdGFiYXNlcwoKCiMgTmV0d29ya3MKCk5ldHdvcmtzIGFyZSBldmVyeXdoZXJlIGFuZCB0aGV5IGFyZSBmb3JtZWQgYnkgdGhlIGludGVyYWN0aW9ucy4gU3BlY2lmaWNhbGx5LCBpbnRlcmFjdGlvbnMgYmV0d2VlbiBlbGVtZW50cyBpbiBhIG5ldHdvcmsuIFRob3NlIGVsZW1lbnRzIG1pZ2h0IGJlIGNvbXB1dGVycywgaWYgd2UncmUgdGhpbmtpbmcgYWJvdXQgdGhlIG5ldHdvcmsgb2YgY29tcHV0ZXJzIG9uIGNhbXB1cywgb3IgdGhleSBtaWdodCBiZSBzcGVjaWVzIGluIGEgY29tcGxleCBlY29zeXN0ZW0uIFRvZGF5LCB3ZSdsbCBleHBsb3JlIHZhcmlvdXMgbmV0d29ya3Mgd2UgaGF2ZSBhdmFpbGFibGUgaW4gYmlvc2NpZW5jZXMuCgpCaW9sb2dpY2FsIG5ldHdvcmtzIGFyZSBvZnRlbiBpbmNvbXBsZXRlLiBTb21lIG5ldHdvcmtzIGFyZSB2ZXJ5IGNvbXBsZXRlLCBtZWFuaW5nIHdlIGtub3cgYWxsIGludGVyYWN0aW9ucywgYmVjYXVzZSB3ZSBoYXZlIGRlc2lnbmVkIHRoZW0gdG8gYmUuIE90aGVycywgbGlrZSBpbnRlcmFjdGlvbnMgYmV0d2VlbiBvcmdhbmlzbXMgKG1pY3JvYmVzIHRvIG1hY3JvYmVzKSBpbiBjb2FzdGFsIHdldGxhbmRzLCBtYXkgYmUgc2V2ZXJlbHkgdW5kZXJzcGVjaWZpZWQgLSBtZWFuaW5nIHdlIGFyZSBtaXNzaW5nIG1hbnkgcmVhbCBpbnRlcmFjdGlvbnMuIEFzIHdlIGFkZCBtb3JlIGxheWVycyBvZiBpbmZvcm1hdGlvbiB0byBuZXR3b3Jrcywgd2Ugb2Z0ZW4gY2hhbmdlIChzb21ldGltZXMgZHJhc3RpY2FsbHkpIHRoZSB0b3BvbG9neSBvZiBhIG5ldHdvcmsuCgpOZXR3b3JrcyBhcmUgdXNlZnVsIHRvb2xzIHRvIGhlbHAgdXMgZXhwbGFpbiBhIGNvbXBsZXggd29ybGQuIFVzZWZ1bCBhcyBuZXR3b3JrcyBhcmUgdGhleSBub3Qgd2l0aG91dCBmYXVsdHMuIEl0IGlzIGltcG9ydGFudCB0byByZW1lbWJlciB0aGF0IG91ciBpZGVhcyBhYm91dCBuZXR3b3JrcywgYW5kIHRoZSB0aGVvcnkgYW5kIHByYWN0aWNlIG9mIGFuYWx5emluZyB0aGVtLCBhcmUgaHVtYW4gaW52ZW50aW9ucy4gT3JnYW5pc21zIGluIG5hdHVyZSBkbyBub3QgY2FyZSBhYm91dCBuZXR3b3Jrcy4gTmV0d29ya3MgYXJlIGFuIGVtZXJnZW50IHByb3BlcnR5IG9mIG9yZ2FuaXNtcyBsaXZpbmcgdGhlaXIgbGl2ZXMsIGRheSB0byBkYXkuIE5ldHdvcmtzIGFsc28gaW1wbHkgc29tZXRoaW5nIHN0YXRpYyBhYm91dCBpbnRlcmFjdGlvbnMuIFRoaXMgY2FuIGJlIHZlcnkgbWlzbGVhZGluZywgcGFydGljdWxhcmx5IGluIG5hdHVyYWwgc3lzdGVtcyB3aGVyZSBzcGVjaWVzIG1lbWJlcnMgb3IgZGlldHMgbWF5IGJlIGVwaGVtZXJhbCAob3Igc2hvcnQgbGl2ZWQpLgoKU28sIGFzIHdlIGV4YW1pbmUgbmV0d29ya3MgaGVyZSBvciBhcyB5b3UgdXNlIHRoZW0gaW4geW91ciByZXNlYXJjaCwgcmVtYWluIGNyaXRpY2FsIGFib3V0IHdoYXQgaW50ZXJhY3Rpb25zIGluIGEgbmV0d29yayBtZWFuIGFuZCB3aGV0aGVyIHRoZSBuZXR3b3JrIGJlaW5nIHVzZWQgaXMgYSBmYWlybHkgY29tcGxldGUgcmVwcmVzZW50YXRpb24gb2YgcG9zc2libGUgaW50ZXJhY3Rpb25zLgoKIyMgRWNvbG9naWNhbCBuZXR3b3JrIGRhdGFiYXNlcwoKVGhlcmUgYXJlIGEgd2lkZSB2YXJpZXR5IGVjb2xvZ2ljYWwgZGF0YWJhc2VzLiBNb3N0IHB1YmxpYyBkYXRhYmFzZXMgZGVzY3JpYmUgaW50ZXJhY3Rpb25zIG9mIHNwZWNpZXMgaW4gYSBnaXZlbiBlbnZpcm9ubWVudC4gCgpIZXJlIGFyZSBhIGZldzoKCi0gTWFuZ2FsOiBodHRwczovL3d3dy5tYW5nYWwuaW8KLSBXZWIgb2YgTGlmZTogaHR0cHM6Ly93d3cud2ViLW9mLWxpZmUuZXMvCi0gR2xvYmk6IGh0dHBzOi8vd3d3Lmdsb2JhbGJpb3RpY2ludGVyYWN0aW9ucy5vcmcvCgpUaGUgdHJhbnNpdGlvbiB0byBwdWJsaWMgYXZhaWxhYmlsaXR5IGluIGVjb2xvZ2ljYWwgZGF0YSBpcyBmYWlybHkgbmV3LiBBcyBhIHJlc3VsdCwgbWFueSBvZiB0aGVzZSBkYXRhYmFzZXMgYXJlIHVuZGVyZGV2ZWxvcGVkIGNvbXBhcmVkIHRvIHNvbWUgb2YgdGhlIGV4dGVuc2l2ZSBjZWxsdWxhciBwYXRod2F5IGRhdGFiYXNlcy4gSG93ZXZlciwgdGhlcmUgaXMgYSBsb3Qgb2YgaW50ZXJlc3QgaW4gc2hhcmluZyB0aGVzZSB0eXBlcyBvZiBkYXRhIGluIGRldmVsb3BpbmcgZWNvbG9naWNhbCBtb2RlbHMgc28gdGhlcmUgaXMgcmFwaWQgZ3Jvd3RoIGluIGVjb2xvZ2ljYWwgZGF0YSBzaGFyaW5nLgoKIyMgUGF0aHdheSBkYXRhYmFzZXMKCk1ham9yIHNvdXJjZXMgb2YgYmlvbG9naWNhbCBwYXRod2F5cyBhcmUgaW4gY2VsbHVsYXIgc2lnbmFsaW5nLCBjZWxsdWxhciBtZXRhYm9saXNtLCBhbmQgbnV0cmllbnQgY3ljbGluZy4gV2UnbGwgZm9jdXMgb24gYSBjb3VwbGUgb2YgcGF0aHdheSBkYXRhYmFzZXMuCgotIFJlYWN0b21lOiBodHRwczovL3JlYWN0b21lLm9yZy8KLSBCaW9DeWM6IGh0dHBzOi8vYmlvY3ljLm9yZy8gKHdlJ2xsIGZvY3VzIG9uIEVjb0N5YykKCiMjIyBSZWFjdG9tZQoKVGFrZSBhIGxvb2sgYXQgdGhlIFBhdGh3YXkgQnJvd3Nlci4KCi0tLQoKKipRdWVzdGlvbioqCgpXaGF0IGtpbmQgb2YgaW5mb3JtYXRpb24gZG8geW91IGZpbmQgYXZhaWxhYmxlIGZvciBIb21vIHNhcGllbnM/IExpc3QgMyBvciA0LgoKLS0tCgojIyMgQmlvQ3ljCgpOb3csIGxldCdzIHRha2UgYSBsb29rIGF0IEJpb0N5Yy4gSW4gdGhlIHNlYXJjaCBmaWVsZCwgaW5wdXQgImdseWNvbHlzaXMiLiBTZWxlY3QgIkdseWNvbHlzaXMgSSIuCgotLS0KCioqUXVlc3Rpb24qKgoKRGVzY3JpYmUgMyB0eXBlcyBvZiBpbmZvcm1hdGlvbiB5b3UgY291bGQgZ2F0aGVyIGZyb20gdGhpcyBkYXRhYmFzZSBlbnRyeT8KCi0tLQoKIyMgRnVuY3Rpb25hbCBpbnRlcmFjdGVyaW9uIGRhdGFiYXNlcwoKVGhlcmUgYXJlIG1hbnkgZGlmZmVyZW50IHR5cGVzIG9mIGludGVyYWN0aW9ucyBpbiBhIGNlbGwgdGhhdCByZXN1bHQgaW4gY2hhbmdlcyBpbiBjZWxsdWxhciBiZWhhdmlvci4gU29tZSBvZiB0aGUgcHJpbWFyeSBvbmVzIHRoYXQgZHJhdyBtdWNoIGJpb2xvZ2ljYWwgaW50ZXJlc3QgYXJlIHByb3RlaW4tcHJvdGVpbiBpbnRlcmFjdGlvbnMgYW5kIHByb3RlaW4tbWV0YWJvbGl0ZSBpbnRlcmFjdGlvbnMuIEhlcmUsIHdlJ2xsIGV4YW1pbmUgYSBwcm90ZWluLXByb3RlaW4gaW50ZXJhY3Rpb24gZGF0YWJhc2UsIEJpb0dSSUQuCgotIEJpb0dSSUQ6IGh0dHBzOi8vdGhlYmlvZ3JpZC5vcmcvCgojIyMgQmlvR1JJRAoKQmlvR1JJRCBpcyBhIGN1cmF0ZWQgZGF0YWJhc2Ugb2YgaW50ZXJhY3Rpb25zIGRlZmluZWQgYnkgZXhwZXJpbWVudHMgYW5kIGNvbXB1dGF0aW9uIGluIHB1Ymxpc2hlZCBsaXRlcmF0dXJlLiBUaGVyZSBpcyBhbHNvIHN1YnN0YW50aWFsIGludGVncmF0aW9uIGludG8gdmFyaW91cyBjb21wYXJhdGl2ZSBiaW9pbmZvcm1hdGljcyB0b29scyB3ZSBoYXZlIGNvdmVyZWQgZWxzZXdoZXJlIGluIHRoZSBjb3Vyc2UgKE5DQkkgRW50cmV6LCBldGMuKS4KClBlcmZvcm0gYSBzZWFyY2ggZm9yIGh1bWFuICJBQ0UyIi4KCi0tLQoKKipRdWVzdGlvbioqCgpFeGFtaW5lIHRoZSBOZXR3b3JrIG9mIEFDRTIgaW50ZXJhY3Rpb25zIGluIGh1bWFucy4gV2hhdCBhcmUgdGhlIGtub3duIGNoZW1pY2FsIGludGVyYWN0aW9ucyBiYXNlZCBvbiB0aGUgQmlvR1JJRCBkYXRhPwoKLS0tCgoKIyBVc2luZyBSIHRvIGFuYWx5emUgbmV0d29ya3MKClRoZXJlIGFyZSBhIG51bWJlciBvZiBSIHBhY2thZ2VzIHRvIGhlbHAgeW91IHZpc3VhbGl6ZSBhbmQgYW5hbHl6ZSBkYXRhLiBUaGVyZSBhcmUgYWxzbyBhIGdyb3dpbmcgbnVtYmVyIG9mIGludGVyZmFjZXMgdGhhdCBoZWxwIHlvdSBpbnRlcmFjdCB3aXRoIGxhcmdlIGRhdGFiYXNlcy4gV2UnbGwgZXhwbG9yZSBhIGZldyBoZXJlLgoKQmV5b25kIHNvbWUgb2YgdGhlIGJhc2ljIGZ1bmN0aW9uYWxpdHkgSSB3aWxsIGRlbW9uc3RyYXRlIGhlcmUsIHRoZXJlIGFyZSBudW1iZXIgb2YgZ3JlYXQgb25saW5lIHJlc291cmNlcy4gRm9yIGV4YW1wbGUsIGNoZWNrIG91dCB0aGUgc2l0ZSBwdXQgdG9nZXRoZXIgYnkgS2F0aGVyaW5lIE9nbnlhbm92YSAoaHR0cHM6Ly9rYXRldG8ubmV0L25ldHdvcmtzLXItaWdyYXBoLykuCgpPdXIgZXhlcmNpc2Ugd2lsbCBmb2N1cyBvbiBhbmFseXppbmcgbmV0d29ya3MgZnJvbSB0aGUgTWFuZ2FsIGRhdGFiYXNlIChodHRwczovL21hbmdhbC5pby8pLgoKYGBge3J9CmxpYnJhcnkocm1hbmdhbCkKbGlicmFyeShpZ3JhcGgpCgptZ3MgPC0gc2VhcmNoX2RhdGFzZXRzKCJBc3BlbiBQYXJrbGFuZCIpICNzZWFyY2ggZm9yIGRhdGFzZXRzIGludm9sdmluZyAiQXNwZW4gUGFya2xhbmQiIGVudmlyb25tZW50cyAodGhlc2UgYXJlIGRhdGEgc2V0IGZyb20gYSBtYXJzaGxhbmQgaW4gc291dGhlcm4gTWFudGlvYmEpCgptZ24gPC0gZ2V0X2NvbGxlY3Rpb24obWdzKSAjZG93bmxvYWQgdGhlIG5ldHdvcmtzIGZyb20gTWFuZ2FsCmBgYAoKYGBge3J9CmNsYXNzKG1nbikKbWduCgppZzEgPC0gYXMuaWdyYXBoKG1nbltbM11dKSAjY292ZXJ0IHRoZSBNYW5nYWwgZGF0YSBpbnRvIGlncmFwaCBmb3JtYXQgZm9yIGFuYWx5c2lzIHdpdGggdGhlIGlncmFwaCBwYWNrYWdlIC8gd2UnbGwgZm9jdXMgb24gYSBsYXJnZSBpbnRlcmFjdGlvbiBkYXRhc2V0CmBgYAoKTGV0J3MgbG9vayBhdCB3aGF0IGlzIGluIHRoZSBncmFwaCAoYS5rLmEuIG5ldHdvcmspLiBZb3Ugd2lsbCBzZWUgaXQgaXMgYSBtYXRyaXguCmBgYHtyfQpoZWFkKGlnMSkKYGBgCgotLS0KCipRdWVzdGlvbioKCldoYXQgaXMgeW91ciBpbnRlcnByZXRhdGlvbiBvZiB0aGUgYC5gIGFuZCBgMWAgdmFsdWVzIGluIHRoaXMgbWF0cml4PyBXaGF0IGFyZSB0aGUgcm93cyBhbmQgY29sdW1ucz8KCi0tLQoKKipXaGF0IHRoZSBoZWNrPyEgV2hhdCBkbyB0aG9zZSBudW1iZXJzIG1lYW4/ISoqIEdyZWF0IHF1ZXN0aW9ucyEgTGV0J3Mgc2VlIGlmIHdlIGNhbiBmaWd1cmUgdGhpcyBvdXQuIFdlJ2xsIHN0YXJ0IGJ5IGludGVycm9nYXRpbmcgdGhlIG9yaWdpbmFsIGRhdGEgd2UgZG93bmxvYWRlZCBmcm9tIE1hbmdhbC4KCmBgYHtyfQptZ25bWzNdXSAjd2UgY2hvc2UgdGhlIDNyZCBkYXRhc2V0IGZyb20gb3VyIHF1ZXJ5LgpgYGAKCklmIHdlIGxvb2sgaW4gb3VyIEVudmlyb25tZW50IHRhYiwgd2UnbGwgc2VlIGBtZ25gIGlzIGFuIE9iamVjdCB2YXJpYWJsZSBtZWFuaW5nIGl0IGhhcyBzZXZlcmFsIHR5cGVzIG9mIGluZm9ybWF0aW9uIHN0b3JlZCBpbiBpdC4gVG8gYWNjZXNzIHRoZSBjb21wb25lbnRzIG9mIGFuIG9iamVjdCBpbiBSLCB3ZSBjYW4gdXNlIHRoZSBgJGAgYWZ0ZXIgb3VyIHZhcmlhYmxlIG5hbWUuIExldCdzIHRyeSBpdCEKCkluIHRoZSBzcGFjZSBiZWxvdywgdHlwZSBgbWduW1szXV0kYCBhbmQgd2FpdCBhIHNlY29uZCBhZnRlciB0aGUgYCRgIG9yIHByZXNzIHRoZSBkb3duIGFycm93IGtleS4gWW91IHNob3VsZCBzZWUgYSBkcm9wZG93biBtZW51IGFwcGVhciBmdWxsIG9mIHZhcmlhYmxlIG5hbWVzLiBUaGVzZSBhcmUgdGhlIGNvbXBvbmVudHMgb2YgdGhpcyBvYmplY3QgdmFyaWFibGUuIExldCdzIGFjY2VzcyB0aGUgYG5vZGVzYC4gSSB0aGluayB3ZSBoYXZlIG91ciBhbnN3ZXIhIENvbnZlcnRpbmcgYmV0d2VlbiBkYXRhIGZvcm1hdHMgc29tZXRpbWVzIHJlc3VsdHMgaW4gZGF0YSBsb3NzIGFzIHdlIHNlZSB3aGVuIHdlIGNvbnZlcnQgdG8gdGhlIGBpZ3JhcGhgIGZvcm1hdCwgYWJvdmUuIEluIHRoaXMgY2FzZSwgdGhlIGRhdGEgaXMgbG9zdCBpdCBpcyBqdXN0IGFzc29jaWF0ZWQgd2l0aCBvdXIgaWdyYXBoIG9iamVjdCBhIGJpdCBkaWZmZXJlbnRseS4gV2UnbGwgc2VlIGJlbG93LgoKYGBge3J9Cm1nbltbM11dJG5vZGVzCmBgYAoKTm93LCBsZXQncyBzZWUgb3VyIG5ldHdvcmshCgpgYGB7cn0KcGxvdChpZzEpCmBgYAoKVGhlIGBpZ3JhcGhgIHBhY2thZ2UgYWRkcyBhZGRpdGlvbmFsIHBsb3R0aW5nIGNhcGFiaWxpdGllcyBmb3IgbmV0d29ya3MuIFdlIHNlZSwgaGVyZSwgdGhpcyBpcyBhIGxpdHRsZSBjdW1iZXJzb21lIGxvb2tpbmcgdXNpbmcgZGVmYXVsdCBzZXR0aW5ncy4gV2UgY2FuIG1vZGlmeSBhIHZhcmlldHkgb2YgdmFyaWFibGVzIGlmIHdhbnQgYW5kIHRob3NlIGNhbiBiZSBmb3VuZCBpbiB0aGUgYGlncmFwaGAgSGVscCBwYWdlLgoKTGV0J3Mgc3RhcnQgYnkgY2hhbmdpbmcgb3VyIG5vZGUgbGFiZWxzIHRvIHNvbWV0aGluZyB1c2VmdWwuCgpgYGB7cn0KCnZlcnRMYWJlbHMgPC0gdmVydGV4X2F0dHIoaWcxKSRvcmlnaW5hbF9uYW1lICNleHRyYWN0IHRoZSBvcmlnaW5hbCBuYW1lcyBmcm9tIG91ciBkYXRhCgpwbG90KAogIGlnMSwKICB2ZXJ0ZXgubGFiZWw9dmVydExhYmVscwogICkKYGBgCgpBbiBleGFtcGxlIHRoYXQgbWlnaHQgbWFrZSB0aGluZ3MgbG9vayBiZXR0ZXIuCgpgYGB7cn0KcGxvdChpZzEsCiAgICAgdmVydGV4LmxhYmVsPXZlcnRMYWJlbHMsCiAgICAgdmVydGV4LmxhYmVsLmNleD0wLjIsICMgcmVkdWNlIGxhYmVsIHNpemUgb24gbm9kZXMgKGEuay5hLiB2ZXJ0aWNlcykKICAgICB2ZXJ0ZXguc2l6ZT01LCAjIG1ha2UgdGhlIHZlcnRpY2VzIGEgbGl0dGxlIHNtYWxsZXIKICAgICBlZGdlLmFycm93LnNpemU9MCwgIyBzaW5jZSB3ZSBtaWdodCBub3Qga25vdyBhbnl0aGluZyBhYm91dCBkaXJlY3Rpb25hbGl0eQogICAgICkKYGBgCgpUaGVyZSBhcmUgd2lkZSB2YXJpZXR5IG9mIGFwcHJvYWNoZXMgYW5kIG1ldHJpY3MgZm9yIHVuZGVyc3RhbmRpbmcgbmV0d29ya3MuLi4gaW4gZmFjdCB0aGVyZSBhcmUgd2hvbGUgYXJlYXMgb2YgbWF0aCBhbmQgY29tcHV0ZXIgc2NpZW5jZSBkZWRpY2F0ZWQgdG8gaXQuIFdlJ2xsIGp1c3Qgc2FtcGxlIGEgZmV3IGlkZWFzIGhlcmUuCgpNYXliZSB3ZSB3YW50IHRvIHRyeSBhbmQgaWRlbnRpZnkgY2x1c3RlcnMgKG9yIHN1Ym5ldHdvcmtzKS4gSGVyZSwgd2UgY2FuIHVzZSB0aGUgbnVtYmVyIG9mIGludGVyY29ubmVjdGlvbnMgYmV0d2VlbiBub2RlcyBhcyBhIG1ldHJpYyB0byBkZWZpbmUgY2x1c3RlcnMuCmBgYHtyfQpjZWIgPC0gY2x1c3Rlcl9lZGdlX2JldHdlZW5uZXNzKGFzLnVuZGlyZWN0ZWQoaWcxKSkKCnBsb3QoY2ViLCAKICAgICBpZzEsCiAgICAgdmVydGV4LmxhYmVsPXZlcnRMYWJlbHMsCiAgICAgdmVydGV4LmxhYmVsLmNleD0wLjIsICMgcmVkdWNlIGxhYmVsIHNpemUgb24gbm9kZXMgKGEuay5hLiB2ZXJ0aWNlcykKICAgICB2ZXJ0ZXguc2l6ZT01LCAjIG1ha2UgdGhlIHZlcnRpY2VzIGEgbGl0dGxlIHNtYWxsZXIKICAgICBlZGdlLmFycm93LnNpemU9MCwgIyBzaW5jZSB3ZSBtaWdodCBub3Qga25vdyBhbnl0aGluZyBhYm91dCBkaXJlY3Rpb25hbGl0eQogICAgICkKYGBgCgpPciwgd2UgY2FuIHVzZSBncmVlZHkgYWxnb3JpdGhtcyB0byBzZWFyY2ggZm9yIG1vc3QgIm9wdGltYWwiIGNsdXN0ZXJzLiBUaGlzIGlzIGJleW9uZCBvdXIgc2NvcGUsIEkganVzdCB3YW50IHlvdSB0byBzZWUgdGhlcmUgYXJlIGRpZmZlcmVudCBtZXRob2RzIG91dCB0aGVyZS4gQXMgd2UgY2FuIHNlZSwgdGhlcmUgYXJlIHNvbWUgZGlmZmVyZW50IG91dGNvbWVzIGJhc2VkIG9uIGNsdXN0ZXJpbmcgYXBwcm9hY2guCgpgYGB7cn0KY2ZnIDwtIGNsdXN0ZXJfZmFzdF9ncmVlZHkoYXMudW5kaXJlY3RlZChpZzEpKQoKcGxvdChjZmcsIAogICAgIGFzLnVuZGlyZWN0ZWQoaWcxKSwKICAgICB2ZXJ0ZXgubGFiZWw9dmVydExhYmVscywKICAgICB2ZXJ0ZXgubGFiZWwuY2V4PTAuMiwgIyByZWR1Y2UgbGFiZWwgc2l6ZSBvbiBub2RlcyAoYS5rLmEuIHZlcnRpY2VzKQogICAgIHZlcnRleC5zaXplPTUsICMgbWFrZSB0aGUgdmVydGljZXMgYSBsaXR0bGUgc21hbGxlcgogICAgIGVkZ2UuYXJyb3cuc2l6ZT0wLCAjIHNpbmNlIHdlIG1pZ2h0IG5vdCBrbm93IGFueXRoaW5nIGFib3V0IGRpcmVjdGlvbmFsaXR5CikKYGBgClRoZXJlIGFyZSBudW1iZXIgb2Ygb3RoZXIgbWV0cmljcyB0aGF0IG9mdGVuIHVzZWQgdG8gZGVzY3JpYmUgbmV0d29ya3MuIAoKVGhpbmdzIGxpa2UgZGlzdGFuY2UgY2FuIHRlbGwgdXMgYWJvdXQgaG93IHNwcmVhZCBvdXQgZWxlbWVudHMgb2YgdGhlIG5ldHdvcmsgYXJlLiBUaGlzIGNhbGN1bGF0ZXMgdGhlIG51bWJlciBvZiBlZGdlcyB0aGF0IHdvdWxkIG5lZWQgdG8gYmUgdHJhbnN2ZXJzZWQgdG8gZ2V0IGZyb20gb25lIHBvaW50IHRvIGFub3RoZXIuCmBgYHtyfQpkaXN0YW5jZXMoaWcxKQptZWFuKGRpc3RhbmNlcyhpZzEpKSAjIHRoaXMgcmVwb3J0cyB0aGUgYXZlcmFnZSBkaXN0YW5jZSBiZXR3ZWVuIGVhY2ggbm9kZQpgYGAKCldlIG1heSBhbHNvIHdhbnQgdG8gdW5kZXJzdGFuZCBob3cgbWFueSBjb25uZWN0aW9ucy9pbnRlcmFjdGlvbnMgZWFjaCBub2RlIGhhcywgb24gYXZlcmFnZS4KCmBgYHtyfQpkZWdyZWUoaWcxLCBtb2RlPSJhbGwiKQpoaXN0KGRlZ3JlZShpZzEsIG1vZGU9ImFsbCIpLCAjIG1ha2VzIGEgc2ltcGxlIGhpc3RvZ3JhbSBwbG90IG9mIHRoZXNlIGRhdGEKICAgICBtYWluPSJEaXN0cmlidXRpb24gb2YgTm9kZSBDb25uZWN0aW9ucyIsCiAgICAgeGxhYj0iTnVtYmVyIG9mIGNvbm5lY3Rpb25zIGF0IGVhY2ggbm9kZSIKKQoKbWVhbihkZWdyZWUoaWcxLCBtb2RlPSJhbGwiKSkKYGBgCkFzIHdlIGNhbiBpbWFnaW5lLCBuZXR3b3JrcyBhcmUgZXZlcnl3aGVyZS4gVGhlcmUgaXMgYW4gZXh0cmFvcmRpbmFyeSBzZXQgb2YgdGhlb3J5IGJlaGluZCBhbmFseXppbmcgbmV0d29ya3MgYnV0IGl0IGFsd2F5cyByZXF1aXJlcyBkZWVwZXIgdW5kZXJzdGFuZGluZyB0aGUgc3lzdGVtcyBzdHVkaWVkIHRvIGludGVycHJldCB3aGF0IHRoZXNlIHRoZW9yZXRpY2FsIHZhbHVlcyBhbmQgZ3JhcGhzIG1lYW4gaW4gdGhlIHJlYWwgd29ybGQu