1 Doublet detection

Source: Doublet detection chapter of the OSCA book (with only few edits of its text).

1.1 Learning objectives

In this section we will learn how to identify droplets that may include more than one cell, using a method based on simulation of doublets from the single-cell expression profiles.

1.2 Set up analysis

Let’s set some variables (eg path to files) and load R pcakages.

projDir <- "/mnt/scratcha/bioinformatics/baller01/20200511_FernandesM_ME_crukBiSs2020"
outDirBit <- "AnaWiSce/Attempt1"
nbPcToComp <- 50

We will load:

  • ggplot2, for plots
  • dplyr, for data management
  • scater, for UMI count normalisation
  • scran, here for doublet detection
suppressMessages(library(ggplot2))
suppressMessages(library(scater)) # for logNormCounts
suppressMessages(library(scran))
suppressMessages(library(dplyr))
suppressMessages(library(BiocSingular)) # for faster PCA
fontsize <- theme(axis.text=element_text(size=12), axis.title=element_text(size=16))

1.3 Load data

We will load the R file keeping the SCE object with the normalised counts (no cell subsampling).

setName <- "caron"
setSuf <- ""
tmpFn <- sprintf("%s/%s/Robjects/%s_sce_nz_postDeconv%s.Rds", projDir, outDirBit, setName, setSuf)

Input file: AnaWiSce/Attempt1/Robjects/caron_sce_nz_postDeconv.Rds.

if(!file.exists(tmpFn))
{
    knitr::knit_exit()
}
sce <- readRDS(tmpFn)

Number of genes: 18372.

Number of cells: 45669.

1.4 Overview

In single-cell RNA sequencing (scRNA-seq) experiments, doublets are artifactual libraries generated from two cells. They typically arise due to errors in cell sorting or capture, especially in droplet-based protocols (Zheng et al. 2017) involving thousands of cells. Doublets are obviously undesirable when the aim is to characterize populations at the single-cell level. In particular, doublets can be mistaken for intermediate populations or transitory states that do not actually exist. Thus, it is desirable to identify and remove doublet libraries so that they do not compromise interpretation of the results.

Several experimental strategies are available for doublet removal. One approach exploits natural genetic variation when pooling cells from multiple donor individuals (Kang et al. 2018). Doublets can be identified as libraries with allele combinations that do not exist in any single donor. Another approach is to mark a subset of cells (e.g., all cells from one sample) with an antibody conjugated to a different oligonucleotide (Stoeckius, Zheng, et al. 2017). Upon pooling, libraries that are observed to have different oligonucleotides are considered to be doublets and removed. These approaches can be highly effective but rely on experimental information that may not be available.

A more general approach is to infer doublets from the expression profiles alone (Dahlin et al. 2018). The Doublet detection chapter of the OSCA book also describes a second method, which relies on clusters identified, and their quality.

1.5 Doublet detection by simulation

This strategy involves in silico simulation of doublets from the single-cell expression profiles (Dahlin et al. 2018). This is performed using the doubletCells() function from scran, which will:

  • Simulate thousands of doublets by adding together two randomly chosen single-cell profiles.
  • For each original cell, compute the density of simulated doublets in the surrounding neighborhood.
  • For each original cell, compute the density of other observed cells in the neighborhood.
  • Return the ratio between the two densities as a “doublet score” for each cell.

This approach assumes that the simulated doublets are good approximations for real doublets. The use of random selection accounts for the relative abundances of different subpopulations, which affect the likelihood of their involvement in doublets; and the calculation of a ratio avoids high scores for non-doublet cells in highly abundant subpopulations.

We see the function in action below. To speed up the density calculations, doubletCells() will perform a PCA on the log-expression matrix, and we perform some (optional) parametrization to ensure that the computed PCs are consistent with that from our previous analysis on this dataset.

We will get data for one sample.

splNames <- unique(colData(sce)$Sample.Name)
sceOrig <- sce
sce <- sceOrig[,sce$Sample.Name == splNames[1] ]

set.seed(123)
#--- normalization ---#
library(scran)
#set.seed(101000110)
clusters <- quickCluster(sce)
sce <- computeSumFactors(sce, clusters=clusters)
sce <- logNormCounts(sce)
#--- variance-modelling ---#
#set.seed(00010101)
dec.sce <- modelGeneVarByPoisson(sce)
top.sce <- getTopHVGs(dec.sce, prop=0.1)
#--- dimensionality-reduction ---#
#set.seed(101010011)
sce <- denoisePCA(sce, technical=dec.sce, subset.row=top.sce)
sce <- runTSNE(sce, dimred="PCA")
#--- clustering ---#
snn.gr <- buildSNNGraph(sce, use.dimred="PCA", k=25)
sce$cluster <- factor(igraph::cluster_walktrap(snn.gr)$membership)
sce$clusterStg <- factor(paste0("c", sce$cluster),
             levels = paste0("c", levels( sce$cluster)) )

We also plot the t-SNE showing clusters, which are not used for the doublet detection by simulation used here, but help visulaise cells with different expression profiles.

colLabels(sce) <- sce$clusterStg
plotTSNE(sce, colour_by="clusterStg")

Let’s run doubletCells() and display moments of the distribution of the doublet scores returned:

library(BiocSingular)
set.seed(100)

# Setting up the parameters for consistency with denoisePCA();
# this can be changed depending on your feature selection scheme.
dbl.dens <- doubletCells(sce,
             subset.row=top.sce, 
             d=ncol(reducedDim(sce)))
summary(dbl.dens)
    Min.  1st Qu.   Median     Mean  3rd Qu.     Max. 
    0.00    22.85    47.36   171.47   118.14 36180.50 

