Description

This R notebook is a bioinformatics pipeline to map reads from a barcoded transposon library to the genome of a target organism. For background and details regarding the method, see Wetmore at al., mBio, 2015 and Price et al., Nature, 2018). The initial steps of processing next generation sequencing data were directly adapted from Morgan Price’s Feba repository, see also README.md of this repository.

Bash pipeline

Fastq raw data files can be processed as outlined in the README.md documentation for this repository. This creates the barcode mappings and the summary pool files.

cd /path/to/TnSeq-pipe
source/run_tnseq_mapping.sh --pattern H16.* --ref GCF_000009285.1_ASM928v2_genomic

Libraries

library(lattice)
library(latticeExtra)
library(latticetools)
library(tidyverse)
library(stringi)
library(data.table)

Mapping statistics and distribution on genome

The next step is to inspect basic statistics of transposon insertions and their distribution over the genome.

Basic statistics

First read in a pooled data table and display summary statistics. Remove barcodes without mapped position.

# import data
df_pool <- read_tsv("../data/pool/pool.tsv") %>%
  filter(!is.na(pos))

# import reference genome
df_ref <- read_tsv("../ref/GCF_000009285.1_ASM928v2_genomic.gff") %>%
  filter(!duplicated(old_locus_tag))
[1] "Number of total reads: 6029"
Number of total reads: 6029
[1] "Number of unique barcodes: 2309"
Number of unique barcodes: 2309
[1] "Number of barcodes with >= 2 reads: 680"
Number of barcodes with >= 2 reads: 680
[1] "Number of barcodes with >= 10 reads: 112"
Number of barcodes with >= 10 reads: 112
[1] "Number of barcodes with only 1 read: 1629"
Number of barcodes with only 1 read: 1629
[1] "Number of barcodes with > 1 position: 82"
Number of barcodes with > 1 position: 82
[1] "Number of barcodes on -/+ strand: 1181, 1128"
Number of barcodes on -/+ strand: 1181, 1128

Next we can plot the frequency of reads per barcoded transposons.

plot_reads_per_bc <- histogram(~ log2(nTot) | paste("strand:", strand), df_pool,
  par.settings = custom.colorblind(), breaks = 8,
  between = list(x = 0.5, y = 0.5), xlim = c(-0.5, 7.5),
  xlab = expression("log"[2]*" reads per barcode"),
  scales = list(alternating = FALSE),
  panel = function(x, ...) {
    panel.grid(h = -1, v = -1, col = grey(0.9))
    panel.histogram(x, border = "white", ...)
  }
)

print(plot_reads_per_bc)

Distribution over the genome

Read frequency over genome

Each transposon insertion is indexed with a position on the genome. We can now plot insertion frequency over the genome. There are different ways to do that depending on how the data is treated. The most simple case (as done below) is plotting the number of reads per transposon versus its insertion site on the genome, broken down by chromosome type (‘scaffold’).

plot_reads_on_genome <- xyplot(nTot ~ pos | scaffold,
  df_pool %>% arrange(pos),
  par.settings = custom.colorblind(),
  between = list(x = 0.5, y = 0.5),
  layout = c(1,3), type = "l", lwd = 1.5,
  scales = list(alternating = FALSE),
  panel = function(x, y, ...) {
    panel.grid(h = -1, v = -1, col = grey(0.9))
    panel.xyplot(x, y, ...)
  }
)

print(plot_reads_on_genome)

Tn insertion frequency over genome

However this does not really reflect the actual insertion frequency. For the frequency, what matters is the number of different, unique insertions per kb of the genome. We can apply a density function or generate a rolling mean to evaluate frequency. Here, a defined window of 10,000 bp was used, and the sum of Tn insertion events per window was determined.

plot_Tns_on_genome <- df_pool %>% arrange(pos) %>%
  mutate(interval = cut_interval(pos, length = 10000, labels = FALSE)*10000) %>%
  group_by(scaffold, interval) %>%
  summarize(tn_frequency = length(pos)) %>%
  
  xyplot(tn_frequency ~ interval | scaffold, .,
    par.settings = custom.colorblind(),
    ylab = "Tn insertions / 10 kb",
    between = list(x = 0.5, y = 0.5),
    layout = c(1,3), type = "l", lwd = 1.5,
    scales = list(alternating = FALSE),
    panel = function(x, y, ...) {
      panel.grid(h = -1, v = -1, col = grey(0.9))
      panel.xyplot(x, y, ...)
    }
  )

print(plot_Tns_on_genome)

Mapping barcodes to genes

The basic Feba scripts produce a table of barcodes, their frequencies and genomic position information. What we really want to know is how many transposons/barcodes are mapped to each gene, which position within a gene they have, how many barcodes do not map to a gene (intergenic, low importance), and how many genes were not hit by a transposon (probably essential). For this purpose we can use the function foverlaps() from package data.table to map transposon insertion sites to genes (or vice versa). The following part was inspired by previous work of Kyle Kimler (github link).

# prepare input data in form of data tables
dt_pool <- data.table(df_pool)
dt_ref <- data.table(df_ref)

