Overview

This R notebook may be a simpler way to follow along with the lecture notes that introduce the idea of genomic prediction (HTML, PDF). Much of the code is taken directly from http://darwin.eeb.uconn.edu/eeb348-resources/genomic-prediction.R with some minor modifications to reflect things I’ve learned about coding in R in the last two and a half years. The final part (Comparing one-locus GWAS and genomic predictions) includes some new code.

Generating the data for analysis

The first step in exploring genomic prediction is to generate data where we know the answer so that we can compare our estimate from the data with the truth. generate_data() does this by following these steps.

  1. Generate an genotype at each locus for an individual. By default, generate_data() generates genotypes at 20 loci, but you can change that when you call it by changing n_loci_total in the call. The genotype at each locus is generated randomly assuming that the genotypes are in proportions 0.25, 0.5, and 0.25 for one homozygote, the heterozygote, and the other homozygote respectively.

  2. Generate a phenotype for this individual.

    1. Calculate the genotypic mean at each locus from the specified allelic effect and the genotype at that locus. By default the allelic effects are 1.0, -1.0, 0.5, -0.5, and 0.25 at loci 1-5 and 0.0 at the remaining 15 loci. You can change that by changing effect when you call generate_data().
    2. Generate a phenotypic contribution each locus as a random variable having a normal distribution with the genotypic mean and a specified standard deviation. By default the standard deviation is 0.2. You can change that by changing s_dev when you call generate_data().
    3. Sum the phenotypic contribution across all of the loci.1
  3. Repeat #1 and #2 until you have the number of individuals in the sample data set that you want. By default that’s 100, but you can change that by changing n_indiv when you call generate_data.

generate_data() returns the results of the simulation as a data frame with each individual on a row and with the phenotype in the first column and the genotypes at each locus in the remaining columns.

NOTE: I’m using set.seed() to ensure that you get the same sequence of random numbers that I do if you run this code on your own. You can delete that line or comment it out if you want to see what happens with different randomly generated data sets.

set.seed(12345)

generate_genotypes <- function(n) {
  x <- rmultinom(n, 1, c(0.25, 0.5, 0.25))
  return(apply(x == 1, 2, which) - 1)
}

generate_data <- function(n_indiv = 100,
                          n_loci_total = 20,
                          effect = c(1, -1, 0.5, -0.5, 0.25),
                          s_dev = 0.2)
{
  pheno <- numeric(n_indiv)
  geno <- matrix(nrow = n_indiv, ncol = n_loci_total)
  for (i in 1:n_indiv) {
    for (j in 1:n_loci_total) {
      x <- generate_genotypes(n_loci_total)
    }
    geno[i, ] <- x
    pheno[i] <- 0.0
    n_loci_assoc <- length(effect)
    for (j in 1:n_loci_assoc) {
      pheno[i] <- pheno[i] + rnorm(1, effect[j]*geno[i,j], s_dev)
    }
  }
  dat <- cbind(pheno, geno)
  colnames(dat) <- c("pheno", paste("locus_", 1:n_loci_total, sep = ""))
  return(as.data.frame(dat))
}

dat <- generate_data()
loci <- colnames(dat)[-1]
n_loci <- length(loci)

Running the analysis

We generated the data assuming that the individuals are all part of one, very large, well-mixed population. As a result, we don’t need to worry about relatedness as we did in Lab 13. We’ll use stan_lm() for the analysis. It does a simple linear regression of phenotype on genotype, but as you can probably guess from the “stan” in its name, it uses Stan as a backend to give is not only a posterior mean, but also credible intervals.

Locus-by-locus GWAS

We’ll start with a locus-by-locus GWAS like the one in Lab 13.

library(tidyverse)
Registered S3 methods overwritten by 'dbplyr':
  method         from
  print.tbl_lazy     
  print.tbl_sql      
── Attaching packages ───────────────────────────── tidyverse 1.3.1 ──
✓ ggplot2 3.3.5     ✓ purrr   0.3.4
✓ tibble  3.1.6     ✓ dplyr   1.0.7
✓ tidyr   1.1.4     ✓ stringr 1.4.0
✓ readr   2.1.0     ✓ forcats 0.5.1
── Conflicts ──────────────────────────────── tidyverse_conflicts() ──
x dplyr::filter() masks stats::filter()
x dplyr::lag()    masks stats::lag()
library(rstanarm)
Loading required package: Rcpp
Registered S3 methods overwritten by 'htmltools':
  method               from         
  print.html           tools:rstudio
  print.shiny.tag      tools:rstudio
  print.shiny.tag.list tools:rstudio
Registered S3 method overwritten by 'htmlwidgets':
  method           from         
  print.htmlwidget tools:rstudio
This is rstanarm version 2.21.1
- See https://mc-stan.org/rstanarm/articles/priors for changes to default priors!
- Default priors may change, so it's safest to specify priors, even if equivalent to the defaults.
- For execution on a local, multicore CPU with excess RAM we recommend calling
  options(mc.cores = parallel::detectCores())
options(mc.cores = parallel::detectCores())

results <- tibble(Locus = NA,
                  Mean = NA,
                  `2.5%` = NA,
                  `97.5%` = NA)
for (locus in 1:n_loci) {
  fit <- stan_lm(paste("pheno ~ ", loci[locus], sep=""),
                 prior = R2(0.5, what = "mean"),
                 data = dat,
                 refresh = 0)
  tmp <- data.frame(fit)
  effect <- tmp[[loci[locus]]]
  conf <- quantile(effect, c(0.025, 0.975))
  results <- add_row(results,
                     Locus = locus,
                     Mean = round(mean(effect), 3),
                     `2.5%` = round(conf[1], 3),
                     `97.5%` = round(conf[2], 3))
}
results %>%
  filter(!is.na(Mean)) %>%
  arrange(desc(abs(Mean)))

Notice that locus 5, which we know has an allelic effect of 0.25 doesn’t appear among the top 5 in this list. In fact, it has the smallest estimated effect. It comes in at number 20. Similarly, locus 15, which we know doesn’t have an effect, appears in the top 5.

Genomic prediction