The t-SNE plot below help identify any cluster with high number of cell with a high score.

sce$DoubletScore <- log10(dbl.dens+1)
plotTSNE(sce, colour_by="DoubletScore")

The violin plot below shows the distribution of score across clusters identified in the whole data set. Clusters with a large fraction of high-scoring cells are worth checking. Comparing marker genes for these clusters to other, ‘doublet-free’ clusters may inform on the type of cells involved. If the ‘source’ clusters are not related biologically these high-scoring cells should be discarded. If on the other hand the ‘source’ clusters are two well defined steps along a differentiation path, the high-scoring cells may represent an intermediary state.

plotColData(sce, y = "DoubletScore", x = "clusterStg", 
   colour_by = "DoubletScore")

The advantage of doubletCells() is that it does not depend on clusters, reducing the sensitivity of the results to clustering quality. The downside is that it requires some strong assumptions about how doublets form, such as the combining proportions and the sampling from pure subpopulations. In particular, doubletCells() treats the library size of each cell as an accurate proxy for its total RNA content. If this is not true, the simulation will not combine expression profiles from different cells in the correct proportions. This means that the simulated doublets will be systematically shifted away from the real doublets, resulting in doublet scores that are too low.

Simply removing cells with high doublet scores will not be sufficient to eliminate real doublets from the data set. In some cases, only a subset of the cells in the putative doublet cluster actually have high scores, and removing these would still leave enough cells in that cluster to mislead downstream analyses. In fact, even defining a threshold on the doublet score is difficult as the interpretation of the score is relative. There is no general definition for a fixed threshold above which libraries are to be considered doublets.

We recommend interpreting the doubletCells() scores in the context of cluster annotation. All cells from a cluster with a large average doublet score should be considered suspect, and close neighbors of problematic clusters should also be treated with caution. In contrast, a cluster containing a small proportion of high-scoring cells is probably safe provided that any interesting results are not being driven by those cells (e.g., checking that DE in an interesting gene is not driven solely by cells with high doublet scores). While clustering is still required, this approach is more robust than doubletClusters() to the quality of the clustering as the scores are computed on a per-cell basis.

(As an aside, the issue of unknown combining proportions can be solved completely if spike-in information is available, e.g., in plate-based protocols. This will provide an accurate estimate of the total RNA content of each cell. To this end, spike-in-based size factors from Section 7.4 can be supplied to the doubletCells() function via the size.factors.content= argument. This will use the spike-in size factors to scale the contribution of each cell to a doublet library.)

1.6  Further comments

Doublet detection procedures should only be applied to libraries generated in the same experimental batch. It is obviously impossible for doublets to form between two cells that were captured separately. Thus, some understanding of the experimental design is required prior to the use of the above functions. This avoids unnecessary concerns about the validity of batch-specific clusters that cannot possibly consist of doublets.

It is also difficult to interpret doublet predictions in data containing cellular trajectories. By definition, cells in the middle of a trajectory are always intermediate between other cells and are liable to be incorrectly detected as doublets. Some protection is provided by the non-linear nature of many real trajectories, which reduces the risk of simulated doublets coinciding with real cells in doubletCells(). One can also put more weight on the relative library sizes in doubletCluster() instead of relying solely on N, under the assumption that sudden spikes in RNA content are unlikely in a continuous biological process.

The best solution to the doublet problem is experimental - that is, to avoid generating them in the first place. This should be a consideration when designing scRNA-seq experiments, where the desire to obtain large numbers of cells at minimum cost should be weighed against the general deterioration in data quality and reliability when doublets become more frequent.

