1 Feature selection

suppressMessages(library(ggplot2))
suppressMessages(library(scater))
suppressMessages(library(scran))
projDir <- "/mnt/scratcha/bioinformatics/baller01/20200511_FernandesM_ME_crukBiSs2020"
outDirBit <- "AnaWiSce/Attempt1"
fontsize <- theme(axis.text=element_text(size=12), axis.title=element_text(size=16))

1.1 Load data

We will load the R file keeping the SCE object with the normalised counts for 500 cells per sample.

setName <- "caron"
setSuf <- "_5hCellPerSpl"

# Read object in:
tmpFn <- sprintf("%s/%s/Robjects/%s_sce_nz_postDeconv%s_dimRed.Rds", projDir, outDirBit, setName, setSuf)
print(tmpFn)
[1] "/mnt/scratcha/bioinformatics/baller01/20200511_FernandesM_ME_crukBiSs2020/AnaWiSce/Attempt1/Robjects/caron_sce_nz_postDeconv_5hCellPerSpl_dimRed.Rds"
if(!file.exists(tmpFn))
{
    knitr::knit_exit()
}
sce <- readRDS(tmpFn)
sce
class: SingleCellExperiment 
dim: 18372 5500 
metadata(0):
assays(2): counts logcounts
rownames(18372): ENSG00000238009 ENSG00000237491 ... ENSG00000275063
  ENSG00000271254
rowData names(11): ensembl_gene_id external_gene_name ... detected
  gene_sparsity
colnames: NULL
colData names(20): Sample Barcode ... cell_sparsity sizeFactor
reducedDimNames(3): PCA TSNE UMAP
altExpNames(0):
head(rowData(sce))
DataFrame with 6 rows and 11 columns
                ensembl_gene_id external_gene_name chromosome_name
                    <character>        <character>     <character>
ENSG00000238009 ENSG00000238009         AL627309.1               1
ENSG00000237491 ENSG00000237491          LINC01409               1
ENSG00000225880 ENSG00000225880          LINC00115               1
ENSG00000230368 ENSG00000230368             FAM41C               1
ENSG00000230699 ENSG00000230699         AL645608.2               1
ENSG00000188976 ENSG00000188976              NOC2L               1
                start_position end_position strandNum      Symbol
                     <integer>    <integer> <integer> <character>
ENSG00000238009          89295       133723        -1  AL627309.1
ENSG00000237491         778747       810065         1  AL669831.5
ENSG00000225880         826206       827522        -1   LINC00115
ENSG00000230368         868071       876903        -1      FAM41C
ENSG00000230699         911435       914948         1  AL645608.3
ENSG00000188976         944203       959309        -1       NOC2L
                           Type        mean   detected gene_sparsity
                    <character>   <numeric>  <numeric>     <numeric>
ENSG00000238009 Gene Expression 0.000815739  0.0815739      0.999256
ENSG00000237491 Gene Expression 0.033200190  3.1966535      0.979330
ENSG00000225880 Gene Expression 0.013530022  1.3200511      0.985855
ENSG00000230368 Gene Expression 0.019421026  1.8757987      0.981826
ENSG00000230699 Gene Expression 0.000642947  0.0638929      0.998270
ENSG00000188976 Gene Expression 0.168154822 13.2828888      0.831308
#any(duplicated(rowData(sce)$ensembl_gene_id))
# some function(s) used below complain about 'strand' already being used in row data,
# so rename that column now:
colnames(rowData(sce))[colnames(rowData(sce)) == "strand"] <- "strandNum"

1.2 Feature selection with scran

scRNASeq measures the expression of thousands of genes in each cell. The biological question asked in a study will most often relate to a fraction of these genes only, linked for example to differences between cell types, drivers of differentiation, or response to perturbation.

Most high-throughput molecular data include variation created by the assay itself, not biology, i.e. technical noise, for example caused by sampling during RNA capture and library preparation. In scRNASeq, this technical noise will result in most genes being detected at different levels. This noise may hinder the detection of the biological signal.

Let’s identify Highly Variables Genes (HVGs) with the aim to find those underlying the heterogeneity observed across cells.

1.2.1 Modelling and removing technical noise

Some assays allow the inclusion of known molecules in a known amount covering a wide range, from low to high abundance: spike-ins. The technical noise is assessed based on the amount of spike-ins used, the corresponding read counts obtained and their variation across cells. The variance in expression can then be decomposed into the biolgical and technical components.

UMI-based assays do not (yet?) allow spike-ins. But one can still identify HVGs, that is genes with the highest biological component. Assuming that expression does not vary across cells for most genes, the total variance for these genes mainly reflects technical noise. The latter can thus be assessed by fitting a trend to the variance in expression. The fitted value will be the estimate of the technical component.

Let’s fit a trend to the variance, using modelGeneVar().

dec.sce <- modelGeneVar(sce)

Let’s plot variance against mean of expression (log scale) and the mean-dependent trend fitted to the variance:

# Visualizing the fit:
var.fit <- metadata(dec.sce)
plot(var.fit$mean, var.fit$var, xlab="Mean of log-expression",
    ylab="Variance of log-expression")
curve(var.fit$trend(x), col="dodgerblue", add=TRUE, lwd=2)

In the absence of spike-in data, one can attempt to create a trend by making some distributional assumptions about the noise. For example, UMI counts typically exhibit near-Poisson variation if we only consider technical noise from library preparation and sequencing. This can be used to construct a mean-variance trend in the log-counts with the modelGeneVarByPoisson() function. Note the increased residuals of the high-abundance genes, which can be interpreted as the amount of biological variation that was assumed to be “uninteresting” when fitting the gene-based trend above.

set.seed(0010101)
dec.pois.sce <- modelGeneVarByPoisson(sce)
dec.pois.sce <- dec.pois.sce[order(dec.pois.sce$bio, decreasing=TRUE),]
head(dec.pois.sce)
DataFrame with 6 rows and 6 columns
                     mean     total      tech       bio   p.value       FDR
                <numeric> <numeric> <numeric> <numeric> <numeric> <numeric>
