# A detailed model of gene promoter dynamics reveals the entry into productive
elongation to be a highly punctual process.

Jaroslav Albert
<EMAIL_ADDRESS>Ronin Institute

###### Abstract

Gene transcription is a multistep stochastic process that involves thousands
of reactions. The first set of these reactions, which happen near a gene
promoter, are considered to be the most important in the context of stochastic
noise and have been a focus of much research. The most common models of
transcription are primarily concerned with the effect of activators/repressors
on the overall transcription rate and approximate the basal transcription
processes as a one step event. According to such effective models, the Fano
factor of mRNA copy distributions is always greater than (super-Poissonian) or
equal to 1 (Poissonian), and the only way to go below this limit (sub-
Poissonian) is via a negative feedback. It is partly due to this limit that
the first stage of transcription is held responsible for most of the
stochastic noise in mRNA copy numbers. However, by considering all major
reactions that build and drive the basal transcription machinery, from the
first protein that binds a promoter to the entrance of the transcription
complex (TC) into productive elongation, it is shown that the first two stages
of transcription, namely the pre-initiation complex (PIC) formation and the
promoter proximal pausing (PPP), is a highly punctual process. In other words,
the time between the first and the last step of this process is narrowly
distributed, which gives rise to sub-Poissonian distributions for the number
of TCs that have entered productive elongation. In fact, having simulated the
PIC formation and the PPP via the Gillespie algorithm using 2000 distinct
parameter sets and 4 different reaction network topologies, it is shown that
only 4.4$\%$ give rise to a Fano factor that is $>1$ with the upper bound of
1.7, while for 31$\%$ of cases the Fano factor is below 0.5, with 0.19 as the
lower bound. The two parameters that exert the most control on the Fano factor
are the binding and dissociation rates between the activator and its enhancer.
In the limit as these rates become low, our model approaches the conventional
two-state promoter model, which can give rise Fano factors much larger than
one. These results cast doubt on the notion that most of the stochastic noise
observed in mRNA distributions always originates at the promoter.

## Introduction

Gene transcription is a stochastic process involving a multitude of
biochemical reactions by which the genetic code of a gene is copied into
messenger RNA (mRNA). In eukaryotes, transcription occurs in four stages: 1)
pre-initiation complex (PIC) formation Luse ; Greber ; Petrenko ; 2) promoter
proximal pausing (PPP) Chen ; Jonkers ; Mayer ; Li ; Levine ; Core ; Core2 ;
3) productive elongation Gonzalez ; Bai ; Muniz ; and 4) termination Rosonina
; Proudfoot ; Porrua ; Porrua2 ; Kuehner ; Richard ; Luo ; Kornblihtt . In
stage 1) general transcription factors (GTF) bind the promoter in order to
recruit RNA Polymerase II (Pol II) and other GTFs that enable the Pol II
complex to begin transcription. In stage 2) the Pol II complex pauses a short
distance downstream from the promoter site in order to give time to necessary
processes, such as RNA capping and the addition of elongation-promoting
factors, to do their job. In stage 3) the Pol II complex - known at this stage
as elongation complex (EC) - enters the main body of a gene where it continues
to transcribe mRNA until stage 4) in which transcription is terminated and the
completed mRNA, along with the Pol II complex, are released. There are
additional stages, such as splicing and the synthesis of ribonucleoprotein
particles Stefl ; however, these tend to occur (though not always) during the
elongation stage and can be incorporated into the elongation process itself
Bentley .

Traditionally, stochastic models of transcription tend to focus on a highly
simplified version of stage 1), while either ignoring the subsequent stages
Walczak  or handling them by introducing a delay Ribeiro . By doing so, such
models are forced to operate under the assumption that whatever noise in mRNA
copy numbers they are meant to explain/simulate, it all comes from this first
stage. For super-Poissonian distributions, these models do quite well, owing
to the multitude of promoter states that can be produced via
activators/repressors. On the other hand, for sub-Poissonian distributions,
this class of models works only in the presence of a negative feedback and
only under certain conditions Dublanche ; Tao ; Lago ; Zhang1 . However,
models that take into account the reinitiation of Pol II at the promoter have
revealed that mRNA distributions can in fact be sub-Poissonian without any
feedback Karmakar , or at the very least reduce the variance Boettiger ; Liu ;
Filatova ; Braichenko ; Choubey ; Choubey2 ; Xu ; Cao  as compared to the
above-mentioned simpler models. This discovery challenges the conventional
wisdom that sub-Poissonian mRNA distributions are necessarily indicative of a
negative feedback.

In this paper, we present a detailed stochastic model of the PIC formation and
the PPP, one that involves 15 macromolecules - 13 general transcription
factors (GTF), 1 activator, and the RNA polymerase II. The model is based on
the current understanding of these two transcription stages. The goal of this
paper is to investigate the range of Fano factors for the number distribution
of ECs in a given time. we do this by generating 500 parameter sets and
simulate for each set the stochastic evolution of the system, starting with an
empty promoter. A crucial feature of this model is the relationship between
the PPP stage and the reinitiation of Pol II, which can take several forms,
two of which are considered herein: 1) Pol II is able to bind the promoter
only when the promoter proximal region is free of a paused complex (PC); and
2) Pol II can bind but it cannot clear the promoter while a PC is present. The
effects of activator dynamics on the resulting Fano factors are also simulated
using a simple on-off model, where “on” means the activator is bound to the
promoter and “off” means it is not. Since the exact order in which the GTFs
are recruited to the promoter is still unsettled, all simulations are repeated
using models with one and two additional reaction pathways. The simulations
show a remarkable reluctance of the Fano factors to rise above 1 when the
activator dynamics are relatively fast. In those cases where the binding rate
is fast and the dissociation rate is slow, the Fano factors concentrate around
the value of 0.4 with a maximum of 0.6. On the other hand, when both the
binding and dissociation factors are low, the Fano factors can reach values in
excess of xxx. While the correlation between the activator dynamics and the
Fano factors is consistent with previous studies, the migration of the Fano
factors to such extremely low values is a novel feature of the highly
sequential nature of stages 1) and 2).

## Gene transcription

### Pre-initiation complex formation

Figure 1: Pre-clearance complex (PCC) formation. 1) Empty promoter; 2) TBP
binds to TATA box and bends the DNA; 3) TFIIA binds TBP; 4) TFIIB binds the
TATA/TBP complex; 5) the complex Pol II/TFIIF is recruited; 6) the complex
TFIIH/TFIIE is recruited; 7) initiation: DNA unwinds; 8) Serine 7 is
phosphorelated, bubble grows and TFIIB is released; 9) Serine 5 is
phosphorelated; 10) the EC clears the promoter.

The first step in mRNA transcription is the pre-initiation complex (PIC), the
formation of which begins with the binding of a transcription factor (TF)
called TFIID to the promoter. TFIID is a multi sub-unit factor comprising of
TBP (TATA binding protein) and TAFs (TBP associated factors). As the name
suggests, the TBP binds to the part of the promoter with the sequence TATA
(Fig. 1.1 and 1.2). When the TBP binds the TATA box, it creates an almost 80
degree bend in the DNA. In order to stabilize this TATA-TBP complex, another
TF, called TFIIA, binds to it (Fig. 1.3). Strictly speaking, TFIIA is not a
general TF, as transcription can proceed without it, but merely functions as a
scaffold protein. The TF that is crucial for transcription is TFIIB (Fig.
1.4), which can bind the promoter independently of TFIIA. In this state, the
promoter can receive the RNA polymerase II (Pol II). Since Pol II has no
affinity to the DNA, it must bind the promoter via a TF called TFIIF (Fig.
1.5), which has affinity to TFIIB. The TFIIB has a part that binds the
promoter, and another part, called the B-reader, that ensured that Pol II
faces the downstream direction. Another role of TFIIF is to recruit TFIIE,
which acts as a loading factor for another TF called TFIIH. TFIIE and TFIIH
usually bind the promoter as a complex (Fig. 1.6). In higher eukaryotes –
which is the focus of this paper – all these processes are happening in a
3-dimensional confirmation with the help of long range enhancers and mediator
proteins, which together form the enhancer-mediator complex. For simplicity,
the mediator or the enhancers were are not shown in Fig. 1.

### Initiation

At this point the DNA is still closed and the Pol II is not yet making any
mRNA. However, soon after TFIIH comes into play, the DNA unwinds in the
activity center of Pol II (Fig. 1.7). What causes this unwinding is a tug of
war between TFIIH and TBP. Pol II is a processive enzyme and wants to move
forward. However, because it is bound to TFIIB via TFIIF, it is unable to
move. The XPB-subunit of TFIIH, which is the translocate part of TFIIH, tracks
the DNA forward, but because it is bound to Pol II via TFIIE, it, too, cannot
move. As a result of these opposing forces, the DNA unwinds. Such unwound DNA
is called a bubble Pal . At this stage the Pol II tries to synthesize mRNA but
is blocked by the B-reader part of TFIIB, which partially extends to the
active site of Pol II. The partial blocking of the B-reader ensures that Pol
II begins transcription at the correct site, called +1. Since this blocking is
only partial, Pol II sometimes manages to produce short transcripts $\sim$ 3-5
base pair long, which, unless the Pol II can clear the promoter, are released
from the active site – a process known as abortive transcription (not shown in
the figure). This transition from closed to open bubble is called initiation.

### Promoter clearance

When the nascent RNA grows to a length of about 9 nucleotides, thus
strengthening the RNA-DNA bond, it becomes harder to abort. The growing
transcript forces TFIIB to dissociate, allowing the bubble to grow to a length
of about 18 nucleotides (Fig. 1.8). However, such a large bubble is
thermodynamically unstable and collapses to a smaller bubble of length of
about 10 nucleotides. This collapse creates a force that causes a forward
movement of Pol II. At the time of the bubble collapse, the C-terminal domain
(CTD) of Pol II is phosphorylated (Fig. 1.8 and 1.9). This phosphorylation is
facilitated by the CDK7 subunit of TFIIH and the enhancer-bound kineses, which
add phosphate groups to Serine 7 and Serine 5 (in that order) of each heptad
repeat of the CDT. Serine 5 phosphorylation breaks the bond between Pol II and
the mediator complex, allowing Pol II to move forward and increasing the
transcript to a length of 20 base pairs on average (Fig. 1.10).

