GWAS with Stan

Friedline et al.1 investigated the role of natural selection in the rapid spread of gypsy moth (Lymantria dispar) across Eastern North America. Their analysis focused on analysis of polymorphisms at 91,468 SNPs identified through double digest restriction-site associated DNA sequencing (ddRADseq). As part of their work, they also collected data on pupal mass (Mass), pupal development time (PD), and total development time (TDT). This allows us to perform a genome-wide association analysis that assesses the relationship, if any, between individual SNP loci and each of the phenotypes. You’ll find two data sets on the course web site:

The data set is a subset of the data included in the paper. Specifically, I filtered the data to include only (a) loci that were scored in more than 100 individuals, (b) individuals that had more than 4000 of the remaing SNP loci scored, and (c) loci that were scored in all of the remaining individuals. The resulting data set includes 141 individuals scored at 218 loci. Using these data, answer the following questions:

  1. What loci (if any) are associated with each of the three traits (pupal mass, pupal development time, and total development time)?

IMPORTANT NOTE: The loci are ordered from the strongest estimated effect (mean) to the weakest, but loci showing a weaker estimated effect may have stronger evidence for them, i.e., the credible interval may not overlap zero. Because of the small sample size, I recommend considering both the 80% and the 95% credible intervals whenn answering these questions.

In the example below you’ll see that X4293 has the largest estimated effect, 0.01318, but that both the 80% and the 95% credible intervals overlap zero, meaning that we the evidence supporting a positive effect at this locus is weak. In contrast, the magnitude of the estimated effect at X2841 is smaller, -0.00853,2 but the 80 percent credible interval, (0.00115, 0.02514), does not overlap zero. You’re probably wondering why the mean isn’t inside the credible interval. It’s because the distribution is very skewed the median is 0.01325. Even though I’ve ordered the loci by the mean, it’s probably better to focus on the median, i.e., the 50% quantile. If you do that, you can see that for X4293, the magnitude of the estimated effect, -0.00827, is smaller than for X2841, which is consistent with us having stronger evidence for an effect at X2841.

  1. Is there evidence that any of the SNP loci are associated with variation in more than one of the traits?

  2. Given your answer to #2, would you expect to see a change in pupal development time, total development time, or both if natural selection led to a change in pupal mass? Why or why not?

Short example of an analysis

NOTE: To run this code you will also have to download gwas.stan from the course website using the link here. Save it in the same directory as you save the data files. Then run the code. Here are links to the files you’ll need:

I suggest running the code below as is so that you get a sense of how long the analyses will take. Once you’ve run this code, you can run other analyses simply by running analyze_trait(). If you leave off the num_loci argument, it will perform an analysis for all of the loci in the data set. For example,

results <- analyze_trait(dat, L, "Mass")

Will analyze the association between each of the 218 loci in the data set and Mass, and the results will be stored in results. Then if you

summarize_analysis(results)

You’ll get a report with the estimated effect at the 20 loci having the largest effect on the phenotype (sorted by largest effect to smallest). The first number is the posterior mean of the estimated effect and the numbers in parentheses are the 2.5%, 10%, 50%, 90%, and 97.5% quantiles. The lower bound of the 95% credible interval is given by the 2.5% quantile, and the upper bound is given by the 97.5% quantile. The lower bound of the 80% credible interval is given by the 10% quantile, and the upper bound is given by the 90% quantile.

If you’d like to see the effects for all of the loci, simply use

summarize_analysis(results, n_report = 218)

The n_report argument is the number of loci on which to report. With these data you can select any number between 1 and 218.

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(rstan)
Loading required package: StanHeaders
rstan (Version 2.21.2, GitRev: 2e1f913d3ca3)
For execution on a local, multicore CPU with excess RAM we recommend calling
options(mc.cores = parallel::detectCores()).
To avoid recompilation of unchanged Stan programs, we recommend calling
rstan_options(auto_write = TRUE)

Attaching package: ‘rstan’

The following object is masked from ‘package:tidyr’:

    extract
rm(list = ls())

options(mc.cores = parallel::detectCores())

dat <- read_csv("gypsymoth.csv",
                show_col_types = FALSE)
L <- read_csv("gypsymoth_relatedness.csv",
                show_col_types = FALSE)

analyze_trait <- function(dat, L, trait, n_loci = NA) {
  ## convert dat to data frame for subscripting
  ##
  dat <- as.data.frame(dat)

  if (is.na(n_loci)) {
    n_loci <- ncol(dat) - 5
  }
  n_chains <- 4
  n_iter <- 5000
  n_samples <- n_iter*n_chains
  p <- matrix(nrow = n_loci, ncol = n_samples)
  mean_p <- numeric(n_loci)
  mu <- array(dim = c(n_loci, n_samples, nrow(dat)))
  for (i in 1:n_loci) {
    cat("Checking locus ", i, "\n", sep = "")
    stan_data <- list(n_indiv = nrow(dat),
                      geno = dat[, i+5],
                      pheno = dat[[trait]],
                      L = L)
    stan_pars <- c("p", "mu")
    fit <- stan("gwas.stan",
                data = stan_data,
                pars = stan_pars,
                iter = n_iter,
                chains = n_chains,
                refresh = 0)
    x <- as.data.frame(fit)
    p[i,] <- x$p
    mean_p[i] <- mean(x$p)
  }
  loci <- data.frame(locus = colnames(dat)[(1:n_loci) + 5],
                     p_mean = mean_p)
  loci <- loci[order(abs(loci$p_mean), decreasing = TRUE), ]
  rownames(p) <- loci$locus
  return(list(loci = loci, p = p))
}