ENSG00000244734  2.487368  11.39855  0.913036  10.48551         0         0
ENSG00000188536  1.848790   9.16065  1.020994   8.13966         0         0
ENSG00000206172  1.585734   8.27191  1.007091   7.26482         0         0
ENSG00000019582  2.929866   4.40937  0.781826   3.62755         0         0
ENSG00000223609  0.770139   4.24159  0.691198   3.55040         0         0
ENSG00000204287  2.404310   3.75521  0.934058   2.82115         0         0

Plot:

plot(dec.pois.sce$mean, dec.pois.sce$total, pch=16, xlab="Mean of log-expression",
    ylab="Variance of log-expression")
curve(metadata(dec.pois.sce)$trend(x), col="dodgerblue", add=TRUE)

Interestingly, trends based purely on technical noise tend to yield large biological components for highly-expressed genes. This often includes so-called “house-keeping” genes coding for essential cellular components such as ribosomal proteins, which are considered uninteresting for characterizing cellular heterogeneity. These observations suggest that a more accurate noise model does not necessarily yield a better ranking of HVGs, though one should keep an open mind - house-keeping genes are regularly DE in a variety of conditions (Glare et al. 2002; Nazari, Parham, and Maleki 2015; Guimaraes and Zavolan 2016), and the fact that they have large biological components indicates that there is strong variation across cells that may not be completely irrelevant.

1.2.2 Choosing some HVGs:

Identify the top 20 HVGs by sorting genes in decreasing order of biological component.

# order genes by decreasing order of biological component
o <- order(dec.sce$bio, decreasing=TRUE)
# check top and bottom of sorted table
head(dec.sce[o,])
DataFrame with 6 rows and 6 columns
                     mean     total      tech       bio      p.value
                <numeric> <numeric> <numeric> <numeric>    <numeric>
ENSG00000244734  2.487368  11.39855  1.463827   9.93472  0.00000e+00
ENSG00000188536  1.848790   9.16065  1.362805   7.79785  0.00000e+00
ENSG00000206172  1.585734   8.27191  1.280827   6.99108 2.64879e-304
ENSG00000223609  0.770139   4.24159  0.787929   3.45367 4.21240e-197
ENSG00000019582  2.929866   4.40937  1.404771   3.00460  1.32522e-48
ENSG00000206177  0.572339   3.18102  0.616104   2.56491 4.89490e-178
                         FDR
                   <numeric>
ENSG00000244734  0.00000e+00
ENSG00000188536  0.00000e+00
ENSG00000206172 1.61691e-300
ENSG00000223609 1.92854e-193
ENSG00000019582  7.35416e-46
ENSG00000206177 1.49401e-174
tail(dec.sce[o,])
DataFrame with 6 rows and 6 columns
                     mean     total      tech       bio   p.value       FDR
                <numeric> <numeric> <numeric> <numeric> <numeric> <numeric>
ENSG00000232112   1.74745  1.047294   1.33227 -0.284978  0.927926         1
ENSG00000115268   3.91154  0.978745   1.26887 -0.290126  0.940762         1
ENSG00000140264   2.21495  1.128841   1.45721 -0.328371  0.938052         1
ENSG00000173812   3.13508  1.033705   1.37027 -0.336568  0.953237         1
ENSG00000174748   3.90858  0.924135   1.26938 -0.345243  0.968348         1
ENSG00000149806   2.95350  1.007274   1.40060 -0.393324  0.972410         1
# choose the top 20 genes with the highest biological component
chosen.genes.index <- o[1:20]

Show the top 20 HVGs on the plot displaying the variance against the mean expression:

plot(var.fit$mean, var.fit$var)
curve(var.fit$trend(x), col="red", lwd=2, add=TRUE)
points(var.fit$mean[chosen.genes.index], var.fit$var[chosen.genes.index], col="orange")

Rather than choosing a fixed number of top genes, one may define ‘HVGs’ as genes with a positive biological component, ie whose variance is higher than the fitted value for the corresponding mean expression.

Select and show these ‘HVGs’ on the plot displaying the variance against the mean expression:

hvgBool <- dec.sce$bio > 0
table(hvgBool)
hvgBool
FALSE  TRUE 
 8406  9966 
hvg.index <- which(hvgBool)
plot(var.fit$mean, var.fit$var)
curve(var.fit$trend(x), col="red", lwd=2, add=TRUE)
points(var.fit$mean[hvg.index], var.fit$var[hvg.index], col="orange")

Save objects to file

tmpFn <- sprintf("%s/%s/Robjects/%s_sce_nz_postDeconv%s_featSel.Rds", projDir, outDirBit, setName, setSuf)
saveRDS(list("dec.sce"=dec.sce,"hvg.index"=hvg.index), tmpFn)

HVGs may be driven by outlier cells. So let’s plot the distribution of expression values for the genes with the largest biological components.

First, get gene names to replace ensembl IDs on plot.

# the count matrix rows are named with ensembl gene IDs. Let's label gene with their name instead:
# row indices of genes in rowData(sce)
tmpInd <- which(rowData(sce)$ensembl_gene_id %in% rownames(dec.sce)[chosen.genes.index])
# check:
rowData(sce)[tmpInd,c("ensembl_gene_id","external_gene_name")]
DataFrame with 20 rows and 2 columns
                ensembl_gene_id external_gene_name
                    <character>        <character>
ENSG00000163220 ENSG00000163220             S100A9
ENSG00000143546 ENSG00000143546             S100A8
ENSG00000211592 ENSG00000211592               IGKC
ENSG00000170180 ENSG00000170180               GYPA
ENSG00000019582 ENSG00000019582               CD74
...                         ...                ...
ENSG00000206177 ENSG00000206177                HBM
ENSG00000188536 ENSG00000188536               HBA2
ENSG00000206172 ENSG00000206172               HBA1
ENSG00000169877 ENSG00000169877               AHSP
ENSG00000090013 ENSG00000090013              BLVRB
# store names:
tmpName <- rowData(sce)[tmpInd,"external_gene_name"]
# the gene name may not be known, so keep the ensembl gene ID in that case:
tmpName[tmpName==""] <- rowData(sce)[tmpInd,"ensembl_gene_id"][tmpName==""]
tmpName[is.na(tmpName)] <- rowData(sce)[tmpInd,"ensembl_gene_id"][is.na(tmpName)]
rm(tmpInd)