Note: by conventional definition, PIC refers to the protein complex consisting
of TBP, TFIIA (optional), TFIIB, TFIIE, TFIIF, Pol II and TFIIH. For
convenience we will define the term “Pre-clearance complex” (PCC) to mean the
state of the Pol II complex prior to clearance in order to place the
initiation and phosphorylation processes under one umbrella.

### Promoter proximal pausing and escape

Figure 2: Promoter proximal pausing and escape. 1) DISF is recruited by
phosphorelated Serine-5 and Serine-7 to the nascent mRNA; 2) HCE caps the 5’
end of mRNA; 3) mTASE is recruited to the 5’ end; 4) NELF is recruited; 5)
Gdown1 is recruited; 6) PAFC1 is recruited; 7) the pTEFb/SEC complex is
recruited; 8) the pTEFb/SEC complex phosphorelates Serine 2; 9) the complex
pTEFb/BRD is recrired; 10) escape into productive elongation.

The 5’ end of the transcript is now sticking out of the Pol II exit channel.
At this time, Spt 4 and Spt 5, which togeher are known as the DSIF complex,
are recruited to the phosphorelated Serine-5 and Serine-7 of the CDK, while in
the process removing TFIIF (Fig. 2.1). The function of the DSIF complex is to
recruit two capping enzymes, the human capping enzyme (HCE) and mTASE, to the
5’ end of the transcript (Fig. 2.2 and 2.3), which increases the stability of
the RNA, and also to recruit a TF called NELF (negative elongation factor)
(Fig. 2.4). NELF freezes Pol II, thus locking the RNA-DNA hybrid inside its
active center. Another TF, called Gdown1, binds the growing complex (Fig. 2.5)
and helps NELF to maintain this frozen state. Gdown1 also prevents TFIIF from
binding back to Poll II and keeps protein called TTF2 (transcription
termination factor 2) from binding the complex. Another TF called PAFC1 (Pol
associated factor complex 1) binds Pol II (Fig. 2.6); it has a dual role of
promoting the frozen state and helps maintain elongation. To overcome this
frozen state, two special proteins BRD-4 and SEC bind a TF called pTEF-b, thus
stimulating its kinase activity. The pTEF-b/SEC complex changes the
comformation of PAFC1 and phosphorelates the Spt5 part of DISF and Seren-2 of
the CTD, which releases the Stp4 part of DISF in the process (Fig. 2.8). Now
the PAFC1 and Spt5, which were previously negative regulators in the promoter
proximal state, are now positive regulators of elongation and stay bound to
Pol II. To complete the transition from the PPP to productive elongation,
pTEF-b/BRD-4 must bind the complex (Fig. 2.9), which stimulates the release of
Spt4, NELF and Gdown1, allowing Pol II to enter the elongation phase (Fig.
2.10).

### Reinitiation of Pol II

When the Pol II complex clears the promoter, the promoter returns to one of
the states TATA, TATA/TBP or TATA/TBP/A. That means that the PIC can begin to
form again. However, due to structural reasons, e. g. the size of the PC
(paused complex) and its location on the gene, a newly bound Pol II may not
have enough physical space to clear the promoter Darst ; Hahn ; Schier ;
Adelman . The question as to whether another Pol II can even bind the promoter
in the presence of a PC or whether it is simply blocked from clearing has not
been settled. However, there is increasing evidence for a negative correlation
between the amount of time the PC stays in the paused state and the clearance
rate Shao ; Gressel .

## Materials and Methods

### The model

Figure 3: Reactions involved in the pre-clearance complex (PCC) formation.
Figure 4: Reactions involved in the promoter proximal pausing and escape.

The biochemical reactions that form the PCC and those that cause and maintain
the PC are shown in Fig. 3 and 4, respectively. The variables, i. e. promoter
states, are labeled so as to make clear what proteins are bound to the complex
and what parts of the complex have been phosphorylated. For example, in the
transition from TATA/TBP/B/F/Pol/H to TATA/TBP/F/Pol+/H, the complex has moved
into the initiation phase, conveyed by the plus sign, and TFII B was released
in the process, as indicated by the absence of B in the latter state. This
transition changes the value of the former variable from 1 to 0, and
conversely so for the latter variable. The subscript in, e. g.
TATA/TBP/F/Pol${}^{+}_{7,5}$/H, indicates that both Serine 7 and Serine 5 have
been phosphorylated. In Fig. 4, the double plus in the superscript of H
signifies that the PCC has cleared the promoter. The reactions that lead to
the state $\emptyset$ cause Pol II to dissociate from the DNA. Hence,
$\emptyset$, which also takes on the values of 0 or 1, represents an empty DNA
in the region downstream from the PCC. Two distinct interactions between the
PCC and PC were considered: 1) Pol II cannot bind the promoter unless
$\emptyset=1$; and 2) Pol II can bind the promoter but cannot clear it unless
$\emptyset=1$. Thus, the reaction propensity for case 1) was
$k_{\text{Pol}}^{\text{on}}\emptyset$, while the propensity in case 2) was
$k_{\text{clear}}\emptyset$.

In addition to the reactions in Figs. 3 and 4, the following reactions were
added to the system:

$\displaystyle\emptyset\xrightarrow{\makebox[28.45274pt]{$k^{\text{on}}_{\text{act}}$}}Z$
$\displaystyle
Z\xrightarrow{\makebox[28.45274pt]{$k^{\text{off}}_{\text{act}}$}}\emptyset,$

where $Z$ is the state of an enhancer, such that when $Z=1$, the enhancer is
occupied by an activator, and when $Z=0$, the enhancer is unoccupied. Although
the mechanism by which activators enhance transcription is not unique and can
occur in both the PCC formation Cosma  and during the PPP XavierChen ; LJCore
, some evidence suggests that in the PCC formation the primary role of
activators is to bring Pol II to the promoter Ma . To keep things simple, we
have incorporated the state of the enhancer, i. e. the variable $Z$, into the
main model by multiplying the propensities for transitioning from the state
TATA/TBP/B and TATA/TBP/A/B to TATA/TBP/B/Pol and TATA/TBP/A/B/Pol,
respectively, by $(1+99Z)/100$. The logic behind this factor is simple. When
$Z=0$, and remains so (no activator, i. e. $k^{\text{on}}_{\text{act}}=0$),
the propensity for the binding of Pol II is $k^{\text{on}}_{\text{Pol}}/100$,
which diminishes the overall rate of transcription; we consider this as the
state of basal transcription. When $Z=1$, and remains so, i. e.
$k^{\text{off}}_{\text{act}}=0$, the propensity for the binding of Pol II is
restored to $k^{\text{on}}_{\text{Pol}}$. Finally, there is the intermediate
situation, in which $k^{\text{on}}_{\text{Pol}}\neq 0$ and
$k^{\text{off}}_{\text{Pol}}\neq 0$. By regulating
$k^{\text{on}}_{\text{Pol}}$ and $k^{\text{off}}_{\text{Pol}}$, one can not
only adjust the overall transcription rate, but also the stochastic nose in
the system, as will be demonstrated later.

### Parameter selection

The parameters used in all simulations were selected from ranges that are
consistent with values found in literature. Table 1 shows the parameter ranges
for the PIC formation and the relevant references.

Table 1: at $nM=8$ Description | Symbol | Range | Reference
---|---|---|---
Binding rate of TBP | $k_{\text{TBP}}$ | 0.001-0.1 s-1 | Chen ; Zhang ; Revyakin ; Jung
Binding rate of TFIIA | $k_{\text{A}}$ | 0.01-0.1 s-1 | Zhang
Binding rate of TFIIB | $k_{\text{B}}$ | 0.025-0.25 s-1 | Zhang
Binding rate of Pol II | $k_{\text{Pol}}$ | 0.025-0.25 s-1 | Darzacq
Dissociation rate of TBP | $k_{\text{TBP}}$ | 0.125-0.0125 s-1 | Zhang ; Jung ; Presman ; Hasegawa ; Heiss
Dissociation rate of TFIIA | $k_{\text{A}}$ | 0.01-0.001 s-1 | Zhang ; Jung
Dissociation rate of TFIIB | $k_{\text{B}}$ | 0.6-0.006 s-1 | Zhang ; Jung ; Presman
Average pause time | $t_{\text{pause}}$ |  $\sim$5 mins | Buckley ; Boettiger
Efficiency | $r$ | 5.5-83.3$\times 10^{-4}$s-1 |

For the PPP, specific reaction rates are much less available than the rates
for the PIC formation. However, since the reactions that occur during the PPP
are of the same kind as those in the PIC formation, namely association and
dissociation of proteins, it is reasonable to assume they too have ranges
similar to those given in Table 1, e. g. 0.001-0.1s-1. Also, these rates can
be constrained by the average duration of the pausing, for which there are
data. In, for example, Buckley , the average duration of the PPP, $\langle
t_{\text{pause}}\rangle$, was measured to be $\sim$ 5 minutes. Note: in
Buckley  and other studies, $\langle t_{\text{pause}}\rangle$ is not
considered to be the time it takes the freshly cleared complex to reach the
elongation stage; rather it is treated as the time that Pol II spends bound to
the DNA during the paused state. In other words, $\langle
t_{\text{pause}}\rangle$ is the average waiting time for either $\emptyset$ to
go from 0 to 1, or for
Pol${}^{++}_{7,5,2}$/H/Spt5${}_{\text{p}}$/HCE/mTASE/PAFC1/SEC/BRD to
transition into PE. Another limiting factor that can help restrict not only
the reaction rates of the PPP but the rates of the PCC formation as well, is
the efficiency of transcription, or transcription rate $r$, which is typically
in the range 5.5-83.3$\times 10^{-4}$s-1. The rate $r$ is defined as the
inverse of the average waiting time to reach productive elongation $\langle
t_{\text{elong}}\rangle$, starting from randomized initial conditions, i. e. a
value of one is randomly assigned to one of the variables TATA, TATA/TBP,
TATA/TBP/A, TATA/TBP/B, TATA/TBP/A/B at time $t=0$. For the purposes of this
paper it is not necessary to compute $\langle t_{\text{elong}}\rangle$
exactly; an estimate is sufficient and can be obtained by computing $\langle
t_{\text{clear}}\rangle$, which is the average waiting time for clearance to
occur, subject to the aforementioned randomized initial conditions, and then
adding $\langle t_{\text{escape}}\rangle$, which is defined as the time to go
from the state F/Pol7,5/H to PE (see Fig. 4). Thus, $r=\langle
t_{\text{elong}}\rangle^{-1}$, where $\langle
t_{\text{elong}}\rangle\sim\langle t_{\text{clear}}\rangle+\langle
t_{\text{escape}}\rangle$. The exact details on how $\langle
t_{\text{clear}}\rangle$, $\langle t_{\text{escape}}\rangle$ and $\langle
t_{\text{pause}}\rangle$ were computed can be found in appendix A.