summarize_analysis <- function(results, n_report = 20) {
  if (n_report > nrow(results$loci)) {
    n_report <- nrow(results$loci)
  }
  cat("Mean: (2.5%, 10%, 50%, 90%, 97.5%)\n")
  for (i in 1:n_report) {
    ci <- quantile(results$p[results$loci$locus[i], ],
                   c(0.025, 0.1, 0.5, 0.9, 0.975))
    output <- sprintf("%6s: %8.5f (%8.5f, %8.5f, %8.5f, %8.5f, %8.5f)\n",
                      results$loci$locus[i],
                      results$loci$p_mean[i],
                      ci[1], ci[2], ci[3], ci[4], ci[5])
    cat(output)
  }
}

results <- analyze_trait(dat, L, "Mass", n_loci = 10)
Checking locus 1
recompiling to avoid crashing R session
Checking locus 2
recompiling to avoid crashing R session
Checking locus 3
Checking locus 4
Checking locus 5
Checking locus 6
Checking locus 7
Checking locus 8
Checking locus 9
Checking locus 10
summarize_analysis(results)
Mean: (2.5%, 10%, 50%, 90%, 97.5%)
 X4293:  0.01318 (-0.02831, -0.02130, -0.00827,  0.00453,  0.01123)
 X5330:  0.00920 (-0.02810, -0.02177, -0.00918,  0.00360,  0.01017)
 X3915: -0.00918 (-0.02792, -0.02098, -0.00842,  0.00384,  0.01023)
 X2840: -0.00913 (-0.02723, -0.02096, -0.00909,  0.00235,  0.00848)
 X2841: -0.00853 (-0.00521,  0.00115,  0.01325,  0.02514,  0.03131)
 X2517: -0.00838 (-0.02457, -0.01676, -0.00350,  0.00958,  0.01672)
 X4680:  0.00533 (-0.01223, -0.00604,  0.00537,  0.01655,  0.02270)
 X4612: -0.00355 (-0.01609, -0.00986,  0.00231,  0.01395,  0.02034)
 X4753:  0.00215 (-0.00771, -0.00172,  0.00910,  0.02027,  0.02624)
 X6607: -0.00116 (-0.01949, -0.01291, -0.00124,  0.01085,  0.01741)

How I prepared the data for analysis

If you’re interested in seeing how I prepared the data from the version on Dryad. Here’s what I did.

First, I downloaded the data from Dryad: https://doi.org/10.5061/dryad.8ts2867. Then I renamed the phenotype filename so that it begins with gm. The rest is pretty straightforward, except that you haven’t seen popkin() before, which produces the relatedness matrix. I also fiddle a bit with the results from popkin() to get them in the form that’s most convenient for analysis in Stan.

library(tidyverse)
library(popkin)

rm(list = ls())

genos <- read_tsv("gm_genotypes_012_final_5122017.txt",
                  col_names = FALSE,
                  na = "-1",
                  show_col_types = FALSE)
phenos <- read_csv("gm_phenotypes.csv",
                   show_col_types = FALSE)

## keep only loci scored in more than 100 individuals
##
n_scored <- apply(genos, 2, sum, na.rm = TRUE)
genos <- genos[, n_scored > 100]

## keep only individuals scored at more than 4000 loci
##
n_scored <- apply(genos, 1, sum, na.rm = TRUE)
genos <- genos[n_scored > 4000, ]
phenos <- phenos[n_scored > 4000, ]
## and exclude any remaining loci where one or more individuals isn't scored
##
genos <- genos[, !is.na(apply(genos, 2, sum))]

## strip off the individual ids to identify populations
##
pops <- gsub("_.*", "", phenos$sample)

## bind the poopulation, phenotype, and genotype information together and save it in a CSV file
##
dat <- cbind(pops, phenos, genos)
write_csv(dat, 
          file = "gypsymoth.csv")

## estimate the kinship among individuals and save it in a CSV file
##
phi <- popkin(t(as.matrix(genos)), 
              subpops = pops)
L <- t(chol(phi))
write_csv(as.data.frame(L),
          file = "gypsymoth_relatedness.csv")

  1. Friedline, C.J., T.M. Faske, B.M. Lind, E.M. Hobson, D. Parry, R.J. Dyer, D.M. Johnson, L.M. Thompson, K.L. Grayson, and A.J. Eckert. 2019. Evolutionary genomics of gypsy moth populations sampled along a latitudinal gradient. Molecular Ecology 28:2206-2223 doi: https://doi.org/10.1111/mec.15069↩︎

  2. Note that we are comparing magnitudes, so take the absolute value of numbers before comparing them.↩︎

