Introduction

Kidney transplantation or renal transplantation is the organ transplant of a kidney into a patient who has an end-stage renal disease. Scientists claim that some genes are responsible for a patient’s likelihood of rejecting a kidney after transplantation.

In this project, you are to investigate this claim. You will analyze data from the study by Einecke et al. (2010). The original data consists of microarray measurements from 54675 genes across 282 patients. For the purpose of this project, a random subset was made of 250 patients and 10.000 from the 25% most variable genes.

You can access the data through the HDDAData package, which can be installed from GitHub by running the following code in an R session:

if (!requireNamespace("remotes", quietly = TRUE)) {
    install.packages("remotes")
}
remotes::install_github("statOmics/HDDAData")

Note that you need to run this piece of code only once. Don’t include it in your R script, just run it once in an R console and you’re good to go.

You can then access the data in your script as follows:

library(HDDAData)
data("Einecke2010Kidney")

## Data dimensions
dim(Einecke2010Kidney)
#> [1]   250 10001

## Showing first 6 rows and 10 columns
head(Einecke2010Kidney[, 1:10])

More information about the data and its format can be found in the documentation, see ?Einecke2010Kidney.

The first column, Reject_Status, consists of a binary variable encoding whether the kidney transplant was accepted (0) or rejected (1) for each patient. The other columns contain the microarray expression data for the 10.000 genes. The rownames of the data frame contains the patient identifiers.

## Extract gene expression data as matrix X
X <- as.matrix(Einecke2010Kidney[, -1])
dim(X)
#> [1]   250 10000
str(X)
#>  num [1:250, 1:10000] 2.369 -1.488 0.556 0.127 -0.38 ...
#>  - attr(*, "dimnames")=List of 2
#>   ..$ : chr [1:250] "GSM534173" "GSM534125" "GSM534044" "GSM533968" ...
#>   ..$ : chr [1:10000] "X211352_s_at" "X239275_at" "X1554536_at" "X1558452_at" ...

## Extract Reject_Status column as vector
reject_status <- Einecke2010Kidney$Reject_Status
names(reject_status) <- rownames(Einecke2010Kidney)
table(reject_status) # number of 0's (accepts) and 1's (rejects)
#> reject_status
#>   0   1 
#> 183  67

Assignment

You must work in groups of four students.

We are interested in the following research questions:

  • How do the genes vary in terms of their gene expression levels? Is the variability associated with kidney rejection? (only to be answered in a data explorative / graphical manner)

  • Which genes are differentially expressed between the two kidney rejection groups? You must control the FDR at 10%.

  • Can the kidney rejection be predicted from the gene expression levels? What genes are most important in predicting the kidney transplant rejection? How well does the prediction model perform in terms of predicting rejection status?

    Note that the response variable is binary, so if you use regression models, you will need to use logistic regression, which models the response with a binomial distribution. This can generally be done in R by specifying family = "binomial" in regression functions such as glm and glmnet.

Write a scientific report that answers the research questions related to this study. The report must consist of two parts:

  • An executive summary of about half a page. This summary contains the answers to the original research questions, and should be written in a non-technical manner (it is meant for researchers without a statistical background).

  • A technical report that explains in detail how the results were obtained. The reader should understand what you did without looking at the code!

It’s recommended to prepare the report as an RMarkdown file. If you choose to use another format, then the R code should be submitted as a separate file (please properly comment your R code).

The report is expected to be concise, but must evidently be accurate and sufficiently detailed to enable the reader to verify the correctness of the result (i.e. your results must be reproducible). The total length of the report (excluding graphs, R code and possibly appendices) should not be more than three pages. The report should not contain an explanation of the theory behind the statistical methods, and should also not contain the study description given above (you can assume that the reader already knows this).

Interpretation of the results is key!

Some more specific guidelines:

  • For the first research question, you may use one of the data exploration tools that we have seen in class. However, you are also free to search the literature for other techniques for data exploration and visualisation (your final mark will not depend on whether you searched the literature or not). You are only asked to explore whether the variability in gene expression levels is associated with rejection status; no need for hypothesis testing.

  • For the second research question, you should perform hypothesis testing and correct for multiple testing so as to control the FDR at 10%. The full list with differentially expressed genes may be presented in an appendix. Only list the most important results in the body of the report.

  • For the third research question you are asked to predict rejection status using gene expression levels. You should randomly split the data into a test (30%) and a training (70%) dataset. Make sure you use a seed (set.seed() function) in R for reproducibility. The following prediction models should be evaluated:

    • Principal Component Regression (PCR)

    • Ridge Regression

    • Lasso regression

Note that the response variable (the rejection status) is binary, so you will have to use logistic regression!