We generated 500 parameter sets in the range restriction $0.001-0.1$ and
subject to the constraints $4<\langle t_{\text{pause}}\rangle<6$ min and
$13\times 10^{-4}$s${}^{-1}<r<20\times 10^{-4}$s-1. Evidence suggests Zhang
that when TFIIA is bound to the promoter, the binding rate of TFIIB is
significantly enhanced, while its dissociation rate is much reduced. This was
taken into account by setting $k^{\text{on}}_{\text{A$|$B}}$ to
$10k^{\text{on}}_{\text{B}}$ and $k^{\text{on}}_{\text{A$|$B}}$ to
$0.1k^{\text{on}}_{\text{B}}$ (see Fig. 3). Note that while binding factors
must have an upper bound, due to physical restrictions such as protein
density, number of collisions with their target, et cetera, no such
restrictions apply to the lower bounds of dissociation factors; they are
instead restricted by thermodynamic stability and degradation by enzymatic
reactions. Thus, the values of some dissociation factors below $10^{-3}$s-1
were allowed. They were also necessary, as we will now explain.

The aforementioned scheme for computing $\langle t_{\text{pause}}\rangle$ and
estimating $r$ was unable to generate $r$ in the desired range $13\times
10^{-4}$s${}^{-1}-20\times 10^{-4}$s-1 when all parameter values were
constrained to $0.001$s-1 \- $0.1$s-1; the largest value of $r$ yielded by
this range after ten thousand selections was $0.7\times 10^{-4}$s-1. For this
reason, we decided to lower the dissociation rate for Pol II in PCC (but not
in the PC) by some factor $\beta$. Then, $\beta$ was incrementally increased
until the scheme started producing the desired results. The lowest value of
$\beta$ that yielded the desired results within ten thousand selections was
10. Thus, the range for the dissociation rate for Pol II in PCC was set to
$0.0001-0.01$s-1.

### Simulations

All simulations were done with the Gillespie algorithm (GA) Gillespie . For
all simulations, each realization in an ensemble started at time $t=0$, and
with the initial conditions TATA$=1$, and stopped when the algorithm passed
$t=60000$s. The number of times the reaction
Pol${}^{++}_{7,5,2}$/H/Spt5p/HCE/mTASE/PAFC1/SEC/BRD$\rightarrow$ EC occurred
before $t=60000$s was recorded. From now on, we will let EC represent this
number. Note: the transcription rate $r$ is related to the average EC via
$r=\langle EC\rangle/60000$. In all subsequent sections we will refer to
$\langle EC\rangle$, rather than $r$.

## Results

Figure 5: Results of simulations for PCC-PC interaction model 1. (a) \- (d):
Fano factors (blue bars) and average EC for all 500 parameter sets. (e) and
(f): Increase in average EC relative to basal average EC in ascending order.
(g): Probability distribution for times of entrance into PE for the maximum
(green) and minimum (red) Fano factor. (h): Cumulative distributions for the
curves in (g). Figure 6: Comparison of results between PCC-PC interaction
models 1 and 2. (a) \- (d): Fano distributions for PCC-PC interaction models 1
(orange) and model 2 (blue). (a) \- (d): Increase in average EC of PCC-PC
interaction model 1 relative to PCC-PC interaction model 2 in ascending order.
Figure 7: Fano distributions (a) and averages of EC (b) for
$k^{\text{on}}_{\text{Act}}=k^{\text{off}}_{\text{Act}}=0$,
$k^{\text{on}}_{\text{Act}}=k^{\text{off}}_{\text{Act}}=5\times 10^{-5}$s-1
and $k^{\text{on}}_{\text{Act}}=k^{\text{off}}_{\text{Act}}=10^{-5}$s-1.

For each of the 500 parameter sets, using the PCC-PC interaction model 1) (see
previous section) a simulation was done with the following combinations of
$(k^{\text{on}}_{\text{act}},k^{\text{off}}_{\text{act}})$: $(0,0)$,
$(10^{-3},10^{-3})$, $(10^{-3},10^{-4})$ and $(10^{-3},10^{-5})$ (in inverse
seconds). The averages and Fano factors for the variable EC are presented in
Fig. 5 a-d. The averages, represented by the orange dots, are sorted in an
ascending order. The histograms were constructed in Mathematica using the
“Histogram” function with 30 bars. Fig. 5 e and f show the increase in average
EC upon introducing an activator for different combinations
$(k^{\text{on}}_{\text{act}},k^{\text{off}}_{\text{act}})$, represented by
different colors. For each color, the curves were sorted in their own
ascending order. Shown in Fig. 5 g are two probability density functions
$P(t)$ for the reaction
Pol${}^{++}_{7,5,2}$/H/Spt5p/HCE/mTASE/PAFC1/SEC/BRD$\rightarrow$ EC to occur
between the times $t$ and $t+dt$. Fig. 5 h shows the cumulative distribution
functions $P_{c}(t)$ defined as

$P_{c}(t)=1-\int_{0}^{t}dt^{\prime}P(t^{\prime}).$ (2)

The cumulative function, Eq. (2), is used to sample $t$ by solving the
equation $P_{c}(t)=\xi$, where $\xi$ is a random real number ranging from 0 to
1. The red (green) curve in both graphs was generated from a parameter set
responsible for the smallest (largest) Fano factor in all the obtained data.
Fig. 5 g reveals an interesting feature of this system: even though the bulk
of the red curve seems to be wider than that of the green curve, the green
curve has a much longer tail. If one was to sample the time at which a new EC
occurred using the cumulative functions in Fig. 5 h, the times that are
greater than $\sim$800 seconds would occur much more often for the green curve
than the red curve.

This entire procedure was repeated for the second PCC-PC interaction (see
previous section), the results of which are shown in Fig. 6. For all
combinations of $(k^{\text{on}}_{\text{act}},k^{\text{off}}_{\text{act}})$
mentioned above, the Fano distributions tend slightly towards the right (see
Fig. 6 a-d). With this increased noise, the efficiencies also increase. It is
clear from these graphs that the distributions of EC tend to be sub-Poissonian
regardless of the reaction rates. This is more true the smaller
$k^{\text{off}}_{\text{act}}$ is compared to
$k^{\text{on}}_{\text{act}}=10^{-3}$s-1.

However, what would happen if both $k^{\text{on}}_{\text{act}}$ and
$k^{\text{off}}_{\text{act}}$ were small, e. g. $\sim 10^{-5}$? To answer this
question, I ran additional simulations for these combinations of
$(k^{\text{on}}_{\text{act}},k^{\text{off}}_{\text{act}})$:
$(10^{-4},10^{-4})$, $(5\times 10^{-5},5\times 10^{-5})$ and
$(10^{-5},10^{-5})$ (in inverse seconds). The results shown in Fig. 7 a) are
consistent with previous research: the slower the activator dynamics, the
greater the noise tends to be. The averages, shown in Fig. 7 b), do not seem
to change very much compared to those in Figs. 5 and 6.

###  .1 Alternative pathways

Figure 8: Two additional pathways to get from F/Pol/7,5/H++ to EC. Figure 9:
Four additional pathways to get from F/Pol/7,5/H++ to EC.

The mechanism of the PCC formation and the PPP is still a subject of ongoing
research with many details to be worked out, as well as some major discoveries
to be made. For example, the precise order in which the two complexes are
formed and whether they are always formed the same way has not yet reached a
consensus. Given such a state of affairs, it is reasonable to wonder if the
results obtained thus far would hold up if some of the reactions in Figs. 3
and 4 could also happen in a different order. In other words, what would
happen if there were alternative pathways to get from an empty promoter to PE?
To answer this question, we ran simulations for the PCC-PC interaction model
1) but with additional pathways, shown in Figs. 8 and 9. The reactions in blue
are the additional pathways. In Fig. 8, there are two additional pathways: HCE
and mTASE bind before DISF; and Gdown1 binds before NELF. In Fig. 9, there are
two additional pathways on top of those from Fig. 8: mTASE binds before HCE,
followed by DISF; and BRD binds before SEC, followed by the phosphorylation of
Serine 2 and Spt5.

In terms of noise, adding more pathways does not seem to change much: in Fig.
8b, the Fano distribution is slightly shifted to the right; on the other hand,
in Fig. 8d, it is shifted slightly to the left. The efficiencies, however,
have more of a consistent trend: adding more pathways does increase the
efficiency in the ballpark of 10 to 30 percent.

Figure 10: (a) \- (d): Fano distributions for PCC-PC interaction model 1
(orange), two additional pathways (light blue) and four additional pathways
(green). (e) \- (h): Increase in average EC of PCC-PC interaction model 1
relative to two additional pathways (blue) and four additional pathways
(brown).

## Discussion

Gene transcription is a process that contains several stages and thousands of
reactions. Models that reduce such a complex system to a few parameters run
the risk of offering erroneous interpretations of data. In this paper we have
studied stochastic dynamics of the first two stages – the pre-initiation
complex (PIC) formation and promoter proximal pausing (PPP) – using a detailed
stochastic model. The reaction rates were selected on the basis of
experimental observations, either direct or inferred from optimized model
parameters, and by imposing constraints on the transcriptional efficiency and
on the half-life of the paused state. Four different reaction network
topologies were simulated: 1) binding of Pol II was allowed only when the
promoter proximal pause region was empty; 2) Pol II was allowed to bind when
the promoter proximal pause region was occupied by a Pol II complex, but it
was not allowed to clear the promoter; 3) same as 1) but with two new pathways
added to the reaction network; and 4) same as 1) but with four new pathways
added to the reaction network.