Genomic prediction is very similar to what we’ve just seen. We simply do one multiple regression in which all of the genotypes are included rather than doing a series of regressions separately for each locus. We start by constructing the regression_formula, which looks pretty strange. We wouldn’t have to do this, but it’s easier than constructing the multiple regression formula by typing every locus into the formula.

regression_formula <- paste("pheno ~ ", 
                            paste("locus_", 1:n_loci, sep = "",
                                  collapse = " + "))
regression_formula
[1] "pheno ~  locus_1 + locus_2 + locus_3 + locus_4 + locus_5 + locus_6 + locus_7 + locus_8 + locus_9 + locus_10 + locus_11 + locus_12 + locus_13 + locus_14 + locus_15 + locus_16 + locus_17 + locus_18 + locus_19 + locus_20"

Now we’re ready to run the analysis and display the results. We’re going to use stan_glm() with a gaussian() family instead of stan_lm(), because we want to use what’s known as a “shrinkage prior”. That’s a prior with the interesting property that either a covariate is included in the regression and the prior is fairly vague or it’s not included and the prior is tightly constrained around zero. It’s a way of letting the data tell us which covariates have strong associations and which don’t and simultaneously limiting the influence of those that don’t have strong associations on the results. But it does this without forcing us to pick particular covariates for the analysis.

The particular tool we use is what’s called a “horseshoe prior”. We only need to tell it one thing: How many coefficients we think might be important. The data will tell us how many actually are. p0, which I set to 10 in this example is merely our best guess before we start the analysis.

n <- nrow(dat)
D <- ncol(dat) - 1
p0 <- 10
tau0 <- p0/(D - p0) * 1/sqrt(n)
prior_coeff <- hs(global_scale = tau0, slab_scale = 1)

fit <- stan_glm(as.formula(regression_formula),
                family = gaussian(),
                prior = prior_coeff,
                data = dat,
                refresh = 0)
fit_df <- as.data.frame(fit)

results_gp <- tibble(Locus = NA,
                     Mean = NA,
                     `2.5%` = NA,
                     `97.5%` = NA)
for (locus in 1:n_loci) {
  tmp <- data.frame(fit)
  effect <- tmp[[loci[locus]]]
  conf <- quantile(effect, c(0.025, 0.975))
  results_gp <- add_row(results_gp,
                        Locus = locus,
                        Mean = round(mean(effect), 3),
                       `2.5%` = round(conf[1], 3),
                       `97.5%` = round(conf[2], 3))
}
results_gp %>%
  filter(!is.na(Mean)) %>%
  arrange(desc(abs(Mean)))

Notice that with the genomic prediction approach we get the estimated allelic effects in the right order and roughly right in magnitude. This is only one example, and it is dangerous to extrapolate from one example, but if you’re familiar with multiple regression and its advantages, you’re probably wondering, “Why didn’t we just go directly with genomic prediction in Lab 13?”

Well, look at those data again. Even after severe filtering to remove loci that weren’t scored in at least 100 individuals, keeping only individuals scored at more than 4000 of the remaining loci, and excluding any loci where one or more of the remaining individuals wasn’t scored we had data from 218 loci and 141 individuals. That means we have 141 observations that we are trying to “predict” from 218 covariates. We have more covariates than observations, and for multiple linear regression to work we need more observations than covariates. To get good estimates of regression coefficients you need several observations per coefficient. Here we did pretty well with 5 observations per coefficient. You might want to try increasing the number of loci included in the data set to 50, keeping effect set at the default and tyring the simulation again to see what you get.

Comparing one-locus GWAS and genomic predictions

Let’s first look at the locus-by-locus estimates of allelic effects.

for_plot <- tibble(GWAS = results$Mean,
                   GP = results_gp$Mean) %>%
  filter(!is.na(GWAS))
p <- ggplot(for_plot, aes(x = GWAS, y = GP)) +
  geom_point() +
  geom_abline(slope = 1, intercept = 0, color = "red",
              linetype = "dashed") +
  theme_bw()
p

They are broadly similar, but there are also clearly some differences. Now let’s see how well we can predict the phenotypes.

predictions <- tibble(Observed = NA,
                      Model = NA,
                      Predicted = NA,
                      Error = NA)
for (i in 1:nrow(dat)) {
  predicted <-0.0
  for (j in 1:n_loci) {
    predicted <- predicted + results$Mean[i]*dat[i, j+1]
  }
  predictions <- add_row(predictions,
                         Observed = dat$pheno[i],
                         Model = "GWAS",
                         Predicted = predicted,
                         Error = Predicted - Observed)
  predicted <-0.0
  for (j in 1:n_loci) {
    predicted <- predicted + results_gp$Mean[i]*dat[i, j+1]
  }
  predictions <- add_row(predictions,
                         Observed = dat$pheno[i],
                         Model = "GP",
                         Predicted = predicted,
                         Error = Predicted - Observed)
}
predictions <- filter(predictions, !is.na(Predicted))
p <- ggplot(predictions, aes(x = Observed, y = Predicted)) +
  geom_point() +
  geom_abline(slope = 1, intercept = 0, color = "red", 
              linetype = "dashed") +
  facet_wrap(~ Model) +
  theme_bw()
p

You can see that there’s a cluster of points close to the 1:1 line with genomic prediction, and that the points seem to be a bit farther from the 1:1 line with the locus by locus GWAS. We can check that by calculating the mean squared error.

cat("Mean squared error:\n",
    "   GWAS: ", round(sum(subset(predictions, Model == "GWAS")$Error^2),
                       3)/nrow(dat), "\n",
    "     GP: ", round(sum(subset(predictions, Model == "GP")$Error^2),
                       3)/nrow(dat), "\n",
    sep = "")
Mean squared error:
   GWAS: 6.01941
     GP: 8.02203

As you can see, our (or at least my) subjective impression was wrong. If we were to use all 20 loci, the locus by locus GWAS would, on average, be closer to the “truth” than the genomic prediction approach – even though we know that it got the effects wrong.


  1. Since we’re assuming that only loci 1-5 influence the phenotype, we only do this sum across loci 1-5.↩︎