LS0tCnRpdGxlOiAiR1dBUyBpbiBneXBzeSBtb3RocyIKb3V0cHV0OiBodG1sX25vdGVib29rCi0tLQoKIyBHV0FTIHdpdGggYFN0YW5gCgpGcmllZGxpbmUgZXQgYWwuXltGcmllZGxpbmUsIEMuSi4sIFQuTS4gRmFza2UsIEIuTS4gTGluZCwgRS5NLiBIb2Jzb24sIEQuIFBhcnJ5LCBSLkouIER5ZXIsIEQuTS4gSm9obnNvbiwgTC5NLiBUaG9tcHNvbiwgSy5MLiBHcmF5c29uLCBhbmQgQS5KLiBFY2tlcnQuICAyMDE5LiAgRXZvbHV0aW9uYXJ5IGdlbm9taWNzIG9mIGd5cHN5IG1vdGggcG9wdWxhdGlvbnMgc2FtcGxlZCBhbG9uZyBhIGxhdGl0dWRpbmFsIGdyYWRpZW50LiBfTW9sZWN1bGFyIEVjb2xvZ3lfIDI4OjIyMDYtMjIyMyBkb2k6IFtodHRwczovL2RvaS5vcmcvMTAuMTExMS9tZWMuMTUwNjldKGh0dHBzOi8vZG9pLm9yZy8xMC4xMTExL21lYy4xNTA2OSldIGludmVzdGlnYXRlZCB0aGUgcm9sZSBvZiBuYXR1cmFsIHNlbGVjdGlvbiBpbiB0aGUgcmFwaWQgc3ByZWFkIG9mIGd5cHN5IG1vdGggKF9MeW1hbnRyaWEgZGlzcGFyXykgYWNyb3NzIEVhc3Rlcm4gTm9ydGggQW1lcmljYS4gVGhlaXIgYW5hbHlzaXMgZm9jdXNlZCBvbiBhbmFseXNpcyBvZiBwb2x5bW9ycGhpc21zIGF0IDkxLDQ2OCBTTlBzIGlkZW50aWZpZWQgdGhyb3VnaCBkb3VibGUgZGlnZXN0IHJlc3RyaWN0aW9uLXNpdGUgYXNzb2NpYXRlZCBETkEgc2VxdWVuY2luZyAoZGRSQURzZXEpLiBBcyBwYXJ0IG9mIHRoZWlyIHdvcmssIHRoZXkgYWxzbyBjb2xsZWN0ZWQgZGF0YSBvbiBwdXBhbCBtYXNzIChNYXNzKSwgcHVwYWwgZGV2ZWxvcG1lbnQgdGltZSAoUEQpLCBhbmQgdG90YWwgZGV2ZWxvcG1lbnQgdGltZSAoVERUKS4gVGhpcyBhbGxvd3MgdXMgdG8gcGVyZm9ybSBhIGdlbm9tZS13aWRlIGFzc29jaWF0aW9uIGFuYWx5c2lzIHRoYXQgYXNzZXNzZXMgdGhlIHJlbGF0aW9uc2hpcCwgaWYgYW55LCBiZXR3ZWVuIGluZGl2aWR1YWwgU05QIGxvY2kgYW5kIGVhY2ggb2YgdGhlIHBoZW5vdHlwZXMuIFlvdeKAmWxsIGZpbmQgdHdvIGRhdGEgc2V0cyBvbiB0aGUgY291cnNlIHdlYiBzaXRlOgoKLSBneXBzeW1vdGguY3N2OiBBIENTViBmaWxlIGNvbnRhaW5pbmcgaW5mb3JtYXRpb24gYWJvdXQgZWFjaCBpbmRpdmlkdWFsIGluIHRoZSBzYW1wbGUgKHBvcHVsYXRpb24gb2Ygb3JpZ2luLCBzYW1wbGUgbGFiZWwsIHBoZW5vdHlwZSwgZ2Vub3R5cGUgYXQgZWFjaCBTTlAgbG9jdXMpLgotIGd5cHN5bW90aC1yZWxhdGVkbmVzcy5jc3Y6IEEgQ1NWIGZpbGUgY29udGFpbmluZyB0aGUgcmVsYXRlZG5lc3MgbWF0cml4IGZvciBpbmRpLSB2aWR1YWxzIGluY2x1ZGVkIGluIHRoZSBkYXRhIHNldC4KClRoZSBkYXRhIHNldCBpcyBhIHN1YnNldCBvZiB0aGUgZGF0YSBpbmNsdWRlZCBpbiB0aGUgcGFwZXIuIFNwZWNpZmljYWxseSwgSSBmaWx0ZXJlZCB0aGUgZGF0YSB0byBpbmNsdWRlIG9ubHkgKGEpIGxvY2kgdGhhdCB3ZXJlIHNjb3JlZCBpbiBtb3JlIHRoYW4gMTAwIGluZGl2aWR1YWxzLCAoYikgaW5kaXZpZHVhbHMgdGhhdCBoYWQgbW9yZSB0aGFuIDQwMDAgb2YgdGhlIHJlbWFpbmcgU05QIGxvY2kgc2NvcmVkLCBhbmQgKGMpIGxvY2kgdGhhdCB3ZXJlIHNjb3JlZCBpbiBhbGwgb2YgdGhlIHJlbWFpbmluZyBpbmRpdmlkdWFscy4gVGhlIHJlc3VsdGluZyBkYXRhIHNldCBpbmNsdWRlcyAxNDEgaW5kaXZpZHVhbHMgc2NvcmVkIGF0IDIxOCBsb2NpLiBVc2luZyB0aGVzZSBkYXRhLCBhbnN3ZXIgdGhlIGZvbGxvd2luZyBxdWVzdGlvbnM6CgoxLiBXaGF0IGxvY2kgKGlmIGFueSkgYXJlIGFzc29jaWF0ZWQgd2l0aCBlYWNoIG9mIHRoZSB0aHJlZSB0cmFpdHMgKHB1cGFsIG1hc3MsIHB1cGFsIGRldmVsb3BtZW50IHRpbWUsIGFuZCB0b3RhbCBkZXZlbG9wbWVudCB0aW1lKT8KCklNUE9SVEFOVCBOT1RFOiBUaGUgbG9jaSBhcmUgb3JkZXJlZCBmcm9tIHRoZSBzdHJvbmdlc3QgZXN0aW1hdGVkIGVmZmVjdCAobWVhbikgdG8gdGhlIHdlYWtlc3QsIGJ1dCBsb2NpIHNob3dpbmcgYSB3ZWFrZXIgZXN0aW1hdGVkIGVmZmVjdCBtYXkgaGF2ZSBzdHJvbmdlciBldmlkZW5jZSBmb3IgdGhlbSwgaS5lLiwgdGhlIGNyZWRpYmxlIGludGVydmFsIG1heSBub3Qgb3ZlcmxhcCB6ZXJvLiBCZWNhdXNlIG9mIHRoZSBzbWFsbCBzYW1wbGUgc2l6ZSwgSSByZWNvbW1lbmQgY29uc2lkZXJpbmcgYm90aCB0aGUgODAlIGFuZCB0aGUgOTUlIGNyZWRpYmxlIGludGVydmFscyB3aGVubiBhbnN3ZXJpbmcgdGhlc2UgcXVlc3Rpb25zLiAKCkluIHRoZSBleGFtcGxlIGJlbG93IHlvdSdsbCBzZWUgdGhhdCBYNDI5MyBoYXMgdGhlIGxhcmdlc3QgZXN0aW1hdGVkIGVmZmVjdCwgMC4wMTMxOCwgYnV0IHRoYXQgYm90aCB0aGUgODAlIGFuZCB0aGUgOTUlIGNyZWRpYmxlIGludGVydmFscyBvdmVybGFwIHplcm8sIG1lYW5pbmcgdGhhdCB3ZSB0aGUgZXZpZGVuY2Ugc3VwcG9ydGluZyBhIHBvc2l0aXZlIGVmZmVjdCBhdCB0aGlzIGxvY3VzIGlzIHdlYWsuIEluIGNvbnRyYXN0LCB0aGUgbWFnbml0dWRlIG9mIHRoZSBlc3RpbWF0ZWQgZWZmZWN0IGF0IFgyODQxIGlzIHNtYWxsZXIsIC0wLjAwODUzLF5bTm90ZSB0aGF0IHdlIGFyZSBjb21wYXJpbmcgbWFnbml0dWRlcywgc28gdGFrZSB0aGUgYWJzb2x1dGUgdmFsdWUgb2YgbnVtYmVycyBiZWZvcmUgY29tcGFyaW5nIHRoZW0uXSBidXQgdGhlIDgwIHBlcmNlbnQgY3JlZGlibGUgaW50ZXJ2YWwsICgwLjAwMTE1LCAgMC4wMjUxNCksIGRvZXMgbm90IG92ZXJsYXAgemVyby4gWW91J3JlIHByb2JhYmx5IHdvbmRlcmluZyB3aHkgdGhlIG1lYW4gaXNuJ3QgaW5zaWRlIHRoZSBjcmVkaWJsZSBpbnRlcnZhbC4gSXQncyBiZWNhdXNlIHRoZSBkaXN0cmlidXRpb24gaXMgdmVyeSBza2V3ZWQgdGhlIG1lZGlhbiBpcyAwLjAxMzI1LiBFdmVuIHRob3VnaCBJJ3ZlIG9yZGVyZWQgdGhlIGxvY2kgYnkgdGhlIG1lYW4sIGl0J3MgcHJvYmFibHkgYmV0dGVyIHRvIGZvY3VzIG9uIHRoZSBtZWRpYW4sIGkuZS4sIHRoZSA1MCUgcXVhbnRpbGUuIElmIHlvdSBkbyB0aGF0LCB5b3UgY2FuIHNlZSB0aGF0IGZvciBYNDI5MywgdGhlIG1hZ25pdHVkZSBvZiB0aGUgZXN0aW1hdGVkIGVmZmVjdCwgLTAuMDA4MjcsIGlzIHNtYWxsZXIgdGhhbiBmb3IgWDI4NDEsIHdoaWNoIGlzIGNvbnNpc3RlbnQgd2l0aCB1cyBoYXZpbmcgc3Ryb25nZXIgZXZpZGVuY2UgZm9yIGFuIGVmZmVjdCBhdCBYMjg0MS4KCjIuIElzIHRoZXJlIGV2aWRlbmNlIHRoYXQgYW55IG9mIHRoZSBTTlAgbG9jaSBhcmUgYXNzb2NpYXRlZCB3aXRoIHZhcmlhdGlvbiBpbiBtb3JlIHRoYW4gb25lIG9mIHRoZSB0cmFpdHM/CgozLiBHaXZlbiB5b3VyIGFuc3dlciB0byAjMiwgd291bGQgeW91IGV4cGVjdCB0byBzZWUgYSBjaGFuZ2UgaW4gcHVwYWwgZGV2ZWxvcG1lbnQgdGltZSwgdG90YWwgZGV2ZWxvcG1lbnQgdGltZSwgb3IgYm90aCBpZiBuYXR1cmFsIHNlbGVjdGlvbiBsZWQgdG8gYSBjaGFuZ2UgaW4gcHVwYWwgbWFzcz8gV2h5IG9yIHdoeSBub3Q/CgojIFNob3J0IGV4YW1wbGUgb2YgYW4gYW5hbHlzaXMKCk5PVEU6IFRvIHJ1biB0aGlzIGNvZGUgeW91IHdpbGwgYWxzbyBoYXZlIHRvIGRvd25sb2FkIFtnd2FzLnN0YW5dKGh0dHA6Ly9kYXJ3aW4uZWViLnVjb25uLmVkdS9lZWIzNDgtcmVzb3VyY2VzL2d3YXMuc3RhbikgZnJvbSB0aGUgY291cnNlIHdlYnNpdGUgdXNpbmcgdGhlIGxpbmsgaGVyZS4gU2F2ZSBpdCBpbiB0aGUgc2FtZSBkaXJlY3RvcnkgYXMgeW91IHNhdmUgdGhlIGRhdGEgZmlsZXMuIFRoZW4gcnVuIHRoZSBjb2RlLiBIZXJlIGFyZSBsaW5rcyB0byB0aGUgZmlsZXMgeW91J2xsIG5lZWQ6CgotIFtnd2FzLnN0YW5dKGh0dHA6Ly9kYXJ3aW4uZWViLnVjb25uLmVkdS9lZWIzNDgtcmVzb3VyY2VzL2d3YXMuc3RhbikKLSBbZ3lwc3ltb3RoLmNzdl0oaHR0cDovL2Rhcndpbi5lZWIudWNvbm4uZWR1L2VlYjM0OC1yZXNvdXJjZXMvZ3lwc3ltb3RoLmNzdikKLSBbZ3lwc3ltb3RoX3JlbGF0ZWRuZXNzLmNzdl0oaHR0cDovL2Rhcndpbi5lZWIudWNvbm4uZWR1L2VlYjM0OC1yZXNvdXJjZXMvZ3lwc3ltb3RoX3JlbGF0ZWRuZXNzLmNzdikKCkkgc3VnZ2VzdCBydW5uaW5nIHRoZSBjb2RlIGJlbG93IGFzIGlzIHNvIHRoYXQgeW91IGdldCBhIHNlbnNlIG9mIGhvdyBsb25nIHRoZSBhbmFseXNlcyB3aWxsIHRha2UuIE9uY2UgeW91J3ZlIHJ1biB0aGlzIGNvZGUsIHlvdSBjYW4gcnVuIG90aGVyIGFuYWx5c2VzIHNpbXBseSBieSBydW5uaW5nIGBhbmFseXplX3RyYWl0KClgLiBJZiB5b3UgbGVhdmUgb2ZmIHRoZSBgbnVtX2xvY2lgIGFyZ3VtZW50LCBpdCB3aWxsIHBlcmZvcm0gYW4gYW5hbHlzaXMgZm9yIGFsbCBvZiB0aGUgbG9jaSBpbiB0aGUgZGF0YSBzZXQuIEZvciBleGFtcGxlLAoKYGBge3J9CnJlc3VsdHMgPC0gYW5hbHl6ZV90cmFpdChkYXQsIEwsICJNYXNzIikKYGBgCgpXaWxsIGFuYWx5emUgdGhlIGFzc29jaWF0aW9uIGJldHdlZW4gZWFjaCBvZiB0aGUgMjE4IGxvY2kgaW4gdGhlIGRhdGEgc2V0IGFuZCBNYXNzLCBhbmQgdGhlIHJlc3VsdHMgd2lsbCBiZSBzdG9yZWQgaW4gYHJlc3VsdHNgLiBUaGVuIGlmIHlvdQoKYGBge3J9CnN1bW1hcml6ZV9hbmFseXNpcyhyZXN1bHRzKQpgYGAKCllvdSdsbCBnZXQgYSByZXBvcnQgd2l0aCB0aGUgZXN0aW1hdGVkIGVmZmVjdCBhdCB0aGUgMjAgbG9jaSBoYXZpbmcgdGhlIGxhcmdlc3QgZWZmZWN0IG9uIHRoZSBwaGVub3R5cGUgKHNvcnRlZCBieSBsYXJnZXN0IGVmZmVjdCB0byBzbWFsbGVzdCkuIFRoZSBmaXJzdCBudW1iZXIgaXMgdGhlIHBvc3RlcmlvciBtZWFuIG9mIHRoZSBlc3RpbWF0ZWQgZWZmZWN0IGFuZCB0aGUgbnVtYmVycyBpbiBwYXJlbnRoZXNlcyBhcmUgdGhlIDIuNSUsIDEwJSwgNTAlLCA5MCUsIGFuZCA5Ny41JSBxdWFudGlsZXMuIFRoZSBsb3dlciBib3VuZCBvZiB0aGUgOTUlIGNyZWRpYmxlIGludGVydmFsIGlzIGdpdmVuIGJ5IHRoZSAyLjUlIHF1YW50aWxlLCBhbmQgdGhlIHVwcGVyIGJvdW5kIGlzIGdpdmVuIGJ5IHRoZSA5Ny41JSBxdWFudGlsZS4gVGhlIGxvd2VyIGJvdW5kIG9mIHRoZSA4MCUgY3JlZGlibGUgaW50ZXJ2YWwgaXMgZ2l2ZW4gYnkgdGhlIDEwJSBxdWFudGlsZSwgYW5kIHRoZSB1cHBlciBib3VuZCBpcyBnaXZlbiBieSB0aGUgOTAlIHF1YW50aWxlLgoKSWYgeW91J2QgbGlrZSB0byBzZWUgdGhlIGVmZmVjdHMgZm9yIGFsbCBvZiB0aGUgbG9jaSwgc2ltcGx5IHVzZQoKYGBge3J9CnN1bW1hcml6ZV9hbmFseXNpcyhyZXN1bHRzLCBuX3JlcG9ydCA9IDIxOCkKYGBgCgpUaGUgYG5fcmVwb3J0YCBhcmd1bWVudCBpcyB0aGUgbnVtYmVyIG9mIGxvY2kgb24gd2hpY2ggdG8gcmVwb3J0LiBXaXRoIHRoZXNlIGRhdGEgeW91IGNhbiBzZWxlY3QgYW55IG51bWJlciBiZXR3ZWVuIDEgYW5kIDIxOC4KCmBgYHtyfQpsaWJyYXJ5KHRpZHl2ZXJzZSkKbGlicmFyeShyc3RhbikKCnJtKGxpc3QgPSBscygpKQoKb3B0aW9ucyhtYy5jb3JlcyA9IHBhcmFsbGVsOjpkZXRlY3RDb3JlcygpKQoKZGF0IDwtIHJlYWRfY3N2KCJneXBzeW1vdGguY3N2IiwKICAgICAgICAgICAgICAgIHNob3dfY29sX3R5cGVzID0gRkFMU0UpCkwgPC0gcmVhZF9jc3YoImd5cHN5bW90aF9yZWxhdGVkbmVzcy5jc3YiLAogICAgICAgICAgICAgICAgc2hvd19jb2xfdHlwZXMgPSBGQUxTRSkKCmFuYWx5emVfdHJhaXQgPC0gZnVuY3Rpb24oZGF0LCBMLCB0cmFpdCwgbl9sb2NpID0gTkEpIHsKICAjIyBjb252ZXJ0IGRhdCB0byBkYXRhIGZyYW1lIGZvciBzdWJzY3JpcHRpbmcKICAjIwogIGRhdCA8LSBhcy5kYXRhLmZyYW1lKGRhdCkKCiAgaWYgKGlzLm5hKG5fbG9jaSkpIHsKICAgIG5fbG9jaSA8LSBuY29sKGRhdCkgLSA1CiAgfQogIG5fY2hhaW5zIDwtIDQKICBuX2l0ZXIgPC0gNTAwMAogIG5fc2FtcGxlcyA8LSBuX2l0ZXIqbl9jaGFpbnMKICBwIDwtIG1hdHJpeChucm93ID0gbl9sb2NpLCBuY29sID0gbl9zYW1wbGVzKQogIG1lYW5fcCA8LSBudW1lcmljKG5fbG9jaSkKICBtdSA8LSBhcnJheShkaW0gPSBjKG5fbG9jaSwgbl9zYW1wbGVzLCBucm93KGRhdCkpKQogIGZvciAoaSBpbiAxOm5fbG9jaSkgewogICAgY2F0KCJDaGVja2luZyBsb2N1cyAiLCBpLCAiXG4iLCBzZXAgPSAiIikKICAgIHN0YW5fZGF0YSA8LSBsaXN0KG5faW5kaXYgPSBucm93KGRhdCksCiAgICAgICAgICAgICAgICAgICAgICBnZW5vID0gZGF0WywgaSs1XSwKICAgICAgICAgICAgICAgICAgICAgIHBoZW5vID0gZGF0W1t0cmFpdF1dLAogICAgICAgICAgICAgICAgICAgICAgTCA9IEwpCiAgICBzdGFuX3BhcnMgPC0gYygicCIsICJtdSIpCiAgICBmaXQgPC0gc3RhbigiZ3dhcy5zdGFuIiwKICAgICAgICAgICAgICAgIGRhdGEgPSBzdGFuX2RhdGEsCiAgICAgICAgICAgICAgICBwYXJzID0gc3Rhbl9wYXJzLAogICAgICAgICAgICAgICAgaXRlciA9IG5faXRlciwKICAgICAgICAgICAgICAgIGNoYWlucyA9IG5fY2hhaW5zLAogICAgICAgICAgICAgICAgcmVmcmVzaCA9IDApCiAgICB4IDwtIGFzLmRhdGEuZnJhbWUoZml0KQogICAgcFtpLF0gPC0geCRwCiAgICBtZWFuX3BbaV0gPC0gbWVhbih4JHApCiAgfQogIGxvY2kgPC0gZGF0YS5mcmFtZShsb2N1cyA9IGNvbG5hbWVzKGRhdClbKDE6bl9sb2NpKSArIDVdLAogICAgICAgICAgICAgICAgICAgICBwX21lYW4gPSBtZWFuX3ApCiAgbG9jaSA8LSBsb2NpW29yZGVyKGFicyhsb2NpJHBfbWVhbiksIGRlY3JlYXNpbmcgPSBUUlVFKSwgXQogIHJvd25hbWVzKHApIDwtIGxvY2kkbG9jdXMKICByZXR1cm4obGlzdChsb2NpID0gbG9jaSwgcCA9IHApKQp9CgpzdW1tYXJpemVfYW5hbHlzaXMgPC0gZnVuY3Rpb24ocmVzdWx0cywgbl9yZXBvcnQgPSAyMCkgewogIGlmIChuX3JlcG9ydCA+IG5yb3cocmVzdWx0cyRsb2NpKSkgewogICAgbl9yZXBvcnQgPC0gbnJvdyhyZXN1bHRzJGxvY2kpCiAgfQogIGNhdCgiTWVhbjogKDIuNSUsIDEwJSwgNTAlLCA5MCUsIDk3LjUlKVxuIikKICBmb3IgKGkgaW4gMTpuX3JlcG9ydCkgewogICAgY2kgPC0gcXVhbnRpbGUocmVzdWx0cyRwW3Jlc3VsdHMkbG9jaSRsb2N1c1tpXSwgXSwKICAgICAgICAgICAgICAgICAgIGMoMC4wMjUsIDAuMSwgMC41LCAwLjksIDAuOTc1KSkKICAgIG91dHB1dCA8LSBzcHJpbnRmKCIlNnM6ICU4LjVmICglOC41ZiwgJTguNWYsICU4LjVmLCAlOC41ZiwgJTguNWYpXG4iLAogICAgICAgICAgICAgICAgICAgICAgcmVzdWx0cyRsb2NpJGxvY3VzW2ldLAogICAgICAgICAgICAgICAgICAgICAgcmVzdWx0cyRsb2NpJHBfbWVhbltpXSwKICAgICAgICAgICAgICAgICAgICAgIGNpWzFdLCBjaVsyXSwgY2lbM10sIGNpWzRdLCBjaVs1XSkKICAgIGNhdChvdXRwdXQpCiAgfQp9CgpyZXN1bHRzIDwtIGFuYWx5emVfdHJhaXQoZGF0LCBMLCAiTWFzcyIsIG5fbG9jaSA9IDEwKQpzdW1tYXJpemVfYW5hbHlzaXMocmVzdWx0cykKYGBgCgojIEhvdyBJIHByZXBhcmVkIHRoZSBkYXRhIGZvciBhbmFseXNpcwoKSWYgeW91J3JlIGludGVyZXN0ZWQgaW4gc2VlaW5nIGhvdyBJIHByZXBhcmVkIHRoZSBkYXRhIGZyb20gdGhlIHZlcnNpb24gb24gRHJ5YWQuIEhlcmUncyB3aGF0IEkgZGlkLiAKCkZpcnN0LCBJIGRvd25sb2FkZWQgdGhlIGRhdGEgZnJvbSBEcnlhZDogW2h0dHBzOi8vZG9pLm9yZy8xMC41MDYxL2RyeWFkLjh0czI4NjddKGh0dHBzOi8vZG9pLm9yZy8xMC41MDYxL2RyeWFkLjh0czI4NjcpLiBUaGVuIEkgcmVuYW1lZCB0aGUgcGhlbm90eXBlIGZpbGVuYW1lIHNvIHRoYXQgaXQgYmVnaW5zIHdpdGggYGdtYC4gVGhlIHJlc3QgaXMgcHJldHR5IHN0cmFpZ2h0Zm9yd2FyZCwgZXhjZXB0IHRoYXQgeW91IGhhdmVuJ3Qgc2VlbiBgcG9wa2luKClgIGJlZm9yZSwgd2hpY2ggcHJvZHVjZXMgdGhlIHJlbGF0ZWRuZXNzIG1hdHJpeC4gSSBhbHNvIGZpZGRsZSBhIGJpdCB3aXRoIHRoZSByZXN1bHRzIGZyb20gYHBvcGtpbigpYCB0byBnZXQgdGhlbSBpbiB0aGUgZm9ybSB0aGF0J3MgbW9zdCBjb252ZW5pZW50IGZvciBhbmFseXNpcyBpbiBgU3RhbmAuCgpgYGB7cn0KbGlicmFyeSh0aWR5dmVyc2UpCmxpYnJhcnkocG9wa2luKQoKcm0obGlzdCA9IGxzKCkpCgpnZW5vcyA8LSByZWFkX3RzdigiZ21fZ2Vub3R5cGVzXzAxMl9maW5hbF81MTIyMDE3LnR4dCIsCiAgICAgICAgICAgICAgICAgIGNvbF9uYW1lcyA9IEZBTFNFLAogICAgICAgICAgICAgICAgICBuYSA9ICItMSIsCiAgICAgICAgICAgICAgICAgIHNob3dfY29sX3R5cGVzID0gRkFMU0UpCnBoZW5vcyA8LSByZWFkX2NzdigiZ21fcGhlbm90eXBlcy5jc3YiLAogICAgICAgICAgICAgICAgICAgc2hvd19jb2xfdHlwZXMgPSBGQUxTRSkKCiMjIGtlZXAgb25seSBsb2NpIHNjb3JlZCBpbiBtb3JlIHRoYW4gMTAwIGluZGl2aWR1YWxzCiMjCm5fc2NvcmVkIDwtIGFwcGx5KGdlbm9zLCAyLCBzdW0sIG5hLnJtID0gVFJVRSkKZ2Vub3MgPC0gZ2Vub3NbLCBuX3Njb3JlZCA+IDEwMF0KCiMjIGtlZXAgb25seSBpbmRpdmlkdWFscyBzY29yZWQgYXQgbW9yZSB0aGFuIDQwMDAgbG9jaQojIwpuX3Njb3JlZCA8LSBhcHBseShnZW5vcywgMSwgc3VtLCBuYS5ybSA9IFRSVUUpCmdlbm9zIDwtIGdlbm9zW25fc2NvcmVkID4gNDAwMCwgXQpwaGVub3MgPC0gcGhlbm9zW25fc2NvcmVkID4gNDAwMCwgXQojIyBhbmQgZXhjbHVkZSBhbnkgcmVtYWluaW5nIGxvY2kgd2hlcmUgb25lIG9yIG1vcmUgaW5kaXZpZHVhbHMgaXNuJ3Qgc2NvcmVkCiMjCmdlbm9zIDwtIGdlbm9zWywgIWlzLm5hKGFwcGx5KGdlbm9zLCAyLCBzdW0pKV0KCiMjIHN0cmlwIG9mZiB0aGUgaW5kaXZpZHVhbCBpZHMgdG8gaWRlbnRpZnkgcG9wdWxhdGlvbnMKIyMKcG9wcyA8LSBnc3ViKCJfLioiLCAiIiwgcGhlbm9zJHNhbXBsZSkKCiMjIGJpbmQgdGhlIHBvb3B1bGF0aW9uLCBwaGVub3R5cGUsIGFuZCBnZW5vdHlwZSBpbmZvcm1hdGlvbiB0b2dldGhlciBhbmQgc2F2ZSBpdCBpbiBhIENTViBmaWxlCiMjCmRhdCA8LSBjYmluZChwb3BzLCBwaGVub3MsIGdlbm9zKQp3cml0ZV9jc3YoZGF0LCAKICAgICAgICAgIGZpbGUgPSAiZ3lwc3ltb3RoLmNzdiIpCgojIyBlc3RpbWF0ZSB0aGUga2luc2hpcCBhbW9uZyBpbmRpdmlkdWFscyBhbmQgc2F2ZSBpdCBpbiBhIENTViBmaWxlCiMjCnBoaSA8LSBwb3BraW4odChhcy5tYXRyaXgoZ2Vub3MpKSwgCiAgICAgICAgICAgICAgc3VicG9wcyA9IHBvcHMpCkwgPC0gdChjaG9sKHBoaSkpCndyaXRlX2Nzdihhcy5kYXRhLmZyYW1lKEwpLAogICAgICAgICAgZmlsZSA9ICJneXBzeW1vdGhfcmVsYXRlZG5lc3MuY3N2IikKYGBgCgo=