The results showed that in most cases, regardless of the specific values of
the system parameters obtained under these constraints, the number of Pol II
complexes that enter productive elongation per time follow a sub-Poissonian
distribution. Only 4.4 $\%$ of all cases led to super-Poissonian distributions
with the maximum Fano factor of 1.7. This trend was shared by all four network
topologies, although the distributions of Fano factors were shifted slightly
to the right in 2). These results run contrary to the view that noise in gene
expression necessarily comes from the promoter. It is certainly true that
sometimes it does, as was also demonstrated herein: slow activator-enhancer
dynamics led to greater variation in the number of elongation complexes.
However, for fast activator-enhancer binding rates, the Fano factors remained
well below 1. It is not entirely surprising that a sequential set of reactions
leads to small noise; as in reaction cascades Amir  or a compartmentalization
Albert0 .

This study was a step towards understanding how complexity at the promoter and
promoter proximal region effectuates noise in the number of elongation
complexes. Although, based on these results, one cannot comment on the
fluctuations in the copy number of mRNA transcripts, as the journey to being a
fully processed mRNA is far from over, it can be said that the contribution to
the fluctuations coming from the PIC formation and PPP is negligible. Of
course, the present study has only scratched the surface. There remain many
possibilities to explore, such as: what happens when the average half-life of
the PC is much longer/shorter; and how a dependence of the Pol II dissociation
rates on the state of the PCC and the PC affects noise. These and other
questions still need to be investigated, and this paper can serve as a bases
for answering them.

## Appendix

Before we compute $\langle t_{\text{clear}}\rangle$, $\langle
t_{\text{escape}}\rangle$ and $\langle t_{\text{pause}}\rangle$, let us first
label all the states of the PCC and PC:

$\displaystyle
1:\,\,\,\,\,\text{TATA}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,9:\,\,\,\,\,\text{TATA/TBP/B/Pol${}^{+}_{7}$/H}$
$\displaystyle
2:\,\,\,\,\,\text{TATA/TBP}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,10:\,\,\,\,\,\text{TATA/TBP/A/B/Pol${}^{+}_{7,5}$/H}$
$\displaystyle
3:\,\,\,\,\,\text{TATA/TBP/A}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,11:\,\,\,\,\,\text{TATA/TBP/A/B/Pol}$
$\displaystyle
4:\,\,\,\,\,\text{TATA/TBP/B}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,12:\,\,\,\,\,\text{TATA/TBP/A/B/Pol/H}$
$\displaystyle
5:\,\,\,\,\,\text{TATA/TBP/A/B}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,13:\,\,\,\,\,\text{TATA/TBP/A/B/Pol${}^{+}$/H}$
$\displaystyle
6:\,\,\,\,\,\text{TATA/TBP/B/Pol}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,14:\,\,\,\,\,\text{TATA/TBP/A/B/Pol${}^{+}_{7}$/H}$
$\displaystyle
7:\,\,\,\,\,\text{TATA/TBP/B/Pol/H}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,15:\,\,\,\,\,\text{TATA/TBP/A/B/Pol${}^{+}_{7,5}$/H}$
$\displaystyle 8:\,\,\,\,\,\text{TATA/TBP/B/Pol${}^{+}$/H}$

and

$\displaystyle 1:\,\,\,\,\,\text{F/Pol${}_{7,5}$/H${}^{++}$}$ $\displaystyle
2:\,\,\,\,\,\text{F/Pol${}_{7,5}$/H${}^{++}$/DISF}$ $\displaystyle
3:\,\,\,\,\,\text{F/Pol${}_{7,5}$/H${}^{++}$/DISF/HCE}$ $\displaystyle
4:\,\,\,\,\,\text{F/Pol${}_{7,5}$/H${}^{++}$/DISF/HCE/mTASE}$ $\displaystyle
5:\,\,\,\,\,\text{F/Pol${}_{7,5}$/H${}^{++}$/DISF/HCE/mTASE/NELF}$
$\displaystyle
6:\,\,\,\,\,\text{F/Pol${}_{7,5}$/H${}^{++}$/DISF/HCE/mTASE/NELF/Gdown1}$
$\displaystyle
7:\,\,\,\,\,\text{F/Pol${}_{7,5}$/H${}^{++}$/DISF/HCE/mTASE/NELF/Gdown1/PAFC1}$
$\displaystyle
8:\,\,\,\,\,\text{F/Pol${}_{7,5}$/H${}^{++}$/DISF/HCE/mTASE/NELF/Gdown1/PAFC1/SEC}$
$\displaystyle
9:\,\,\,\,\,\text{F/Pol${}_{7,5,2}$/H${}^{++}$/Spt5${}_{p}$/HCE/mTASE/NELF/Gdown1/PAFC1/SEC}$
$\displaystyle
10:\,\,\,\,\,\text{F/Pol${}_{7,5,2}$/H${}^{++}$/Spt5${}_{p}$/HCE/mTASE/NELF/Gdown1/PAFC1/SEC/BRD}$

To compute $\langle t_{\text{clear}}\rangle$, we need to know the cumulative
probability $Q(t)$ that either of these reactions

R1: TATA/TBP/B/Pol${}_{7,5}^{+}$/H$\rightarrow$F/Pol7,5/H+++TATA/TBP R2:
TATA/TBP/A/B/Pol${}_{7,5}^{+}$/H$\rightarrow$F/Pol7,5/H+++TATA/TBP/A

will occur at time $t$. The average of times sampled from $Q(t)$, i. e.
$\langle t_{\text{clear}}\rangle$, is equal to

$\langle t_{\text{clear}}\rangle=\int_{0}^{\infty}dt^{\prime}Q(t^{\prime}).$
(4)

To compute $Q(t)$, let us first define a system $S^{\prime}$ that is identical
to the system in Fig. 3 but one which does not contain reactions R1 and R2.
Then, $Q(t)$ can be computed by a previously published method Albert ; Albert2
, which states that

$Q(t)=\sum_{i}Q_{i}(t),$ (5)

where $Q_{i}(t)$ satisfy

$\frac{d}{dt}Q_{i}(t)=\sum_{j}[T_{ij}+M_{ij}]Q_{j}(t).$ (6)

The nondiagonal matrix elements of $T_{ij}$

$\displaystyle T_{i\neq
j}=\left[\begin{array}[]{ccccccccccccccc}\cdot&k^{\text{off}}_{\text{TBP}}&0&0&0&0&0&0&0&0&0&0&0&0&0\\\
k^{\text{on}}_{\text{TBP}}&\cdot&k^{\text{off}}_{\text{A}}&k^{\text{off}}_{\text{B}}&0&0&0&k^{\text{off}}_{\text{Pol}}&k^{\text{off}}_{\text{Pol}}&k^{\text{off}}_{\text{Pol}}&0&0&0&0&0\\\
0&k^{\text{on}}_{\text{A}}&\cdot&0&k^{\text{off}}_{\text{A$|$B}}&0&0&0&0&0&0&0&k^{\text{off}}_{\text{Pol}}&k^{\text{off}}_{\text{Pol}}&k^{\text{off}}_{\text{Pol}}\\\
0&k^{\text{on}}_{\text{B}}&0&\cdot&k^{\text{off}}_{\text{A}}&k^{\text{off}}_{\text{Pol}}&k^{\text{off}}_{\text{Pol}}&0&0&0&0&0&0&0&0\\\
0&0&k^{\text{on}}_{\text{B}}&k^{\text{on}}_{\text{A}}&\cdot&0&0&0&0&0&k^{\text{off}}_{\text{Pol}}&k^{\text{off}}_{\text{Pol}}&0&0&0\\\
0&0&0&k^{\text{on}}_{\text{Pol}}&0&\cdot&k^{\text{off}}_{\text{H}}&0&0&0&k^{\text{off}}_{\text{A}}&0&0&0&0\\\
0&0&0&0&0&k^{\text{on}}_{\text{H}}&\cdot&0&0&0&0&k^{\text{off}}_{\text{A}}&0&0&0\\\
0&0&0&0&0&0&k^{\text{on}}_{\text{+}}&\cdot&0&0&0&0&k^{\text{off}}_{\text{A}}&0&0\\\
0&0&0&0&0&0&0&k^{\text{on}}_{\text{Ser7}}&\cdot&0&0&0&0&k^{\text{off}}_{\text{A}}&0\\\
0&0&0&0&0&0&0&0&k^{\text{on}}_{\text{Ser5}}&\cdot&0&0&0&0&k^{\text{off}}_{\text{A}}\\\
0&0&0&0&0&0&k^{\text{on}}_{\text{A}}&0&0&0&k^{\text{on}}_{\text{H}}&\cdot&0&0&0\\\
0&0&0&0&0&0&0&k^{\text{on}}_{\text{A}}&0&0&0&k^{\text{on}}_{\text{+}}&\cdot&0&0\\\
0&0&0&0&0&0&0&0&k^{\text{on}}_{\text{A}}&0&0&0&k^{\text{on}}_{\text{Ser7}}&\cdot&0\\\
0&0&0&0&0&0&0&0&0&k^{\text{on}}_{\text{A}}&0&0&0&k^{\text{on}}_{\text{Ser5}}&\cdot\\\
\end{array}\right]$ (21)

are the probabilities for state $j\neq i$ to transition to state $i$; the
diagonal elements, $T_{ii}$

