library(dplyr)
library(tidyr)
library(ggplot2)
mean_fragment_length = 300

counts = tibble(Gene = c('A', 'B', 'C', 'D'),
                Length = c(700, 700, 800, 800),
                Control = c(40, 20, 30, 40),
                Treatment = c(20, 20, 30, 40) * 2) %>%
    gather(Library, Count, -Gene, -Length) %>%
    mutate(EffectiveLength = Length - mean_fragment_length + 1)

counts
gene_colors = c(A = 'dodgerblue2', B = 'darkgrey', C = 'darkgrey', D = 'darkgrey')

RNA-seq gene expression by counts

ggplot(counts, aes(x = Gene, y = Count, fill = Gene)) +
    geom_bar(stat = 'identity') +
    facet_wrap(~ Library) +
    scale_fill_manual(values = gene_colors, guide = FALSE) +
    labs(y = 'Sequenced fragments') +
    nogrid()


But: we don’t want
fragments per library.

We want
RNA molecules per cell.

Library size effect

ggplot(counts, aes(x = Library, y = Count, fill = Gene)) +
    geom_bar(stat = 'sum') +
    scale_fill_manual(values = gene_colors) +
    labs(y = 'Sequenced fragments') +
    nogrid() +
    theme(legend.position = 'none')

RNA-seq gene expression as fractions

# FIXME: Direction should be clockwise but `direction = 1` does anticlockwise
# on my computer. But labels are clockwise?!
counts %>%
    group_by(Library) %>%
    mutate(Fraction = Count / sum(Count)) %>%
    mutate(LabelPos = sum(Fraction) - (cumsum(Fraction) - Fraction / 2)) %>%
    ggplot(aes(x = '', y = Fraction, fill = Gene)) +
    geom_bar(stat = 'identity', width = 1, color = 'white') +
    geom_text(aes(y = LabelPos, label = Gene)) +
    pie_chart() +
    facet_wrap(~ Library) +
    scale_fill_manual(values = gene_colors, guide = FALSE) +
    labs(x = '', y = 'Fraction of RNA molecules')

Sources of variability

Transcript length

tlen = 22
flen = 10
gap = 0.3
transcript = tibble(xmin = 1, ymin = 1, xmax = tlen, ymax = 2, type = 'transcript')
fragments = tibble(xmin = seq(1, tlen - flen), ymin = xmin * (1 + gap) + 1,
                   xmax = xmin + flen, ymax = ymin + 1, type = 'fragment')

annotate_equation = function (x, y, label)
    annotate('text', x = x, y = y, label = label, parse = TRUE,
             size = 8, family = 'Times New Roman')

ggplot(bind_rows(transcript, fragments),
       aes(xmin = xmin, ymin = ymin, xmax = xmax, ymax = ymax, fill = type)) +
    geom_rect() +
    coord_cartesian(xlim = c(-1.5, tlen), ylim = c(-3, tail(fragments$ymax, 1))) +
    annotation_custom(brackets(0.135, 0.28, 0.135, 1, h = 0.1, lwd = 2)) +
    annotate_equation(-1.5, 11, 'italic(l)[plain(eff)]') +
    annotation_custom(brackets(0.145, 0.21, 0.95, 0.21, h = -0.1, lwd = 2)) +
    annotate_equation(11.4, -2.9, 'italic(l)') +
    annotation_custom(brackets(0.145, 0.34, 0.526, 0.34, h = 0.1, lwd = 2)) +
    annotate_equation(6.15, 7.5, 'italic(bar(n))') +
    scale_fill_manual(values = c(transcript = 'darkolivegreen4', fragment = 'darkgrey')) +
    theme(panel.grid = element_blank(),
          legend.position = 'none',
          axis.title = element_blank(),
          axis.text = element_blank())

\[ \large l_\text{eff} = l - \bar{n} + 1 \]


Different transcript lengths lead to different expected fragment counts

transcripts = IRanges::IRanges(start = c(1, 22), width = c(20, 40))

fstarts = IRanges::resize(transcripts, IRanges::width(transcripts) - flen + 1) %>%
    IRanges::coverage() %>%
    {seq_along(.)[as.integer(.) == 1]}

set.seed(1234)
fragments = IRanges::IRanges(start = sample(fstarts, 9), width = flen)
fragment_data = fragments %>%
    as.data.frame() %>%
    mutate(bin = IRanges::disjointBins(fragments), type = 'read')
transcripts %>%
    as.data.frame() %>%
    mutate(bin = 0, type = c('a', 'b')) %>%
    bind_rows(fragment_data) %>%
    mutate(ymin = bin * (1 + gap), ymax = ymin + 1) %>%
    ggplot(aes(xmin = start, ymin = ymin, xmax = end, ymax = ymax, fill = type)) +
    geom_rect() +
    scale_fill_manual(values = c(a = 'darkolivegreen4', b = 'dodgerblue3', read = 'darkgrey')) +
    theme(panel.grid = element_blank(),
          legend.position = 'none',
          axis.title = element_blank(),
          axis.text = element_blank())