Now show a violin plot for each gene, using plotExpression() and label genes with their name:

g <- plotExpression(sce, rownames(dec.sce)[chosen.genes.index], 
    point_alpha=0.05, jitter="jitter") + fontsize
g <- g + scale_x_discrete(breaks=rownames(dec.sce)[chosen.genes.index],
        labels=tmpName)
g

Another few genes:

chosen.genes.index <- o[21:40]

tmpInd <- which(rowData(sce)$ensembl_gene_id %in% rownames(dec.sce)[chosen.genes.index])
# check:
rowData(sce)[tmpInd,c("ensembl_gene_id","external_gene_name")]
DataFrame with 20 rows and 2 columns
                ensembl_gene_id external_gene_name
                    <character>        <character>
ENSG00000117632 ENSG00000117632              STMN1
ENSG00000177606 ENSG00000177606                JUN
ENSG00000196154 ENSG00000196154             S100A4
ENSG00000145335 ENSG00000145335               SNCA
ENSG00000250361 ENSG00000250361               GYPB
...                         ...                ...
ENSG00000013306 ENSG00000013306           SLC25A39
ENSG00000007312 ENSG00000007312              CD79B
ENSG00000171223 ENSG00000171223               JUNB
ENSG00000167815 ENSG00000167815              PRDX2
ENSG00000169575 ENSG00000169575             VPREB1
# store names:
tmpName <- rowData(sce)[tmpInd,"external_gene_name"]
# the gene name may not be known, so keep the ensembl gene ID in that case:
tmpName[tmpName==""] <- rowData(sce)[tmpInd,"ensembl_gene_id"][tmpName==""]
tmpName[is.na(tmpName)] <- rowData(sce)[tmpInd,"ensembl_gene_id"][is.na(tmpName)]
rm(tmpInd)

g <- plotExpression(sce, rownames(dec.sce)[chosen.genes.index], 
    point_alpha=0.05, jitter="jitter") + fontsize
g <- g + scale_x_discrete(breaks=rownames(dec.sce)[chosen.genes.index],
        labels=tmpName)
g

Challenge: Show violin plots for the 20 genes with the lowest biological component. How do they compare to the those for HVGs chosen above?

chosen.genes.index.tmp <- order(dec.sce$bio, decreasing=FALSE)[1:20]
tmpInd <- (which(rowData(sce)$ensembl_gene_id %in% rownames(dec.sce)[chosen.genes.index.tmp]))
# check:
rowData(sce)[tmpInd,c("ensembl_gene_id","external_gene_name")]
DataFrame with 20 rows and 2 columns
                ensembl_gene_id external_gene_name
                    <character>        <character>
ENSG00000142676 ENSG00000142676              RPL11
ENSG00000174748 ENSG00000174748              RPL15
ENSG00000232112 ENSG00000232112               TMA7
ENSG00000104529 ENSG00000104529              EEF1D
ENSG00000161016 ENSG00000161016               RPL8
...                         ...                ...
ENSG00000105640 ENSG00000105640             RPL18A
ENSG00000221983 ENSG00000221983              UBA52
ENSG00000063177 ENSG00000063177              RPL18
ENSG00000142534 ENSG00000142534              RPS11
ENSG00000170889 ENSG00000170889               RPS9
# store names:
tmpName <- rowData(sce)[tmpInd,"external_gene_name"]
# the gene name may not be known, so keep the ensembl gene ID in that case:
tmpName[tmpName==""] <- rowData(sce)[tmpInd,"ensembl_gene_id"][tmpName==""]
tmpName[is.na(tmpName)] <- rowData(sce)[tmpInd,"ensembl_gene_id"][is.na(tmpName)]
rm(tmpInd)
g <- plotExpression(sce, rownames(dec.sce)[chosen.genes.index.tmp], 
            point_alpha=0.05, jitter="jitter") + fontsize
g <- g + scale_x_discrete(breaks=rownames(dec.sce)[chosen.genes.index.tmp],
        labels=tmpName)
g