In choosing the number of PCs in PCR, and the \(\gamma\) in the Ridge and Lasso models, you need to use cross validation (CV) on the training dataset. You should use the area under the receiver characteristic curve (AUC) as a performance measure. An example of how to do this for PC Regression can be found on UFora.

Once you have selected the optimal PCR, Ridge and Lasso models, you have to decide with what model you want to continue. For this final model you have to determine a good threshold \(c\) for the prediction cut-off, where \(c\) threshold where when a predicted probability from your final model \(p > c\), we predict kidney rejection (\(y=1\)) and non-rejection (\(y=0\)) otherwise. \(c\) should be chosen such that the misclassification error is minimal. This should be evaluated on the test data, i.e. the data not used for training the model. Also report the specificity and sensitivity of your final model and cut-off \(c\).

Hint: You can find an example function to calculate the misclassification errors for a range of cut-off values below. This should help you find an optimal value for \(c\).

## Inputs:
##   * obs: vector of test observations
##   * pred: vector of model predictions
##   * cutoff_values: vector of prediction thresholds c
calculate_misclass_error <- function(obs, pred, cutoff_values) { 
  stopifnot(lenth(obs) == length(pred))
  
  misclass_errors <- rep(NA, length(cutoff_values))
  
  for (i in seq_along(cutoff_values)) {
    cutoff <- cutoff_values[i]
    ypred <- as.numeric(pred > cutoff) # translates TRUE/FALSE to 1/0 
  
    misclass_errors[i] <- mean(ypred != obs) # proportion of misclassifications
  }
  
  data.frame(
    "cutoff" = cutoff_values,
    "misclass" = misclass_errors
  )
}

Submission

It is recommended (but not mandatory) to prepare your report in RMarkdown. You can render it to either HTML (output: html_document) or to PDF (output: pdf_document). In both cases the original .Rmd file should be included when handing in the assignment. If you don’t use RMarkdown, you should include the .R file(s) containing your implementation and analysis scripts.

When submitting, please use the following format:

  • HW-Name1-Name2-Name3-Name4.[pdf|html]

  • HW-Name1-Name2-Name3-Name4.R[md]

where Name is your family name. It’s also recommended to mention your full name in the report itself.

Submissions should be done through UFora.

The deadline for submission is 16/12/2021 at 23:59

References

Einecke, Gunilla, Jeff Reeve, Banu Sis, Michael Mengel, Luis Hidalgo, Konrad S Famulski, Arthur Matas, et al. 2010. “A Molecular Classifier for Predicting Future Graft Loss in Late Kidney Transplant Biopsies.” The Journal of Clinical Investigation 120 (6): 1862–72.