#dummy begin/end columns are created in the pool file to allow foverlap function
dt_pool$begin <- dt_pool$pos
dt_pool$end <- dt_pool$pos

# map Tn insertion sites to genes
setkey(dt_ref, scaffold, begin, end)
df_pool_annotated <- foverlaps(dt_pool, dt_ref, 
    by.x = c("scaffold", "begin", "end"), type = "within") %>%
  as_tibble %>%
  select(!matches("2$|^i\\.[be]")) %>%
  rename(gene_strand = strand, strand = i.strand) %>%
  # exclude alternative mappings in case of overlapping genes
  filter(!duplicated(barcode)) %>%
  # include also unhit genes in main table
  full_join(df_ref) %>%
  # sort by scaffold, then position
  arrange(scaffold, begin)

head(df_pool_annotated)

Gene insertion frequency

Now that all transposons are mapped to genes (if possible), we can calculate basic statistics about how many genes were hit, how many transposons inserted in a gene on average, and how many transposons hit intergenic regions.

Barcodes per gene type

The majority of transposon insertions should take place in gene ORFs. NA are intergenic regions with no annotated function.

df_pool_annotated %>%
  group_by(desc) %>%
  summarize(n_barcodes = sum(!is.na(barcode))) %>%
  mutate(desc = replace_na(desc, "intergenic")) %>%
  arrange(desc(n_barcodes))

Insertions per gene

plot_insertions_per_gene <- df_pool_annotated %>% 
  filter(!is.na(old_locus_tag)) %>%
  group_by(old_locus_tag) %>%
  summarize(n_barcodes = length(unique(barcode))) %>%
  
  histogram( ~ n_barcodes, .,
  par.settings = custom.colorblind(),
  breaks = 10,
  panel = function(x, ...) {
    panel.grid(h = -1, v = -1, col = grey(0.9))
    panel.histogram(x, border = "white", ...)
  }
)

print(plot_insertions_per_gene)


Top 10 genes by number of Tn insertions

df_pool_annotated %>% 
  filter(!is.na(old_locus_tag)) %>%
  group_by(old_locus_tag) %>%
  summarize(n_barcodes = length(unique(barcode))) %>%
  arrange(desc(n_barcodes)) %>% slice(1:10)

Position of transposons within a gene

The mapping of a transposon to a gene also reveals its relative position within the gene. We can use this information to tag insertions as more likely to have a fitness effect, or not. We can also filter out transposons that lie outside the central portion of a gene (e.g. 10% margin to each side), or within a fixed flanking region (e.g. first or last 100 bp). The original FEBA protocol from Morgan Price uses a quality filter that requires transposons be located within the central 80% of a gene. We follow this definition and flag transposons outside the central portion of a gene.

# apply margin of 10% gene length
df_pool_annotated <- df_pool_annotated %>%
  mutate(
    gene_length = end-begin,
    pos_relative = (pos-begin)/(end-begin),
    central = between(pos_relative, 0.1, 0.9)
  )

How many transposons that inserted into a gene are central? We can summarize.

df_pool_annotated %>%
  filter(!is.na(central)) %>%
  group_by(central) %>%
  summarize(frequence = length(pos))

How are insertions distributed over the gene, in relative position? There is a trend towards higher insertion frequency at the termini of genes. Otherwise the insertion frequency is homogeneously distributed.

plot_insertion_position <- df_pool_annotated %>% 
  filter(!is.na(central)) %>%
  
  histogram( ~ pos_relative, .,
  par.settings = custom.colorblind(),
  breaks = 50,
  panel = function(x, ...) {
    panel.grid(h = -1, v = -1, col = grey(0.9))
    panel.histogram(x, border = "white", ...)
  }
)

print(plot_insertion_position)

Export result tables and figures

Export the annotated pool file containing the final barcodes and their locations in the genome.

df_pool_annotated %>% filter(!is.na(barcode)) %>%
  write_tsv("../data/pool/pool_genes.tsv")

Export figures to *.svg image files.