rm(chosen.genes.index.tmp)
LS0tCnRpdGxlOiAiQ1JVSyBDSSBTdW1tZXIgU2Nob29sIDIwMjAgLSBpbnRyb2R1Y3Rpb24gdG8gc2luZ2xlLWNlbGwgUk5BLXNlcSBhbmFseXNpcyIKc3VidGl0bGU6ICdGZWF0dXJlIHNlbGVjdGlvbicKCmF1dGhvcjogIlN0ZXBoYW5lIEJhbGxlcmVhdSwgWmV5bmVwIEthbGVuZGVyIEF0YWssIEthdGFyenluYSBLYW5pYSIKI2RhdGU6ICdgciBzdHJmdGltZShTeXMudGltZSgpLCBmb3JtYXQgPSAiJUIgJWQsICVZIilgJwpkYXRlOiBKdWx5IDIwMjAKI2JpYmxpb2dyYXBoeTogYmlibGlvZ3JhcGh5LmJpYgojY3NsOiBiaW9tZWQtY2VudHJhbC5jc2wKb3V0cHV0OgogIGh0bWxfbm90ZWJvb2s6CiAgICBudW1iZXJfc2VjdGlvbnM6IHllcwogICAgdG9jOiB5ZXMKICAgIHRvY19mbG9hdDogeWVzCiAgICBmaWdfY2FwdGlvbjogeWVzCiAgICBzZWxmX2NvbnRhaW5lZDogdHJ1ZQogICAgZmlnX3dpZHRoOiA2CiAgICBmaWdfaGVpZ2h0OiA0Ci0tLQoKIyBGZWF0dXJlIHNlbGVjdGlvbgoKYGBge3IsIHdhcm5pbmc9RkFMU0V9CnN1cHByZXNzTWVzc2FnZXMobGlicmFyeShnZ3Bsb3QyKSkKc3VwcHJlc3NNZXNzYWdlcyhsaWJyYXJ5KHNjYXRlcikpCnN1cHByZXNzTWVzc2FnZXMobGlicmFyeShzY3JhbikpCmBgYAoKYGBge3J9CnByb2pEaXIgPC0gIi9tbnQvc2NyYXRjaGEvYmlvaW5mb3JtYXRpY3MvYmFsbGVyMDEvMjAyMDA1MTFfRmVybmFuZGVzTV9NRV9jcnVrQmlTczIwMjAiCm91dERpckJpdCA8LSAiQW5hV2lTY2UvQXR0ZW1wdDEiCmZvbnRzaXplIDwtIHRoZW1lKGF4aXMudGV4dD1lbGVtZW50X3RleHQoc2l6ZT0xMiksIGF4aXMudGl0bGU9ZWxlbWVudF90ZXh0KHNpemU9MTYpKQpgYGAKCmBgYHtyIHNldHVwLCBpbmNsdWRlPUZBTFNFLCBlY2hvPUZBTFNFfQojIEZpcnN0LCBzZXQgc29tZSB2YXJpYWJsZXM6CmtuaXRyOjpvcHRzX2NodW5rJHNldChlY2hvID0gVFJVRSkKb3B0aW9ucyhzdHJpbmdzQXNGYWN0b3JzID0gRkFMU0UpCnNldC5zZWVkKDEyMykgIyBmb3IgcmVwcm9kdWNpYmlsaXR5CmtuaXRyOjpvcHRzX2NodW5rJHNldChldmFsID0gVFJVRSkgCmBgYAoKIyMgTG9hZCBkYXRhCgpXZSB3aWxsIGxvYWQgdGhlIFIgZmlsZSBrZWVwaW5nIHRoZSBTQ0Ugb2JqZWN0IHdpdGggdGhlIG5vcm1hbGlzZWQgY291bnRzIGZvciA1MDAgY2VsbHMgcGVyIHNhbXBsZS4KCmBgYHtyfQpzZXROYW1lIDwtICJjYXJvbiIKc2V0U3VmIDwtICJfNWhDZWxsUGVyU3BsIgoKIyBSZWFkIG9iamVjdCBpbjoKdG1wRm4gPC0gc3ByaW50ZigiJXMvJXMvUm9iamVjdHMvJXNfc2NlX256X3Bvc3REZWNvbnYlc19kaW1SZWQuUmRzIiwgcHJvakRpciwgb3V0RGlyQml0LCBzZXROYW1lLCBzZXRTdWYpCnByaW50KHRtcEZuKQppZighZmlsZS5leGlzdHModG1wRm4pKQp7Cglrbml0cjo6a25pdF9leGl0KCkKfQpzY2UgPC0gcmVhZFJEUyh0bXBGbikKc2NlCgpoZWFkKHJvd0RhdGEoc2NlKSkKCiNhbnkoZHVwbGljYXRlZChyb3dEYXRhKHNjZSkkZW5zZW1ibF9nZW5lX2lkKSkKIyBzb21lIGZ1bmN0aW9uKHMpIHVzZWQgYmVsb3cgY29tcGxhaW4gYWJvdXQgJ3N0cmFuZCcgYWxyZWFkeSBiZWluZyB1c2VkIGluIHJvdyBkYXRhLAojIHNvIHJlbmFtZSB0aGF0IGNvbHVtbiBub3c6CmNvbG5hbWVzKHJvd0RhdGEoc2NlKSlbY29sbmFtZXMocm93RGF0YShzY2UpKSA9PSAic3RyYW5kIl0gPC0gInN0cmFuZE51bSIKYXNzYXlOYW1lcyhzY2UpCmBgYAoKIyMgRmVhdHVyZSBzZWxlY3Rpb24gd2l0aCBzY3JhbgoKc2NSTkFTZXEgbWVhc3VyZXMgdGhlIGV4cHJlc3Npb24gb2YgdGhvdXNhbmRzIG9mIGdlbmVzIGluIGVhY2ggY2VsbC4gVGhlIGJpb2xvZ2ljYWwgcXVlc3Rpb24gYXNrZWQgaW4gYSBzdHVkeSB3aWxsIG1vc3Qgb2Z0ZW4gcmVsYXRlIHRvIGEgZnJhY3Rpb24gb2YgdGhlc2UgZ2VuZXMgb25seSwgbGlua2VkIGZvciBleGFtcGxlIHRvIGRpZmZlcmVuY2VzIGJldHdlZW4gY2VsbCB0eXBlcywgZHJpdmVycyBvZiBkaWZmZXJlbnRpYXRpb24sIG9yIHJlc3BvbnNlIHRvIHBlcnR1cmJhdGlvbi4KCk1vc3QgaGlnaC10aHJvdWdocHV0IG1vbGVjdWxhciBkYXRhIGluY2x1ZGUgdmFyaWF0aW9uIGNyZWF0ZWQgYnkgdGhlIGFzc2F5IGl0c2VsZiwgbm90IGJpb2xvZ3ksIGkuZS4gdGVjaG5pY2FsIG5vaXNlLCBmb3IgZXhhbXBsZSBjYXVzZWQgYnkgc2FtcGxpbmcgZHVyaW5nIFJOQSBjYXB0dXJlIGFuZCBsaWJyYXJ5IHByZXBhcmF0aW9uLiBJbiBzY1JOQVNlcSwgdGhpcyB0ZWNobmljYWwgbm9pc2Ugd2lsbCByZXN1bHQgaW4gbW9zdCBnZW5lcyBiZWluZyBkZXRlY3RlZCBhdCBkaWZmZXJlbnQgbGV2ZWxzLiBUaGlzIG5vaXNlIG1heSBoaW5kZXIgdGhlIGRldGVjdGlvbiBvZiB0aGUgYmlvbG9naWNhbCBzaWduYWwuCgpMZXQncyBpZGVudGlmeSBIaWdobHkgVmFyaWFibGVzIEdlbmVzIChIVkdzKSB3aXRoIHRoZSBhaW0gdG8gZmluZCB0aG9zZSB1bmRlcmx5aW5nIHRoZSBoZXRlcm9nZW5laXR5IG9ic2VydmVkIGFjcm9zcyBjZWxscy4KCiMjIyBNb2RlbGxpbmcgYW5kIHJlbW92aW5nIHRlY2huaWNhbCBub2lzZQoKU29tZSBhc3NheXMgYWxsb3cgdGhlIGluY2x1c2lvbiBvZiBrbm93biBtb2xlY3VsZXMgaW4gYSBrbm93biBhbW91bnQgY292ZXJpbmcgYSB3aWRlIHJhbmdlLCBmcm9tIGxvdyB0byBoaWdoIGFidW5kYW5jZTogc3Bpa2UtaW5zLiBUaGUgdGVjaG5pY2FsIG5vaXNlIGlzIGFzc2Vzc2VkIGJhc2VkIG9uIHRoZSBhbW91bnQgb2Ygc3Bpa2UtaW5zIHVzZWQsIHRoZSBjb3JyZXNwb25kaW5nIHJlYWQgY291bnRzIG9idGFpbmVkIGFuZCB0aGVpciB2YXJpYXRpb24gYWNyb3NzIGNlbGxzLiBUaGUgdmFyaWFuY2UgaW4gZXhwcmVzc2lvbiBjYW4gdGhlbiBiZSBkZWNvbXBvc2VkIGludG8gdGhlIGJpb2xnaWNhbCBhbmQgdGVjaG5pY2FsIGNvbXBvbmVudHMuIAoKVU1JLWJhc2VkIGFzc2F5cyBkbyBub3QgKHlldD8pIGFsbG93IHNwaWtlLWlucy4gQnV0IG9uZSBjYW4gc3RpbGwgaWRlbnRpZnkgSFZHcywgdGhhdCBpcyBnZW5lcyB3aXRoIHRoZSBoaWdoZXN0IGJpb2xvZ2ljYWwgY29tcG9uZW50LiBBc3N1bWluZyB0aGF0IGV4cHJlc3Npb24gZG9lcyBub3QgdmFyeSBhY3Jvc3MgY2VsbHMgZm9yIG1vc3QgZ2VuZXMsIHRoZSB0b3RhbCB2YXJpYW5jZSBmb3IgdGhlc2UgZ2VuZXMgbWFpbmx5IHJlZmxlY3RzIHRlY2huaWNhbCBub2lzZS4gVGhlIGxhdHRlciBjYW4gdGh1cyBiZSBhc3Nlc3NlZCBieSBmaXR0aW5nIGEgdHJlbmQgdG8gdGhlIHZhcmlhbmNlIGluIGV4cHJlc3Npb24uIFRoZSBmaXR0ZWQgdmFsdWUgd2lsbCBiZSB0aGUgZXN0aW1hdGUgb2YgdGhlIHRlY2huaWNhbCBjb21wb25lbnQuCgpMZXQncyBmaXQgYSB0cmVuZCB0byB0aGUgdmFyaWFuY2UsIHVzaW5nIG1vZGVsR2VuZVZhcigpLiAKCmBgYHtyIGZpdF90cmVuZF90b192YXJ9CmRlYy5zY2UgPC0gbW9kZWxHZW5lVmFyKHNjZSkKYGBgCgpMZXTigJlzIHBsb3QgdmFyaWFuY2UgYWdhaW5zdCBtZWFuIG9mIGV4cHJlc3Npb24gKGxvZyBzY2FsZSkgYW5kIHRoZSBtZWFuLWRlcGVuZGVudCB0cmVuZCBmaXR0ZWQgdG8gdGhlIHZhcmlhbmNlOiAKCmBgYHtyIHBsb3RfdmFyX3RyZW5kfQojIFZpc3VhbGl6aW5nIHRoZSBmaXQ6CnZhci5maXQgPC0gbWV0YWRhdGEoZGVjLnNjZSkKcGxvdCh2YXIuZml0JG1lYW4sIHZhci5maXQkdmFyLCB4bGFiPSJNZWFuIG9mIGxvZy1leHByZXNzaW9uIiwKICAgIHlsYWI9IlZhcmlhbmNlIG9mIGxvZy1leHByZXNzaW9uIikKY3VydmUodmFyLmZpdCR0cmVuZCh4KSwgY29sPSJkb2RnZXJibHVlIiwgYWRkPVRSVUUsIGx3ZD0yKQpgYGAKCkluIHRoZSBhYnNlbmNlIG9mIHNwaWtlLWluIGRhdGEsIG9uZSBjYW4gYXR0ZW1wdCB0byBjcmVhdGUgYSB0cmVuZCBieSBtYWtpbmcgc29tZSBkaXN0cmlidXRpb25hbCBhc3N1bXB0aW9ucyBhYm91dCB0aGUgbm9pc2UuIEZvciBleGFtcGxlLCBVTUkgY291bnRzIHR5cGljYWxseSBleGhpYml0IG5lYXItUG9pc3NvbiB2YXJpYXRpb24gaWYgd2Ugb25seSBjb25zaWRlciB0ZWNobmljYWwgbm9pc2UgZnJvbSBsaWJyYXJ5IHByZXBhcmF0aW9uIGFuZCBzZXF1ZW5jaW5nLiBUaGlzIGNhbiBiZSB1c2VkIHRvIGNvbnN0cnVjdCBhIG1lYW4tdmFyaWFuY2UgdHJlbmQgaW4gdGhlIGxvZy1jb3VudHMgd2l0aCB0aGUgbW9kZWxHZW5lVmFyQnlQb2lzc29uKCkgZnVuY3Rpb24uIE5vdGUgdGhlIGluY3JlYXNlZCByZXNpZHVhbHMgb2YgdGhlIGhpZ2gtYWJ1bmRhbmNlIGdlbmVzLCB3aGljaCBjYW4gYmUgaW50ZXJwcmV0ZWQgYXMgdGhlIGFtb3VudCBvZiBiaW9sb2dpY2FsIHZhcmlhdGlvbiB0aGF0IHdhcyBhc3N1bWVkIHRvIGJlIOKAnHVuaW50ZXJlc3RpbmfigJ0gd2hlbiBmaXR0aW5nIHRoZSBnZW5lLWJhc2VkIHRyZW5kIGFib3ZlLgoKCmBgYHtyfQpzZXQuc2VlZCgwMDEwMTAxKQpkZWMucG9pcy5zY2UgPC0gbW9kZWxHZW5lVmFyQnlQb2lzc29uKHNjZSkKZGVjLnBvaXMuc2NlIDwtIGRlYy5wb2lzLnNjZVtvcmRlcihkZWMucG9pcy5zY2UkYmlvLCBkZWNyZWFzaW5nPVRSVUUpLF0KaGVhZChkZWMucG9pcy5zY2UpCmBgYAoKUGxvdDoKCmBgYHtyfQpwbG90KGRlYy5wb2lzLnNjZSRtZWFuLCBkZWMucG9pcy5zY2UkdG90YWwsIHBjaD0xNiwgeGxhYj0iTWVhbiBvZiBsb2ctZXhwcmVzc2lvbiIsCiAgICB5bGFiPSJWYXJpYW5jZSBvZiBsb2ctZXhwcmVzc2lvbiIpCmN1cnZlKG1ldGFkYXRhKGRlYy5wb2lzLnNjZSkkdHJlbmQoeCksIGNvbD0iZG9kZ2VyYmx1ZSIsIGFkZD1UUlVFKQpgYGAKCkludGVyZXN0aW5nbHksIHRyZW5kcyBiYXNlZCBwdXJlbHkgb24gdGVjaG5pY2FsIG5vaXNlIHRlbmQgdG8geWllbGQgbGFyZ2UgYmlvbG9naWNhbCBjb21wb25lbnRzIGZvciBoaWdobHktZXhwcmVzc2VkIGdlbmVzLiBUaGlzIG9mdGVuIGluY2x1ZGVzIHNvLWNhbGxlZCDigJxob3VzZS1rZWVwaW5n4oCdIGdlbmVzIGNvZGluZyBmb3IgZXNzZW50aWFsIGNlbGx1bGFyIGNvbXBvbmVudHMgc3VjaCBhcyByaWJvc29tYWwgcHJvdGVpbnMsIHdoaWNoIGFyZSBjb25zaWRlcmVkIHVuaW50ZXJlc3RpbmcgZm9yIGNoYXJhY3Rlcml6aW5nIGNlbGx1bGFyIGhldGVyb2dlbmVpdHkuIFRoZXNlIG9ic2VydmF0aW9ucyBzdWdnZXN0IHRoYXQgYSBtb3JlIGFjY3VyYXRlIG5vaXNlIG1vZGVsIGRvZXMgbm90IG5lY2Vzc2FyaWx5IHlpZWxkIGEgYmV0dGVyIHJhbmtpbmcgb2YgSFZHcywgdGhvdWdoIG9uZSBzaG91bGQga2VlcCBhbiBvcGVuIG1pbmQgLSBob3VzZS1rZWVwaW5nIGdlbmVzIGFyZSByZWd1bGFybHkgREUgaW4gYSB2YXJpZXR5IG9mIGNvbmRpdGlvbnMgKEdsYXJlIGV0IGFsLiAyMDAyOyBOYXphcmksIFBhcmhhbSwgYW5kIE1hbGVraSAyMDE1OyBHdWltYXJhZXMgYW5kIFphdm9sYW4gMjAxNiksIGFuZCB0aGUgZmFjdCB0aGF0IHRoZXkgaGF2ZSBsYXJnZSBiaW9sb2dpY2FsIGNvbXBvbmVudHMgaW5kaWNhdGVzIHRoYXQgdGhlcmUgaXMgc3Ryb25nIHZhcmlhdGlvbiBhY3Jvc3MgY2VsbHMgdGhhdCBtYXkgbm90IGJlIGNvbXBsZXRlbHkgaXJyZWxldmFudC4KCiMjIyBDaG9vc2luZyBzb21lIEhWR3M6CgpJZGVudGlmeSB0aGUgdG9wIDIwIEhWR3MgYnkgc29ydGluZyBnZW5lcyBpbiBkZWNyZWFzaW5nIG9yZGVyIG9mIGJpb2xvZ2ljYWwgY29tcG9uZW50LgoKYGBge3IgSFZHc30KIyBvcmRlciBnZW5lcyBieSBkZWNyZWFzaW5nIG9yZGVyIG9mIGJpb2xvZ2ljYWwgY29tcG9uZW50Cm8gPC0gb3JkZXIoZGVjLnNjZSRiaW8sIGRlY3JlYXNpbmc9VFJVRSkKIyBjaGVjayB0b3AgYW5kIGJvdHRvbSBvZiBzb3J0ZWQgdGFibGUKaGVhZChkZWMuc2NlW28sXSkKdGFpbChkZWMuc2NlW28sXSkKIyBjaG9vc2UgdGhlIHRvcCAyMCBnZW5lcyB3aXRoIHRoZSBoaWdoZXN0IGJpb2xvZ2ljYWwgY29tcG9uZW50CmNob3Nlbi5nZW5lcy5pbmRleCA8LSBvWzE6MjBdCmBgYAoKU2hvdyB0aGUgdG9wIDIwIEhWR3Mgb24gdGhlIHBsb3QgZGlzcGxheWluZyB0aGUgdmFyaWFuY2UgYWdhaW5zdCB0aGUgbWVhbiBleHByZXNzaW9uOiAKCmBgYHtyIHBsb3RfdmFyX3RyZW5kX0hWR3RvcDIwfQpwbG90KHZhci5maXQkbWVhbiwgdmFyLmZpdCR2YXIpCmN1cnZlKHZhci5maXQkdHJlbmQoeCksIGNvbD0icmVkIiwgbHdkPTIsIGFkZD1UUlVFKQpwb2ludHModmFyLmZpdCRtZWFuW2Nob3Nlbi5nZW5lcy5pbmRleF0sIHZhci5maXQkdmFyW2Nob3Nlbi5nZW5lcy5pbmRleF0sIGNvbD0ib3JhbmdlIikKYGBgCgpSYXRoZXIgdGhhbiBjaG9vc2luZyBhIGZpeGVkIG51bWJlciBvZiB0b3AgZ2VuZXMsIG9uZSBtYXkgZGVmaW5lICdIVkdzJyBhcyBnZW5lcyB3aXRoIGEgcG9zaXRpdmUgYmlvbG9naWNhbCBjb21wb25lbnQsIGllIHdob3NlIHZhcmlhbmNlIGlzIGhpZ2hlciB0aGFuIHRoZSBmaXR0ZWQgdmFsdWUgZm9yIHRoZSBjb3JyZXNwb25kaW5nIG1lYW4gZXhwcmVzc2lvbi4KClNlbGVjdCBhbmQgc2hvdyB0aGVzZSAnSFZHcycgb24gdGhlIHBsb3QgZGlzcGxheWluZyB0aGUgdmFyaWFuY2UgYWdhaW5zdCB0aGUgbWVhbiBleHByZXNzaW9uOiAKCmBgYHtyIHBsb3RfdmFyX3RyZW5kX0hWR2Jpb0NvbXBQb3N9Cmh2Z0Jvb2wgPC0gZGVjLnNjZSRiaW8gPiAwCnRhYmxlKGh2Z0Jvb2wpCmh2Zy5pbmRleCA8LSB3aGljaChodmdCb29sKQpwbG90KHZhci5maXQkbWVhbiwgdmFyLmZpdCR2YXIpCmN1cnZlKHZhci5maXQkdHJlbmQoeCksIGNvbD0icmVkIiwgbHdkPTIsIGFkZD1UUlVFKQpwb2ludHModmFyLmZpdCRtZWFuW2h2Zy5pbmRleF0sIHZhci5maXQkdmFyW2h2Zy5pbmRleF0sIGNvbD0ib3JhbmdlIikKYGBgCgpTYXZlIG9iamVjdHMgdG8gZmlsZQoKYGBge3IsIGV2YWw9RkFMU0V9CnRtcEZuIDwtIHNwcmludGYoIiVzLyVzL1JvYmplY3RzLyVzX3NjZV9uel9wb3N0RGVjb252JXNfZmVhdFNlbC5SZHMiLCBwcm9qRGlyLCBvdXREaXJCaXQsIHNldE5hbWUsIHNldFN1ZikKc2F2ZVJEUyhsaXN0KCJkZWMuc2NlIj1kZWMuc2NlLCJodmcuaW5kZXgiPWh2Zy5pbmRleCksIHRtcEZuKQpgYGAKCkhWR3MgbWF5IGJlIGRyaXZlbiBieSBvdXRsaWVyIGNlbGxzLiBTbyBsZXQncyBwbG90IHRoZSBkaXN0cmlidXRpb24gb2YgZXhwcmVzc2lvbiB2YWx1ZXMgZm9yIHRoZSBnZW5lcyB3aXRoIHRoZSBsYXJnZXN0IGJpb2xvZ2ljYWwgY29tcG9uZW50cy4KCkZpcnN0LCBnZXQgZ2VuZSBuYW1lcyB0byByZXBsYWNlIGVuc2VtYmwgSURzIG9uIHBsb3QuIAoKYGBge3IgSFZHX2V4dE5hbWV9CiMgdGhlIGNvdW50IG1hdHJpeCByb3dzIGFyZSBuYW1lZCB3aXRoIGVuc2VtYmwgZ2VuZSBJRHMuIExldCdzIGxhYmVsIGdlbmUgd2l0aCB0aGVpciBuYW1lIGluc3RlYWQ6CiMgcm93IGluZGljZXMgb2YgZ2VuZXMgaW4gcm93RGF0YShzY2UpCnRtcEluZCA8LSB3aGljaChyb3dEYXRhKHNjZSkkZW5zZW1ibF9nZW5lX2lkICVpbiUgcm93bmFtZXMoZGVjLnNjZSlbY2hvc2VuLmdlbmVzLmluZGV4XSkKIyBjaGVjazoKcm93RGF0YShzY2UpW3RtcEluZCxjKCJlbnNlbWJsX2dlbmVfaWQiLCJleHRlcm5hbF9nZW5lX25hbWUiKV0KIyBzdG9yZSBuYW1lczoKdG1wTmFtZSA8LSByb3dEYXRhKHNjZSlbdG1wSW5kLCJleHRlcm5hbF9nZW5lX25hbWUiXQojIHRoZSBnZW5lIG5hbWUgbWF5IG5vdCBiZSBrbm93biwgc28ga2VlcCB0aGUgZW5zZW1ibCBnZW5lIElEIGluIHRoYXQgY2FzZToKdG1wTmFtZVt0bXBOYW1lPT0iIl0gPC0gcm93RGF0YShzY2UpW3RtcEluZCwiZW5zZW1ibF9nZW5lX2lkIl1bdG1wTmFtZT09IiJdCnRtcE5hbWVbaXMubmEodG1wTmFtZSldIDwtIHJvd0RhdGEoc2NlKVt0bXBJbmQsImVuc2VtYmxfZ2VuZV9pZCJdW2lzLm5hKHRtcE5hbWUpXQpybSh0bXBJbmQpCmBgYAoKTm93IHNob3cgYSB2aW9saW4gcGxvdCBmb3IgZWFjaCBnZW5lLCB1c2luZyBwbG90RXhwcmVzc2lvbigpIGFuZCBsYWJlbCBnZW5lcyB3aXRoIHRoZWlyIG5hbWU6CgpgYGB7ciBwbG90X2NvdW50X0hWR3RvcDIwfQpnIDwtIHBsb3RFeHByZXNzaW9uKHNjZSwgcm93bmFtZXMoZGVjLnNjZSlbY2hvc2VuLmdlbmVzLmluZGV4XSwgCiAgICBwb2ludF9hbHBoYT0wLjA1LCBqaXR0ZXI9ImppdHRlciIpICsgZm9udHNpemUKZyA8LSBnICsgc2NhbGVfeF9kaXNjcmV0ZShicmVha3M9cm93bmFtZXMoZGVjLnNjZSlbY2hvc2VuLmdlbmVzLmluZGV4XSwKICAgICAgICBsYWJlbHM9dG1wTmFtZSkKZwpgYGAKCkFub3RoZXIgZmV3IGdlbmVzOgoKYGBge3J9CmNob3Nlbi5nZW5lcy5pbmRleCA8LSBvWzIxOjQwXQoKdG1wSW5kIDwtIHdoaWNoKHJvd0RhdGEoc2NlKSRlbnNlbWJsX2dlbmVfaWQgJWluJSByb3duYW1lcyhkZWMuc2NlKVtjaG9zZW4uZ2VuZXMuaW5kZXhdKQojIGNoZWNrOgpyb3dEYXRhKHNjZSlbdG1wSW5kLGMoImVuc2VtYmxfZ2VuZV9pZCIsImV4dGVybmFsX2dlbmVfbmFtZSIpXQojIHN0b3JlIG5hbWVzOgp0bXBOYW1lIDwtIHJvd0RhdGEoc2NlKVt0bXBJbmQsImV4dGVybmFsX2dlbmVfbmFtZSJdCiMgdGhlIGdlbmUgbmFtZSBtYXkgbm90IGJlIGtub3duLCBzbyBrZWVwIHRoZSBlbnNlbWJsIGdlbmUgSUQgaW4gdGhhdCBjYXNlOgp0bXBOYW1lW3RtcE5hbWU9PSIiXSA8LSByb3dEYXRhKHNjZSlbdG1wSW5kLCJlbnNlbWJsX2dlbmVfaWQiXVt0bXBOYW1lPT0iIl0KdG1wTmFtZVtpcy5uYSh0bXBOYW1lKV0gPC0gcm93RGF0YShzY2UpW3RtcEluZCwiZW5zZW1ibF9nZW5lX2lkIl1baXMubmEodG1wTmFtZSldCnJtKHRtcEluZCkKCmcgPC0gcGxvdEV4cHJlc3Npb24oc2NlLCByb3duYW1lcyhkZWMuc2NlKVtjaG9zZW4uZ2VuZXMuaW5kZXhdLCAKICAgIHBvaW50X2FscGhhPTAuMDUsIGppdHRlcj0iaml0dGVyIikgKyBmb250c2l6ZQpnIDwtIGcgKyBzY2FsZV94X2Rpc2NyZXRlKGJyZWFrcz1yb3duYW1lcyhkZWMuc2NlKVtjaG9zZW4uZ2VuZXMuaW5kZXhdLAogICAgICAgIGxhYmVscz10bXBOYW1lKQpnCmBgYAoKX19DaGFsbGVuZ2VfXzogU2hvdyB2aW9saW4gcGxvdHMgZm9yIHRoZSAyMCBnZW5lcyB3aXRoIHRoZSBsb3dlc3QgYmlvbG9naWNhbCBjb21wb25lbnQuIEhvdyBkbyB0aGV5IGNvbXBhcmUgdG8gdGhlIHRob3NlIGZvciBIVkdzIGNob3NlbiBhYm92ZT8KCmBgYHtyIHBsb3RfY291bnRfdmlvbG9pbl9IVkdib3QyMCwgZXZhbCA9IFRSVUV9CmNob3Nlbi5nZW5lcy5pbmRleC50bXAgPC0gb3JkZXIoZGVjLnNjZSRiaW8sIGRlY3JlYXNpbmc9RkFMU0UpWzE6MjBdCnRtcEluZCA8LSAod2hpY2gocm93RGF0YShzY2UpJGVuc2VtYmxfZ2VuZV9pZCAlaW4lIHJvd25hbWVzKGRlYy5zY2UpW2Nob3Nlbi5nZW5lcy5pbmRleC50bXBdKSkKIyBjaGVjazoKcm93RGF0YShzY2UpW3RtcEluZCxjKCJlbnNlbWJsX2dlbmVfaWQiLCJleHRlcm5hbF9nZW5lX25hbWUiKV0KIyBzdG9yZSBuYW1lczoKdG1wTmFtZSA8LSByb3dEYXRhKHNjZSlbdG1wSW5kLCJleHRlcm5hbF9nZW5lX25hbWUiXQojIHRoZSBnZW5lIG5hbWUgbWF5IG5vdCBiZSBrbm93biwgc28ga2VlcCB0aGUgZW5zZW1ibCBnZW5lIElEIGluIHRoYXQgY2FzZToKdG1wTmFtZVt0bXBOYW1lPT0iIl0gPC0gcm93RGF0YShzY2UpW3RtcEluZCwiZW5zZW1ibF9nZW5lX2lkIl1bdG1wTmFtZT09IiJdCnRtcE5hbWVbaXMubmEodG1wTmFtZSldIDwtIHJvd0RhdGEoc2NlKVt0bXBJbmQsImVuc2VtYmxfZ2VuZV9pZCJdW2lzLm5hKHRtcE5hbWUpXQpybSh0bXBJbmQpCmcgPC0gcGxvdEV4cHJlc3Npb24oc2NlLCByb3duYW1lcyhkZWMuc2NlKVtjaG9zZW4uZ2VuZXMuaW5kZXgudG1wXSwgCgkJCXBvaW50X2FscGhhPTAuMDUsIGppdHRlcj0iaml0dGVyIikgKyBmb250c2l6ZQpnIDwtIGcgKyBzY2FsZV94X2Rpc2NyZXRlKGJyZWFrcz1yb3duYW1lcyhkZWMuc2NlKVtjaG9zZW4uZ2VuZXMuaW5kZXgudG1wXSwKICAgICAgICBsYWJlbHM9dG1wTmFtZSkKZwpybShjaG9zZW4uZ2VuZXMuaW5kZXgudG1wKQpgYGAK