LS0tCnRpdGxlOiAiUHJvamVjdCBhc3NpZ25tZW50IgpzdWJ0aXRsZTogIkhpZ2ggRGltZW5zaW9uYWwgRGF0YSBBbmFseXNpcyAyMDIxIgphdXRob3I6ICJBZGFwdGVkIGJ5IE1pbGFuIE1hbGZhaXQiCmRhdGU6ICIxOCBOb3YgMjAyMSA8YnIvPiAoTGFzdCB1cGRhdGVkOiAyMDIxLTExLTEyKSIKb3V0cHV0OgogIGh0bWxfZG9jdW1lbnQ6CiAgICBudW1iZXJfc2VjdGlvbnM6IGZhbHNlCiAgcGRmX2RvY3VtZW50OgogICAgbnVtYmVyX3NlY3Rpb25zOiBmYWxzZQpyZWZlcmVuY2VzOgotIGlkOiBlaW5lY2tlMjAxMG1vbGVjdWxhcgogIHR5cGU6IGFydGljbGUtam91cm5hbAogIGF1dGhvcjoKICAtIGZhbWlseTogRWluZWNrZQogICAgZ2l2ZW46IEd1bmlsbGEKICAtIGZhbWlseTogUmVldmUKICAgIGdpdmVuOiBKZWZmCiAgLSBmYW1pbHk6IFNpcwogICAgZ2l2ZW46IEJhbnUKICAtIGZhbWlseTogTWVuZ2VsCiAgICBnaXZlbjogTWljaGFlbAogIC0gZmFtaWx5OiBIaWRhbGdvCiAgICBnaXZlbjogTHVpcwogIC0gZmFtaWx5OiBGYW11bHNraQogICAgZ2l2ZW46IEtvbnJhZCBTCiAgLSBmYW1pbHk6IE1hdGFzCiAgICBnaXZlbjogQXJ0aHVyCiAgLSBmYW1pbHk6IEthc2lza2UKICAgIGdpdmVuOiBCZXJ0CiAgLSBmYW1pbHk6IEthcGxhbgogICAgZ2l2ZW46IEJydWNlCiAgLSBmYW1pbHk6IEhhbGxvcmFuCiAgICBnaXZlbjogUGhpbGlwIEYKICAtIGxpdGVyYWw6IG90aGVycwogIGlzc3VlZDoKICAtIHllYXI6IDIwMTAKICB0aXRsZTogQSBtb2xlY3VsYXIgY2xhc3NpZmllciBmb3IgcHJlZGljdGluZyBmdXR1cmUgZ3JhZnQgbG9zcyBpbiBsYXRlIGtpZG5leSB0cmFuc3BsYW50CiAgICBiaW9wc2llcwogIGNvbnRhaW5lci10aXRsZTogVGhlIEpvdXJuYWwgb2YgY2xpbmljYWwgaW52ZXN0aWdhdGlvbgogIHB1Ymxpc2hlcjogQW0gU29jIENsaW4gSW52ZXN0aWcKICBwYWdlOiAxODYyLTE4NzIKICB2b2x1bWU6ICcxMjAnCiAgaXNzdWU6ICc2JwotLS0KCmBgYHtyIHNldHVwLCBpbmNsdWRlPUZBTFNFLCBjYWNoZT1GQUxTRX0Ka25pdHI6Om9wdHNfY2h1bmskc2V0KAogIGNvbGxhcHNlID0gVFJVRSwKICBjb21tZW50ID0gIiM+IgopCmBgYAoKKioqCgojIEludHJvZHVjdGlvbgoKS2lkbmV5IHRyYW5zcGxhbnRhdGlvbiBvciByZW5hbCB0cmFuc3BsYW50YXRpb24gaXMgdGhlIG9yZ2FuIHRyYW5zcGxhbnQgb2YgYQpraWRuZXkgaW50byBhIHBhdGllbnQgd2hvIGhhcyBhbiBlbmQtc3RhZ2UgcmVuYWwgZGlzZWFzZS4gU2NpZW50aXN0cyBjbGFpbSAgdGhhdApzb21lIGdlbmVzIGFyZSByZXNwb25zaWJsZSBmb3IgYSBwYXRpZW50J3MgbGlrZWxpaG9vZCBvZiByZWplY3RpbmcgYSBraWRuZXkKYWZ0ZXIgdHJhbnNwbGFudGF0aW9uLgoKSW4gdGhpcyBwcm9qZWN0LCB5b3UgYXJlIHRvIGludmVzdGlnYXRlIHRoaXMgY2xhaW0uIFlvdSB3aWxsIGFuYWx5emUgZGF0YSBmcm9tCnRoZSBzdHVkeSBieSBAZWluZWNrZTIwMTBtb2xlY3VsYXIuIFRoZSBvcmlnaW5hbCBkYXRhIGNvbnNpc3RzIG9mIG1pY3JvYXJyYXkKbWVhc3VyZW1lbnRzIGZyb20gNTQ2NzUgZ2VuZXMgYWNyb3NzIDI4MiBwYXRpZW50cy4gRm9yIHRoZSBwdXJwb3NlIG9mIHRoaXMKcHJvamVjdCwgYSByYW5kb20gc3Vic2V0IHdhcyBtYWRlIG9mIDI1MCBwYXRpZW50cyBhbmQgMTAuMDAwIGZyb20gdGhlIDI1JSBtb3N0CnZhcmlhYmxlIGdlbmVzLgoKWW91IGNhbiBhY2Nlc3MgdGhlIGRhdGEgdGhyb3VnaCB0aGUgX18qSEREQURhdGEqX18gcGFja2FnZSwgd2hpY2ggY2FuIGJlCmluc3RhbGxlZCBmcm9tIFtHaXRIdWJdKGh0dHBzOi8vZ2l0aHViLmNvbS9zdGF0T21pY3MvSEREQURhdGEpIGJ5IHJ1bm5pbmcgdGhlCmZvbGxvd2luZyBjb2RlIGluIGFuIFIgc2Vzc2lvbjoKCmBgYHtyIGluc3RhbGxhdGlvbiwgZXZhbD1GQUxTRX0KaWYgKCFyZXF1aXJlTmFtZXNwYWNlKCJyZW1vdGVzIiwgcXVpZXRseSA9IFRSVUUpKSB7CiAgICBpbnN0YWxsLnBhY2thZ2VzKCJyZW1vdGVzIikKfQpyZW1vdGVzOjppbnN0YWxsX2dpdGh1Yigic3RhdE9taWNzL0hEREFEYXRhIikKYGBgCgoqKk5vdGUqKiB0aGF0IHlvdSBuZWVkIHRvIHJ1biB0aGlzIHBpZWNlIG9mIGNvZGUgb25seSBvbmNlLiAqRG9uJ3QqIGluY2x1ZGUgaXQgaW4geW91ciBSCnNjcmlwdCwganVzdCBydW4gaXQgb25jZSBpbiBhbiBSIGNvbnNvbGUgYW5kIHlvdSdyZSBnb29kIHRvIGdvLgoKWW91IGNhbiB0aGVuIGFjY2VzcyB0aGUgZGF0YSBpbiB5b3VyIHNjcmlwdCBhcyBmb2xsb3dzOgoKYGBge3IgZ2V0LWRhdGF9CmxpYnJhcnkoSEREQURhdGEpCmRhdGEoIkVpbmVja2UyMDEwS2lkbmV5IikKCiMjIERhdGEgZGltZW5zaW9ucwpkaW0oRWluZWNrZTIwMTBLaWRuZXkpCgojIyBTaG93aW5nIGZpcnN0IDYgcm93cyBhbmQgMTAgY29sdW1ucwpoZWFkKEVpbmVja2UyMDEwS2lkbmV5WywgMToxMF0pCmBgYAoKTW9yZSBpbmZvcm1hdGlvbiBhYm91dCB0aGUgZGF0YSBhbmQgaXRzIGZvcm1hdCBjYW4gYmUgZm91bmQgaW4gdGhlCmRvY3VtZW50YXRpb24sIHNlZSBgP0VpbmVja2UyMDEwS2lkbmV5YC4KClRoZSBmaXJzdCBjb2x1bW4sIGBSZWplY3RfU3RhdHVzYCwgY29uc2lzdHMgb2YgYSBfX2JpbmFyeSB2YXJpYWJsZV9fIGVuY29kaW5nCndoZXRoZXIgdGhlIGtpZG5leSB0cmFuc3BsYW50IHdhcyBhY2NlcHRlZCAoYDBgKSBvciByZWplY3RlZCAoYDFgKSBmb3IgZWFjaApwYXRpZW50LiBUaGUgb3RoZXIgY29sdW1ucyBjb250YWluIHRoZSBtaWNyb2FycmF5IGV4cHJlc3Npb24gZGF0YSBmb3IgdGhlIDEwLjAwMApnZW5lcy4gVGhlIGByb3duYW1lc2Agb2YgdGhlIGRhdGEgZnJhbWUgY29udGFpbnMgdGhlIHBhdGllbnQgaWRlbnRpZmllcnMuCgpgYGB7ciBleHBscm9lLWRhdGF9CiMjIEV4dHJhY3QgZ2VuZSBleHByZXNzaW9uIGRhdGEgYXMgbWF0cml4IFgKWCA8LSBhcy5tYXRyaXgoRWluZWNrZTIwMTBLaWRuZXlbLCAtMV0pCmRpbShYKQpzdHIoWCkKCiMjIEV4dHJhY3QgUmVqZWN0X1N0YXR1cyBjb2x1bW4gYXMgdmVjdG9yCnJlamVjdF9zdGF0dXMgPC0gRWluZWNrZTIwMTBLaWRuZXkkUmVqZWN0X1N0YXR1cwpuYW1lcyhyZWplY3Rfc3RhdHVzKSA8LSByb3duYW1lcyhFaW5lY2tlMjAxMEtpZG5leSkKdGFibGUocmVqZWN0X3N0YXR1cykgIyBudW1iZXIgb2YgMCdzIChhY2NlcHRzKSBhbmQgMSdzIChyZWplY3RzKQpgYGAKCiMgQXNzaWdubWVudAoKX19Zb3UgbXVzdCB3b3JrIGluIGdyb3VwcyBvZiBmb3VyIHN0dWRlbnRzLl9fCgpXZSBhcmUgaW50ZXJlc3RlZCBpbiB0aGUgZm9sbG93aW5nIHJlc2VhcmNoIHF1ZXN0aW9uczoKCi0gSG93IGRvIHRoZSBnZW5lcyB2YXJ5IGluIHRlcm1zIG9mIHRoZWlyIGdlbmUgZXhwcmVzc2lvbiBsZXZlbHM/IElzIHRoZSB2YXJpYWJpbGl0eSBhc3NvY2lhdGVkIHdpdGgga2lkbmV5IHJlamVjdGlvbj8gKG9ubHkgdG8gYmUgYW5zd2VyZWQgaW4gYSBkYXRhIGV4cGxvcmF0aXZlIC8gZ3JhcGhpY2FsIG1hbm5lcikKCi0gV2hpY2ggZ2VuZXMgYXJlIGRpZmZlcmVudGlhbGx5IGV4cHJlc3NlZCBiZXR3ZWVuIHRoZSB0d28ga2lkbmV5IHJlamVjdGlvbiBncm91cHM/IFlvdSBtdXN0IGNvbnRyb2wgdGhlIEZEUiBhdCAxMCUuIAoKLSBDYW4gdGhlIGtpZG5leSByZWplY3Rpb24gIGJlIHByZWRpY3RlZCBmcm9tIHRoZSBnZW5lIGV4cHJlc3Npb24gbGV2ZWxzPyBXaGF0IGdlbmVzICBhcmUgbW9zdCBpbXBvcnRhbnQgaW4gcHJlZGljdGluZyB0aGUga2lkbmV5IHRyYW5zcGxhbnQgcmVqZWN0aW9uPyBIb3cgd2VsbCBkb2VzIHRoZSBwcmVkaWN0aW9uIG1vZGVsIHBlcmZvcm0gaW4gdGVybXMgb2YgcHJlZGljdGluZyByZWplY3Rpb24gc3RhdHVzPwoKICBOb3RlIHRoYXQgdGhlIHJlc3BvbnNlIHZhcmlhYmxlIGlzICpiaW5hcnkqLCBzbyBpZiB5b3UgdXNlIHJlZ3Jlc3Npb24gbW9kZWxzLAogIHlvdSB3aWxsIG5lZWQgdG8gdXNlICAqbG9naXN0aWMgcmVncmVzc2lvbiosIHdoaWNoIG1vZGVscyB0aGUgcmVzcG9uc2Ugd2l0aCBhCiAgYmlub21pYWwgZGlzdHJpYnV0aW9uLiBUaGlzIGNhbiBnZW5lcmFsbHkgYmUgZG9uZSBpbiBgUmAgYnkgc3BlY2lmeWluZyBgZmFtaWx5CiAgPSAiYmlub21pYWwiYCBpbiByZWdyZXNzaW9uIGZ1bmN0aW9ucyBzdWNoIGFzIGBnbG1gIGFuZCBgZ2xtbmV0YC4KCgpXcml0ZSBhIHNjaWVudGlmaWMgcmVwb3J0IHRoYXQgYW5zd2VycyB0aGUgcmVzZWFyY2ggcXVlc3Rpb25zIHJlbGF0ZWQgdG8gdGhpcyBzdHVkeS4KVGhlIHJlcG9ydCBtdXN0IGNvbnNpc3Qgb2YgdHdvIHBhcnRzOgoKLSBBbiBleGVjdXRpdmUgc3VtbWFyeSBvZiBhYm91dCBoYWxmIGEgcGFnZS4gVGhpcyBzdW1tYXJ5IGNvbnRhaW5zIHRoZSBhbnN3ZXJzIHRvIHRoZSBvcmlnaW5hbCByZXNlYXJjaCBxdWVzdGlvbnMsIGFuZCBzaG91bGQgYmUgd3JpdHRlbiBpbiBhIG5vbi10ZWNobmljYWwgbWFubmVyIChpdCBpcyBtZWFudCBmb3IgcmVzZWFyY2hlcnMgd2l0aG91dCBhIHN0YXRpc3RpY2FsIGJhY2tncm91bmQpLgogCi0gQSB0ZWNobmljYWwgcmVwb3J0IHRoYXQgZXhwbGFpbnMgaW4gZGV0YWlsIGhvdyB0aGUgcmVzdWx0cyB3ZXJlIG9idGFpbmVkLiBUaGUKcmVhZGVyIHNob3VsZCB1bmRlcnN0YW5kIHdoYXQgeW91IGRpZCB3aXRob3V0IGxvb2tpbmcgYXQgdGhlIGNvZGUhCgpJdCdzIHJlY29tbWVuZGVkIHRvIHByZXBhcmUgdGhlIHJlcG9ydCBhcyBhbiBfX1JNYXJrZG93bl9fIGZpbGUuIElmIHlvdSBjaG9vc2UKdG8gdXNlIGFub3RoZXIgZm9ybWF0LCB0aGVuIHRoZSBSIGNvZGUgc2hvdWxkIGJlIHN1Ym1pdHRlZCBhcyBhIHNlcGFyYXRlIGZpbGUKKHBsZWFzZSBwcm9wZXJseSBjb21tZW50IHlvdXIgUiBjb2RlKS4KClRoZSByZXBvcnQgaXMgZXhwZWN0ZWQgdG8gYmUgY29uY2lzZSwgYnV0IG11c3QgZXZpZGVudGx5IGJlIGFjY3VyYXRlIGFuZApzdWZmaWNpZW50bHkgZGV0YWlsZWQgdG8gZW5hYmxlIHRoZSByZWFkZXIgdG8gdmVyaWZ5IHRoZSBjb3JyZWN0bmVzcyBvZiB0aGUKcmVzdWx0IChpLmUuIHlvdXIgcmVzdWx0cyBtdXN0IGJlIHJlcHJvZHVjaWJsZSkuIFRoZSB0b3RhbCBsZW5ndGggb2YgdGhlIHJlcG9ydAooZXhjbHVkaW5nIGdyYXBocywgUiBjb2RlIGFuZCBwb3NzaWJseSBhcHBlbmRpY2VzKSBzaG91bGQgbm90IGJlIG1vcmUgdGhhbiB0aHJlZQpwYWdlcy4gVGhlIHJlcG9ydCBzaG91bGQgbm90IGNvbnRhaW4gYW4gZXhwbGFuYXRpb24gb2YgdGhlIHRoZW9yeSBiZWhpbmQgdGhlCnN0YXRpc3RpY2FsIG1ldGhvZHMsIGFuZCBzaG91bGQgYWxzbyBub3QgY29udGFpbiB0aGUgc3R1ZHkgZGVzY3JpcHRpb24gZ2l2ZW4KYWJvdmUgKHlvdSBjYW4gYXNzdW1lIHRoYXQgdGhlIHJlYWRlciBhbHJlYWR5IGtub3dzIHRoaXMpLgoKX18qSW50ZXJwcmV0YXRpb24qIG9mIHRoZSByZXN1bHRzIGlzIGtleSFfXwoKU29tZSBtb3JlIHNwZWNpZmljIGd1aWRlbGluZXM6CgotIEZvciB0aGUgZmlyc3QgcmVzZWFyY2ggcXVlc3Rpb24sIHlvdSBtYXkgdXNlIG9uZSBvZiB0aGUgZGF0YSBleHBsb3JhdGlvbiB0b29scwp0aGF0IHdlIGhhdmUgc2VlbiBpbiBjbGFzcy4gSG93ZXZlciwgeW91IGFyZSBhbHNvIGZyZWUgdG8gc2VhcmNoIHRoZSBsaXRlcmF0dXJlCmZvciBvdGhlciB0ZWNobmlxdWVzIGZvciBkYXRhIGV4cGxvcmF0aW9uIGFuZCB2aXN1YWxpc2F0aW9uICh5b3VyIGZpbmFsIG1hcmsKd2lsbCBub3QgZGVwZW5kIG9uIHdoZXRoZXIgeW91IHNlYXJjaGVkIHRoZSBsaXRlcmF0dXJlIG9yIG5vdCkuIFlvdSBhcmUgb25seQphc2tlZCB0byAqZXhwbG9yZSogd2hldGhlciB0aGUgdmFyaWFiaWxpdHkgaW4gZ2VuZSBleHByZXNzaW9uIGxldmVscyBpcwphc3NvY2lhdGVkIHdpdGggcmVqZWN0aW9uIHN0YXR1czsgbm8gbmVlZCBmb3IgaHlwb3RoZXNpcyB0ZXN0aW5nLgogCi0gRm9yIHRoZSBzZWNvbmQgcmVzZWFyY2ggcXVlc3Rpb24sIHlvdSBzaG91bGQgcGVyZm9ybSBoeXBvdGhlc2lzIHRlc3RpbmcgYW5kCmNvcnJlY3QgZm9yIG11bHRpcGxlIHRlc3Rpbmcgc28gYXMgdG8gY29udHJvbCB0aGUgRkRSIGF0IDEwJS4gVGhlIGZ1bGwgbGlzdCB3aXRoCmRpZmZlcmVudGlhbGx5IGV4cHJlc3NlZCBnZW5lcyBtYXkgYmUgcHJlc2VudGVkIGluIGFuIGFwcGVuZGl4LiBPbmx5IGxpc3QgdGhlCm1vc3QgaW1wb3J0YW50IHJlc3VsdHMgaW4gdGhlIGJvZHkgb2YgdGhlIHJlcG9ydC4KIAotIEZvciB0aGUgdGhpcmQgcmVzZWFyY2ggcXVlc3Rpb24geW91IGFyZSBhc2tlZCB0byBwcmVkaWN0IHJlamVjdGlvbiBzdGF0dXMKdXNpbmcgZ2VuZSBleHByZXNzaW9uIGxldmVscy4gWW91IHNob3VsZCByYW5kb21seSBzcGxpdCB0aGUgZGF0YSBpbnRvIGEgdGVzdAooMzAlKSBhbmQgYSB0cmFpbmluZyAoNzAlKSBkYXRhc2V0LiBNYWtlIHN1cmUgeW91IHVzZSBhIHNlZWQgKGBzZXQuc2VlZCgpYApmdW5jdGlvbikgaW4gUiBmb3IgcmVwcm9kdWNpYmlsaXR5LiBUaGUgZm9sbG93aW5nIHByZWRpY3Rpb24gbW9kZWxzIHNob3VsZCBiZQpldmFsdWF0ZWQ6CiAgCiAgKiBQcmluY2lwYWwgQ29tcG9uZW50IFJlZ3Jlc3Npb24gKFBDUikKICAgIAogICogUmlkZ2UgUmVncmVzc2lvbgoKICAqIExhc3NvIHJlZ3Jlc3Npb24KICAKKipOb3RlKiogdGhhdCB0aGUgcmVzcG9uc2UgdmFyaWFibGUgKHRoZSByZWplY3Rpb24gc3RhdHVzKSBpcyAqYmluYXJ5Kiwgc28geW91CndpbGwgaGF2ZSB0byB1c2UgKipsb2dpc3RpYyByZWdyZXNzaW9uKiohCgpJbiBjaG9vc2luZyB0aGUgbnVtYmVyIG9mIFBDcyAgaW4gUENSLCBhbmQgdGhlICRcZ2FtbWEkIGluIHRoZSBSaWRnZSAgYW5kIExhc3NvCm1vZGVscywgeW91IG5lZWQgdG8gdXNlIGNyb3NzIHZhbGlkYXRpb24gKENWKSBvbiB0aGUgdHJhaW5pbmcgZGF0YXNldC4gWW91CnNob3VsZCB1c2UgdGhlIF9fYXJlYSB1bmRlciB0aGUgcmVjZWl2ZXIgY2hhcmFjdGVyaXN0aWMgY3VydmUgKEFVQylfXyBhcyBhCnBlcmZvcm1hbmNlIG1lYXN1cmUuIEFuIGV4YW1wbGUgb2YgaG93IHRvIGRvIHRoaXMgZm9yIFBDIFJlZ3Jlc3Npb24gY2FuIGJlIGZvdW5kCm9uIFtVRm9yYV0oaHR0cHM6Ly91Zm9yYS51Z2VudC5iZS9kMmwvbGUvY29udGVudC80NDQyMjYvdmlld0NvbnRlbnQvMTExNjUzNi9WaWV3KS4KCk9uY2UgeW91IGhhdmUgc2VsZWN0ZWQgdGhlIG9wdGltYWwgUENSLCBSaWRnZSBhbmQgTGFzc28gbW9kZWxzLCB5b3UgaGF2ZSB0bwpkZWNpZGUgd2l0aCB3aGF0IG1vZGVsIHlvdSB3YW50IHRvIGNvbnRpbnVlLiBGb3IgdGhpcyBmaW5hbCBtb2RlbCB5b3UgaGF2ZSB0bwpkZXRlcm1pbmUgYSBnb29kIHRocmVzaG9sZCAkYyQgZm9yIHRoZSBwcmVkaWN0aW9uIGN1dC1vZmYsIHdoZXJlICRjJCB0aHJlc2hvbGQKd2hlcmUgd2hlbiBhIHByZWRpY3RlZCBwcm9iYWJpbGl0eSBmcm9tIHlvdXIgZmluYWwgbW9kZWwgJHAgPiBjJCwgd2UgcHJlZGljdApraWRuZXkgcmVqZWN0aW9uICgkeT0xJCkgYW5kIG5vbi1yZWplY3Rpb24gKCR5PTAkKSBvdGhlcndpc2UuICRjJCBzaG91bGQgYmUKY2hvc2VuIHN1Y2ggdGhhdCB0aGUgKm1pc2NsYXNzaWZpY2F0aW9uIGVycm9yKiBpcyBtaW5pbWFsLiBUaGlzIHNob3VsZCBiZQpldmFsdWF0ZWQgb24gdGhlICp0ZXN0IGRhdGEqLCBpLmUuIHRoZSBkYXRhIG5vdCB1c2VkIGZvciB0cmFpbmluZyB0aGUgbW9kZWwuCkFsc28gcmVwb3J0IHRoZSAqc3BlY2lmaWNpdHkqIGFuZCAqc2Vuc2l0aXZpdHkqIG9mIHlvdXIgZmluYWwgbW9kZWwgYW5kIGN1dC1vZmYKJGMkLgoKKipIaW50Kio6IFlvdSBjYW4gZmluZCBhbiBleGFtcGxlIGZ1bmN0aW9uIHRvIGNhbGN1bGF0ZSB0aGUgbWlzY2xhc3NpZmljYXRpb24KZXJyb3JzIGZvciBhIHJhbmdlIG9mIGN1dC1vZmYgdmFsdWVzIGJlbG93LiBUaGlzIHNob3VsZCBoZWxwIHlvdSBmaW5kIGFuIG9wdGltYWwKdmFsdWUgZm9yICRjJC4KCmBgYHtyLCBldmFsPUZBTFNFfQojIyBJbnB1dHM6CiMjICAgKiBvYnM6IHZlY3RvciBvZiB0ZXN0IG9ic2VydmF0aW9ucwojIyAgICogcHJlZDogdmVjdG9yIG9mIG1vZGVsIHByZWRpY3Rpb25zCiMjICAgKiBjdXRvZmZfdmFsdWVzOiB2ZWN0b3Igb2YgcHJlZGljdGlvbiB0aHJlc2hvbGRzIGMKY2FsY3VsYXRlX21pc2NsYXNzX2Vycm9yIDwtIGZ1bmN0aW9uKG9icywgcHJlZCwgY3V0b2ZmX3ZhbHVlcykgeyAKICBzdG9waWZub3QobGVudGgob2JzKSA9PSBsZW5ndGgocHJlZCkpCiAgCiAgbWlzY2xhc3NfZXJyb3JzIDwtIHJlcChOQSwgbGVuZ3RoKGN1dG9mZl92YWx1ZXMpKQogIAogIGZvciAoaSBpbiBzZXFfYWxvbmcoY3V0b2ZmX3ZhbHVlcykpIHsKICAgIGN1dG9mZiA8LSBjdXRvZmZfdmFsdWVzW2ldCiAgICB5cHJlZCA8LSBhcy5udW1lcmljKHByZWQgPiBjdXRvZmYpICMgdHJhbnNsYXRlcyBUUlVFL0ZBTFNFIHRvIDEvMCAKICAKICAgIG1pc2NsYXNzX2Vycm9yc1tpXSA8LSBtZWFuKHlwcmVkICE9IG9icykgIyBwcm9wb3J0aW9uIG9mIG1pc2NsYXNzaWZpY2F0aW9ucwogIH0KICAKICBkYXRhLmZyYW1lKAogICAgImN1dG9mZiIgPSBjdXRvZmZfdmFsdWVzLAogICAgIm1pc2NsYXNzIiA9IG1pc2NsYXNzX2Vycm9ycwogICkKfQpgYGAKCgojIFN1Ym1pc3Npb24KCkl0IGlzIHJlY29tbWVuZGVkIChidXQgbm90IG1hbmRhdG9yeSkgdG8gcHJlcGFyZSB5b3VyIHJlcG9ydCBpbiBfX1JNYXJrZG93bl9fLgpZb3UgY2FuIHJlbmRlciBpdCB0byBlaXRoZXIgSFRNTCAoYG91dHB1dDogaHRtbF9kb2N1bWVudGApIG9yIHRvIFBERiAoYG91dHB1dDogcGRmX2RvY3VtZW50YCkuCkluIGJvdGggY2FzZXMgdGhlIG9yaWdpbmFsIGAuUm1kYCBmaWxlIHNob3VsZCBiZSBpbmNsdWRlZCB3aGVuIGhhbmRpbmcgaW4gdGhlIGFzc2lnbm1lbnQuCklmIHlvdSBkb24ndCB1c2UgUk1hcmtkb3duLCB5b3Ugc2hvdWxkIGluY2x1ZGUgdGhlIGAuUmAgZmlsZShzKSBjb250YWluaW5nIHlvdXIgaW1wbGVtZW50YXRpb24gYW5kIGFuYWx5c2lzIHNjcmlwdHMuCgpXaGVuIHN1Ym1pdHRpbmcsIHBsZWFzZSB1c2UgdGhlIGZvbGxvd2luZyBmb3JtYXQ6CgoqIEhXLU5hbWUxLU5hbWUyLU5hbWUzLU5hbWU0LltwZGZ8aHRtbF0KCiogSFctTmFtZTEtTmFtZTItTmFtZTMtTmFtZTQuUlttZF0KCndoZXJlIGBOYW1lYCBpcyB5b3VyIF9fZmFtaWx5IG5hbWVfXy4KSXQncyBhbHNvIHJlY29tbWVuZGVkIHRvIG1lbnRpb24geW91ciBmdWxsIG5hbWUgaW4gdGhlIHJlcG9ydCBpdHNlbGYuCgpfX1N1Ym1pc3Npb25zIHNob3VsZCBiZSBkb25lIHRocm91Z2ggW1VGb3JhXShodHRwczovL3Vmb3JhLnVnZW50LmJlL2QybC9ob21lLzQ0NDIyNilfXy4KCjxzcGFuIHN0eWxlPSJjb2xvcjpyZWQiPl9fVGhlIGRlYWRsaW5lIGZvciBzdWJtaXNzaW9uIGlzIDE2LzEyLzIwMjEgYXQgMjM6NTlfXzwvc3Bhbj4KCgoKIyBSZWZlcmVuY2VzIHstfQo=