$\displaystyle
T_{11}=-k^{\text{on}}_{\text{TBP}}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,T_{99}=-(k^{\text{on}}_{\text{A}}+k^{\text{on}}_{\text{Ser5}}+k^{\text{off}}_{\text{Pol}})$
$\displaystyle
T_{22}=-(k^{\text{on}}_{\text{A}}+k^{\text{on}}_{\text{B}}+k^{\text{off}}_{\text{TBP}})\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,T_{10,10}=-(k^{\text{on}}_{\text{A}}+k^{\text{off}}_{\text{Pol}})$
$\displaystyle
T_{33}=-(k^{\text{off}}_{\text{A}}+k^{\text{on}}_{\text{A$|$B}})\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,T_{11,11}=-(k^{\text{on}}_{\text{A}}+k^{\text{on}}_{\text{H}}+k^{\text{off}}_{\text{Pol}})$
$\displaystyle
T_{44}=-(k^{\text{on}}_{\text{A}}+k^{\text{off}}_{\text{B}}+k^{\text{on}}_{\text{Pol}})\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,T_{12,12}=-(k^{\text{off}}_{\text{A}}+k^{\text{off}}_{\text{H}}+k^{\text{on}}_{\text{+}}+k^{\text{off}}_{\text{Pol}})$
$\displaystyle
T_{55}=-(k^{\text{off}}_{\text{A}}+k^{\text{off}}_{\text{A$|$B}}+k^{\text{on}}_{\text{Pol}})\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,T_{13,13}=-(k^{\text{off}}_{\text{A}}+k^{\text{on}}_{\text{Ser7}}+k^{\text{off}}_{\text{Pol}})$
$\displaystyle
T_{66}=-(k^{\text{on}}_{\text{A}}+k^{\text{on}}_{\text{H}}+k^{\text{off}}_{\text{Pol}})\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,T_{14,14}=-(k^{\text{off}}_{\text{A}}+k^{\text{on}}_{\text{Ser5}}+k^{\text{off}}_{\text{Pol}})$
$\displaystyle
T_{77}=-(k^{\text{on}}_{\text{A}}+k^{\text{on}}_{\text{H}}+k^{\text{on}}_{\text{+}}+k^{\text{off}}_{\text{Pol}})\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,T_{15,15}=-(k^{\text{off}}_{\text{A}}+k^{\text{off}}_{\text{Pol}}),$
$\displaystyle
T_{88}=-(k^{\text{on}}_{\text{A}}+k^{\text{on}}_{\text{Ser7}}+k^{\text{off}}_{\text{Pol}})$

are probabilities for state $i$ to transition out of $i$. The always diagonal
matrix elements
$M_{ij}=k^{\text{on}}_{\text{clear}}\delta_{ij}(\delta_{i,10}+\delta_{i,15})$
give the probability for a state $i$ to transition into F/Pol7,5/H++ via R1 or
R2. If all elements of $M_{ij}$ were zero, Eq. (6) would become the Master
equation for $S^{\prime}$.

The same method can be applied to compute $\langle t_{\text{escape}}\rangle$.
In this case, $S^{\prime}$ contains all reactions in Fig. 4 except for the one
that leads to PE. When a reaction that leads to the state $\emptyset$ occurs,
i. e. where the Pol II complex dissociates from the DNA, the variable
F/Pol7,5/H++ is set to 1, and the process of reaching PE must start all over
again. The off-diagonal elements of $T_{ij}$ for this system then read:

$\displaystyle T_{i\neq
j}=\left[\begin{array}[]{cccccccccc}\cdot&k^{\text{off}}_{\text{DISF}}&k^{\text{off}}_{\text{Pol}}&k^{\text{off}}_{\text{Pol}}&k^{\text{off}}_{\text{Pol}}&k^{\text{off}}_{\text{Pol}}&k^{\text{off}}_{\text{Pol}}&k^{\text{off}}_{\text{Pol}}&k^{\text{off}}_{\text{Pol}}&k^{\text{off}}_{\text{Pol}}\\\
k^{\text{on}}_{\text{DISF}}&\cdot&k^{\text{off}}_{\text{HCE}}&0&0&0&0&0&0&0\\\
0&k^{\text{on}}_{\text{HCE}}&\cdot&k^{\text{off}}_{\text{mTASE}}&0&0&0&0&0&0\\\
0&0&k^{\text{on}}_{\text{mTASE}}&\cdot&k^{\text{off}}_{\text{NELF}}&0&0&0&0&0\\\
0&0&0&k^{\text{on}}_{\text{NELF}}&\cdot&k^{\text{off}}_{\text{Gdown}}&0&0&0&0\\\
0&0&0&0&k^{\text{on}}_{\text{Gdown}}&\cdot&k^{\text{off}}_{\text{PAFC}}&0&0&0\\\
0&0&0&0&0&k^{\text{on}}_{\text{PAFC}}&\cdot&k^{\text{off}}_{\text{SEC}}&0&0\\\
0&0&0&0&0&0&k^{\text{on}}_{\text{SEC}}&\cdot&0&0\\\
0&0&0&0&0&0&0&k^{\text{on}}_{\text{Ser2}}&\cdot&k^{\text{off}}_{\text{BRD}}\\\
0&0&0&0&0&0&0&0&k^{\text{on}}_{\text{BRD}}&\cdot\\\ \end{array}\right],$ (33)

while the diagonal elements are given by

$\displaystyle
T_{11}=-k^{\text{on}}_{\text{DISF}}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,T_{66}=-(k^{\text{off}}_{\text{Gdown}}+k^{\text{on}}_{\text{PAFC}}+k^{\text{off}}_{\text{Pol}})$
$\displaystyle
T_{22}=-(k^{\text{off}}_{\text{DISF}}+k^{\text{on}}_{\text{HCE}}+k^{\text{off}}_{\text{Pol}})\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,T_{77}=-(k^{\text{off}}_{\text{PAFC}}+k^{\text{on}}_{\text{SEC}}+k^{\text{off}}_{\text{Pol}})$
$\displaystyle
T_{33}=-(k^{\text{off}}_{\text{HCE}}+k^{\text{on}}_{\text{mTASE}}+k^{\text{off}}_{\text{Pol}})\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,T_{88}=-(k^{\text{off}}_{\text{SEC}}+k^{\text{on}}_{\text{Ser2}}+k^{\text{off}}_{\text{Pol}})$
$\displaystyle
T_{44}=-(k^{\text{off}}_{\text{mTASE}}+k^{\text{on}}_{\text{NELF}}+k^{\text{off}}_{\text{Pol}})\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,T_{99}=-(k^{\text{on}}_{\text{BRD}}+k^{\text{off}}_{\text{Pol}})$
$\displaystyle
T_{55}=-(k^{\text{off}}_{\text{NELF}}+k^{\text{off}}_{\text{Gdown}}+k^{\text{off}}_{\text{Pol}})\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,T_{10,10}=-(k^{\text{off}}_{\text{BRD}}+k^{\text{off}}_{\text{Pol}}).$

For the case of $\langle t_{\text{pause}}\rangle$, we need to remove all
reactions that lead to the state $\emptyset$, and also the reaction that leads
to PE. This renders both diagonal and off-diagonal elements of $T_{ij}$
identical to Eq. (33) and (Appendix) at $k^{\text{off}}_{\text{Pol}}=0$, while
$M_{ij}=-[k^{\text{off}}_{\text{Pol}}(1-\delta_{1,i})+k_{\text{escape}}^{\text{on}}\delta_{i,10}]\delta_{ij}$.
The reason for omitting the state $i=1$ from $M_{ij}$ is that via the reaction
F/Pol7,5/H${}^{++}\rightarrow\emptyset$ it leads to itself (since
$\emptyset=$F/Pol7,5/H++).

## Acknowledgments