To review

RNA-seq count is influenced by


TPM (transcripts per millions): Given a million RNA fragments, how many fragments of a given transcript do we see?

→ TPM is a relative fraction, not absolute expression


\[ \large \text{TPM}_\color{orchid}i = {\color{dodgerblue}{\frac{x_\color{orchid}i}{{l_\text{eff}}_\color{orchid}i}}} \cdot \frac{1}{\sum_\color{tomato}j \color{dodgerblue}{\frac{x_\color{tomato}j}{{l_\text{eff}}_\color{tomato}j}}} \cdot \color{darkcyan}{10^6} \]

tpm = function (counts, effective_lengths) {
    rate = log(counts) - log(effective_lengths)
    exp(rate - log(sum(exp(rate))) + log(10 ^ 6))
}
tpms = counts %>%
    group_by(Library) %>%
    mutate(TPM = tpm(Count, EffectiveLength))

tpms

RNA-seq gene expression in TPM

tpm_plot = ggplot(tpms, aes(x = Gene, y = TPM, fill = Gene)) +
    geom_bar(stat = 'identity') +
    facet_wrap(~ Library) +
    scale_fill_manual(values = gene_colors, guide = FALSE) +
    labs(y = 'TPM') +
    nogrid()

tpm_plot


Cross-library normalisation

Fundamental assumption:

Most transcripts are not differentially expressed.


size_factors_ = function (counts, genes, experiment) {
    counts %>%
        group_by_(genes) %>%
        mutate(LogGeomMean = mean(log(Count))) %>%
        group_by_(experiment) %>%
        mutate(SF = exp(median(log(Count) - LogGeomMean)))
}

size_factors = function (counts, genes, experiment) {
    size_factors_(counts, lazyeval::lazy(genes), lazyeval::lazy(experiment))
}

norm_counts = counts %>%
    size_factors(Gene, Library) %>%
    mutate(Count = Count / SF)

norm_counts
# TPM plot again, for comparison
tpm_plot %+% mutate(tpms, TPM = TPM / 10000) + ylab('') + ggtitle('TPM / 10000')

ggplot(norm_counts, aes(Gene, Count, fill = Gene)) +
    geom_bar(stat = 'identity') +
    facet_wrap(~ Library) +
    scale_fill_manual(values = gene_colors, guide = FALSE) +
    ylab('') +
    ggtitle('Count / DESeq size factors') +
    nogrid()

Literature

Supplementary material

Legacy normalisation methods

  • CPM = RPM = {counts/reads} per million

    \[ \text{CPM}_i = x_i \cdot \frac{1}{\sum_j x_j} \cdot 10^6 \]

    👎 Does not account for differences in transcript length

  • RPKM = FPKM = {reads/fragments} per kilobase per million

    \[ \text{FPKM}_i = \frac{x_i}{{l_\text{eff}}_i} \cdot \frac{1}{\sum_j x_j} \cdot 10^6 \cdot 10^3 \]

    👎 Has different scaling factors for each RNA-seq library