for (plt in grep("^plot_", ls(), value = TRUE)) {
  svg(filename = paste0("../images/", plt, ".svg"), width = 6, height = 4)
    print(get(plt))
  dev.off()
}
LS0tCnRpdGxlOiAiVG5TZXEgLS0gbWFwcGluZyBiYXJjb2RlZCB0cmFuc3Bvc29ucyB0byBnZW5vbWUiCmRhdGU6ICJgciBmb3JtYXQoU3lzLnRpbWUoKSwgJyVkICVCLCAlWScpYCIKYXV0aG9yOiAiTWljaGFlbCBKYWhuIgpvdXRwdXQ6CiAgaHRtbF9ub3RlYm9vazogCiAgICB0aGVtZTogc3BhY2VsYWIKICAgIHRvYzogeWVzCi0tLQoKIyMgRGVzY3JpcHRpb24KClRoaXMgUiBub3RlYm9vayBpcyBhIGJpb2luZm9ybWF0aWNzIHBpcGVsaW5lIHRvIG1hcCByZWFkcyBmcm9tIGEgYmFyY29kZWQgdHJhbnNwb3NvbiBsaWJyYXJ5IHRvIHRoZSBnZW5vbWUgb2YgYSB0YXJnZXQgb3JnYW5pc20uIEZvciBiYWNrZ3JvdW5kIGFuZCBkZXRhaWxzIHJlZ2FyZGluZyB0aGUgbWV0aG9kLCBzZWUgW1dldG1vcmUgYXQgYWwuLCBtQmlvLCAyMDE1XShodHRwczovL21iaW8uYXNtLm9yZy9jb250ZW50LzYvMy9lMDAzMDYtMTUpIGFuZCBbUHJpY2UgZXQgYWwuLCBOYXR1cmUsIDIwMThdKGh0dHA6Ly93d3cubmF0dXJlLmNvbS9hcnRpY2xlcy9zNDE1ODYtMDE4LTAxMjQtMCkpLiBUaGUgaW5pdGlhbCBzdGVwcyBvZiBwcm9jZXNzaW5nIG5leHQgZ2VuZXJhdGlvbiBzZXF1ZW5jaW5nIGRhdGEgd2VyZSBkaXJlY3RseSBhZGFwdGVkIGZyb20gW01vcmdhbiBQcmljZSdzIEZlYmEgcmVwb3NpdG9yeV0oaHR0cHM6Ly9iaXRidWNrZXQub3JnL2JlcmtlbGV5bGFiL2ZlYmEvc3JjL21hc3Rlci8pLCBzZWUgYWxzbyBgUkVBRE1FLm1kYCBvZiB0aGlzIHJlcG9zaXRvcnkuCgojIyBCYXNoIHBpcGVsaW5lCgpgRmFzdHFgIHJhdyBkYXRhIGZpbGVzIGNhbiBiZSBwcm9jZXNzZWQgYXMgb3V0bGluZWQgaW4gdGhlIGBSRUFETUUubWRgIGRvY3VtZW50YXRpb24gZm9yIHRoaXMgcmVwb3NpdG9yeS4gVGhpcyBjcmVhdGVzIHRoZSBiYXJjb2RlIG1hcHBpbmdzIGFuZCB0aGUgc3VtbWFyeSBwb29sIGZpbGVzLgoKYGBge2Jhc2gsIGV2YWwgPSBGQUxTRX0KY2QgL3BhdGgvdG8vVG5TZXEtcGlwZQpzb3VyY2UvcnVuX3Ruc2VxX21hcHBpbmcuc2ggLS1wYXR0ZXJuIEgxNi4qIC0tcmVmIEdDRl8wMDAwMDkyODUuMV9BU005Mjh2Ml9nZW5vbWljCmBgYAoKIyMgTGlicmFyaWVzCgpgYGB7ciwgbWVzc2FnZSA9IEZBTFNFfQpsaWJyYXJ5KGxhdHRpY2UpCmxpYnJhcnkobGF0dGljZUV4dHJhKQpsaWJyYXJ5KGxhdHRpY2V0b29scykKbGlicmFyeSh0aWR5dmVyc2UpCmxpYnJhcnkoc3RyaW5naSkKbGlicmFyeShkYXRhLnRhYmxlKQpgYGAKCiMjIE1hcHBpbmcgc3RhdGlzdGljcyBhbmQgZGlzdHJpYnV0aW9uIG9uIGdlbm9tZQoKVGhlIG5leHQgc3RlcCBpcyB0byBpbnNwZWN0IGJhc2ljIHN0YXRpc3RpY3Mgb2YgdHJhbnNwb3NvbiBpbnNlcnRpb25zIGFuZCB0aGVpciBkaXN0cmlidXRpb24gb3ZlciB0aGUgZ2Vub21lLgoKIyMjIEJhc2ljIHN0YXRpc3RpY3MKCkZpcnN0IHJlYWQgaW4gYSBwb29sZWQgZGF0YSB0YWJsZSBhbmQgZGlzcGxheSBzdW1tYXJ5IHN0YXRpc3RpY3MuIFJlbW92ZSBiYXJjb2RlcyB3aXRob3V0IG1hcHBlZCBwb3NpdGlvbi4KCmBgYHtyLCBtZXNzYWdlID0gRkFMU0V9CiMgaW1wb3J0IGRhdGEKZGZfcG9vbCA8LSByZWFkX3RzdigiLi4vZGF0YS9wb29sL3Bvb2wudHN2IikgJT4lCiAgZmlsdGVyKCFpcy5uYShwb3MpKQoKIyBpbXBvcnQgcmVmZXJlbmNlIGdlbm9tZQpkZl9yZWYgPC0gcmVhZF90c3YoIi4uL3JlZi9HQ0ZfMDAwMDA5Mjg1LjFfQVNNOTI4djJfZ2Vub21pYy5nZmYiKSAlPiUKICBmaWx0ZXIoIWR1cGxpY2F0ZWQob2xkX2xvY3VzX3RhZykpCmBgYAoKCmBgYHtyLCBlY2hvID0gRkFMU0UsIG1lc3NhZ2UgPSBGQUxTRX0KcGFzdGUoIk51bWJlciBvZiB0b3RhbCByZWFkczoiLCBzdW0oZGZfcG9vbCRuVG90KSkKcGFzdGUoIk51bWJlciBvZiB1bmlxdWUgYmFyY29kZXM6IiwgbnJvdyhkZl9wb29sKSkKcGFzdGUoIk51bWJlciBvZiBiYXJjb2RlcyB3aXRoID49IDIgcmVhZHM6IiwgZGZfcG9vbCAlPiUgZmlsdGVyKG5Ub3QgPj0gMikgJT4lIG5yb3cpCnBhc3RlKCJOdW1iZXIgb2YgYmFyY29kZXMgd2l0aCA+PSAxMCByZWFkczoiLCBkZl9wb29sICU+JSBmaWx0ZXIoblRvdCA+PSAxMCkgJT4lIG5yb3cpCnBhc3RlKCJOdW1iZXIgb2YgYmFyY29kZXMgd2l0aCBvbmx5IDEgcmVhZDoiLCBkZl9wb29sICU+JSBmaWx0ZXIoblRvdCA9PSAxKSAlPiUgbnJvdykKcGFzdGUoIk51bWJlciBvZiBiYXJjb2RlcyB3aXRoID4gMSBwb3NpdGlvbjoiLCBkZl9wb29sICU+JSBmaWx0ZXIobjIgPiAwKSAlPiUgbnJvdykKcGFzdGUoIk51bWJlciBvZiBiYXJjb2RlcyBvbiAtLysgc3RyYW5kOiIsIGRmX3Bvb2wgJT4lIGdyb3VwX2J5KHN0cmFuZCkgJT4lCiAgc3VtbWFyaXplKG4gPSBsZW5ndGgobikpICU+JSBwdWxsKG4pICU+JSBwYXN0ZShjb2xsYXBzZSA9ICIsICIpKQpgYGAKCk5leHQgd2UgY2FuIHBsb3QgdGhlIGZyZXF1ZW5jeSBvZiByZWFkcyBwZXIgYmFyY29kZWQgdHJhbnNwb3NvbnMuCgpgYGB7ciwgbWVzc2FnZSA9IEZBTFNFfQpwbG90X3JlYWRzX3Blcl9iYyA8LSBoaXN0b2dyYW0ofiBsb2cyKG5Ub3QpIHwgcGFzdGUoInN0cmFuZDoiLCBzdHJhbmQpLCBkZl9wb29sLAogIHBhci5zZXR0aW5ncyA9IGN1c3RvbS5jb2xvcmJsaW5kKCksIGJyZWFrcyA9IDgsCiAgYmV0d2VlbiA9IGxpc3QoeCA9IDAuNSwgeSA9IDAuNSksIHhsaW0gPSBjKC0wLjUsIDcuNSksCiAgeGxhYiA9IGV4cHJlc3Npb24oImxvZyJbMl0qIiByZWFkcyBwZXIgYmFyY29kZSIpLAogIHNjYWxlcyA9IGxpc3QoYWx0ZXJuYXRpbmcgPSBGQUxTRSksCiAgcGFuZWwgPSBmdW5jdGlvbih4LCAuLi4pIHsKICAgIHBhbmVsLmdyaWQoaCA9IC0xLCB2ID0gLTEsIGNvbCA9IGdyZXkoMC45KSkKICAgIHBhbmVsLmhpc3RvZ3JhbSh4LCBib3JkZXIgPSAid2hpdGUiLCAuLi4pCiAgfQopCgpwcmludChwbG90X3JlYWRzX3Blcl9iYykKYGBgCgoKIyMjIERpc3RyaWJ1dGlvbiBvdmVyIHRoZSBnZW5vbWUKCioqUmVhZCBmcmVxdWVuY3kgb3ZlciBnZW5vbWUqKgoKRWFjaCB0cmFuc3Bvc29uIGluc2VydGlvbiBpcyBpbmRleGVkIHdpdGggYSBwb3NpdGlvbiBvbiB0aGUgZ2Vub21lLiBXZSBjYW4gbm93IHBsb3QgaW5zZXJ0aW9uIGZyZXF1ZW5jeSBvdmVyIHRoZSBnZW5vbWUuIFRoZXJlIGFyZSBkaWZmZXJlbnQgd2F5cyB0byBkbyB0aGF0IGRlcGVuZGluZyBvbiBob3cgdGhlIGRhdGEgaXMgdHJlYXRlZC4gVGhlIG1vc3Qgc2ltcGxlIGNhc2UgKGFzIGRvbmUgYmVsb3cpIGlzIHBsb3R0aW5nIHRoZSBudW1iZXIgb2YgcmVhZHMgcGVyIHRyYW5zcG9zb24gdmVyc3VzIGl0cyBpbnNlcnRpb24gc2l0ZSBvbiB0aGUgZ2Vub21lLCBicm9rZW4gZG93biBieSBjaHJvbW9zb21lIHR5cGUgKCdzY2FmZm9sZCcpLgoKYGBge3J9CnBsb3RfcmVhZHNfb25fZ2Vub21lIDwtIHh5cGxvdChuVG90IH4gcG9zIHwgc2NhZmZvbGQsCiAgZGZfcG9vbCAlPiUgYXJyYW5nZShwb3MpLAogIHBhci5zZXR0aW5ncyA9IGN1c3RvbS5jb2xvcmJsaW5kKCksCiAgYmV0d2VlbiA9IGxpc3QoeCA9IDAuNSwgeSA9IDAuNSksCiAgbGF5b3V0ID0gYygxLDMpLCB0eXBlID0gImwiLCBsd2QgPSAxLjUsCiAgc2NhbGVzID0gbGlzdChhbHRlcm5hdGluZyA9IEZBTFNFKSwKICBwYW5lbCA9IGZ1bmN0aW9uKHgsIHksIC4uLikgewogICAgcGFuZWwuZ3JpZChoID0gLTEsIHYgPSAtMSwgY29sID0gZ3JleSgwLjkpKQogICAgcGFuZWwueHlwbG90KHgsIHksIC4uLikKICB9CikKCnByaW50KHBsb3RfcmVhZHNfb25fZ2Vub21lKQpgYGAKCioqVG4gaW5zZXJ0aW9uIGZyZXF1ZW5jeSBvdmVyIGdlbm9tZSoqCgpIb3dldmVyIHRoaXMgZG9lcyBub3QgcmVhbGx5IHJlZmxlY3QgdGhlIGFjdHVhbCBpbnNlcnRpb24gKmZyZXF1ZW5jeSouIEZvciB0aGUgZnJlcXVlbmN5LCB3aGF0IG1hdHRlcnMgaXMgdGhlIG51bWJlciBvZiBkaWZmZXJlbnQsIHVuaXF1ZSBpbnNlcnRpb25zIHBlciBrYiBvZiB0aGUgZ2Vub21lLiBXZSBjYW4gYXBwbHkgYSBkZW5zaXR5IGZ1bmN0aW9uIG9yIGdlbmVyYXRlIGEgcm9sbGluZyBtZWFuIHRvIGV2YWx1YXRlIGZyZXF1ZW5jeS4gSGVyZSwgYSBkZWZpbmVkIHdpbmRvdyBvZiAxMCwwMDAgYnAgd2FzIHVzZWQsIGFuZCB0aGUgc3VtIG9mIFRuIGluc2VydGlvbiBldmVudHMgcGVyIHdpbmRvdyB3YXMgZGV0ZXJtaW5lZC4KCmBgYHtyLCBtZXNzYWdlID0gRkFMU0V9CnBsb3RfVG5zX29uX2dlbm9tZSA8LSBkZl9wb29sICU+JSBhcnJhbmdlKHBvcykgJT4lCiAgbXV0YXRlKGludGVydmFsID0gY3V0X2ludGVydmFsKHBvcywgbGVuZ3RoID0gMTAwMDAsIGxhYmVscyA9IEZBTFNFKSoxMDAwMCkgJT4lCiAgZ3JvdXBfYnkoc2NhZmZvbGQsIGludGVydmFsKSAlPiUKICBzdW1tYXJpemUodG5fZnJlcXVlbmN5ID0gbGVuZ3RoKHBvcykpICU+JQogIAogIHh5cGxvdCh0bl9mcmVxdWVuY3kgfiBpbnRlcnZhbCB8IHNjYWZmb2xkLCAuLAogICAgcGFyLnNldHRpbmdzID0gY3VzdG9tLmNvbG9yYmxpbmQoKSwKICAgIHlsYWIgPSAiVG4gaW5zZXJ0aW9ucyAvIDEwIGtiIiwKICAgIGJldHdlZW4gPSBsaXN0KHggPSAwLjUsIHkgPSAwLjUpLAogICAgbGF5b3V0ID0gYygxLDMpLCB0eXBlID0gImwiLCBsd2QgPSAxLjUsCiAgICBzY2FsZXMgPSBsaXN0KGFsdGVybmF0aW5nID0gRkFMU0UpLAogICAgcGFuZWwgPSBmdW5jdGlvbih4LCB5LCAuLi4pIHsKICAgICAgcGFuZWwuZ3JpZChoID0gLTEsIHYgPSAtMSwgY29sID0gZ3JleSgwLjkpKQogICAgICBwYW5lbC54eXBsb3QoeCwgeSwgLi4uKQogICAgfQogICkKCnByaW50KHBsb3RfVG5zX29uX2dlbm9tZSkKYGBgCgojIyMgTWFwcGluZyBiYXJjb2RlcyB0byBnZW5lcwoKClRoZSBiYXNpYyBGZWJhIHNjcmlwdHMgcHJvZHVjZSBhIHRhYmxlIG9mIGJhcmNvZGVzLCB0aGVpciBmcmVxdWVuY2llcyBhbmQgZ2Vub21pYyBwb3NpdGlvbiBpbmZvcm1hdGlvbi4gV2hhdCB3ZSByZWFsbHkgd2FudCB0byBrbm93IGlzICoqaG93IG1hbnkgdHJhbnNwb3NvbnMvYmFyY29kZXMgYXJlIG1hcHBlZCB0byBlYWNoIGdlbmUsIHdoaWNoIHBvc2l0aW9uIHdpdGhpbiBhIGdlbmUgdGhleSBoYXZlLCBob3cgbWFueSBiYXJjb2RlcyBkbyBub3QgbWFwIHRvIGEgZ2VuZSAoaW50ZXJnZW5pYywgbG93IGltcG9ydGFuY2UpLCBhbmQgaG93IG1hbnkgZ2VuZXMgd2VyZSBub3QgaGl0IGJ5IGEgdHJhbnNwb3NvbiAocHJvYmFibHkgZXNzZW50aWFsKSoqLiBGb3IgdGhpcyBwdXJwb3NlIHdlIGNhbiB1c2UgdGhlIGZ1bmN0aW9uIGBmb3ZlcmxhcHMoKWAgZnJvbSBwYWNrYWdlIGBkYXRhLnRhYmxlYCB0byBtYXAgdHJhbnNwb3NvbiBpbnNlcnRpb24gc2l0ZXMgdG8gZ2VuZXMgKG9yIHZpY2UgdmVyc2EpLiBUaGUgZm9sbG93aW5nIHBhcnQgd2FzIGluc3BpcmVkIGJ5IHByZXZpb3VzIHdvcmsgb2YgS3lsZSBLaW1sZXIgKFtnaXRodWIgbGlua10oaHR0cHM6Ly9naXRodWIuY29tL2t5bGVraW1sZXIvKSkuCgpgYGB7ciwgbWVzc2FnZSA9IEZBTFNFfQojIHByZXBhcmUgaW5wdXQgZGF0YSBpbiBmb3JtIG9mIGRhdGEgdGFibGVzCmR0X3Bvb2wgPC0gZGF0YS50YWJsZShkZl9wb29sKQpkdF9yZWYgPC0gZGF0YS50YWJsZShkZl9yZWYpCgojZHVtbXkgYmVnaW4vZW5kIGNvbHVtbnMgYXJlIGNyZWF0ZWQgaW4gdGhlIHBvb2wgZmlsZSB0byBhbGxvdyBmb3ZlcmxhcCBmdW5jdGlvbgpkdF9wb29sJGJlZ2luIDwtIGR0X3Bvb2wkcG9zCmR0X3Bvb2wkZW5kIDwtIGR0X3Bvb2wkcG9zCgojIG1hcCBUbiBpbnNlcnRpb24gc2l0ZXMgdG8gZ2VuZXMKc2V0a2V5KGR0X3JlZiwgc2NhZmZvbGQsIGJlZ2luLCBlbmQpCmRmX3Bvb2xfYW5ub3RhdGVkIDwtIGZvdmVybGFwcyhkdF9wb29sLCBkdF9yZWYsIAogICAgYnkueCA9IGMoInNjYWZmb2xkIiwgImJlZ2luIiwgImVuZCIpLCB0eXBlID0gIndpdGhpbiIpICU+JQogIGFzX3RpYmJsZSAlPiUKICBzZWxlY3QoIW1hdGNoZXMoIjIkfF5pXFwuW2JlXSIpKSAlPiUKICByZW5hbWUoZ2VuZV9zdHJhbmQgPSBzdHJhbmQsIHN0cmFuZCA9IGkuc3RyYW5kKSAlPiUKICAjIGV4Y2x1ZGUgYWx0ZXJuYXRpdmUgbWFwcGluZ3MgaW4gY2FzZSBvZiBvdmVybGFwcGluZyBnZW5lcwogIGZpbHRlcighZHVwbGljYXRlZChiYXJjb2RlKSkgJT4lCiAgIyBpbmNsdWRlIGFsc28gdW5oaXQgZ2VuZXMgaW4gbWFpbiB0YWJsZQogIGZ1bGxfam9pbihkZl9yZWYpICU+JQogICMgc29ydCBieSBzY2FmZm9sZCwgdGhlbiBwb3NpdGlvbgogIGFycmFuZ2Uoc2NhZmZvbGQsIGJlZ2luKQoKaGVhZChkZl9wb29sX2Fubm90YXRlZCkKYGBgCgojIyMgR2VuZSBpbnNlcnRpb24gZnJlcXVlbmN5CgpOb3cgdGhhdCBhbGwgdHJhbnNwb3NvbnMgYXJlIG1hcHBlZCB0byBnZW5lcyAoaWYgcG9zc2libGUpLCB3ZSBjYW4gY2FsY3VsYXRlIGJhc2ljIHN0YXRpc3RpY3MgYWJvdXQgaG93IG1hbnkgZ2VuZXMgd2VyZSBoaXQsIGhvdyBtYW55IHRyYW5zcG9zb25zIGluc2VydGVkIGluIGEgZ2VuZSBvbiBhdmVyYWdlLCBhbmQgaG93IG1hbnkgdHJhbnNwb3NvbnMgaGl0IGludGVyZ2VuaWMgcmVnaW9ucy4KCioqQmFyY29kZXMgcGVyIGdlbmUgdHlwZSoqCgpUaGUgbWFqb3JpdHkgb2YgdHJhbnNwb3NvbiBpbnNlcnRpb25zIHNob3VsZCB0YWtlIHBsYWNlIGluIGdlbmUgT1JGcy4gYE5BYCBhcmUgaW50ZXJnZW5pYyByZWdpb25zIHdpdGggbm8gYW5ub3RhdGVkIGZ1bmN0aW9uLgoKYGBge3IsIG1lc3NhZ2UgPSBGQUxTRX0KZGZfcG9vbF9hbm5vdGF0ZWQgJT4lCiAgZ3JvdXBfYnkoZGVzYykgJT4lCiAgc3VtbWFyaXplKG5fYmFyY29kZXMgPSBzdW0oIWlzLm5hKGJhcmNvZGUpKSkgJT4lCiAgbXV0YXRlKGRlc2MgPSByZXBsYWNlX25hKGRlc2MsICJpbnRlcmdlbmljIikpICU+JQogIGFycmFuZ2UoZGVzYyhuX2JhcmNvZGVzKSkKYGBgCgotLS0tLS0tLS0tCgoqKkluc2VydGlvbnMgcGVyIGdlbmUqKgoKYGBge3IsIG1lc3NhZ2UgPSBGQUxTRX0KcGxvdF9pbnNlcnRpb25zX3Blcl9nZW5lIDwtIGRmX3Bvb2xfYW5ub3RhdGVkICU+JSAKICBmaWx0ZXIoIWlzLm5hKG9sZF9sb2N1c190YWcpKSAlPiUKICBncm91cF9ieShvbGRfbG9jdXNfdGFnKSAlPiUKICBzdW1tYXJpemUobl9iYXJjb2RlcyA9IGxlbmd0aCh1bmlxdWUoYmFyY29kZSkpKSAlPiUKICAKICBoaXN0b2dyYW0oIH4gbl9iYXJjb2RlcywgLiwKICBwYXIuc2V0dGluZ3MgPSBjdXN0b20uY29sb3JibGluZCgpLAogIGJyZWFrcyA9IDEwLAogIHBhbmVsID0gZnVuY3Rpb24oeCwgLi4uKSB7CiAgICBwYW5lbC5ncmlkKGggPSAtMSwgdiA9IC0xLCBjb2wgPSBncmV5KDAuOSkpCiAgICBwYW5lbC5oaXN0b2dyYW0oeCwgYm9yZGVyID0gIndoaXRlIiwgLi4uKQogIH0KKQoKcHJpbnQocGxvdF9pbnNlcnRpb25zX3Blcl9nZW5lKQpgYGAKCi0tLS0tLS0tLS0KCioqVG9wIDEwIGdlbmVzIGJ5IG51bWJlciBvZiBUbiBpbnNlcnRpb25zKioKCmBgYHtyLCBtZXNzYWdlID0gRkFMU0V9CmRmX3Bvb2xfYW5ub3RhdGVkICU+JSAKICBmaWx0ZXIoIWlzLm5hKG9sZF9sb2N1c190YWcpKSAlPiUKICBncm91cF9ieShvbGRfbG9jdXNfdGFnKSAlPiUKICBzdW1tYXJpemUobl9iYXJjb2RlcyA9IGxlbmd0aCh1bmlxdWUoYmFyY29kZSkpKSAlPiUKICBhcnJhbmdlKGRlc2Mobl9iYXJjb2RlcykpICU+JSBzbGljZSgxOjEwKQpgYGAKCgojIyMgUG9zaXRpb24gb2YgdHJhbnNwb3NvbnMgd2l0aGluIGEgZ2VuZQoKVGhlIG1hcHBpbmcgb2YgYSB0cmFuc3Bvc29uIHRvIGEgZ2VuZSBhbHNvIHJldmVhbHMgaXRzIHJlbGF0aXZlIHBvc2l0aW9uIHdpdGhpbiB0aGUgZ2VuZS4gV2UgY2FuIHVzZSB0aGlzIGluZm9ybWF0aW9uIHRvIHRhZyBpbnNlcnRpb25zIGFzIG1vcmUgbGlrZWx5IHRvIGhhdmUgYSBmaXRuZXNzIGVmZmVjdCwgb3Igbm90LiBXZSBjYW4gYWxzbyBmaWx0ZXIgb3V0IHRyYW5zcG9zb25zIHRoYXQgbGllIG91dHNpZGUgdGhlIGNlbnRyYWwgcG9ydGlvbiBvZiBhIGdlbmUgKGUuZy4gMTAlIG1hcmdpbiB0byBlYWNoIHNpZGUpLCBvciB3aXRoaW4gYSBmaXhlZCBmbGFua2luZyByZWdpb24gKGUuZy4gZmlyc3Qgb3IgbGFzdCAxMDAgYnApLiBUaGUgb3JpZ2luYWwgRkVCQSBwcm90b2NvbCBmcm9tIE1vcmdhbiBQcmljZSB1c2VzIGEgcXVhbGl0eSBmaWx0ZXIgdGhhdCByZXF1aXJlcyB0cmFuc3Bvc29ucyBiZSBsb2NhdGVkIHdpdGhpbiB0aGUgY2VudHJhbCA4MCUgb2YgYSBnZW5lLiBXZSBmb2xsb3cgdGhpcyBkZWZpbml0aW9uIGFuZCBmbGFnIHRyYW5zcG9zb25zIG91dHNpZGUgdGhlIGNlbnRyYWwgcG9ydGlvbiBvZiBhIGdlbmUuCgpgYGB7cn0KIyBhcHBseSBtYXJnaW4gb2YgMTAlIGdlbmUgbGVuZ3RoCmRmX3Bvb2xfYW5ub3RhdGVkIDwtIGRmX3Bvb2xfYW5ub3RhdGVkICU+JQogIG11dGF0ZSgKICAgIGdlbmVfbGVuZ3RoID0gZW5kLWJlZ2luLAogICAgcG9zX3JlbGF0aXZlID0gKHBvcy1iZWdpbikvKGVuZC1iZWdpbiksCiAgICBjZW50cmFsID0gYmV0d2Vlbihwb3NfcmVsYXRpdmUsIDAuMSwgMC45KQogICkKYGBgCgotLS0tLS0tLS0tCgpIb3cgbWFueSB0cmFuc3Bvc29ucyB0aGF0IGluc2VydGVkIGludG8gYSBnZW5lIGFyZSBjZW50cmFsPyBXZSBjYW4gc3VtbWFyaXplLgoKYGBge3IsIG1lc3NhZ2UgPSBGQUxTRX0KZGZfcG9vbF9hbm5vdGF0ZWQgJT4lCiAgZmlsdGVyKCFpcy5uYShjZW50cmFsKSkgJT4lCiAgZ3JvdXBfYnkoY2VudHJhbCkgJT4lCiAgc3VtbWFyaXplKGZyZXF1ZW5jZSA9IGxlbmd0aChwb3MpKQpgYGAKCi0tLS0tLS0tLS0KCkhvdyBhcmUgaW5zZXJ0aW9ucyBkaXN0cmlidXRlZCBvdmVyIHRoZSBnZW5lLCBpbiByZWxhdGl2ZSBwb3NpdGlvbj8gVGhlcmUgaXMgYSB0cmVuZCB0b3dhcmRzIGhpZ2hlciBpbnNlcnRpb24gZnJlcXVlbmN5IGF0IHRoZSB0ZXJtaW5pIG9mIGdlbmVzLiBPdGhlcndpc2UgdGhlIGluc2VydGlvbiBmcmVxdWVuY3kgaXMgaG9tb2dlbmVvdXNseSBkaXN0cmlidXRlZC4KCmBgYHtyfQpwbG90X2luc2VydGlvbl9wb3NpdGlvbiA8LSBkZl9wb29sX2Fubm90YXRlZCAlPiUgCiAgZmlsdGVyKCFpcy5uYShjZW50cmFsKSkgJT4lCiAgCiAgaGlzdG9ncmFtKCB+IHBvc19yZWxhdGl2ZSwgLiwKICBwYXIuc2V0dGluZ3MgPSBjdXN0b20uY29sb3JibGluZCgpLAogIGJyZWFrcyA9IDUwLAogIHBhbmVsID0gZnVuY3Rpb24oeCwgLi4uKSB7CiAgICBwYW5lbC5ncmlkKGggPSAtMSwgdiA9IC0xLCBjb2wgPSBncmV5KDAuOSkpCiAgICBwYW5lbC5oaXN0b2dyYW0oeCwgYm9yZGVyID0gIndoaXRlIiwgLi4uKQogIH0KKQoKcHJpbnQocGxvdF9pbnNlcnRpb25fcG9zaXRpb24pCmBgYAoKCiMjIEV4cG9ydCByZXN1bHQgdGFibGVzIGFuZCBmaWd1cmVzCgpFeHBvcnQgdGhlIGFubm90YXRlZCBwb29sIGZpbGUgY29udGFpbmluZyB0aGUgZmluYWwgYmFyY29kZXMgYW5kIHRoZWlyIGxvY2F0aW9ucyBpbiB0aGUgZ2Vub21lLgoKYGBge3J9CmRmX3Bvb2xfYW5ub3RhdGVkICU+JSBmaWx0ZXIoIWlzLm5hKGJhcmNvZGUpKSAlPiUKICB3cml0ZV90c3YoIi4uL2RhdGEvcG9vbC9wb29sX2dlbmVzLnRzdiIpCmBgYAoKRXhwb3J0IGZpZ3VyZXMgdG8gYCouc3ZnYCBpbWFnZSBmaWxlcy4KCmBgYHtyfQpmb3IgKHBsdCBpbiBncmVwKCJecGxvdF8iLCBscygpLCB2YWx1ZSA9IFRSVUUpKSB7CiAgc3ZnKGZpbGVuYW1lID0gcGFzdGUwKCIuLi9pbWFnZXMvIiwgcGx0LCAiLnN2ZyIpLCB3aWR0aCA9IDYsIGhlaWdodCA9IDQpCiAgICBwcmludChnZXQocGx0KSkKICBkZXYub2ZmKCkKfQpgYGAKCg==