We want to thank the creator of the YouTube channel theCrux
(https://www.youtube.com/c/theCrux/featured). It was a starting point for
researching material for this paper.

## References

  * (1) Luse DS (2014) The RNA polymerase II preinitiation complex, Transcription, 5(1): e27050
  * (2) Greber BJ, Nogales E (2019) The Structures of Eukaryotic Transcription Pre-initiation Complexes and Their Functional Implications Subcell Biochem, 93: 143–192
  * (3) Petrenko N, Jin Y, Dong L, Wong KH, Struhl K (2019) Requirements for RNA polymerase II preinitiation complex formation in vivo, eLife, 8:e43654
  * (4) Chen FX, Smith ER, Shilatifard A (2018) Born to run: control of transcription elongation by RNA polymerase II Nature Reviews Molecular Cell Biology, 19, 464–478
  * (5) Jonkers I, Lis JT (2015) Getting up to speed with transcription elongation by RNA polymerase II, Nat Rev Mol Cell Biol, 16(3): 167–177
  * (6) Mayer A, Landry HM, Churchman LS (2017) Pause $\&$ Go: from the discovery of RNA polymerase pausing to its functional implications, Curr Opin Cell Biol, 46: 72–80
  * (7) Li J, Gilmour DS (2011) Promoter proximal pausing and the control of gene expression, Curr Opin in Gen $\&$ Dev, 21:231–235
  * (8) Levine M (2011) Paused RNA Polymerase II as a Developmental Checkpoint, Cell, 13;145(4):502-11
  * (9) Core LJ, Lis TJ (2008) Transcription Regulation Through Promoter-Proximal Pausing of RNA Polymerase II, Science, 319, 1791
  * (10) Core L, Adelman K (2019) Promoter-proximal pausing of RNA polymerase II: a nexus of gene regulation, Genes Dev, 33(15-16):960-982
  * (11) Gonzalez MN, Blears D, Svejstrup JQ (2021) Causes and consequences of RNA polymerase II stalling during transcript elongation, Nature Reviews Molecular Cell Biology, 22, 3–21
  * (12) Bai L, Shundrovsky A, Wang MD (2004) Sequence-dependent Kinetic Model for Transcription Elongation by RNA Polymerase, J. Mol. Biol. 344, 335–349
  * (13) Muniz L, Nicolas E, Trouche D (2021) RNA polymerase II speed: a key player in controlling and adapting transcriptome composition, The EMBO Journal, 40: e105740
  * (14) Rosonina E, Kaneko S, Manley JL (2006) Terminating the transcript: breaking up is hard to do, Genes $\&$ Dev, 20:1050–1056
  * (15) Proudfoot NJ (2016) Transcriptional termination in mammals: Stopping the RNA polymerase II juggernaut, Science, 352(6291)
  * (16) Porrua O, Libri D (2015) Transcription termination and the control of the transcriptome: why, where and how to stop, Nat Rev Mol Cell Biol, 16(3):190-202
  * (17) Porrua O, Boudvillain M, Libri D (2016) Transcription Termination: Variations on Common Themes, Trends in Genetics, 32(8): 508-522
  * (18) Kuehner JN, Pearson EL, Moore C (2011) Unravelling the means to an end: RNA polymerase II transcription termination, Nature Reviews Molecular Cell Biology, 12: 283–294
  * (19) Richard P, Manley JL (2009) Transcription termination by nuclear RNA polymerases, Genes $\&$ Dev, 23:1247–1269
  * (20) Luo W, Johnson AW, Bentley DL (2006) The role of Rat1 in coupling mRNA 3’-end processing to transcription termination: implications for a unified allosteric–torpedo model, Genes $\&$ Dev, 20:954–965
  * (21) Kornblihtt AR (2004) Shortcuts to the end, Nat Struct Mol Biol, 11(12):1156-7
  * (22) Stefl R, Skrisovska L, Allain FHT (2005) RNA sequence- and shape-dependent recognition by proteins in the ribonucleoprotein particle, EMBO Rep, 6(1): 33–38.
  * (23) Bentley DL (2014) Coupling mRNA processing with transcription in time and space, Nature Reviews Genetics, 15:163–175
  * (24) Walczak AM, Mugler A, Wiggins CH (2012) Analytic Methods for Modeling Stochastic Regulatory Networks, Computational Modeling of Signaling Networks, 273-322
  * (25) Ribeiro AS (2010) Stochastic and delayed stochastic models of gene expression and regulation, Mathematical Biosciences, 223(1): 1-11
  * (26) Dublanche Y, Michalodimitrakis K, Kümmerer N, Foglierini M, Serrano L (2006) Noise in transcription negative feedback loops: simulation and experimental analysis, Mol Syst Biol, 2:41
  * (27) Tao Y, Zheng X, Sun Y (2007) Effect of feedback regulation on stochastic gene expression, J Theor Biol, 247(4):827-36.
  * (28) Marquez-Lago TT, Stelling J (2010) Counter-Intuitive Stochastic Behavior of Simple Gene Circuits with Negative Feedback, Biophys J, 98(9): 1742–1750.
  * (29) Zhang H, Chen Y, Chen Y (2012) Noise Propagation in Gene Regulation Networks Involving Interlinked Positive and Negative Feedback Loops, PLoS ONE 7(12): e51840
  * (30) Karmakar R (2020) Control of noise in gene expression by transcriptional reinitiation, J. Stat. Mech. 063402
  * (31) Boettiger AN, Ralph PL, Evans SN (2011) Transcriptional Regulation: Effects of Promoter Proximal Pausing on Speed, Synchrony and Reliability, PLoS Computational Biology, 7(5): e1001136
  * (32) Liu B, Yuan Z, Aihara K, Chen L (2011) Reinitiation enhances reliable transcriptional responses in eukaryotes, J R Soc Interface. 2014 Aug 6; 11(97): 20140326.
  * (33) Filatova T, Popovic N, Grima R (2020) Statistics of nascent and mature RNA fluctuations in a stochastic model of transcriptional initiation, elongation, pausing, and termination, Bulletin of Mathematical Biology, 83(3): 3
  * (34) Braichenko S, Holehouse J, Grima R (2021) Distinguishing between models of mammalian gene expression: telegraphlike models versus mechanistic models, J. R. Soc. Interface, 18: 20210510.
  * (35) Choubey S, Kondev J, Sanchez A (2010) Deciphering Transcriptional Dynamics In Vivo by Counting Nascent RNA Molecules, PLoS Comput Biol 11(11): e1004345
  * (36) Choubey S (2018) Nascent RNA kinetics: Transient and steady state behavior of models of transcription, Phys Rev E, 97(2-1):022402
  * (37) Xu H, Skinner SO, Sokac AM, Golding I (2016) Stochastic Kinetics of Nascent RNA, Phys Rev Lett, 117(12):128101
  * (38) Cao Z, Grima R (2020) Analytical distributions for detailed models of stochastic gene expression in eukaryotic cells, PNAS, 117(9): 4682-4692
  * (39) Pal M, Ponticelli AS (2005) The Role of the Transcription Bubble and TFIIB in Promoter Clearance by RNA Polymerase II, Molecular Cell, 19, 101–110
  * (40) Darst SA, Kubalek EW, Kornberg RD (1989) Three-dimensional structure of Escherichia coli RNA polymerase holoenzyme determined by electron crystallography, Nature, 340(6236):730-2
  * (41) Hahn S (2004) Structure and mechanism of the RNA Polymerase II transcription machinery, Nat Struct Mol Biol, 11(5): 394–403.
  * (42) Schier AC, Taatjes DJ (2020) Structure and mechanism of the RNA polymerase II transcription machinery, Genes $\&$ Dev, 34: 465-488
  * (43) Adelman K, Lis JT (2012) Promoter-proximal pausing of RNA polymerase II: emerging roles in metazoans, Nat Rev Genet, 13(10): 720–731.
  * (44) Shao W, Zeitlinger J (2017) Paused RNA polymerase II inhibits new transcriptional initiation, Nature Genetics, 49, 1045–1051
  * (45) Gressel S, Schwalb B, Cramer P (2019) The pause-initiation limit restricts transcription activation in human cells, Nature Communications, 10:3603
  * (46) Cosma MP (2002) Ordered Recruitment: Gene-Specific Mechanism of Transcription Activation, Molecular Cell, 10: 227–236
  * (47) Fei Xavier Chen, 1 Peng Xie, 2 Clayton K. Collings, 1 Kaixiang Cao, 1 Yuki Aoi, 1 Stacy A. Marshall, 1 Emily J. Rendleman, 1 Michal Ugarenko, 1 Patrick A. Ozark, 1 Anda Zhang, 3 Ramin Shiekhattar, 3 Edwin R. Smith, 1 Michael Q. Zhang, 2,4 Ali Shilatifard (2017) PAF1 regulation of promoter-proximal pause release via enhancer activation, Science, 357(6357):1294-1298
  * (48) Core LJ, Lis JT (2008) Transcription Regulation Through Promoter-Proximal Pausing of RNA Polymerase II, Science, 319, 1791
  * (49) Ma J (2011) Transcriptional activators and activation mechanisms, Protein Cell, 2(11): 879–888
  * (50) Zhang Z, English BP, Grimm JB, Kazane SA, Hu W, Tsai A, Inouye C, You C, Piehler J, Schultz PG, Lavis LD, Revyakin A, Tjian R (2016) Rapid dynamics of general transcription factor TFIIB binding during preinitiation complex assembly revealed by single-molecule analysis, Genes Dev, 30(18): 2106-2118
  * (51) Revyakin A, Zhang A, Coleman RA, Li Y, Inouye C, Lucas JK, Park S-R, Chu S, Tjian R (2012) Transcription initiation by human RNA polymerase II visualized at single-molecule resolution, Genes Dev, 26(15):1691-702
  * (52) Jung Y, Mikata Y, Lippard SJ (2001) Kinetic Studies of the TATA-binding Protein Interaction with Cisplatin-modified DNA Journal of Biological Chemistry, 276:47, 43589–43596
  * (53) Darzacq X, Shav-Tal Y, De Turris V, Brody Y, Shenoy SM, Phair RD, Singer RH (2007) In vivo dynamics of RNA polymerase II transcription Nature Structural and Molecular Biology, 14, 796–806
  * (54) Presman DM, Ball DA, Paakinaho V, Grimm JB, Lavis LD, Karpova TS, Hager GL (2017) Quantifying transcription factor binding dynamics at the single-molecule level in live cells Methods, 123:76-88
  * (55) Hasegawa Y, Struhl K (2019) Promoter-specific dynamics of TATA-binding protein association with the human genome Genome Res, doi: 10.1101/gr.254466.119
  * (56) Heiss G, Ploetz E, Von Voithenberg LV, Viswanathan R, Glaser S, Schluesche P, Madhira S, Meisterernst M, Auble DT, Lamb DC (2019) Conformational changes and catalytic inefficiency associated with Mot1-mediated TBP–DNA dissociation Nucleic Acids Research, 47(6): 2793–2806
  * (57) Buckley MS, Kwak H, Zipfel WR, Lis JT (2014) Kinetics of promoter Pol II on Hsp70 reveal stable pausing and key insights into its regulation Genes and Dev, 28: 14-19
  * (58) Gillespie DT, (1977) Exact Stochastic Simulation of Coupled Chemical Reactions. J. Phys. Chem. 81(25), 2340-2361
  * (59) Amir A, Kobiler O, Rokney A, Oppenheim AB, Stavans J (2007) Noise in timing and precision of gene activities in a genetic cascade Mol Syst Biol, 3: 71
  * (60) Albert J (2015) Is the Cell Nucleus a Necessary Component in Precise Temporal Patterning? PLoS ONE 10(7): e0134239.
  * (61) Albert J (2019) Path integral approach to generating functions for multistep post-transcription and post-translation processes and arbitrary initial conditions, J Math Biol, 79(6-7):2211-2236
  * (62) Albert J (2021) Dimensionality reduction via path integration for computing mRNA distributions, J Math Biol, 83(5): 57


# Computation of Rate-Distortion-Perception Function under $f$-Divergence
Perception Constraints

Giuseppe Serra, Photios A. Stavrou, Marios Kountouris  Communication Systems
Department, EURECOM, Sophia-Antipolis, France
<EMAIL_ADDRESS>
###### Abstract

In this paper, we study the computation of the rate-distortion-perception
function (RDPF) for discrete memoryless sources subject to a single-letter
average distortion constraint and a perception constraint that belongs to the
family of $f$-divergences. For that, we leverage the fact that RDPF, assuming
mild regularity conditions on the perception constraint, forms a convex
programming problem. We first develop parametric characterizations of the
optimal solution and utilize them in an alternating minimization approach for
which we prove convergence guarantees. The resulting structure of the
iterations of the alternating minimization approach renders the implementation
of a generalized Blahut-Arimoto (BA) type of algorithm infeasible. To overcome
this difficulty, we propose a relaxed formulation of the structure of the
iterations in the alternating minimization approach, which allows for the
implementation of an approximate iterative scheme. This approximation is
shown, via the derivation of necessary and sufficient conditions, to guarantee
convergence to a globally optimal solution. We also provide sufficient
conditions on the distortion and the perception constraints which guarantee
that our algorithm converges exponentially fast. We corroborate our
theoretical results with numerical simulations, and we draw connections with
existing results.

##  I Introduction

The theoretical framework of rate distortion theory subject to a single-letter
average distortion constraint stems from the seminal work of Shannon in [1,
2]. Therein, Shannon described, for the first time, the fundamental trade-offs
between the desired bit rate used for a compressed representation of the
source messages and the associated achievable distortion criterion attained
between the source message and its reconstructed representation. The
mathematical representation in rate distortion theory is manifested by the
rate-distortion function (RDF). Rate distortion theory has been the
foundational basis to study and develop lossy compression algorithms for
various multimedia applications.

In recent years, it has been shown through multiple works, spanning from
machine learning and computer vision to multimedia applications [3, 4, 5, 6,
7, 8], that focusing exclusively on distortion minimization does not
necessarily imply a good perceptual quality of the reconstructed signal, where
perceptual quality refers to the property of a sample to appear visually
pleasing from a human perspective. Motivated by the need for a general
characterization of RDF to enable encompassing the perceptual quality of the
sample, Blau and Michaeli in [9] introduced a generalization of the single-
letter RDF, coined rate-distortion-perception function (RDPF). The specific
information theoretic characterization complements the classical single-letter
distortion constraint between a source message and its reconstruction, which
is inherent in RDF formulation, with a divergence constraint between the
induced distributions of the source and its estimated value. The divergence
constraint in RDPF is precisely used as a proxy of the human perception,
measuring the degree of satisfaction in the consumption of the data from a
human perspective. The divergence constraint can also be viewed as a semantic
quality metric, which measures the degree of relevance of the reconstructed
source from the perspective of the observer, a point first hinted at in [10].
Another relevant yet different setup is the recently introduced robust source
coding framework, see, e.g., [11] (and references therein), in which in place
of the perception quality, there exists an additional distortion criterion.

Since its conception, RDPF has received substantial interest from the
information theory community. Theis and Wagner in [12] proved that the RDPF
can be achieved via stochastic, variable-length codes by making use of a
strong functional representation lemma [13], whereas Chen et al. in [14]
studied the role of stochasticity in the encoder/decoder structure and proved
the achievability of the RDPF by deterministic codes (except certain extreme
cases) in the asymptotic regime. Wagner in [15] considered the case of perfect
perceptual quality in the definition of RDPF and devised a coding theorem that
allows for a specified amount of common randomness between the encoder and
decoder.

It should be emphasized that similarly to the classical RDF, there are no
known closed-form representations of the RDPF for general alphabet sources. In
fact, there are only a few examples in the literature where analytical
expressions are provided for the RDPF, such as the case of binary sources
subject to Hamming distortion and total variation distance [9, 16] or the case
of a Gaussian source subject to a mean-squared error distortion and a
2-Wasserstein distance [4].

In this paper, we focus on the computation of the RDPF for discrete memoryless
sources subject to a single-letter average distortion constraint and a
perception constraint that belongs to the class of $f$-divergences111For a
mathematical background on $f$-divergences and their properties we refer the
reader to [17].. In particular, we leverage the fact that under mild
regularity conditions on the perception constraint (i.e., convexity on the
second argument) the RDPF forms a convex program. This enables us to derive a
parametric characterization of the optimal solution of the RDPF (Lemma 1),
which is subsequently utilized to construct an alternating minimization
procedure222For details on the alternating minimization procedure, see e.g.,
[18, 19]. for which we also establish convergence guarantees (Theorem
LABEL:th:BA_Convergence). The resulting structure of the iterations in Theorem
LABEL:th:BA_Convergence prohibits the implementation of a generic Blahut-
Arimoto (BA) algorithm similar to what is already known for the classical rate
distortion theory for $\operatorname{i.i.d}$ sources and single-letter
distortions [20]. To overcome this technical difficulty, we introduce a new
relaxed formulation of the structure of the iterations in Theorem
LABEL:th:BA_Convergence, which results in a variant of an approximate BA
algorithm (Theorem LABEL:th:BA_Convergence_Approximate). Additionally, in
Theorem LABEL:th:BA_Convergence_Approximate, we derive necessary and
sufficient conditions to ensure that our approximation algorithm converges to
a globally optimal solution. In light of our result in Theorem
LABEL:th:BA_Convergence_Approximate, we also provide sufficient conditions on
the structure of the distortion and the perception constraints based on which
our algorithm converges exponentially fast (Theorems
LABEL:th:_EXPConvergenceBase, LABEL:th:_approximation_exponential_interval).
We corroborate our theoretical findings with numerical simulations and draw
comparisons with existing results in the literature (Section
LABEL:sec:_Numerical_Examples).

### Notation

We denote with $p_{x}(x)$ the probability distribution over the source
alphabet $\mathcal{X}$ evaluated on the symbol $x$, and by
$q_{\hat{x}}(\hat{x})$ any arbitrary marginal probability on the output
alphabet $\mathcal{\hat{X}}$ evaluated on the symbol $\hat{x}$.
$Q_{\hat{x}|x}(\hat{x}|x)$ denotes the entry $(\hat{x},x)$ of the transition
matrix $Q_{\hat{x}|x}$ while $Q_{\hat{x}}(\hat{x})$ denotes the marginal on
$\mathcal{\hat{X}}$ induced by $p_{x}$ and $Q_{\hat{x}|x}$, evaluated on the
symbol $\hat{x}$. We denote by $\mathbb{E}\left[\cdot\right]$ the expectation
operator, and by $\mathbb{E}_{q}\left[\cdot\right]$ the probability
distribution $q$ on which the expectation operator is applied. We denote by
$p_{1}[p_{2}]$ the explicit form of the functional dependence of some
probability distribution $p_{1}$ functionally dependent on another probability
distribution $p_{2}$. We denote by $D(\cdot||\cdot)$ any divergence measure
and by $D_{f}(\cdot||\cdot)$, $D_{KL}(\cdot||\cdot)$,
$D_{\chi^{2}}(\cdot||\cdot)$, $TV(\cdot||\cdot)$, the class of $f$-divergence,
the Kullback–Leibler divergence, the chi-squared divergence and the total
variation distance, respectively. We denote by $f\in C^{0}$, the continuous
function defining the $f$-divergence and $\partial f$ denotes its sub-gradient
[21, Definition 8.3]. For a continuous and twice differentiable function $f\in
C^{2}$, we denote by $f^{\prime\prime}(\cdot)$ the second derivative with
respect to its argument.

##  II Preliminaries on the RDPF

In this section, we consider finite alphabets sources and deterministic
encoders/decoders pairs and define the minimum achievable rates subject to
average per-letter distortion and average per-letter perception constraints.
Our analysis herein stems from recent results in [14].

We assume that we are given an $\operatorname{i.i.d}$ sequence of $n$-length
random variables ${X}^{n}$ that induce the probability distribution $p_{x}$.
The source sequence is received by an encoder $(e)$ that generates the index
$e(X^{n})\in{\cal Z}$, ${\cal Z}=\\{1,2,\ldots,2^{nR}\\}$, whereas at the
decoder $(g)$, the system reconstructs an estimate of $\hat{X}^{n}$. Formally,
the encoder and decoder are deterministic mappings with
$e:\mathcal{X}^{n}\to\mathcal{Z}$ and $g:\mathcal{Z}\to\mathcal{\hat{X}}^{n}$,
respectively.

We let $d:\mathcal{X}\times\mathcal{\hat{X}}\to\mathcal{R}_{0}^{+}$ to denote
a single-letter distortion function and
$D:\mathcal{P}\times\mathcal{Q}\to\mathcal{R}_{0}^{+}$ to denote a divergence
measure. Moreover, we define the fidelity criterion $\Delta$ as the expected
per-symbol distortion and the fidelity criterion $\Phi$ as the expected per-
symbol divergence333Following for instance [14, Remark 3], one can choose the
perception fidelity criterion to be
$D(p_{x}||q_{\hat{x}_{i}}),~{}i=1,\ldots,n$, or
$D(p_{x}||\sum_{i=1}^{n}q_{\hat{x}_{i}})$. Both types of fidelity criteria
result in the same operational quantity for finite alphabets in the asymptotic
regime. as follows:

$\displaystyle\Delta\triangleq\mathbb{E}\left[\frac{1}{n}\sum_{i=1}^{n}d(x_{i},\hat{x}_{i})\right]\qquad\Phi\triangleq\frac{1}{n}\sum_{i=1}^{n}D(p_{x}||q_{\hat{x}_{i}}).$

We are now ready to introduce the definition of achievability and that of
infimum of all achievable rates.

######  Definition 1.

(Achievability) Given a distortion level $D>0$ and a perception constraint
$P>0$, a rate $R$ is said to be $(D,P)$-achievable if for an arbitrary
$\epsilon>0$, there exists, for large enough n, a deterministic lossy source
code $(n,M,\Delta,\Phi)$ with $M\leq 2^{n(R+\epsilon)}$ such that $\Delta\leq
D+\epsilon$ and $\Phi\leq P+\epsilon$. Then, we define

$\displaystyle R_{nr}(D,P)\equiv\inf\\{R:(R,D,P)\text{ is achievable}\\}.$ (1)

Next, we give the definition of the information theoretic characterization of
the RDPF (see [9]) assuming that $D>0$ and $P>0$.

######  Definition 2.

(RDPF) For a given finite alphabet source distribution $p_{x}$, a single-
letter distortion $d(\cdot,\cdot)$ and a divergence $D(\cdot||\cdot)$, the
RDPF is characterized as follows:

$\displaystyle\begin{split}R(D,P)=&\min_{Q_{\hat{x}|x}}I(X,\hat{X})\\\
\textrm{s.t.}&\quad\mathbb{E}\left[d(x,\hat{x})\right]\leq D,\quad
D(p_{x}||Q_{\hat{x}})\leq P\end{split}$ (2)

where $D\in[D_{\min},D_{\max}]\subset(0,\infty)$,
$P\in[P_{\min},P_{\max}]\subset(0,\infty)$ and

$\displaystyle
I(X,\hat{X})=D_{KL}(p_{x}Q_{\hat{x}|x},p_{x}Q_{\hat{x}})\triangleq
I(p_{x},Q_{\hat{x}|x})$ (3)

where $I(p_{x},Q_{\hat{x}|x})$ highlights the dependency on
$\\{p_{x},Q_{\hat{x}|x}\\}$.

We stress the following technical remarks on Definition 2.

######  Remark 1.

(On Definition 2) Following [9], it can be shown that (2) has some useful
properties, under mild regularity conditions. In particular, [9, Theorem 1]
shows that $R(D,P)$ is (i) monotonically non-increasing function in both
$D\in[D_{\min},D_{\max}]\subset[0,\infty)$ and
$P\in[P_{\min},P_{\max}]\subset[0,\infty)$; (ii) convex if the divergence
$D(\cdot||\cdot)$ is convex in its second argument.

In the sequel, we consider that in (2) the perception constraint is an
$f$-divergence, i.e., $D(\cdot||\cdot)=D_{f}(\cdot||\cdot)$, which is known to
be convex in both arguments [22, Lemma 4.1]. Hence in light of the discussion
in Remark 1, $R(D,P)$ forms a convex programming problem.

We conclude this section by providing a theorem that connects $R_{nr}(D,P)$
with $R(D,P)$ for finite alphabets, as long as $D>0$ and $P>0$.

######  Theorem 1.

For $|{\cal X}|<\infty$, $D>0$, $P>0$, we obtain

$\displaystyle R_{nr}(D,P)=R(D,P).$ (4)

###### Proof:

This is a consequence of [14, Assumption 2] that results into [14, Theorem 2].
∎

It should be noted that in the previous analysis, we excluded the extreme case
where $P=0$. This is because, in that scenario, deterministic encoders and
decoders do not achieve $R(D,0)$ and one instead requires common [12, Theorem
3] or private [14, Theorems 4] randomness to achieve it.

##  III Main Results

In this section, we present our main results. We start by reformulating (2)
into a double minimization problem.

######  Lemma 1.

(Double minimization) Let $s_{1}\geq{0}$, $s_{2}\geq{0}$, and define
$s=(s_{1},s_{2})$. Moreover, let $D>0$, $P>0$ and let
$D(\cdot||\cdot)=D_{f}(\cdot||\cdot)$. Then (2) can be expressed as a double
minimum as follows:

$\displaystyle\begin{split}R(D,P)=&-s_{1}D-s_{2}P+\min_{Q_{\hat{x}|x}}\min_{q_{\hat{x}}}\Bigl{[}s_{1}\mathbb{E}\left[d(x,\hat{x})\right]\\\
&+s_{2}D_{f}(p_{x}||Q_{\hat{x}})+D_{KL}(p_{x}Q_{\hat{x}|x}||p_{x}q_{\hat{x}})\Bigr{]}\end{split}$
(5)

where $D=\mathbb{E}_{Q_{\hat{x}|x}^{*}}\left[d(x,\hat{x})\right]$,
$P=D_{f}(p_{x}||Q_{\hat{x}}^{*})$, with $Q_{\hat{x}|x}^{*}$ achieving the
minimum. Furthermore, for fixed $Q_{\hat{x}|x}(\hat{x}|x)$, the right side of
(5) is minimized by

$\displaystyle
q_{\hat{x}}(\hat{x})=\sum_{x\in\mathcal{X}}p_{x}(x)Q_{\hat{x}|x}(\hat{x}|x).$
(6)

For fixed $q_{\hat{x}}$, the right side of (5) is minimized by

$\displaystyle Q_{\hat{x}|x}(\hat{x}|x)$

where

$\displaystyle A(x,,s$
$\displaystyle=\exp\left\\{-s_{1}d(x,\hat{x})-s_{2}g(p_{x},Q_{\hat{x}},\hat{x})\right\\}$
(7) $\displaystyle g(p_{x},Q_{\hat{x}},\hat{x})$
$\displaystyle=f\left(\tfrac{p_{x}(\hat{x})}{Q_{\hat{x}}(\hat{x})}\right)-\tfrac{p_{x}(\hat{x})}{Q_{\hat{x}}(\hat{x})}\partial
f\left(\tfrac{p_{x}(\hat{x})}{Q_{\hat{x}}(\hat{x})}\right).$

We note that Lemma 1 differs from [23, Theorem 6.3.3] in
(LABEL:eq:_optimization_Qxx_-_Q). Specifically, the presence of the additional
perception constraint $D_{f}(\cdot||\cdot)$ in (2) changes the functional
properties of the parametric solution (LABEL:eq:_optimization_Qxx_-_Q), as it
requires an additional exponential term, i.e.,
$s_{2}g(p_{x},Q_{\hat{x}},\hat{x})$, with $g(\cdot)$ depending on the induced
marginal $Q_{\hat{x}}$.

The next corollary is a consequence of Lemma 1.

######  Corollary 1.

$R(D,P)$ in (5) can be reformulated as follows:

$\displaystyle\begin{split}R(D_{s},P_{s})=&-s_{1}D_{s}-s_{2}P_{s}\\\
&+\min_{q_{\hat{x}}}s_{2}\sum_{\hat{x}\in\mathcal{\hat{X}}}p_{x}(\hat{x})\partial
f\left(\tfrac{p_{x}(\hat{x})}{Q_{\hat{x}}[q_{\hat{x}}](\hat{x})}\right)\\\
&-\sum_{x\in\mathcal{X}}p_{x}(x)\log\left(\sum_{\hat{x}\in\mathcal{\hat{X}}}q_{\hat{x}}(\hat{x})A(x,,s)\right)\end{split}$
(8)

where $q_{\hat{x}}^{*}$ achieves the minimum and

$\displaystyle D_{s}$
$\displaystyle=\sum_{(x,\hat{x})\in\mathcal{X}\times\mathcal{\hat{X}}}p_{x}(x)\tfrac{q_{\hat{x}}^{*}(\hat{x})A(x,,s)}{\sum_{i\in\mathcal{\hat{X}}}q_{\hat{x}}^{*}(i)A(x,i,s)}d(x,\hat{x}$
$\displaystyle P_{s}$
$\displaystyle=D_{f}(p_{x}||Q_{\hat{x}}[q_{\hat{x}}^{*}]).$

Next, we proceed to construct an alternating minimization procedure and show
its convergence to a point of $R(D,P)$.

(b) (c) Figure 1: $R(D,P)$ for a Bernoulli source under a Hamming distortion
and various perception constraints.

## Acknowledgement

This work has received funding from the European Research Council (ERC) under
the European Union’s Horizon 2020 Research and Innovation programme (Grant
agreement No. 101003431).

## References

  * [1] C. E. Shannon, “A mathematical theory of communication,” _Bell System Technical Journal_ , vol. 27, no. 3, pp. 379–423, 1948.
  * [2] ——, “Coding theorems for a discrete source with a fidelity criterion,” _Institute of Radio Engineers, National Convention Record_ , vol. 4, pp. 142–163, 1993.
  * [3] D. Minnen, J. Ballé, and G. D. Toderici, “Joint autoregressive and hierarchical priors for learned image compression,” in _Advances in Neural Information Processing Systems_ , vol. 31, 2018.
  * [4] G. Zhang, J. Qian, J. Chen, and A. Khisti, “Universal rate-distortion-perception representations for lossy compression,” _Advances in Neural Information Processing Systems_ , vol. 34, pp. 11 517–11 529, 2021.
  * [5] L.-H. Chen, C. G. Bampis, Z. Li, A. Norkin, and A. C. Bovik, “ProxIQA: A proxy approach to perceptual optimization of learned image compression,” _IEEE Trans. Image Proc._ , vol. 30, pp. 360–373, 2021.
  * [6] C. Ledig _et al._ , “Photo-realistic single image super-resolution using a generative adversarial network,” in _2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , jul 2017, pp. 105–114.
  * [7] T. R. Shaham and T. Michaeli, “Deformation aware image compression,” in _Proc. of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , June 2018.
  * [8] S. Kudo, S. Orihashi, R. Tanida, and A. Shimizu, “GAN-based image compression using mutual information maximizing regularization,” in _Picture Coding Symposium_ , 2019, pp. 1–5.
  * [9] Y. Blau and T. Michaeli, “Rethinking lossy compression: The rate-distortion-perception tradeoff,” in _International Conference on Machine Learning_. PMLR, 2019, pp. 675–685.
  * [10] M. Kountouris and N. Pappas, “Semantics-empowered communication for networked intelligent systems,” _IEEE Commun. Mag._ , vol. 59, no. 6, pp. 96–102, 2021\.
  * [11] P. A. Stavrou and M. Kountouris, “The role of fidelity in goal-oriented semantic communication: A rate distortion approach,” _IEEE Trans. Commun._ , to appear, 2023.
  * [12] L. Theis and A. B. Wagner, “A coding theorem for the rate-distortion-perception function,” in _International Conference of Learning Representations (ICLR)_ , 2021, pp. 1–5.
  * [13] C. T. Li and A. E. Gamal, “Strong functional representation lemma and applications to coding theorems,” _IEEE Trans. Inf. Theory_ , vol. 64, no. 11, pp. 6967–6978, 2018.
  * [14] J. Chen, L. Yu, J. Wang, W. Shi, Y. Ge, and W. Tong, “On the Rate-Distortion-Perception function,” _IEEE Journal on Selected Areas in Information Theory_ , pp. 1–1, 2022.
  * [15] A. B. Wagner, “The rate-distortion-perception tradeoff: The role of common randomness,” 2022. [Online]. Available: https://arxiv.org/abs/2202.04147
  * [16] J. Qian, G. Zhang, J. Chen, and A. Khisti, “A rate-distortion-perception theory for binary sources,” in _International Zurich Seminar on Information and Communication_ , 2022, pp. 34–38.
  * [17] I. Sason, “On $f$-divergences: Integral representations, local behavior, and inequalities,” _Entropy_ , vol. 20, no. 5, 2018.
  * [18] I. Csiszar and G. Túsnady, “Information geometry and alternating minimization procedures,” _Statistics and Decisions, Dedewicz_ , vol. 1, pp. 205–237, 1984.
  * [19] R. Yeung, _Information theory and network coding_. Springer, 2008.
  * [20] R. E. Blahut, “Computation of channel capacity and rate-distortion functions,” _IEEE Trans. Inf. Theory_ , vol. 18, no. 4, pp. 460–473, 1972\.
  * [21] R. T. Rockafellar and R. J. B. Wets, _Variational Analysis_. Springer Verlag, 1998.
  * [22] I. Csiszár and P. C. Shields, “Information theory and statistics: A tutorial,” _Foundations and Trends® in Communications and Information Theory_ , vol. 1, no. 4, pp. 417–528, 2004.
  * [23] R. E. Blahut, _Principles and practice of Information Theory_. Addison-Wesley, 1987.
  * [24] K. Nakagawa, Y. Takei, S.-i. Hara, and K. Watabe, “Analysis of the convergence speed of the Arimoto-Blahut algorithm by the second-order recurrence formula,” _IEEE Trans. Inf. Theory_ , vol. 67, no. 10, pp. 6810–6831, 2021\.
  * [25] T. M. Cover and J. A. Thomas, _Elements of Information Theory_ , 2nd ed. John Wiley & Sons, Inc., NJ, 2006\.