LS0tCnRpdGxlOiAiUk5BLXNlcSBleHByZXNzaW9uIG5vcm1hbGlzYXRpb24iCmF1dGhvcjogIktvbnJhZCBSdWRvbHBoICg8YSBocmVmPSdodHRwczovL3R3aXR0ZXIuY29tL2tsbXInPkBrbG1yPC9hPikiCm91dHB1dDoKICBodG1sX25vdGVib29rOgogICAgdGhlbWU6IGNvc21vCiAgICBoaWdobGlnaHQ6IHRhbmdvCiAgcmV2ZWFsanM6OnJldmVhbGpzX3ByZXNlbnRhdGlvbjoKICAgIGNlbnRlcjogeWVzCiAgICBjc3M6IHByZXNlbnRhdGlvbi5jc3MKICAgIGluY3JlbWVudGFsOiB5ZXMKICAgIHRoZW1lOiBsZWFndWUKICAgIHRyYW5zaXRpb246IG5vbmUKLS0tCgpgYGB7ciBrbml0ci1zZXR1cCwgZWNobz1GQUxTRX0KcHJlc2VudGF0aW9uX21vZGUgPSBpZGVudGljYWwoa25pdHI6Om9wdHNfa25pdCRnZXQoJ3JtYXJrZG93bi5wYW5kb2MudG8nKSwgJ3JldmVhbGpzJykKCmtuaXRyOjpvcHRzX2NodW5rJHNldChmaWcucGF0aCA9ICdmaWd1cmVzLycsCiAgICAgICAgICAgICAgICAgICAgICBmaWcud2lkdGggPSAzLAogICAgICAgICAgICAgICAgICAgICAgZmlnLmhlaWdodCA9IDMsCiAgICAgICAgICAgICAgICAgICAgICBkZXYgPSAncG5nJywKICAgICAgICAgICAgICAgICAgICAgIGRwaSA9IDEwMCwKICAgICAgICAgICAgICAgICAgICAgIGVjaG8gPSAhIHByZXNlbnRhdGlvbl9tb2RlLAogICAgICAgICAgICAgICAgICAgICAgcmVzdWx0cyA9IGlmIChwcmVzZW50YXRpb25fbW9kZSkgJ2hpZGUnIGVsc2UgJ21hcmt1cCcpCmBgYAoKYGBge3Igc2V0dXAsIG1lc3NhZ2U9RkFMU0V9CmxpYnJhcnkoZHBseXIpCmxpYnJhcnkodGlkeXIpCmxpYnJhcnkoZ2dwbG90MikKYGBgCgpgYGB7ciBnZ3Bsb3Qtc2V0dXAsIGVjaG89RkFMU0V9CnRoZW1lX3NldCh0aGVtZV9taW5pbWFsKCkpCgpub2dyaWQgPSBmdW5jdGlvbiAoKQogICAgdGhlbWUocGFuZWwuZ3JpZC5taW5vciA9IGVsZW1lbnRfYmxhbmsoKSwKICAgICAgICAgIHBhbmVsLmdyaWQubWFqb3IueCA9IGVsZW1lbnRfYmxhbmsoKSkKCnBpZV9jaGFydCA9IGZ1bmN0aW9uICgpCiAgICBsaXN0KGNvb3JkX3BvbGFyKHRoZXRhID0gJ3knLCBkaXJlY3Rpb24gPSAtMSksCiAgICAgICAgIHRoZW1lKGF4aXMudGV4dCA9IGVsZW1lbnRfYmxhbmsoKSwKICAgICAgICAgICAgICAgcGFuZWwuZ3JpZCA9IGVsZW1lbnRfYmxhbmsoKSkpCgpicmFja2V0cyA9IGZ1bmN0aW9uICguLi4pIHsKICAgIGFyZ3MgPSBsaXN0KC4uLikKICAgIGdyaWQ6OjpyZWNvcmRHcm9iKGRvLmNhbGwocEJyYWNrZXRzOjpncmlkLmJyYWNrZXRzLCBhcmdzKSwgZW52aXJvbm1lbnQoKSkKfQpgYGAKCmBgYHtyIHJuYS1zZXEtY291bnRzfQptZWFuX2ZyYWdtZW50X2xlbmd0aCA9IDMwMAoKY291bnRzID0gdGliYmxlKEdlbmUgPSBjKCdBJywgJ0InLCAnQycsICdEJyksCiAgICAgICAgICAgICAgICBMZW5ndGggPSBjKDcwMCwgNzAwLCA4MDAsIDgwMCksCiAgICAgICAgICAgICAgICBDb250cm9sID0gYyg0MCwgMjAsIDMwLCA0MCksCiAgICAgICAgICAgICAgICBUcmVhdG1lbnQgPSBjKDIwLCAyMCwgMzAsIDQwKSAqIDIpICU+JQogICAgZ2F0aGVyKExpYnJhcnksIENvdW50LCAtR2VuZSwgLUxlbmd0aCkgJT4lCiAgICBtdXRhdGUoRWZmZWN0aXZlTGVuZ3RoID0gTGVuZ3RoIC0gbWVhbl9mcmFnbWVudF9sZW5ndGggKyAxKQoKY291bnRzCgpnZW5lX2NvbG9ycyA9IGMoQSA9ICdkb2RnZXJibHVlMicsIEIgPSAnZGFya2dyZXknLCBDID0gJ2RhcmtncmV5JywgRCA9ICdkYXJrZ3JleScpCmBgYAoKIyMgUk5BLXNlcSBnZW5lIGV4cHJlc3Npb24gYnkgY291bnRzCgpgYGB7ciBybmEtc2VxLWJhcmNoYXJ0LCBmaWcud2lkdGg9NiwgZmlnLmhlaWdodD0zfQpnZ3Bsb3QoY291bnRzLCBhZXMoeCA9IEdlbmUsIHkgPSBDb3VudCwgZmlsbCA9IEdlbmUpKSArCiAgICBnZW9tX2JhcihzdGF0ID0gJ2lkZW50aXR5JykgKwogICAgZmFjZXRfd3JhcCh+IExpYnJhcnkpICsKICAgIHNjYWxlX2ZpbGxfbWFudWFsKHZhbHVlcyA9IGdlbmVfY29sb3JzLCBndWlkZSA9IEZBTFNFKSArCiAgICBsYWJzKHkgPSAnU2VxdWVuY2VkIGZyYWdtZW50cycpICsKICAgIG5vZ3JpZCgpCmBgYAoKLS0tCgpCdXQ6IHdlIGRvbuKAmXQgd2FudCAgCjxzcGFuIGNsYXNzPSJlbSI+KipmcmFnbWVudHMgcGVyIGxpYnJhcnkqKjwvc3Bhbj4uCgpXZSB3YW50ICAKPHNwYW4gY2xhc3M9ImVtIj4qKlJOQSBtb2xlY3VsZXMgcGVyIGNlbGwqKjwvc3Bhbj4uCgojIyBMaWJyYXJ5IHNpemUgZWZmZWN0CgpgYGB7ciBsaWJyYXJ5LXNpemUtYmFyY2hhcnR9CmdncGxvdChjb3VudHMsIGFlcyh4ID0gTGlicmFyeSwgeSA9IENvdW50LCBmaWxsID0gR2VuZSkpICsKICAgIGdlb21fYmFyKHN0YXQgPSAnc3VtJykgKwogICAgc2NhbGVfZmlsbF9tYW51YWwodmFsdWVzID0gZ2VuZV9jb2xvcnMpICsKICAgIGxhYnMoeSA9ICdTZXF1ZW5jZWQgZnJhZ21lbnRzJykgKwogICAgbm9ncmlkKCkgKwogICAgdGhlbWUobGVnZW5kLnBvc2l0aW9uID0gJ25vbmUnKQpgYGAKCiMjIFJOQS1zZXEgZ2VuZSBleHByZXNzaW9uIGFzIGZyYWN0aW9ucwoKYGBge3Igcm5hLXNlcS1waWVjaGFydCwgZmlnLndpZHRoPTYsIGZpZy5oZWlnaHQ9M30KIyBGSVhNRTogRGlyZWN0aW9uIHNob3VsZCBiZSBjbG9ja3dpc2UgYnV0IGBkaXJlY3Rpb24gPSAxYCBkb2VzIGFudGljbG9ja3dpc2UKIyBvbiBteSBjb21wdXRlci4gQnV0IGxhYmVscyBhcmUgY2xvY2t3aXNlPyEKY291bnRzICU+JQogICAgZ3JvdXBfYnkoTGlicmFyeSkgJT4lCiAgICBtdXRhdGUoRnJhY3Rpb24gPSBDb3VudCAvIHN1bShDb3VudCkpICU+JQogICAgbXV0YXRlKExhYmVsUG9zID0gc3VtKEZyYWN0aW9uKSAtIChjdW1zdW0oRnJhY3Rpb24pIC0gRnJhY3Rpb24gLyAyKSkgJT4lCiAgICBnZ3Bsb3QoYWVzKHggPSAnJywgeSA9IEZyYWN0aW9uLCBmaWxsID0gR2VuZSkpICsKICAgIGdlb21fYmFyKHN0YXQgPSAnaWRlbnRpdHknLCB3aWR0aCA9IDEsIGNvbG9yID0gJ3doaXRlJykgKwogICAgZ2VvbV90ZXh0KGFlcyh5ID0gTGFiZWxQb3MsIGxhYmVsID0gR2VuZSkpICsKICAgIHBpZV9jaGFydCgpICsKICAgIGZhY2V0X3dyYXAofiBMaWJyYXJ5KSArCiAgICBzY2FsZV9maWxsX21hbnVhbCh2YWx1ZXMgPSBnZW5lX2NvbG9ycywgZ3VpZGUgPSBGQUxTRSkgKwogICAgbGFicyh4ID0gJycsIHkgPSAnRnJhY3Rpb24gb2YgUk5BIG1vbGVjdWxlcycpCmBgYAoKIyMgU291cmNlcyBvZiB2YXJpYWJpbGl0eQoKKiBBY3Jvc3MgbGliYXJpZXMKICAgICogQW1vdW50IG9mIFJOQSBzZXF1ZW5jZWQKICAgICogVGVjaG5pY2FsIG5vaXNlCiogQWNyb3NzIHRyYW5zY3JpcHRzCiAgICAqIOKApiBsb25nZXIgdHJhbnNjcmlwdHMgPSBtb3JlIGZyYWdtZW50cwoqIDxzcGFuIGNsYXNzPSJlbSI+QmlvbG9naWNhbGx5IG1lYW5pbmdmdWw8L2VtPgoKIyMgVHJhbnNjcmlwdCBsZW5ndGgKCmBgYHtyIHRyYW5zY3JpcHQtbGVuZ3RoLCBmaWcud2lkdGg9NiwgZmlnLmhlaWdodD0yLjV9CnRsZW4gPSAyMgpmbGVuID0gMTAKZ2FwID0gMC4zCnRyYW5zY3JpcHQgPSB0aWJibGUoeG1pbiA9IDEsIHltaW4gPSAxLCB4bWF4ID0gdGxlbiwgeW1heCA9IDIsIHR5cGUgPSAndHJhbnNjcmlwdCcpCmZyYWdtZW50cyA9IHRpYmJsZSh4bWluID0gc2VxKDEsIHRsZW4gLSBmbGVuKSwgeW1pbiA9IHhtaW4gKiAoMSArIGdhcCkgKyAxLAogICAgICAgICAgICAgICAgICAgeG1heCA9IHhtaW4gKyBmbGVuLCB5bWF4ID0geW1pbiArIDEsIHR5cGUgPSAnZnJhZ21lbnQnKQoKYW5ub3RhdGVfZXF1YXRpb24gPSBmdW5jdGlvbiAoeCwgeSwgbGFiZWwpCiAgICBhbm5vdGF0ZSgndGV4dCcsIHggPSB4LCB5ID0geSwgbGFiZWwgPSBsYWJlbCwgcGFyc2UgPSBUUlVFLAogICAgICAgICAgICAgc2l6ZSA9IDgsIGZhbWlseSA9ICdUaW1lcyBOZXcgUm9tYW4nKQoKZ2dwbG90KGJpbmRfcm93cyh0cmFuc2NyaXB0LCBmcmFnbWVudHMpLAogICAgICAgYWVzKHhtaW4gPSB4bWluLCB5bWluID0geW1pbiwgeG1heCA9IHhtYXgsIHltYXggPSB5bWF4LCBmaWxsID0gdHlwZSkpICsKICAgIGdlb21fcmVjdCgpICsKICAgIGNvb3JkX2NhcnRlc2lhbih4bGltID0gYygtMS41LCB0bGVuKSwgeWxpbSA9IGMoLTMsIHRhaWwoZnJhZ21lbnRzJHltYXgsIDEpKSkgKwogICAgYW5ub3RhdGlvbl9jdXN0b20oYnJhY2tldHMoMC4xMzUsIDAuMjgsIDAuMTM1LCAxLCBoID0gMC4xLCBsd2QgPSAyKSkgKwogICAgYW5ub3RhdGVfZXF1YXRpb24oLTEuNSwgMTEsICdpdGFsaWMobClbcGxhaW4oZWZmKV0nKSArCiAgICBhbm5vdGF0aW9uX2N1c3RvbShicmFja2V0cygwLjE0NSwgMC4yMSwgMC45NSwgMC4yMSwgaCA9IC0wLjEsIGx3ZCA9IDIpKSArCiAgICBhbm5vdGF0ZV9lcXVhdGlvbigxMS40LCAtMi45LCAnaXRhbGljKGwpJykgKwogICAgYW5ub3RhdGlvbl9jdXN0b20oYnJhY2tldHMoMC4xNDUsIDAuMzQsIDAuNTI2LCAwLjM0LCBoID0gMC4xLCBsd2QgPSAyKSkgKwogICAgYW5ub3RhdGVfZXF1YXRpb24oNi4xNSwgNy41LCAnaXRhbGljKGJhcihuKSknKSArCiAgICBzY2FsZV9maWxsX21hbnVhbCh2YWx1ZXMgPSBjKHRyYW5zY3JpcHQgPSAnZGFya29saXZlZ3JlZW40JywgZnJhZ21lbnQgPSAnZGFya2dyZXknKSkgKwogICAgdGhlbWUocGFuZWwuZ3JpZCA9IGVsZW1lbnRfYmxhbmsoKSwKICAgICAgICAgIGxlZ2VuZC5wb3NpdGlvbiA9ICdub25lJywKICAgICAgICAgIGF4aXMudGl0bGUgPSBlbGVtZW50X2JsYW5rKCksCiAgICAgICAgICBheGlzLnRleHQgPSBlbGVtZW50X2JsYW5rKCkpCmBgYAoKXFsKXGxhcmdlCmxfXHRleHR7ZWZmfSA9IGwgLSBcYmFye259ICsgMQpcXQoKLS0tCgpEaWZmZXJlbnQgdHJhbnNjcmlwdCBsZW5ndGhzIGxlYWQgdG8gZGlmZmVyZW50IGV4cGVjdGVkIGZyYWdtZW50IGNvdW50cwoKYGBge3Igc2ltdWxhdGUtZnJhZ21lbnRzLCBtZXNzYWdlPUZBTFNFfQp0cmFuc2NyaXB0cyA9IElSYW5nZXM6OklSYW5nZXMoc3RhcnQgPSBjKDEsIDIyKSwgd2lkdGggPSBjKDIwLCA0MCkpCgpmc3RhcnRzID0gSVJhbmdlczo6cmVzaXplKHRyYW5zY3JpcHRzLCBJUmFuZ2VzOjp3aWR0aCh0cmFuc2NyaXB0cykgLSBmbGVuICsgMSkgJT4lCiAgICBJUmFuZ2VzOjpjb3ZlcmFnZSgpICU+JQogICAge3NlcV9hbG9uZyguKVthcy5pbnRlZ2VyKC4pID09IDFdfQoKc2V0LnNlZWQoMTIzNCkKZnJhZ21lbnRzID0gSVJhbmdlczo6SVJhbmdlcyhzdGFydCA9IHNhbXBsZShmc3RhcnRzLCA5KSwgd2lkdGggPSBmbGVuKQpmcmFnbWVudF9kYXRhID0gZnJhZ21lbnRzICU+JQogICAgYXMuZGF0YS5mcmFtZSgpICU+JQogICAgbXV0YXRlKGJpbiA9IElSYW5nZXM6OmRpc2pvaW50QmlucyhmcmFnbWVudHMpLCB0eXBlID0gJ3JlYWQnKQpgYGAKCmBgYHtyIHRyYW5zY3JpcHQtbGVuZ3RoLWRpZmZlcmVuY2VzLCBmaWcud2lkdGg9OCwgZmlnLmhlaWdodD0yfQp0cmFuc2NyaXB0cyAlPiUKICAgIGFzLmRhdGEuZnJhbWUoKSAlPiUKICAgIG11dGF0ZShiaW4gPSAwLCB0eXBlID0gYygnYScsICdiJykpICU+JQogICAgYmluZF9yb3dzKGZyYWdtZW50X2RhdGEpICU+JQogICAgbXV0YXRlKHltaW4gPSBiaW4gKiAoMSArIGdhcCksIHltYXggPSB5bWluICsgMSkgJT4lCiAgICBnZ3Bsb3QoYWVzKHhtaW4gPSBzdGFydCwgeW1pbiA9IHltaW4sIHhtYXggPSBlbmQsIHltYXggPSB5bWF4LCBmaWxsID0gdHlwZSkpICsKICAgIGdlb21fcmVjdCgpICsKICAgIHNjYWxlX2ZpbGxfbWFudWFsKHZhbHVlcyA9IGMoYSA9ICdkYXJrb2xpdmVncmVlbjQnLCBiID0gJ2RvZGdlcmJsdWUzJywgcmVhZCA9ICdkYXJrZ3JleScpKSArCiAgICB0aGVtZShwYW5lbC5ncmlkID0gZWxlbWVudF9ibGFuaygpLAogICAgICAgICAgbGVnZW5kLnBvc2l0aW9uID0gJ25vbmUnLAogICAgICAgICAgYXhpcy50aXRsZSA9IGVsZW1lbnRfYmxhbmsoKSwKICAgICAgICAgIGF4aXMudGV4dCA9IGVsZW1lbnRfYmxhbmsoKSkKYGBgCgojIyBUbyByZXZpZXcKClJOQS1zZXEgY291bnQgaXMgaW5mbHVlbmNlZCBieQoKKiBMaWJyYXJ5IHNpemUKKiBUcmFuc2NyaXB0IGxlbmd0aAoKLS0tCgo+ICoqVFBNKiogKHRyYW5zY3JpcHRzIHBlciBtaWxsaW9ucyk6Cj4gR2l2ZW4gYSBtaWxsaW9uIFJOQSBmcmFnbWVudHMsIGhvdyBtYW55IGZyYWdtZW50cyBvZiBhIGdpdmVuIHRyYW5zY3JpcHQgZG8gd2Ugc2VlPwoK4oaSIFRQTSBpcyBhIHJlbGF0aXZlICpmcmFjdGlvbiosIG5vdCBhYnNvbHV0ZSBleHByZXNzaW9uCgotLS0KClxbClxsYXJnZQpcdGV4dHtUUE19X1xjb2xvcntvcmNoaWR9aSA9CiAgICB7XGNvbG9ye2RvZGdlcmJsdWV9e1xmcmFje3hfXGNvbG9ye29yY2hpZH1pfXt7bF9cdGV4dHtlZmZ9fV9cY29sb3J7b3JjaGlkfWl9fX0KICAgIFxjZG90CiAgICBcZnJhY3sxfXtcc3VtX1xjb2xvcnt0b21hdG99aiBcY29sb3J7ZG9kZ2VyYmx1ZX17XGZyYWN7eF9cY29sb3J7dG9tYXRvfWp9e3tsX1x0ZXh0e2VmZn19X1xjb2xvcnt0b21hdG99an19fQogICAgXGNkb3QKICAgIFxjb2xvcntkYXJrY3lhbn17MTBeNn0KXF0KCiogXChcY29sb3J7b3JjaGlkfWlcKTogdHJhbnNjcmlwdCBpbmRleCwKKiBcKHhfaVwpOiB0cmFuc2NyaXB0IHJhdyBjb3VudCwKKiBcKFxjb2xvcnt0b21hdG99alwpIGl0ZXJhdGVzIG92ZXIgYWxsIChrbm93bikgdHJhbnNjcmlwdHMsCiogXChcY29sb3J7ZG9kZ2VyYmx1ZX17XGZyYWN7eF9rfXt7bF9cdGV4dHtlZmZ9fV9rfX1cKTogcmF0ZSBvZiBmcmFnbWVudCBjb3ZlcmFnZSBwZXIgbnVjbGVvYmFzZSwKKiBcKFxjb2xvcntkYXJrY3lhbn17MTBeNn1cKTogc2NhbGluZyBmYWN0b3IgKD0g4oCccGVyIG1pbGxpb25z4oCdKS4KCmBgYHtyIHRwbX0KdHBtID0gZnVuY3Rpb24gKGNvdW50cywgZWZmZWN0aXZlX2xlbmd0aHMpIHsKICAgIHJhdGUgPSBsb2coY291bnRzKSAtIGxvZyhlZmZlY3RpdmVfbGVuZ3RocykKICAgIGV4cChyYXRlIC0gbG9nKHN1bShleHAocmF0ZSkpKSArIGxvZygxMCBeIDYpKQp9CmBgYAoKYGBge3IgdHBtc30KdHBtcyA9IGNvdW50cyAlPiUKICAgIGdyb3VwX2J5KExpYnJhcnkpICU+JQogICAgbXV0YXRlKFRQTSA9IHRwbShDb3VudCwgRWZmZWN0aXZlTGVuZ3RoKSkKCnRwbXMKYGBgCgojIyBSTkEtc2VxIGdlbmUgZXhwcmVzc2lvbiBpbiBUUE0KCmBgYHtyIHJuYS1zZXEtdHBtLWJhcmNoYXJ0LCBmaWcud2lkdGg9NiwgZmlnLmhlaWdodD0zfQp0cG1fcGxvdCA9IGdncGxvdCh0cG1zLCBhZXMoeCA9IEdlbmUsIHkgPSBUUE0sIGZpbGwgPSBHZW5lKSkgKwogICAgZ2VvbV9iYXIoc3RhdCA9ICdpZGVudGl0eScpICsKICAgIGZhY2V0X3dyYXAofiBMaWJyYXJ5KSArCiAgICBzY2FsZV9maWxsX21hbnVhbCh2YWx1ZXMgPSBnZW5lX2NvbG9ycywgZ3VpZGUgPSBGQUxTRSkgKwogICAgbGFicyh5ID0gJ1RQTScpICsKICAgIG5vZ3JpZCgpCgp0cG1fcGxvdApgYGAKCi0tLQoKKiBEaWZmZXJlbnRpYWxseSBleHByZXNzZWQgdHJhbnNjcmlwdHMgYXJlIGNsZWFybHkgZGlmZmVyZW50CiogSWRlbnRpY2FsIHRyYW5zY3JpcHRzIGFyZSB2ZXJ5IHNpbWlsYXIKKiBCdXQgbm90IGVudGlyZWx5IHRoZSBzYW1lCiog8J+OlyBUUE1zIGFyZSByZWxhdGl2ZSBmcmFjdGlvbnMgb2YgbGlicmFyeQoqIOKGkiBDb21wYXJpc29uIGFjcm9zcyBsaWJyYXJpZXMgcmVxdWlyZXMgYWRkaXRpb25hbCBlZmZvcnQKCiMjIENyb3NzLWxpYnJhcnkgbm9ybWFsaXNhdGlvbgoKRnVuZGFtZW50YWwgYXNzdW1wdGlvbjoKCj4gPHNwYW4gY2xhc3M9ImVtIj5Nb3N0IHRyYW5zY3JpcHRzIGFyZSAqKm5vdCoqIGRpZmZlcmVudGlhbGx5IGV4cHJlc3NlZC48L3NwYW4+CgotLS0KCmBgYHtyIHNpemUtZmFjdG9ycywgZmlnLndpZHRoPTYsIGZpZy5oZWlnaHQ9M30Kc2l6ZV9mYWN0b3JzXyA9IGZ1bmN0aW9uIChjb3VudHMsIGdlbmVzLCBleHBlcmltZW50KSB7CiAgICBjb3VudHMgJT4lCiAgICAgICAgZ3JvdXBfYnlfKGdlbmVzKSAlPiUKICAgICAgICBtdXRhdGUoTG9nR2VvbU1lYW4gPSBtZWFuKGxvZyhDb3VudCkpKSAlPiUKICAgICAgICBncm91cF9ieV8oZXhwZXJpbWVudCkgJT4lCiAgICAgICAgbXV0YXRlKFNGID0gZXhwKG1lZGlhbihsb2coQ291bnQpIC0gTG9nR2VvbU1lYW4pKSkKfQoKc2l6ZV9mYWN0b3JzID0gZnVuY3Rpb24gKGNvdW50cywgZ2VuZXMsIGV4cGVyaW1lbnQpIHsKICAgIHNpemVfZmFjdG9yc18oY291bnRzLCBsYXp5ZXZhbDo6bGF6eShnZW5lcyksIGxhenlldmFsOjpsYXp5KGV4cGVyaW1lbnQpKQp9Cgpub3JtX2NvdW50cyA9IGNvdW50cyAlPiUKICAgIHNpemVfZmFjdG9ycyhHZW5lLCBMaWJyYXJ5KSAlPiUKICAgIG11dGF0ZShDb3VudCA9IENvdW50IC8gU0YpCgpub3JtX2NvdW50cwoKIyBUUE0gcGxvdCBhZ2FpbiwgZm9yIGNvbXBhcmlzb24KdHBtX3Bsb3QgJSslIG11dGF0ZSh0cG1zLCBUUE0gPSBUUE0gLyAxMDAwMCkgKyB5bGFiKCcnKSArIGdndGl0bGUoJ1RQTSAvIDEwMDAwJykKCmdncGxvdChub3JtX2NvdW50cywgYWVzKEdlbmUsIENvdW50LCBmaWxsID0gR2VuZSkpICsKICAgIGdlb21fYmFyKHN0YXQgPSAnaWRlbnRpdHknKSArCiAgICBmYWNldF93cmFwKH4gTGlicmFyeSkgKwogICAgc2NhbGVfZmlsbF9tYW51YWwodmFsdWVzID0gZ2VuZV9jb2xvcnMsIGd1aWRlID0gRkFMU0UpICsKICAgIHlsYWIoJycpICsKICAgIGdndGl0bGUoJ0NvdW50IC8gREVTZXEgc2l6ZSBmYWN0b3JzJykgKwogICAgbm9ncmlkKCkKYGBgCgojIyBMaXRlcmF0dXJlCgoqIFtXaGF0IHRoZSBGUEtNPyBBIHJldmlldyBvZiBSTkEtU2VxIGV4cHJlc3Npb24gdW5pdHNdKGh0dHBzOi8vaGFyb2xkcGltZW50ZWwud29yZHByZXNzLmNvbS8yMDE0LzA1LzA4L3doYXQtdGhlLWZwa20tYS1yZXZpZXctcm5hLXNlcS1leHByZXNzaW9uLXVuaXRzLykKKiBbKldhZ25lciwgR1AgJiBhbC4qLCAyMDEyXShodHRwczovL3BhcGVycGlsZS5jb20vYXBwL3AvNmJmMjdhNWMtZDI2Yi0wMDNiLThiMjgtNDFjNjJkZWU1MDUxKQoqIFtERVNlcTIgdmlnbmV0dGVdKGh0dHBzOi8vYmlvY29uZHVjdG9yLm9yZy9wYWNrYWdlcy9kZXZlbC9iaW9jL3ZpZ25ldHRlcy9ERVNlcTIvaW5zdC9kb2MvREVTZXEyLmh0bWwpCiogW/Cfk5wgQ29kZSBmb3Igc2xpZGVzXShodHRwczovL2dpdGh1Yi5jb20va2xtci9ybmFzZXEtbm9ybSkKCiMjIFN1cHBsZW1lbnRhcnkgbWF0ZXJpYWwKCiMjIyBMZWdhY3kgbm9ybWFsaXNhdGlvbiBtZXRob2RzCgoqIENQTSA9IFJQTSA9IHtjb3VudHMvcmVhZHN9IHBlciBtaWxsaW9uCgogICAgXFsKICAgIFx0ZXh0e0NQTX1faSA9IHhfaSBcY2RvdCBcZnJhY3sxfXtcc3VtX2ogeF9qfSBcY2RvdCAxMF42CiAgICBcXQoKICAgIPCfkY4gRG9lcyBub3QgYWNjb3VudCBmb3IgZGlmZmVyZW5jZXMgaW4gdHJhbnNjcmlwdCBsZW5ndGgKCiogUlBLTSA9IEZQS00gPSB7cmVhZHMvZnJhZ21lbnRzfSBwZXIga2lsb2Jhc2UgcGVyIG1pbGxpb24KCiAgICBcWwogICAgXHRleHR7RlBLTX1faSA9IFxmcmFje3hfaX17e2xfXHRleHR7ZWZmfX1faX0gXGNkb3QgXGZyYWN7MX17XHN1bV9qIHhfan0gXGNkb3QgMTBeNiBcY2RvdCAxMF4zCiAgICBcXQoKICAgIPCfkY4gSGFzIGRpZmZlcmVudCBzY2FsaW5nIGZhY3RvcnMgZm9yIGVhY2ggUk5BLXNlcSBsaWJyYXJ5Cg==