LS0tCnRpdGxlOiAiRXhwbG9yaW5nIGdlbm9taWMgcHJlZGljdGlvbiIKb3V0cHV0OiAKICBodG1sX25vdGVib29rOgogICAgdG9jOiB5ZXMKICAgIHRvY19mbG9hdDogdHJ1ZQogICAgY3NzOiAiUi1ub3RlYm9vay5jc3MiCi0tLQoKIyBPdmVydmlldwoKVGhpcyBgUmAgbm90ZWJvb2sgbWF5IGJlIGEgc2ltcGxlciB3YXkgdG8gZm9sbG93IGFsb25nIHdpdGggdGhlIGxlY3R1cmUgbm90ZXMgdGhhdCBpbnRyb2R1Y2UgdGhlIGlkZWEgb2YgZ2Vub21pYyBwcmVkaWN0aW9uIChbSFRNTF0oaHR0cDovL2Rhcndpbi5lZWIudWNvbm4uZWR1L2VlYjM0OC1ub3Rlcy9nZW5vbWljLXByZWRpY3Rpb24uaHRtbCksIFtQREZdKGh0dHA6Ly9kYXJ3aW4uZWViLnVjb25uLmVkdS9lZWIzNDgtbm90ZXMvZ2Vub21pYy1wcmVkaWN0aW9uLnBkZikpLiBNdWNoIG9mIHRoZSBjb2RlIGlzIHRha2VuIGRpcmVjdGx5IGZyb20gW2h0dHA6Ly9kYXJ3aW4uZWViLnVjb25uLmVkdS9lZWIzNDgtcmVzb3VyY2VzL2dlbm9taWMtcHJlZGljdGlvbi5SXShodHRwOi8vZGFyd2luLmVlYi51Y29ubi5lZHUvZWViMzQ4LXJlc291cmNlcy9nZW5vbWljLXByZWRpY3Rpb24uUikgd2l0aCBzb21lIG1pbm9yIG1vZGlmaWNhdGlvbnMgdG8gcmVmbGVjdCB0aGluZ3MgSSd2ZSBsZWFybmVkIGFib3V0IGNvZGluZyBpbiBgUmAgaW4gdGhlIGxhc3QgdHdvIGFuZCBhIGhhbGYgeWVhcnMuIFRoZSBmaW5hbCBwYXJ0IChbQ29tcGFyaW5nIG9uZS1sb2N1cyBHV0FTIGFuZCBnZW5vbWljIHByZWRpY3Rpb25zXSgjY29tcGFyaW5nLW9uZS1sb2N1cy1nd2FzLWFuZC1nZW5vbWljLXByZWRpY3Rpb25zKSkgaW5jbHVkZXMgc29tZSBuZXcgY29kZS4KCiMgR2VuZXJhdGluZyB0aGUgZGF0YSBmb3IgYW5hbHlzaXMKClRoZSBmaXJzdCBzdGVwIGluIGV4cGxvcmluZyBnZW5vbWljIHByZWRpY3Rpb24gaXMgdG8gZ2VuZXJhdGUgZGF0YSB3aGVyZSB3ZSBrbm93IHRoZSBhbnN3ZXIgc28gdGhhdCB3ZSBjYW4gY29tcGFyZSBvdXIgZXN0aW1hdGUgZnJvbSB0aGUgZGF0YSB3aXRoIHRoZSB0cnV0aC4gYGdlbmVyYXRlX2RhdGEoKWAgZG9lcyB0aGlzIGJ5IGZvbGxvd2luZyB0aGVzZSBzdGVwcy4KCjEuIEdlbmVyYXRlIGFuIGdlbm90eXBlIGF0IGVhY2ggbG9jdXMgZm9yIGFuIGluZGl2aWR1YWwuIEJ5IGRlZmF1bHQsIGBnZW5lcmF0ZV9kYXRhKClgIGdlbmVyYXRlcyBnZW5vdHlwZXMgYXQgMjAgbG9jaSwgYnV0IHlvdSBjYW4gY2hhbmdlIHRoYXQgd2hlbiB5b3UgY2FsbCBpdCBieSBjaGFuZ2luZyBgbl9sb2NpX3RvdGFsYCBpbiB0aGUgY2FsbC4gVGhlIGdlbm90eXBlIGF0IGVhY2ggbG9jdXMgaXMgZ2VuZXJhdGVkIHJhbmRvbWx5IGFzc3VtaW5nIHRoYXQgdGhlIGdlbm90eXBlcyBhcmUgaW4gcHJvcG9ydGlvbnMgMC4yNSwgMC41LCBhbmQgMC4yNSBmb3Igb25lIGhvbW96eWdvdGUsIHRoZSBoZXRlcm96eWdvdGUsIGFuZCB0aGUgb3RoZXIgaG9tb3p5Z290ZSByZXNwZWN0aXZlbHkuCgoyLiBHZW5lcmF0ZSBhIHBoZW5vdHlwZSBmb3IgdGhpcyBpbmRpdmlkdWFsLgoKICAgIGEuIENhbGN1bGF0ZSB0aGUgZ2Vub3R5cGljIG1lYW4gYXQgZWFjaCBsb2N1cyBmcm9tIHRoZSBzcGVjaWZpZWQgYWxsZWxpYyBlZmZlY3QgYW5kIHRoZSBnZW5vdHlwZSBhdCB0aGF0IGxvY3VzLiBCeSBkZWZhdWx0IHRoZSBhbGxlbGljIGVmZmVjdHMgYXJlIDEuMCwgLTEuMCwgMC41LCAtMC41LCBhbmQgMC4yNSBhdCBsb2NpIDEtNSBhbmQgMC4wIGF0IHRoZSByZW1haW5pbmcgMTUgbG9jaS4gWW91IGNhbiBjaGFuZ2UgdGhhdCBieSBjaGFuZ2luZyBgZWZmZWN0YCB3aGVuIHlvdSBjYWxsIGBnZW5lcmF0ZV9kYXRhKClgLgogICAgYi4gR2VuZXJhdGUgYSBwaGVub3R5cGljIGNvbnRyaWJ1dGlvbiBlYWNoIGxvY3VzIGFzIGEgcmFuZG9tIHZhcmlhYmxlIGhhdmluZyBhIG5vcm1hbCBkaXN0cmlidXRpb24gd2l0aCB0aGUgZ2Vub3R5cGljIG1lYW4gYW5kIGEgc3BlY2lmaWVkIHN0YW5kYXJkIGRldmlhdGlvbi4gQnkgZGVmYXVsdCB0aGUgc3RhbmRhcmQgZGV2aWF0aW9uIGlzIDAuMi4gWW91IGNhbiBjaGFuZ2UgdGhhdCBieSBjaGFuZ2luZyBgc19kZXZgIHdoZW4geW91IGNhbGwgYGdlbmVyYXRlX2RhdGEoKWAuCiAgICBjLiBTdW0gdGhlIHBoZW5vdHlwaWMgY29udHJpYnV0aW9uIGFjcm9zcyBhbGwgb2YgdGhlIGxvY2kuXltTaW5jZSB3ZSdyZSBhc3N1bWluZyB0aGF0IG9ubHkgbG9jaSAxLTUgaW5mbHVlbmNlIHRoZSBwaGVub3R5cGUsIHdlIG9ubHkgZG8gdGhpcyBzdW0gYWNyb3NzIGxvY2kgMS01Ll0KICAKMy4gUmVwZWF0ICMxIGFuZCAjMiB1bnRpbCB5b3UgaGF2ZSB0aGUgbnVtYmVyIG9mIGluZGl2aWR1YWxzIGluIHRoZSBzYW1wbGUgZGF0YSBzZXQgdGhhdCB5b3Ugd2FudC4gQnkgZGVmYXVsdCB0aGF0J3MgMTAwLCBidXQgeW91IGNhbiBjaGFuZ2UgdGhhdCBieSBjaGFuZ2luZyBgbl9pbmRpdmAgd2hlbiB5b3UgY2FsbCBgZ2VuZXJhdGVfZGF0YWAuCgpgZ2VuZXJhdGVfZGF0YSgpYCByZXR1cm5zIHRoZSByZXN1bHRzIG9mIHRoZSBzaW11bGF0aW9uIGFzIGEgZGF0YSBmcmFtZSB3aXRoIGVhY2ggaW5kaXZpZHVhbCBvbiBhIHJvdyBhbmQgd2l0aCB0aGUgcGhlbm90eXBlIGluIHRoZSBmaXJzdCBjb2x1bW4gYW5kIHRoZSBnZW5vdHlwZXMgYXQgZWFjaCBsb2N1cyBpbiB0aGUgcmVtYWluaW5nIGNvbHVtbnMuCgpOT1RFOiBJJ20gdXNpbmcgYHNldC5zZWVkKClgIHRvIGVuc3VyZSB0aGF0IHlvdSBnZXQgdGhlIHNhbWUgc2VxdWVuY2Ugb2YgcmFuZG9tIG51bWJlcnMgdGhhdCBJIGRvIGlmIHlvdSBydW4gdGhpcyBjb2RlIG9uIHlvdXIgb3duLiBZb3UgY2FuIGRlbGV0ZSB0aGF0IGxpbmUgb3IgY29tbWVudCBpdCBvdXQgaWYgeW91IHdhbnQgdG8gc2VlIHdoYXQgaGFwcGVucyB3aXRoIGRpZmZlcmVudCByYW5kb21seSBnZW5lcmF0ZWQgZGF0YSBzZXRzLgoKYGBge3J9CnNldC5zZWVkKDEyMzQ1KQoKZ2VuZXJhdGVfZ2Vub3R5cGVzIDwtIGZ1bmN0aW9uKG4pIHsKICB4IDwtIHJtdWx0aW5vbShuLCAxLCBjKDAuMjUsIDAuNSwgMC4yNSkpCiAgcmV0dXJuKGFwcGx5KHggPT0gMSwgMiwgd2hpY2gpIC0gMSkKfQoKZ2VuZXJhdGVfZGF0YSA8LSBmdW5jdGlvbihuX2luZGl2ID0gMTAwLAogICAgICAgICAgICAgICAgICAgICAgICAgIG5fbG9jaV90b3RhbCA9IDIwLAogICAgICAgICAgICAgICAgICAgICAgICAgIGVmZmVjdCA9IGMoMSwgLTEsIDAuNSwgLTAuNSwgMC4yNSksCiAgICAgICAgICAgICAgICAgICAgICAgICAgc19kZXYgPSAwLjIpCnsKICBwaGVubyA8LSBudW1lcmljKG5faW5kaXYpCiAgZ2VubyA8LSBtYXRyaXgobnJvdyA9IG5faW5kaXYsIG5jb2wgPSBuX2xvY2lfdG90YWwpCiAgZm9yIChpIGluIDE6bl9pbmRpdikgewogICAgZm9yIChqIGluIDE6bl9sb2NpX3RvdGFsKSB7CiAgICAgIHggPC0gZ2VuZXJhdGVfZ2Vub3R5cGVzKG5fbG9jaV90b3RhbCkKICAgIH0KICAgIGdlbm9baSwgXSA8LSB4CiAgICBwaGVub1tpXSA8LSAwLjAKICAgIG5fbG9jaV9hc3NvYyA8LSBsZW5ndGgoZWZmZWN0KQogICAgZm9yIChqIGluIDE6bl9sb2NpX2Fzc29jKSB7CiAgICAgIHBoZW5vW2ldIDwtIHBoZW5vW2ldICsgcm5vcm0oMSwgZWZmZWN0W2pdKmdlbm9baSxqXSwgc19kZXYpCiAgICB9CiAgfQogIGRhdCA8LSBjYmluZChwaGVubywgZ2VubykKICBjb2xuYW1lcyhkYXQpIDwtIGMoInBoZW5vIiwgcGFzdGUoImxvY3VzXyIsIDE6bl9sb2NpX3RvdGFsLCBzZXAgPSAiIikpCiAgcmV0dXJuKGFzLmRhdGEuZnJhbWUoZGF0KSkKfQoKZGF0IDwtIGdlbmVyYXRlX2RhdGEoKQpsb2NpIDwtIGNvbG5hbWVzKGRhdClbLTFdCm5fbG9jaSA8LSBsZW5ndGgobG9jaSkKYGBgCgojIFJ1bm5pbmcgdGhlIGFuYWx5c2lzCgpXZSBnZW5lcmF0ZWQgdGhlIGRhdGEgYXNzdW1pbmcgdGhhdCB0aGUgaW5kaXZpZHVhbHMgYXJlIGFsbCBwYXJ0IG9mIG9uZSwgdmVyeSBsYXJnZSwgd2VsbC1taXhlZCBwb3B1bGF0aW9uLiBBcyBhIHJlc3VsdCwgd2UgZG9uJ3QgbmVlZCB0byB3b3JyeSBhYm91dCByZWxhdGVkbmVzcyBhcyB3ZSBkaWQgaW4gW0xhYiAxM10oaHR0cDovL2Rhcndpbi5lZWIudWNvbm4uZWR1L2VlYjM0OC1yZXNvdXJjZXMvTGFiMTMubmIuaHRtbCkuIFdlJ2xsIHVzZSBgc3Rhbl9sbSgpYCBmb3IgdGhlIGFuYWx5c2lzLiBJdCBkb2VzIGEgc2ltcGxlIGxpbmVhciByZWdyZXNzaW9uIG9mIHBoZW5vdHlwZSBvbiBnZW5vdHlwZSwgYnV0IGFzIHlvdSBjYW4gcHJvYmFibHkgZ3Vlc3MgZnJvbSB0aGUgInN0YW4iIGluIGl0cyBuYW1lLCBpdCB1c2VzIGBTdGFuYCBhcyBhIGJhY2tlbmQgdG8gZ2l2ZSBpcyBub3Qgb25seSBhIHBvc3RlcmlvciBtZWFuLCBidXQgYWxzbyBjcmVkaWJsZSBpbnRlcnZhbHMuCgojIyBMb2N1cy1ieS1sb2N1cyBHV0FTCgpXZSdsbCBzdGFydCB3aXRoIGEgbG9jdXMtYnktbG9jdXMgR1dBUyBsaWtlIHRoZSBvbmUgaW4gW0xhYiAxM10oaHR0cDovL2Rhcndpbi5lZWIudWNvbm4uZWR1L2VlYjM0OC1yZXNvdXJjZXMvTGFiMTMubmIuaHRtbCkuIAoKYGBge3J9CmxpYnJhcnkodGlkeXZlcnNlKQpsaWJyYXJ5KHJzdGFuYXJtKQoKb3B0aW9ucyhtYy5jb3JlcyA9IHBhcmFsbGVsOjpkZXRlY3RDb3JlcygpKQoKcmVzdWx0cyA8LSB0aWJibGUoTG9jdXMgPSBOQSwKICAgICAgICAgICAgICAgICAgTWVhbiA9IE5BLAogICAgICAgICAgICAgICAgICBgMi41JWAgPSBOQSwKICAgICAgICAgICAgICAgICAgYDk3LjUlYCA9IE5BKQpmb3IgKGxvY3VzIGluIDE6bl9sb2NpKSB7CiAgZml0IDwtIHN0YW5fbG0ocGFzdGUoInBoZW5vIH4gIiwgbG9jaVtsb2N1c10sIHNlcD0iIiksCiAgICAgICAgICAgICAgICAgcHJpb3IgPSBSMigwLjUsIHdoYXQgPSAibWVhbiIpLAogICAgICAgICAgICAgICAgIGRhdGEgPSBkYXQsCiAgICAgICAgICAgICAgICAgcmVmcmVzaCA9IDApCiAgdG1wIDwtIGRhdGEuZnJhbWUoZml0KQogIGVmZmVjdCA8LSB0bXBbW2xvY2lbbG9jdXNdXV0KICBjb25mIDwtIHF1YW50aWxlKGVmZmVjdCwgYygwLjAyNSwgMC45NzUpKQogIHJlc3VsdHMgPC0gYWRkX3JvdyhyZXN1bHRzLAogICAgICAgICAgICAgICAgICAgICBMb2N1cyA9IGxvY3VzLAogICAgICAgICAgICAgICAgICAgICBNZWFuID0gcm91bmQobWVhbihlZmZlY3QpLCAzKSwKICAgICAgICAgICAgICAgICAgICAgYDIuNSVgID0gcm91bmQoY29uZlsxXSwgMyksCiAgICAgICAgICAgICAgICAgICAgIGA5Ny41JWAgPSByb3VuZChjb25mWzJdLCAzKSkKfQpyZXN1bHRzICU+JQogIGZpbHRlcighaXMubmEoTWVhbikpICU+JQogIGFycmFuZ2UoZGVzYyhhYnMoTWVhbikpKQpgYGAKCk5vdGljZSB0aGF0IGxvY3VzIDUsIHdoaWNoIHdlIGtub3cgaGFzIGFuIGFsbGVsaWMgZWZmZWN0IG9mIDAuMjUgZG9lc24ndCBhcHBlYXIgYW1vbmcgdGhlIHRvcCA1IGluIHRoaXMgbGlzdC4gSW4gZmFjdCwgaXQgaGFzIHRoZSAqc21hbGxlc3QqIGVzdGltYXRlZCBlZmZlY3QuIEl0IGNvbWVzIGluIGF0IG51bWJlciAyMC4gU2ltaWxhcmx5LCBsb2N1cyAxNSwgd2hpY2ggd2Uga25vdyBkb2Vzbid0IGhhdmUgYW4gZWZmZWN0LCBhcHBlYXJzIGluIHRoZSB0b3AgNS4KCiMjIEdlbm9taWMgcHJlZGljdGlvbgoKR2Vub21pYyBwcmVkaWN0aW9uIGlzIHZlcnkgc2ltaWxhciB0byB3aGF0IHdlJ3ZlIGp1c3Qgc2Vlbi4gV2Ugc2ltcGx5IGRvIG9uZSBtdWx0aXBsZSByZWdyZXNzaW9uIGluIHdoaWNoIGFsbCBvZiB0aGUgZ2Vub3R5cGVzIGFyZSBpbmNsdWRlZCByYXRoZXIgdGhhbiBkb2luZyBhIHNlcmllcyBvZiByZWdyZXNzaW9ucyBzZXBhcmF0ZWx5IGZvciBlYWNoIGxvY3VzLiBXZSBzdGFydCBieSBjb25zdHJ1Y3RpbmcgdGhlIGByZWdyZXNzaW9uX2Zvcm11bGFgLCB3aGljaCBsb29rcyBwcmV0dHkgc3RyYW5nZS4gV2Ugd291bGRuJ3QgaGF2ZSB0byBkbyB0aGlzLCBidXQgaXQncyBlYXNpZXIgdGhhbiBjb25zdHJ1Y3RpbmcgdGhlIG11bHRpcGxlIHJlZ3Jlc3Npb24gZm9ybXVsYSBieSB0eXBpbmcgZXZlcnkgbG9jdXMgaW50byB0aGUgZm9ybXVsYS4KCmBgYHtyfQpyZWdyZXNzaW9uX2Zvcm11bGEgPC0gcGFzdGUoInBoZW5vIH4gIiwgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBwYXN0ZSgibG9jdXNfIiwgMTpuX2xvY2ksIHNlcCA9ICIiLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgY29sbGFwc2UgPSAiICsgIikpCnJlZ3Jlc3Npb25fZm9ybXVsYQpgYGAKTm93IHdlJ3JlIHJlYWR5IHRvIHJ1biB0aGUgYW5hbHlzaXMgYW5kIGRpc3BsYXkgdGhlIHJlc3VsdHMuIFdlJ3JlIGdvaW5nIHRvIHVzZSBgc3Rhbl9nbG0oKWAgd2l0aCBhIGBnYXVzc2lhbigpYCBmYW1pbHkgaW5zdGVhZCBvZiBgc3Rhbl9sbSgpYCwgYmVjYXVzZSB3ZSB3YW50IHRvIHVzZSB3aGF0J3Mga25vd24gYXMgYSAic2hyaW5rYWdlIHByaW9yIi4gVGhhdCdzIGEgcHJpb3Igd2l0aCB0aGUgaW50ZXJlc3RpbmcgcHJvcGVydHkgdGhhdCBlaXRoZXIgYSBjb3ZhcmlhdGUgaXMgaW5jbHVkZWQgaW4gdGhlIHJlZ3Jlc3Npb24gYW5kIHRoZSBwcmlvciBpcyBmYWlybHkgdmFndWUgb3IgaXQncyBub3QgaW5jbHVkZWQgYW5kIHRoZSBwcmlvciBpcyB0aWdodGx5IGNvbnN0cmFpbmVkIGFyb3VuZCB6ZXJvLiBJdCdzIGEgd2F5IG9mIGxldHRpbmcgdGhlIGRhdGEgdGVsbCB1cyB3aGljaCBjb3ZhcmlhdGVzIGhhdmUgc3Ryb25nIGFzc29jaWF0aW9ucyBhbmQgd2hpY2ggZG9uJ3QgYW5kIHNpbXVsdGFuZW91c2x5IGxpbWl0aW5nIHRoZSBpbmZsdWVuY2Ugb2YgdGhvc2UgdGhhdCBkb24ndCBoYXZlIHN0cm9uZyBhc3NvY2lhdGlvbnMgb24gdGhlIHJlc3VsdHMuIEJ1dCBpdCBkb2VzIHRoaXMgd2l0aG91dCBmb3JjaW5nIHVzIHRvIHBpY2sgcGFydGljdWxhciBjb3ZhcmlhdGVzIGZvciB0aGUgYW5hbHlzaXMuCgpUaGUgcGFydGljdWxhciB0b29sIHdlIHVzZSBpcyB3aGF0J3MgY2FsbGVkIGEgImhvcnNlc2hvZSBwcmlvciIuIFdlIG9ubHkgbmVlZCB0byB0ZWxsIGl0IG9uZSB0aGluZzogSG93IG1hbnkgY29lZmZpY2llbnRzIHdlIHRoaW5rIG1pZ2h0IGJlIGltcG9ydGFudC4gVGhlIGRhdGEgd2lsbCB0ZWxsIHVzIGhvdyBtYW55IGFjdHVhbGx5IGFyZS4gYHAwYCwgd2hpY2ggSSBzZXQgdG8gMTAgaW4gdGhpcyBleGFtcGxlIGlzIG1lcmVseSBvdXIgYmVzdCBndWVzcyBiZWZvcmUgd2Ugc3RhcnQgdGhlIGFuYWx5c2lzLgoKYGBge3J9Cm4gPC0gbnJvdyhkYXQpCkQgPC0gbmNvbChkYXQpIC0gMQpwMCA8LSAxMAp0YXUwIDwtIHAwLyhEIC0gcDApICogMS9zcXJ0KG4pCnByaW9yX2NvZWZmIDwtIGhzKGdsb2JhbF9zY2FsZSA9IHRhdTAsIHNsYWJfc2NhbGUgPSAxKQoKZml0IDwtIHN0YW5fZ2xtKGFzLmZvcm11bGEocmVncmVzc2lvbl9mb3JtdWxhKSwKICAgICAgICAgICAgICAgIGZhbWlseSA9IGdhdXNzaWFuKCksCiAgICAgICAgICAgICAgICBwcmlvciA9IHByaW9yX2NvZWZmLAogICAgICAgICAgICAgICAgZGF0YSA9IGRhdCwKICAgICAgICAgICAgICAgIHJlZnJlc2ggPSAwKQpmaXRfZGYgPC0gYXMuZGF0YS5mcmFtZShmaXQpCgpyZXN1bHRzX2dwIDwtIHRpYmJsZShMb2N1cyA9IE5BLAogICAgICAgICAgICAgICAgICAgICBNZWFuID0gTkEsCiAgICAgICAgICAgICAgICAgICAgIGAyLjUlYCA9IE5BLAogICAgICAgICAgICAgICAgICAgICBgOTcuNSVgID0gTkEpCmZvciAobG9jdXMgaW4gMTpuX2xvY2kpIHsKICB0bXAgPC0gZGF0YS5mcmFtZShmaXQpCiAgZWZmZWN0IDwtIHRtcFtbbG9jaVtsb2N1c11dXQogIGNvbmYgPC0gcXVhbnRpbGUoZWZmZWN0LCBjKDAuMDI1LCAwLjk3NSkpCiAgcmVzdWx0c19ncCA8LSBhZGRfcm93KHJlc3VsdHNfZ3AsCiAgICAgICAgICAgICAgICAgICAgICAgIExvY3VzID0gbG9jdXMsCiAgICAgICAgICAgICAgICAgICAgICAgIE1lYW4gPSByb3VuZChtZWFuKGVmZmVjdCksIDMpLAogICAgICAgICAgICAgICAgICAgICAgIGAyLjUlYCA9IHJvdW5kKGNvbmZbMV0sIDMpLAogICAgICAgICAgICAgICAgICAgICAgIGA5Ny41JWAgPSByb3VuZChjb25mWzJdLCAzKSkKfQpyZXN1bHRzX2dwICU+JQogIGZpbHRlcighaXMubmEoTWVhbikpICU+JQogIGFycmFuZ2UoZGVzYyhhYnMoTWVhbikpKQpgYGAKCk5vdGljZSB0aGF0IHdpdGggdGhlIGdlbm9taWMgcHJlZGljdGlvbiBhcHByb2FjaCB3ZSBnZXQgdGhlIGVzdGltYXRlZCBhbGxlbGljIGVmZmVjdHMgaW4gdGhlIHJpZ2h0IG9yZGVyIGFuZCByb3VnaGx5IHJpZ2h0IGluIG1hZ25pdHVkZS4gVGhpcyBpcyBvbmx5IG9uZSBleGFtcGxlLCBhbmQgaXQgaXMgZGFuZ2Vyb3VzIHRvIGV4dHJhcG9sYXRlIGZyb20gb25lIGV4YW1wbGUsIGJ1dCBpZiB5b3UncmUgZmFtaWxpYXIgd2l0aCBtdWx0aXBsZSByZWdyZXNzaW9uIGFuZCBpdHMgYWR2YW50YWdlcywgeW91J3JlIHByb2JhYmx5IHdvbmRlcmluZywgIldoeSBkaWRuJ3Qgd2UganVzdCBnbyBkaXJlY3RseSB3aXRoIGdlbm9taWMgcHJlZGljdGlvbiBpbiBbTGFiIDEzXShodHRwOi8vZGFyd2luLmVlYi51Y29ubi5lZHUvZWViMzQ4LXJlc291cmNlcy9MYWIxMy5uYi5odG1sKT8iIAoKV2VsbCwgbG9vayBhdCB0aG9zZSBkYXRhIGFnYWluLiBFdmVuIGFmdGVyIHNldmVyZSBmaWx0ZXJpbmcgdG8gcmVtb3ZlIGxvY2kgdGhhdCB3ZXJlbid0IHNjb3JlZCBpbiBhdCBsZWFzdCAxMDAgaW5kaXZpZHVhbHMsIGtlZXBpbmcgb25seSBpbmRpdmlkdWFscyBzY29yZWQgYXQgbW9yZSB0aGFuIDQwMDAgb2YgdGhlIHJlbWFpbmluZyBsb2NpLCBhbmQgZXhjbHVkaW5nIGFueSBsb2NpIHdoZXJlIG9uZSBvciBtb3JlIG9mIHRoZSByZW1haW5pbmcgaW5kaXZpZHVhbHMgd2Fzbid0IHNjb3JlZCB3ZSBoYWQgZGF0YSBmcm9tIDIxOCBsb2NpIGFuZCAxNDEgaW5kaXZpZHVhbHMuIFRoYXQgbWVhbnMgd2UgaGF2ZSAxNDEgb2JzZXJ2YXRpb25zIHRoYXQgd2UgYXJlIHRyeWluZyB0byAicHJlZGljdCIgZnJvbSAyMTggY292YXJpYXRlcy4gV2UgaGF2ZSBtb3JlIGNvdmFyaWF0ZXMgdGhhbiBvYnNlcnZhdGlvbnMsIGFuZCBmb3IgbXVsdGlwbGUgbGluZWFyIHJlZ3Jlc3Npb24gdG8gd29yayB3ZSBuZWVkIG1vcmUgb2JzZXJ2YXRpb25zIHRoYW4gY292YXJpYXRlcy4gVG8gZ2V0IGdvb2QgZXN0aW1hdGVzIG9mIHJlZ3Jlc3Npb24gY29lZmZpY2llbnRzIHlvdSBuZWVkIHNldmVyYWwgb2JzZXJ2YXRpb25zIHBlciBjb2VmZmljaWVudC4gSGVyZSB3ZSBkaWQgcHJldHR5IHdlbGwgd2l0aCA1IG9ic2VydmF0aW9ucyBwZXIgY29lZmZpY2llbnQuIFlvdSBtaWdodCB3YW50IHRvIHRyeSBpbmNyZWFzaW5nIHRoZSBudW1iZXIgb2YgbG9jaSBpbmNsdWRlZCBpbiB0aGUgZGF0YSBzZXQgdG8gNTAsIGtlZXBpbmcgYGVmZmVjdGAgc2V0IGF0IHRoZSBkZWZhdWx0IGFuZCB0eXJpbmcgdGhlIHNpbXVsYXRpb24gYWdhaW4gdG8gc2VlIHdoYXQgeW91IGdldC4KCiMgQ29tcGFyaW5nIG9uZS1sb2N1cyBHV0FTIGFuZCBnZW5vbWljIHByZWRpY3Rpb25zCgpMZXQncyBmaXJzdCBsb29rIGF0IHRoZSBsb2N1cy1ieS1sb2N1cyBlc3RpbWF0ZXMgb2YgYWxsZWxpYyBlZmZlY3RzLgoKYGBge3J9CmZvcl9wbG90IDwtIHRpYmJsZShHV0FTID0gcmVzdWx0cyRNZWFuLAogICAgICAgICAgICAgICAgICAgR1AgPSByZXN1bHRzX2dwJE1lYW4pICU+JQogIGZpbHRlcighaXMubmEoR1dBUykpCnAgPC0gZ2dwbG90KGZvcl9wbG90LCBhZXMoeCA9IEdXQVMsIHkgPSBHUCkpICsKICBnZW9tX3BvaW50KCkgKwogIGdlb21fYWJsaW5lKHNsb3BlID0gMSwgaW50ZXJjZXB0ID0gMCwgY29sb3IgPSAicmVkIiwKICAgICAgICAgICAgICBsaW5ldHlwZSA9ICJkYXNoZWQiKSArCiAgdGhlbWVfYncoKQpwCmBgYApUaGV5IGFyZSBicm9hZGx5IHNpbWlsYXIsIGJ1dCB0aGVyZSBhcmUgYWxzbyBjbGVhcmx5IHNvbWUgZGlmZmVyZW5jZXMuIE5vdyBsZXQncyBzZWUgaG93IHdlbGwgd2UgY2FuIHByZWRpY3QgdGhlIHBoZW5vdHlwZXMuCgpgYGB7cn0KcHJlZGljdGlvbnMgPC0gdGliYmxlKE9ic2VydmVkID0gTkEsCiAgICAgICAgICAgICAgICAgICAgICBNb2RlbCA9IE5BLAogICAgICAgICAgICAgICAgICAgICAgUHJlZGljdGVkID0gTkEsCiAgICAgICAgICAgICAgICAgICAgICBFcnJvciA9IE5BKQpmb3IgKGkgaW4gMTpucm93KGRhdCkpIHsKICBwcmVkaWN0ZWQgPC0wLjAKICBmb3IgKGogaW4gMTpuX2xvY2kpIHsKICAgIHByZWRpY3RlZCA8LSBwcmVkaWN0ZWQgKyByZXN1bHRzJE1lYW5baV0qZGF0W2ksIGorMV0KICB9CiAgcHJlZGljdGlvbnMgPC0gYWRkX3JvdyhwcmVkaWN0aW9ucywKICAgICAgICAgICAgICAgICAgICAgICAgIE9ic2VydmVkID0gZGF0JHBoZW5vW2ldLAogICAgICAgICAgICAgICAgICAgICAgICAgTW9kZWwgPSAiR1dBUyIsCiAgICAgICAgICAgICAgICAgICAgICAgICBQcmVkaWN0ZWQgPSBwcmVkaWN0ZWQsCiAgICAgICAgICAgICAgICAgICAgICAgICBFcnJvciA9IFByZWRpY3RlZCAtIE9ic2VydmVkKQogIHByZWRpY3RlZCA8LTAuMAogIGZvciAoaiBpbiAxOm5fbG9jaSkgewogICAgcHJlZGljdGVkIDwtIHByZWRpY3RlZCArIHJlc3VsdHNfZ3AkTWVhbltpXSpkYXRbaSwgaisxXQogIH0KICBwcmVkaWN0aW9ucyA8LSBhZGRfcm93KHByZWRpY3Rpb25zLAogICAgICAgICAgICAgICAgICAgICAgICAgT2JzZXJ2ZWQgPSBkYXQkcGhlbm9baV0sCiAgICAgICAgICAgICAgICAgICAgICAgICBNb2RlbCA9ICJHUCIsCiAgICAgICAgICAgICAgICAgICAgICAgICBQcmVkaWN0ZWQgPSBwcmVkaWN0ZWQsCiAgICAgICAgICAgICAgICAgICAgICAgICBFcnJvciA9IFByZWRpY3RlZCAtIE9ic2VydmVkKQp9CnByZWRpY3Rpb25zIDwtIGZpbHRlcihwcmVkaWN0aW9ucywgIWlzLm5hKFByZWRpY3RlZCkpCnAgPC0gZ2dwbG90KHByZWRpY3Rpb25zLCBhZXMoeCA9IE9ic2VydmVkLCB5ID0gUHJlZGljdGVkKSkgKwogIGdlb21fcG9pbnQoKSArCiAgZ2VvbV9hYmxpbmUoc2xvcGUgPSAxLCBpbnRlcmNlcHQgPSAwLCBjb2xvciA9ICJyZWQiLCAKICAgICAgICAgICAgICBsaW5ldHlwZSA9ICJkYXNoZWQiKSArCiAgZmFjZXRfd3JhcCh+IE1vZGVsKSArCiAgdGhlbWVfYncoKQpwCmBgYAoKWW91IGNhbiBzZWUgdGhhdCB0aGVyZSdzIGEgY2x1c3RlciBvZiBwb2ludHMgY2xvc2UgdG8gdGhlIDE6MSBsaW5lIHdpdGggZ2Vub21pYyBwcmVkaWN0aW9uLCBhbmQgdGhhdCB0aGUgcG9pbnRzIHNlZW0gdG8gYmUgYSBiaXQgZmFydGhlciBmcm9tIHRoZSAxOjEgbGluZSB3aXRoIHRoZSBsb2N1cyBieSBsb2N1cyBHV0FTLiBXZSBjYW4gY2hlY2sgdGhhdCBieSBjYWxjdWxhdGluZyB0aGUgbWVhbiBzcXVhcmVkIGVycm9yLgoKYGBge3J9CmNhdCgiTWVhbiBzcXVhcmVkIGVycm9yOlxuIiwKICAgICIgICBHV0FTOiAiLCByb3VuZChzdW0oc3Vic2V0KHByZWRpY3Rpb25zLCBNb2RlbCA9PSAiR1dBUyIpJEVycm9yXjIpLAogICAgICAgICAgICAgICAgICAgICAgIDMpL25yb3coZGF0KSwgIlxuIiwKICAgICIgICAgIEdQOiAiLCByb3VuZChzdW0oc3Vic2V0KHByZWRpY3Rpb25zLCBNb2RlbCA9PSAiR1AiKSRFcnJvcl4yKSwKICAgICAgICAgICAgICAgICAgICAgICAzKS9ucm93KGRhdCksICJcbiIsCiAgICBzZXAgPSAiIikKYGBgCgpBcyB5b3UgY2FuIHNlZSwgb3VyIChvciBhdCBsZWFzdCBteSkgc3ViamVjdGl2ZSBpbXByZXNzaW9uIHdhcyB3cm9uZy4gSWYgd2Ugd2VyZSB0byB1c2UgYWxsIDIwIGxvY2ksIHRoZSBsb2N1cyBieSBsb2N1cyBHV0FTIHdvdWxkLCBvbiBhdmVyYWdlLCBiZSBjbG9zZXIgdG8gdGhlICJ0cnV0aCIgdGhhbiB0aGUgZ2Vub21pYyBwcmVkaWN0aW9uIGFwcHJvYWNoIC0tIGV2ZW4gdGhvdWdoIHdlIGtub3cgdGhhdCBpdCBnb3QgdGhlIGVmZmVjdHMgd3Jvbmcu