LS0tCnRpdGxlOiAiQ1JVSyBDSSBTdW1tZXIgU2Nob29sIDIwMjAgLSBpbnRyb2R1Y3Rpb24gdG8gc2luZ2xlLWNlbGwgUk5BLXNlcSBhbmFseXNpcyIKc3VidGl0bGU6ICdEb3VibGV0IGRldGVjdGlvbicKCmF1dGhvcjogIlN0ZXBoYW5lIEJhbGxlcmVhdSIKb3V0cHV0OgogIGh0bWxfbm90ZWJvb2s6CiAgICBjb2RlX2ZvbGRpbmc6IGhpZGUKICAgIHRvYzogeWVzCiAgICB0b2NfZmxvYXQ6IHllcwogICAgbnVtYmVyX3NlY3Rpb25zOiB0cnVlCiAgaHRtbF9kb2N1bWVudDoKICAgIGRmX3ByaW50OiBwYWdlZAogICAgdG9jOiB5ZXMKICAgIG51bWJlcl9zZWN0aW9uczogdHJ1ZQogICAgY29kZV9mb2xkaW5nOiBoaWRlCiAgaHRtbF9ib29rOgogICAgY29kZV9mb2xkaW5nOiBoaWRlCnBhcmFtczoKICBvdXREaXJCaXQ6ICJBbmFXaVNjZS9BdHRlbXB0MSIKLS0tCgojIERvdWJsZXQgZGV0ZWN0aW9uCgpTb3VyY2U6IFtEb3VibGV0IGRldGVjdGlvbl0oaHR0cHM6Ly9vc2NhLmJpb2NvbmR1Y3Rvci5vcmcvZG91YmxldC1kZXRlY3Rpb24uaHRtbCkgY2hhcHRlciBvZiB0aGUgT1NDQSBib29rICh3aXRoIG9ubHkgZmV3IGVkaXRzIG9mIGl0cyB0ZXh0KS4KCiMjIExlYXJuaW5nIG9iamVjdGl2ZXMKCkluIHRoaXMgc2VjdGlvbiB3ZSB3aWxsIGxlYXJuIGhvdyB0byBpZGVudGlmeSBkcm9wbGV0cyB0aGF0IG1heSBpbmNsdWRlIG1vcmUgdGhhbiBvbmUgY2VsbCwgdXNpbmcgYSBtZXRob2QgYmFzZWQgb24gc2ltdWxhdGlvbiBvZiBkb3VibGV0cyBmcm9tIHRoZSBzaW5nbGUtY2VsbCBleHByZXNzaW9uIHByb2ZpbGVzLgoKIyMgU2V0IHVwIGFuYWx5c2lzCgpMZXQncyBzZXQgc29tZSB2YXJpYWJsZXMgKGVnIHBhdGggdG8gZmlsZXMpIGFuZCBsb2FkIFIgcGNha2FnZXMuCgpgYGB7cn0KcHJvakRpciA8LSAiL21udC9zY3JhdGNoYS9iaW9pbmZvcm1hdGljcy9iYWxsZXIwMS8yMDIwMDUxMV9GZXJuYW5kZXNNX01FX2NydWtCaVNzMjAyMCIKb3V0RGlyQml0IDwtICJBbmFXaVNjZS9BdHRlbXB0MSIKbmJQY1RvQ29tcCA8LSA1MApgYGAKCmBgYHtyIHNldHVwLCBpbmNsdWRlPUZBTFNFLCBlY2hvPUZBTFNFfQojIEZpcnN0LCBzZXQgc29tZSB2YXJpYWJsZXM6CmtuaXRyOjpvcHRzX2NodW5rJHNldChlY2hvID0gVFJVRSkKb3B0aW9ucyhzdHJpbmdzQXNGYWN0b3JzID0gRkFMU0UpCnNldC5zZWVkKDEyMykgIyBmb3IgcmVwcm9kdWNpYmlsaXR5CmtuaXRyOjpvcHRzX2NodW5rJHNldChldmFsID0gVFJVRSkgCmBgYAoKV2Ugd2lsbCBsb2FkOgoKKiBnZ3Bsb3QyLCBmb3IgcGxvdHMKKiBkcGx5ciwgZm9yIGRhdGEgbWFuYWdlbWVudAoqIHNjYXRlciwgZm9yIFVNSSBjb3VudCBub3JtYWxpc2F0aW9uCiogc2NyYW4sIGhlcmUgZm9yIGRvdWJsZXQgZGV0ZWN0aW9uIAoKYGBge3J9CnN1cHByZXNzTWVzc2FnZXMobGlicmFyeShnZ3Bsb3QyKSkKc3VwcHJlc3NNZXNzYWdlcyhsaWJyYXJ5KHNjYXRlcikpICPCoGZvciBsb2dOb3JtQ291bnRzCnN1cHByZXNzTWVzc2FnZXMobGlicmFyeShzY3JhbikpCnN1cHByZXNzTWVzc2FnZXMobGlicmFyeShkcGx5cikpCnN1cHByZXNzTWVzc2FnZXMobGlicmFyeShCaW9jU2luZ3VsYXIpKSAjIGZvciBmYXN0ZXIgUENBCmZvbnRzaXplIDwtIHRoZW1lKGF4aXMudGV4dD1lbGVtZW50X3RleHQoc2l6ZT0xMiksIGF4aXMudGl0bGU9ZWxlbWVudF90ZXh0KHNpemU9MTYpKQpgYGAKCiMjIExvYWQgZGF0YQoKV2Ugd2lsbCBsb2FkIHRoZSBSIGZpbGUga2VlcGluZyB0aGUgU0NFIG9iamVjdCB3aXRoIHRoZSBub3JtYWxpc2VkIGNvdW50cyAobm8gY2VsbCBzdWJzYW1wbGluZykuCgpgYGB7cn0Kc2V0TmFtZSA8LSAiY2Fyb24iCnNldFN1ZiA8LSAiIgp0bXBGbiA8LSBzcHJpbnRmKCIlcy8lcy9Sb2JqZWN0cy8lc19zY2VfbnpfcG9zdERlY29udiVzLlJkcyIsIHByb2pEaXIsIG91dERpckJpdCwgc2V0TmFtZSwgc2V0U3VmKQpgYGAKCklucHV0IGZpbGU6IGByIHNwcmludGYoIiVzL1JvYmplY3RzLyVzX3NjZV9uel9wb3N0RGVjb252JXMuUmRzIiwgb3V0RGlyQml0LCBzZXROYW1lLCBzZXRTdWYpYC4KCmBgYHtyfQppZighZmlsZS5leGlzdHModG1wRm4pKQp7Cglrbml0cjo6a25pdF9leGl0KCkKfQpzY2UgPC0gcmVhZFJEUyh0bXBGbikKYGBgCgpOdW1iZXIgb2YgZ2VuZXM6IGByIG5yb3coc2NlKWAuCgpOdW1iZXIgb2YgY2VsbHM6IGByIG5jb2woc2NlKWAuCgojIyBPdmVydmlldwoKSW4gc2luZ2xlLWNlbGwgUk5BIHNlcXVlbmNpbmcgKHNjUk5BLXNlcSkgZXhwZXJpbWVudHMsIGRvdWJsZXRzIGFyZSBhcnRpZmFjdHVhbCBsaWJyYXJpZXMgZ2VuZXJhdGVkIGZyb20gdHdvIGNlbGxzLiBUaGV5IHR5cGljYWxseSBhcmlzZSBkdWUgdG8gZXJyb3JzIGluIGNlbGwgc29ydGluZyBvciBjYXB0dXJlLCBlc3BlY2lhbGx5IGluIGRyb3BsZXQtYmFzZWQgcHJvdG9jb2xzIChaaGVuZyBldCBhbC4gMjAxNykgaW52b2x2aW5nIHRob3VzYW5kcyBvZiBjZWxscy4gRG91YmxldHMgYXJlIG9idmlvdXNseSB1bmRlc2lyYWJsZSB3aGVuIHRoZSBhaW0gaXMgdG8gY2hhcmFjdGVyaXplIHBvcHVsYXRpb25zIGF0IHRoZSBzaW5nbGUtY2VsbCBsZXZlbC4gSW4gcGFydGljdWxhciwgZG91YmxldHMgY2FuIGJlIG1pc3Rha2VuIGZvciBpbnRlcm1lZGlhdGUgcG9wdWxhdGlvbnMgb3IgdHJhbnNpdG9yeSBzdGF0ZXMgdGhhdCBkbyBub3QgYWN0dWFsbHkgZXhpc3QuIFRodXMsIGl0IGlzIGRlc2lyYWJsZSB0byBpZGVudGlmeSBhbmQgcmVtb3ZlIGRvdWJsZXQgbGlicmFyaWVzIHNvIHRoYXQgdGhleSBkbyBub3QgY29tcHJvbWlzZSBpbnRlcnByZXRhdGlvbiBvZiB0aGUgcmVzdWx0cy4KClNldmVyYWwgZXhwZXJpbWVudGFsIHN0cmF0ZWdpZXMgYXJlIGF2YWlsYWJsZSBmb3IgZG91YmxldCByZW1vdmFsLiBPbmUgYXBwcm9hY2ggZXhwbG9pdHMgbmF0dXJhbCBnZW5ldGljIHZhcmlhdGlvbiB3aGVuIHBvb2xpbmcgY2VsbHMgZnJvbSBtdWx0aXBsZSBkb25vciBpbmRpdmlkdWFscyAoS2FuZyBldCBhbC4gMjAxOCkuIERvdWJsZXRzIGNhbiBiZSBpZGVudGlmaWVkIGFzIGxpYnJhcmllcyB3aXRoIGFsbGVsZSBjb21iaW5hdGlvbnMgdGhhdCBkbyBub3QgZXhpc3QgaW4gYW55IHNpbmdsZSBkb25vci4gQW5vdGhlciBhcHByb2FjaCBpcyB0byBtYXJrIGEgc3Vic2V0IG9mIGNlbGxzIChlLmcuLCBhbGwgY2VsbHMgZnJvbSBvbmUgc2FtcGxlKSB3aXRoIGFuIGFudGlib2R5IGNvbmp1Z2F0ZWQgdG8gYSBkaWZmZXJlbnQgb2xpZ29udWNsZW90aWRlIChTdG9lY2tpdXMsIFpoZW5nLCBldCBhbC4gMjAxNykuIFVwb24gcG9vbGluZywgbGlicmFyaWVzIHRoYXQgYXJlIG9ic2VydmVkIHRvIGhhdmUgZGlmZmVyZW50IG9saWdvbnVjbGVvdGlkZXMgYXJlIGNvbnNpZGVyZWQgdG8gYmUgZG91YmxldHMgYW5kIHJlbW92ZWQuIFRoZXNlIGFwcHJvYWNoZXMgY2FuIGJlIGhpZ2hseSBlZmZlY3RpdmUgYnV0IHJlbHkgb24gZXhwZXJpbWVudGFsIGluZm9ybWF0aW9uIHRoYXQgbWF5IG5vdCBiZSBhdmFpbGFibGUuCgpBIG1vcmUgZ2VuZXJhbCBhcHByb2FjaCBpcyB0byBpbmZlciBkb3VibGV0cyBmcm9tIHRoZSBleHByZXNzaW9uIHByb2ZpbGVzIGFsb25lIChEYWhsaW4gZXQgYWwuIDIwMTgpLiBUaGUgW0RvdWJsZXQgZGV0ZWN0aW9uXShodHRwczovL29zY2EuYmlvY29uZHVjdG9yLm9yZy9kb3VibGV0LWRldGVjdGlvbi5odG1sKSBjaGFwdGVyIG9mIHRoZSBPU0NBIGJvb2sgYWxzbyBkZXNjcmliZXMgYSBzZWNvbmQgbWV0aG9kLCB3aGljaCByZWxpZXMgb24gY2x1c3RlcnMgaWRlbnRpZmllZCwgYW5kIHRoZWlyIHF1YWxpdHkuIAoKIyMgRG91YmxldCBkZXRlY3Rpb24gYnkgc2ltdWxhdGlvbgoKVGhpcyBzdHJhdGVneSBpbnZvbHZlcyBpbiBzaWxpY28gc2ltdWxhdGlvbiBvZiBkb3VibGV0cyBmcm9tIHRoZSBzaW5nbGUtY2VsbCBleHByZXNzaW9uIHByb2ZpbGVzIChEYWhsaW4gZXQgYWwuIDIwMTgpLiBUaGlzIGlzIHBlcmZvcm1lZCB1c2luZyB0aGUgZG91YmxldENlbGxzKCkgZnVuY3Rpb24gZnJvbSBzY3Jhbiwgd2hpY2ggd2lsbDoKCiogU2ltdWxhdGUgdGhvdXNhbmRzIG9mIGRvdWJsZXRzIGJ5IGFkZGluZyB0b2dldGhlciB0d28gcmFuZG9tbHkgY2hvc2VuIHNpbmdsZS1jZWxsIHByb2ZpbGVzLgoqIEZvciBlYWNoIG9yaWdpbmFsIGNlbGwsIGNvbXB1dGUgdGhlIGRlbnNpdHkgb2Ygc2ltdWxhdGVkIGRvdWJsZXRzIGluIHRoZSBzdXJyb3VuZGluZyBuZWlnaGJvcmhvb2QuCiogRm9yIGVhY2ggb3JpZ2luYWwgY2VsbCwgY29tcHV0ZSB0aGUgZGVuc2l0eSBvZiBvdGhlciBvYnNlcnZlZCBjZWxscyBpbiB0aGUgbmVpZ2hib3Job29kLgoqIFJldHVybiB0aGUgcmF0aW8gYmV0d2VlbiB0aGUgdHdvIGRlbnNpdGllcyBhcyBhIOKAnGRvdWJsZXQgc2NvcmXigJ0gZm9yIGVhY2ggY2VsbC4KClRoaXMgYXBwcm9hY2ggYXNzdW1lcyB0aGF0IHRoZSBzaW11bGF0ZWQgZG91YmxldHMgYXJlIGdvb2QgYXBwcm94aW1hdGlvbnMgZm9yIHJlYWwgZG91YmxldHMuIFRoZSB1c2Ugb2YgcmFuZG9tIHNlbGVjdGlvbiBhY2NvdW50cyBmb3IgdGhlIHJlbGF0aXZlIGFidW5kYW5jZXMgb2YgZGlmZmVyZW50IHN1YnBvcHVsYXRpb25zLCB3aGljaCBhZmZlY3QgdGhlIGxpa2VsaWhvb2Qgb2YgdGhlaXIgaW52b2x2ZW1lbnQgaW4gZG91YmxldHM7IGFuZCB0aGUgY2FsY3VsYXRpb24gb2YgYSByYXRpbyBhdm9pZHMgaGlnaCBzY29yZXMgZm9yIG5vbi1kb3VibGV0IGNlbGxzIGluIGhpZ2hseSBhYnVuZGFudCBzdWJwb3B1bGF0aW9ucy4KCldlIHNlZSB0aGUgZnVuY3Rpb24gaW4gYWN0aW9uIGJlbG93LiBUbyBzcGVlZCB1cCB0aGUgZGVuc2l0eSBjYWxjdWxhdGlvbnMsIGRvdWJsZXRDZWxscygpIHdpbGwgcGVyZm9ybSBhIFBDQSBvbiB0aGUgbG9nLWV4cHJlc3Npb24gbWF0cml4LCBhbmQgd2UgcGVyZm9ybSBzb21lIChvcHRpb25hbCkgcGFyYW1ldHJpemF0aW9uIHRvIGVuc3VyZSB0aGF0IHRoZSBjb21wdXRlZCBQQ3MgYXJlIGNvbnNpc3RlbnQgd2l0aCB0aGF0IGZyb20gb3VyIHByZXZpb3VzIGFuYWx5c2lzIG9uIHRoaXMgZGF0YXNldC4KCldlIHdpbGwgZ2V0IGRhdGEgZm9yIG9uZSBzYW1wbGUuIAoKYGBge3J9CnNwbE5hbWVzIDwtIHVuaXF1ZShjb2xEYXRhKHNjZSkkU2FtcGxlLk5hbWUpCnNjZU9yaWcgPC0gc2NlCnNjZSA8LSBzY2VPcmlnWyxzY2UkU2FtcGxlLk5hbWUgPT0gc3BsTmFtZXNbMV0gXQoKc2V0LnNlZWQoMTIzKQojLS0tIG5vcm1hbGl6YXRpb24gLS0tIwpsaWJyYXJ5KHNjcmFuKQojc2V0LnNlZWQoMTAxMDAwMTEwKQpjbHVzdGVycyA8LSBxdWlja0NsdXN0ZXIoc2NlKQpzY2UgPC0gY29tcHV0ZVN1bUZhY3RvcnMoc2NlLCBjbHVzdGVycz1jbHVzdGVycykKc2NlIDwtIGxvZ05vcm1Db3VudHMoc2NlKQojLS0tIHZhcmlhbmNlLW1vZGVsbGluZyAtLS0jCiNzZXQuc2VlZCgwMDAxMDEwMSkKZGVjLnNjZSA8LSBtb2RlbEdlbmVWYXJCeVBvaXNzb24oc2NlKQp0b3Auc2NlIDwtIGdldFRvcEhWR3MoZGVjLnNjZSwgcHJvcD0wLjEpCiMtLS0gZGltZW5zaW9uYWxpdHktcmVkdWN0aW9uIC0tLSMKI3NldC5zZWVkKDEwMTAxMDAxMSkKc2NlIDwtIGRlbm9pc2VQQ0Eoc2NlLCB0ZWNobmljYWw9ZGVjLnNjZSwgc3Vic2V0LnJvdz10b3Auc2NlKQpzY2UgPC0gcnVuVFNORShzY2UsIGRpbXJlZD0iUENBIikKIy0tLSBjbHVzdGVyaW5nIC0tLSMKc25uLmdyIDwtIGJ1aWxkU05OR3JhcGgoc2NlLCB1c2UuZGltcmVkPSJQQ0EiLCBrPTI1KQpzY2UkY2x1c3RlciA8LSBmYWN0b3IoaWdyYXBoOjpjbHVzdGVyX3dhbGt0cmFwKHNubi5ncikkbWVtYmVyc2hpcCkKc2NlJGNsdXN0ZXJTdGcgPC0gZmFjdG9yKHBhc3RlMCgiYyIsIHNjZSRjbHVzdGVyKSwKCQkJIGxldmVscyA9IHBhc3RlMCgiYyIsIGxldmVscyggc2NlJGNsdXN0ZXIpKSApCmBgYAoKV2UgYWxzbyBwbG90IHRoZSB0LVNORSBzaG93aW5nIGNsdXN0ZXJzLCB3aGljaCBhcmUgbm90IHVzZWQgZm9yIHRoZSBkb3VibGV0IGRldGVjdGlvbiBieSBzaW11bGF0aW9uIHVzZWQgaGVyZSwgYnV0IGhlbHAgdmlzdWxhaXNlIGNlbGxzIHdpdGggZGlmZmVyZW50IGV4cHJlc3Npb24gcHJvZmlsZXMuCgpgYGB7cn0KY29sTGFiZWxzKHNjZSkgPC0gc2NlJGNsdXN0ZXJTdGcKcGxvdFRTTkUoc2NlLCBjb2xvdXJfYnk9ImNsdXN0ZXJTdGciKQpgYGAKCkxldCdzIHJ1biBkb3VibGV0Q2VsbHMoKSBhbmQgZGlzcGxheSBtb21lbnRzIG9mIHRoZSBkaXN0cmlidXRpb24gb2YgdGhlIGRvdWJsZXQgc2NvcmVzIHJldHVybmVkOgoKYGBge3J9CmxpYnJhcnkoQmlvY1Npbmd1bGFyKQpzZXQuc2VlZCgxMDApCgojIFNldHRpbmcgdXAgdGhlIHBhcmFtZXRlcnMgZm9yIGNvbnNpc3RlbmN5IHdpdGggZGVub2lzZVBDQSgpOwojIHRoaXMgY2FuIGJlIGNoYW5nZWQgZGVwZW5kaW5nIG9uIHlvdXIgZmVhdHVyZSBzZWxlY3Rpb24gc2NoZW1lLgpkYmwuZGVucyA8LSBkb3VibGV0Q2VsbHMoc2NlLAoJCQkgc3Vic2V0LnJvdz10b3Auc2NlLCAKCQkJIGQ9bmNvbChyZWR1Y2VkRGltKHNjZSkpKQpzdW1tYXJ5KGRibC5kZW5zKQpgYGAKClRoZSB0LVNORSBwbG90IGJlbG93IGhlbHAgaWRlbnRpZnkgYW55IGNsdXN0ZXIgd2l0aCBoaWdoIG51bWJlciBvZiBjZWxsIHdpdGggYSBoaWdoIHNjb3JlLgoKYGBge3J9CnNjZSREb3VibGV0U2NvcmUgPC0gbG9nMTAoZGJsLmRlbnMrMSkKcGxvdFRTTkUoc2NlLCBjb2xvdXJfYnk9IkRvdWJsZXRTY29yZSIpCmBgYAoKVGhlIHZpb2xpbiBwbG90IGJlbG93IHNob3dzIHRoZSBkaXN0cmlidXRpb24gb2Ygc2NvcmUgYWNyb3NzIGNsdXN0ZXJzIGlkZW50aWZpZWQgaW4gdGhlIHdob2xlIGRhdGEgc2V0LiBDbHVzdGVycyB3aXRoIGEgbGFyZ2UgZnJhY3Rpb24gb2YgaGlnaC1zY29yaW5nIGNlbGxzIGFyZSB3b3J0aCBjaGVja2luZy4gQ29tcGFyaW5nIG1hcmtlciBnZW5lcyBmb3IgdGhlc2UgY2x1c3RlcnMgdG8gb3RoZXIsICdkb3VibGV0LWZyZWUnIGNsdXN0ZXJzIG1heSBpbmZvcm0gb24gdGhlIHR5cGUgb2YgY2VsbHMgaW52b2x2ZWQuIElmIHRoZSAnc291cmNlJyBjbHVzdGVycyBhcmUgbm90IHJlbGF0ZWQgYmlvbG9naWNhbGx5IHRoZXNlIGhpZ2gtc2NvcmluZyBjZWxscyBzaG91bGQgYmUgZGlzY2FyZGVkLiBJZiBvbiB0aGUgb3RoZXIgaGFuZCB0aGUgJ3NvdXJjZScgY2x1c3RlcnMgYXJlIHR3byB3ZWxsIGRlZmluZWQgc3RlcHMgYWxvbmcgYSBkaWZmZXJlbnRpYXRpb24gcGF0aCwgdGhlIGhpZ2gtc2NvcmluZyBjZWxscyBtYXkgcmVwcmVzZW50IGFuIGludGVybWVkaWFyeSBzdGF0ZS4KCmBgYHtyfQpwbG90Q29sRGF0YShzY2UsIHkgPSAiRG91YmxldFNjb3JlIiwgeCA9ICJjbHVzdGVyU3RnIiwgCiAgIGNvbG91cl9ieSA9ICJEb3VibGV0U2NvcmUiKQpgYGAKClRoZSBhZHZhbnRhZ2Ugb2YgZG91YmxldENlbGxzKCkgaXMgdGhhdCBpdCBkb2VzIG5vdCBkZXBlbmQgb24gY2x1c3RlcnMsIHJlZHVjaW5nIHRoZSBzZW5zaXRpdml0eSBvZiB0aGUgcmVzdWx0cyB0byBjbHVzdGVyaW5nIHF1YWxpdHkuIFRoZSBkb3duc2lkZSBpcyB0aGF0IGl0IHJlcXVpcmVzIHNvbWUgc3Ryb25nIGFzc3VtcHRpb25zIGFib3V0IGhvdyBkb3VibGV0cyBmb3JtLCBzdWNoIGFzIHRoZSBjb21iaW5pbmcgcHJvcG9ydGlvbnMgYW5kIHRoZSBzYW1wbGluZyBmcm9tIHB1cmUgc3VicG9wdWxhdGlvbnMuIEluIHBhcnRpY3VsYXIsIGRvdWJsZXRDZWxscygpIHRyZWF0cyB0aGUgbGlicmFyeSBzaXplIG9mIGVhY2ggY2VsbCBhcyBhbiBhY2N1cmF0ZSBwcm94eSBmb3IgaXRzIHRvdGFsIFJOQSBjb250ZW50LiBJZiB0aGlzIGlzIG5vdCB0cnVlLCB0aGUgc2ltdWxhdGlvbiB3aWxsIG5vdCBjb21iaW5lIGV4cHJlc3Npb24gcHJvZmlsZXMgZnJvbSBkaWZmZXJlbnQgY2VsbHMgaW4gdGhlIGNvcnJlY3QgcHJvcG9ydGlvbnMuIFRoaXMgbWVhbnMgdGhhdCB0aGUgc2ltdWxhdGVkIGRvdWJsZXRzIHdpbGwgYmUgc3lzdGVtYXRpY2FsbHkgc2hpZnRlZCBhd2F5IGZyb20gdGhlIHJlYWwgZG91YmxldHMsIHJlc3VsdGluZyBpbiBkb3VibGV0IHNjb3JlcyB0aGF0IGFyZSB0b28gbG93LgoKU2ltcGx5IHJlbW92aW5nIGNlbGxzIHdpdGggaGlnaCBkb3VibGV0IHNjb3JlcyB3aWxsIG5vdCBiZSBzdWZmaWNpZW50IHRvIGVsaW1pbmF0ZSByZWFsIGRvdWJsZXRzIGZyb20gdGhlIGRhdGEgc2V0LiBJbiBzb21lIGNhc2VzLCBvbmx5IGEgc3Vic2V0IG9mIHRoZSBjZWxscyBpbiB0aGUgcHV0YXRpdmUgZG91YmxldCBjbHVzdGVyIGFjdHVhbGx5IGhhdmUgaGlnaCBzY29yZXMsIGFuZCByZW1vdmluZyB0aGVzZSB3b3VsZCBzdGlsbCBsZWF2ZSBlbm91Z2ggY2VsbHMgaW4gdGhhdCBjbHVzdGVyIHRvIG1pc2xlYWQgZG93bnN0cmVhbSBhbmFseXNlcy4gSW4gZmFjdCwgZXZlbiBkZWZpbmluZyBhIHRocmVzaG9sZCBvbiB0aGUgZG91YmxldCBzY29yZSBpcyBkaWZmaWN1bHQgYXMgdGhlIGludGVycHJldGF0aW9uIG9mIHRoZSBzY29yZSBpcyByZWxhdGl2ZS4gVGhlcmUgaXMgbm8gZ2VuZXJhbCBkZWZpbml0aW9uIGZvciBhIGZpeGVkIHRocmVzaG9sZCBhYm92ZSB3aGljaCBsaWJyYXJpZXMgYXJlIHRvIGJlIGNvbnNpZGVyZWQgZG91YmxldHMuCgpXZSByZWNvbW1lbmQgaW50ZXJwcmV0aW5nIHRoZSBkb3VibGV0Q2VsbHMoKSBzY29yZXMgaW4gdGhlIGNvbnRleHQgb2YgY2x1c3RlciBhbm5vdGF0aW9uLiBBbGwgY2VsbHMgZnJvbSBhIGNsdXN0ZXIgd2l0aCBhIGxhcmdlIGF2ZXJhZ2UgZG91YmxldCBzY29yZSBzaG91bGQgYmUgY29uc2lkZXJlZCBzdXNwZWN0LCBhbmQgY2xvc2UgbmVpZ2hib3JzIG9mIHByb2JsZW1hdGljIGNsdXN0ZXJzIHNob3VsZCBhbHNvIGJlIHRyZWF0ZWQgd2l0aCBjYXV0aW9uLiBJbiBjb250cmFzdCwgYSBjbHVzdGVyIGNvbnRhaW5pbmcgYSBzbWFsbCBwcm9wb3J0aW9uIG9mIGhpZ2gtc2NvcmluZyBjZWxscyBpcyBwcm9iYWJseSBzYWZlIHByb3ZpZGVkIHRoYXQgYW55IGludGVyZXN0aW5nIHJlc3VsdHMgYXJlIG5vdCBiZWluZyBkcml2ZW4gYnkgdGhvc2UgY2VsbHMgKGUuZy4sIGNoZWNraW5nIHRoYXQgREUgaW4gYW4gaW50ZXJlc3RpbmcgZ2VuZSBpcyBub3QgZHJpdmVuIHNvbGVseSBieSBjZWxscyB3aXRoIGhpZ2ggZG91YmxldCBzY29yZXMpLiBXaGlsZSBjbHVzdGVyaW5nIGlzIHN0aWxsIHJlcXVpcmVkLCB0aGlzIGFwcHJvYWNoIGlzIG1vcmUgcm9idXN0IHRoYW4gZG91YmxldENsdXN0ZXJzKCkgdG8gdGhlIHF1YWxpdHkgb2YgdGhlIGNsdXN0ZXJpbmcgYXMgdGhlIHNjb3JlcyBhcmUgY29tcHV0ZWQgb24gYSBwZXItY2VsbCBiYXNpcy4KCihBcyBhbiBhc2lkZSwgdGhlIGlzc3VlIG9mIHVua25vd24gY29tYmluaW5nIHByb3BvcnRpb25zIGNhbiBiZSBzb2x2ZWQgY29tcGxldGVseSBpZiBzcGlrZS1pbiBpbmZvcm1hdGlvbiBpcyBhdmFpbGFibGUsIGUuZy4sIGluIHBsYXRlLWJhc2VkIHByb3RvY29scy4gVGhpcyB3aWxsIHByb3ZpZGUgYW4gYWNjdXJhdGUgZXN0aW1hdGUgb2YgdGhlIHRvdGFsIFJOQSBjb250ZW50IG9mIGVhY2ggY2VsbC4gVG8gdGhpcyBlbmQsIHNwaWtlLWluLWJhc2VkIHNpemUgZmFjdG9ycyBmcm9tIFNlY3Rpb24gNy40IGNhbiBiZSBzdXBwbGllZCB0byB0aGUgZG91YmxldENlbGxzKCkgZnVuY3Rpb24gdmlhIHRoZSBzaXplLmZhY3RvcnMuY29udGVudD0gYXJndW1lbnQuIFRoaXMgd2lsbCB1c2UgdGhlIHNwaWtlLWluIHNpemUgZmFjdG9ycyB0byBzY2FsZSB0aGUgY29udHJpYnV0aW9uIG9mIGVhY2ggY2VsbCB0byBhIGRvdWJsZXQgbGlicmFyeS4pCgojI8KgRnVydGhlciBjb21tZW50cwoKRG91YmxldCBkZXRlY3Rpb24gcHJvY2VkdXJlcyBzaG91bGQgb25seSBiZSBhcHBsaWVkIHRvIGxpYnJhcmllcyBnZW5lcmF0ZWQgaW4gdGhlIHNhbWUgZXhwZXJpbWVudGFsIGJhdGNoLiBJdCBpcyBvYnZpb3VzbHkgaW1wb3NzaWJsZSBmb3IgZG91YmxldHMgdG8gZm9ybSBiZXR3ZWVuIHR3byBjZWxscyB0aGF0IHdlcmUgY2FwdHVyZWQgc2VwYXJhdGVseS4gVGh1cywgc29tZSB1bmRlcnN0YW5kaW5nIG9mIHRoZSBleHBlcmltZW50YWwgZGVzaWduIGlzIHJlcXVpcmVkIHByaW9yIHRvIHRoZSB1c2Ugb2YgdGhlIGFib3ZlIGZ1bmN0aW9ucy4gVGhpcyBhdm9pZHMgdW5uZWNlc3NhcnkgY29uY2VybnMgYWJvdXQgdGhlIHZhbGlkaXR5IG9mIGJhdGNoLXNwZWNpZmljIGNsdXN0ZXJzIHRoYXQgY2Fubm90IHBvc3NpYmx5IGNvbnNpc3Qgb2YgZG91YmxldHMuCgpJdCBpcyBhbHNvIGRpZmZpY3VsdCB0byBpbnRlcnByZXQgZG91YmxldCBwcmVkaWN0aW9ucyBpbiBkYXRhIGNvbnRhaW5pbmcgY2VsbHVsYXIgdHJhamVjdG9yaWVzLiBCeSBkZWZpbml0aW9uLCBjZWxscyBpbiB0aGUgbWlkZGxlIG9mIGEgdHJhamVjdG9yeSBhcmUgYWx3YXlzIGludGVybWVkaWF0ZSBiZXR3ZWVuIG90aGVyIGNlbGxzIGFuZCBhcmUgbGlhYmxlIHRvIGJlIGluY29ycmVjdGx5IGRldGVjdGVkIGFzIGRvdWJsZXRzLiBTb21lIHByb3RlY3Rpb24gaXMgcHJvdmlkZWQgYnkgdGhlIG5vbi1saW5lYXIgbmF0dXJlIG9mIG1hbnkgcmVhbCB0cmFqZWN0b3JpZXMsIHdoaWNoIHJlZHVjZXMgdGhlIHJpc2sgb2Ygc2ltdWxhdGVkIGRvdWJsZXRzIGNvaW5jaWRpbmcgd2l0aCByZWFsIGNlbGxzIGluIGRvdWJsZXRDZWxscygpLiBPbmUgY2FuIGFsc28gcHV0IG1vcmUgd2VpZ2h0IG9uIHRoZSByZWxhdGl2ZSBsaWJyYXJ5IHNpemVzIGluIGRvdWJsZXRDbHVzdGVyKCkgaW5zdGVhZCBvZiByZWx5aW5nIHNvbGVseSBvbiBOLCB1bmRlciB0aGUgYXNzdW1wdGlvbiB0aGF0IHN1ZGRlbiBzcGlrZXMgaW4gUk5BIGNvbnRlbnQgYXJlIHVubGlrZWx5IGluIGEgY29udGludW91cyBiaW9sb2dpY2FsIHByb2Nlc3MuCgpUaGUgYmVzdCBzb2x1dGlvbiB0byB0aGUgZG91YmxldCBwcm9ibGVtIGlzIGV4cGVyaW1lbnRhbCAtIHRoYXQgaXMsIHRvIGF2b2lkIGdlbmVyYXRpbmcgdGhlbSBpbiB0aGUgZmlyc3QgcGxhY2UuIFRoaXMgc2hvdWxkIGJlIGEgY29uc2lkZXJhdGlvbiB3aGVuIGRlc2lnbmluZyBzY1JOQS1zZXEgZXhwZXJpbWVudHMsIHdoZXJlIHRoZSBkZXNpcmUgdG8gb2J0YWluIGxhcmdlIG51bWJlcnMgb2YgY2VsbHMgYXQgbWluaW11bSBjb3N0IHNob3VsZCBiZSB3ZWlnaGVkIGFnYWluc3QgdGhlIGdlbmVyYWwgZGV0ZXJpb3JhdGlvbiBpbiBkYXRhIHF1YWxpdHkgYW5kIHJlbGlhYmlsaXR5IHdoZW4gZG91YmxldHMgYmVjb21lIG1vcmUgZnJlcXVlbnQuCg==