{'fraction_non_alphanumeric': 0.03824751708107347, 'fraction_numerical': 0.01317179685849123, 'mean_word_length': 4.4016487000634115, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 1, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Stochastic thermodynamics and modes of operation of ribosome : A network theoretic perspective

The ribosome is one of the largest and most complex macromolecular machines in living cells. It polymerizes a specific protein in a step-by-step manner as directed by the corresponding template messenger RNA (mRNA) and this process is referred to as ‘translation’ of the genetic message encoded in the sequence of mRNA transcript. In each successful chemo-mechanical cycle during the (protein) elongation stage, the ribosome elongates the protein by a single subunit, called amino acid, and steps forward on the template mRNA by three nucleotides called a codon. Therefore, a ribosome is also regarded as a molecular motor for which the mRNA serves as the track, its step size is that of a codon and two molecules of GTP hydrolyzed in that cycle serve as its fuel. What adds further complexity is the existence of branched pathways and futile consumption of fuel that leads neither to elongation of the nascent protein nor forward stepping of the ribosome on its track. We investigate a model based on the network of the seven discrete chemo-mechanical states of a ribosome using a graph-theoretic approach to derive the exact solution of the corresponding master equations. We identify the various possible modes of operation of a ribosome in terms of its average velocity and mean rate of GTP hydrolysis. We also discuss the stochastic thermodynamics of a ribosome by computing entropy production as functions of the rates of the interstate transitions.


I. INTRODUCTION
The synthesis of proteins, performed by a macromolecular machine, called ribosome, is one of the fundamental processes inside every living cell [1,2]. The sequence of monomeric subunits of the protein, called amino acid, is directed by the sequence of the triplets of monomeric subunits of a messenger RNA (mRNA) template; each triplet is called a codon. In the language of information processing, the template-directed polymerization of a protein by a ribosome is called translation (of genetic message). The ribosome hydrolyzes two molecules of GTP (a strongly exergonic or 'downhill' reaction) to elongate the nascent protein by one amino acid; the latter forms a peptide bond with the nascent growing protein that is also referred to as a polypeptide. Simultaneously it moves forward by one codon on the mRNA template. Therefore, a ribosome can also be regarded as a molecular motor for which the mRNA template serves as a track; the motor is fulled by GTP hydrolysis and its step size on the track is a single codon.
Over the last few decades, enormous progress has been made in characterizing the structure of the ribosome and its dynamics during the process of translation by X-ray crystallography, cryo-electron microscopy and combinations of biochemical and biophysical single molecule techniques such as smFRET, [3][4][5][6][7][8]. There are many theoretical studies of the translation process based on these experimental revelations [9][10][11][12][13][14][15][16][17][18][19][20] but, to our knowledge, there is no report on any study of the stochastic thermodynamics and operational modes of ribosome. * Corresponding author; e-mail: debch@iitk.ac.in The directed movement of the ribosome on its mRNA track is, however, noisy because of the thermal motion of the surrounding aqueous medium and the low concentration of the molecules involved in the chemical reactions. The ribosome can be regarded as a thermodynamically open system that is coupled to various reservoir potentials. More specifically, the reservoirs include not only a thermal reservoir at a constant temperature, but also several chemical reservoirs maintained at the respective chemical potentials and a "force reservoir" describing a load force acting on the ribosome. The main aim of the present work is to improve our theoretical understanding of the translation process from the perspective of stochastic thermodynamics [21][22][23][24][25][26][27][28][29][30][31][32] by a detailed and quantitative description of the various stages of the chemo-mechanical cycle that the ribosome undergoes in a single translation step.
We describe the kinetics of the ribosome in terms of a Markov network of observable mesoscopic states, using experimentally measured interstate transition rates [33,34] . For the exact analytical treatment of this multiple-pathway discrete-state Markov model we develop a graph theoretic framework, following [35][36][37]. In this approach, the network of the states is represented by a graph consisting of vertices and edges. Vertices correspond to the observable mesostates and the directed edges represent the possible transitions between these states. The stationary solution is obtained by studying subgraphs of the graph in a systematic analysis that we outline in this paper.
This approach is powerful since the ratio of the products of the transition rates along a cycle and its time reversal, that are of interest from the perspective of stochastic thermodynamics, is independent of the meso-scopic states. Cycle fluxes, entropy production rate per cycle, thermodynamic force per cycle [38][39][40] and other important quantities can then be calculated explicitly as a function of the rates. This allows for discussion of the operation mode of the ribosome in terms of average velocity and hydrolysis rate.

II. MARKOV MODEL OF THE MECHANOCHEMICAL CYCLE OF A RIBOSOME
A. The ribosome as a complex nanomachine Each ribosome is built from two loosely associated subunits: (1) The small subunit, which is responsible for all the processes related to the deciphering the genetic code present in the mRNA, and (2), the large subunit which serves as the catalytic center where the formation of peptide bonds takes place. The two subunits are joined together by flexible connectors. A class of adaptor molecules, that bring in the amino acid subunits, move along the intersubunit space. One end of the tRNA molecule, that participates in the decoding of the genetic message, interacts with the mRNA. The other end of the tRNA, that brings in the amino acid subunit, interacts with the large subunit. For each end of the tRNA molecule three binding sites are available on the respective subunits of the ribosome. These binding sites are designated by the letters 'A', 'P' and 'E', respectively, in that sequence along the direction of translocation of the tRNAs in the intersubunit space. Each tRNA not only brings in an amino acid whose incorporation elongates the polypeptide (protein), but also holds it transiently thereafter before irreversibly transfering the polypeptide to the next tRNA.
In order to account for the main features of the elongation cycle, Sharma and Chowdhury [19] developed a 7-state stochastic kinetic model (see Fig. 1) which shows the different conformational changes that the ribosome can undergo during the elongation stage of translation. For self-containedness, we review this model and the biological processes that correspond to the various interstate transitions.
The state labelled by 1 represents the situation where both the E and A sites of the ribosome are empty while the site P is occupied by the tRNA carrying the nascent protein. In step 1 → 2 the ternary complex EF-Tu.GTP.aa-tRNA with the elongation factor EF-Tu, one GTP, and an aminoacyl-tRNA (aa-tRNA) binds to the ribosome. This ternary complex can be cognate to the codon in the ribosomal A site (correct aa-tRNA (red)), near cognate (one of the three nucleotides of the aa-tRNA anti-codon does not match the three nucleotides in the codon (black)) or non-cognate (none of the nucleotides on the aa-tRNA match (black)). After initial binding, the cognate aa-tRNA attempts to read the codon at the A site of the ribosome. Ideally, the ribosome is expected to recognize the cognate tRNA and reject both non-cognate and near-cognate tRNAs. A non-cognate tRNA is rejected on the basis of codon-anticodon mismatch (2 → 1).
After the codon recognition, the enzyme GTPase of the EF-Tu is activated, leading to the hydrolysis of a single GTP molecule to GDP and inorganic Phosphate P i which causes an irreversible transition (2 → 3). This process is a quality control mechanism to ensure that the aa-tRNA selected is, indeed, the cognate (i.e. carries the correct amino acid as dictated by the mRNA template). At this stage, the underlying mechanism of kinetic proofreading can reject the tRNA if it is a near-cognate one (3 → 1). However, if the selected aa-tRNA is not rejected, it does not necessarily imply that it is cognate because, occasionally, even non-cognate or near-cognate aa-tRNA escapes the ribosomal quality control mechanism, leading to error in translation which proceeds from state 3 as follows.
The growing polypeptide is then linked by a peptide bond to the amino acid supplied by the selected aa-tRNA thereby transferring the polypeptide from the tRNA located at the P site to the tRNA at the A site. After the transfer of the polypeptide, the deacylated tRNA remains at the P site. This 'peptidyl transferase' activity of the ribosome thus results in the elongation of the polypeptide by one subunit. The composite process comprising the departure of the products of GTP hydrolysis, together with that of the EF-Tu, and the formation of the peptide bond between the amino acid supplied by the selected aa-tRNA and the growing polypeptide is represented by the single transition 3 → 4 (for the cognate aa-tRNA) or 3 → 6 (for the near-cognate or non-cognate aa-tRNA).
While the polypeptide gets elongated by one amino acid, a fresh molecule of GTP enters bound with an elongation factor EF-G. Spontaneous Brownian (relative) rotation of the two subunits of the ribosome coincides with the back and forth transition (4 5 after the correct amino acid incorporation or 6 7 after the wrong amino acid incorporation) between the so-called classical and hybrid configurations of the two tRNA molecules. In the classical configuration, both ends of the two tRNA molecules correspond to the locations of P and A sites. In contrast, in the hybrid configuration, the ends of tRNA molecules interacting with the large subunit are found at the locations of E and P sites, respectively, while their opposite ends interacting with the small subunit continue to be located at the P and A sites, respectively.
Finally the hydrolysis of the fresh GTP drives the irreversible transition 5 → 1 along the pathway for correct amino acid incorporation (or 7 → 1 along the pathway for the wrong amino acid incorporation), thereby completing a cycle. This involves the translocation of the ribosome on its track by one codon and, simultaneously, that of the two tRNAs inside the ribosome by one binding site also on the small subunit, followed by the deacylated (i.e. bare) tRNA exiting from the E site. The EF-G.GDP complex dissociates from the ribosome and the initial state 1 is again attained.
For clarity, Fig. 2 indicates how these internal processes relate to the translocation of the ribosome along the mRNA template. The forward movement by one codon occurs from either state 5 or state 7 and leads to state 1. The total displacement from the start codon at time t is an integer multiple n of the average length ≈ 1nm of a codon where n is the number of elongation cycles completed up to time t. Hence the average ribosome velocity v along the mRNA is proportional to the elongation rate e = v/ which is the average number of completed elongation cycles per time unit which is identical to the average rate of elongation of the nascent protein. Since in this paper we treat the ribosome as a molecular motor, we use the term velocity instead of the rate of elongation.

B. Stochastic reaction kinetics
During the course of an elongation cycle, the ribosome is fed by energy from EF-Tu and EF-G mediated hydrolysis of GTP to GDP and inorganic phosphate P i and ribosome catalyzed transpeptidation. These free energies, which amount to ∆G ∼ 12k B T in each hydrolysis, are consumed for (a) decoding the genetic information encoded in the codon sequences of the mRNA into the amino acid sequence forming the polypeptide, and (b) also for translocation along the mRNA track. The complex ribosome apparatus can thus be viewed as a small system coupled to multiple reservoirs that act as sources and sinks of particles and energy for the system (Fig. 3). Under isothermal conditions the different reservoirs are: (1) Thermal reservoir at temperature T ; (2) Particle reservoirs for the chemical species aatRNA.EF-Tu.GTP, EF-Tu.GDP, EF-G.GTP, EF-G.GDP, and P i , characterized by the chemical potentials µ aatRNA.EF-Tu.GTP , µ EF-Tu.GDP , µ EF-G.GTP , µ EF-G.GDP , µ Pi ; (3) "Force reservoir" that comes into play in the presence of an external force F ext acting on the ribosome, such as a load force opposing the natural forward stepping of the machine.
The extra work that is done in the mechanical movement on the mRNA track in order to overcome the load force is also supplied by the free energy released in hydrolysis. A load force leads to a reduction in the speed of the ribosome, unless it is compensated (or overcompensated) by an increase of the chemical potential differences that contribute to the free energy. Analogously, an external force may act in the same direction as the natural motion of the ribosome, thus either enhancing its speed or reducing the free energy required from hydrolysis.
Thus the functioning of the ribosome machine depends on the thermodynamic forces generated by chemical potential differences of the particle reservoirs and on the external force F ext applied to the machine. The chemical potential differences of the particle reservoirs for the ribosome apparatus arising from hydrolysis are given by It should be noted that EF-Tu is a GTPase that catalyzes the selection and binding of aa-tRNA with the help of hydrolysis of chemical fuel GTP whereas EF-G is a GTPase that catalyzes the translocation step of the ribosome. The system attains chemical equilibrium, without any average net displacement of the ribosome, when ∆µ Tu = ∆µ G = 0. However, when µ aatRNA.EF-Tu.GTP µ EF-Tu.GDP + µ Pi and µ aatRNA.EF-G.GTP µ EF-G.GDP + µ Pi , the likelihood that the GTP will bind to the active site for hydrolysis is much higher than the binding of GDP for GTP synthesis. These non-vanishing chemical potential differences drive the system out of equilibrium and generate a directed movement of the ribosome as indicated above. Moreover, the conversion of chemical energy into mechanical energy involves a thermodynamic cost which results in an increase of the entropy in the environment.
From this thermodynamic perspective, the biological processes that the ribosome undergoes during an elongation cycle can be understood as Markovian transitions between the 7 states, driven by thermal fluctuations, external forces, and chemical reservoirs that supply the molecules required for the transitions to take place. In our approach, the transition rates between the states are assumed to be independent of the spatial position of the ribosome on the mRNA track. This allows us to study the elongation cycle just in terms of the seven internal states of the ribosome, without reference to its location on the mRNA template.
Thus the model reduces to a multi-pathway process as shown in Fig. 4, with the transition rates from a state i to some other state j denoted by k ij . The experimental values of the rate constants used in our model are shown in Tab. I. The rates depend on the concentrations c α of the factor-GTP complexes that bind to the ribosome. In the graphical plots, we use the notation [α] for the concentration. It may be noted that we consider a variant of the model suggested by Sharma and Chowdhury, viz., if there exists a transition from certain state i to some state j, then we take care not to neglect the rate for the reversed process j → i even when it is too small to be measurable in an experiment. Instead we use a small hypothetical small value 10 −5 (by considering the concentrations c aatRNA.EF-Tu.GDP = c EF-Tu.GDP = c EF-G.GDP = c Pi = 10 µmol). This weak reversibility condition [41], which is based on the law of mass action, allows for a discussion of the entropy production of the process.    chemical state i at time t and the number of monomers k in the polypeptide chain that it has polymerized up to time t. This number directly yields the displacement ∆x = k by time t along the mRNA. The stochasticity of the process then leads to a description of the dynamics in terms of the probability P i (k, t) that at time t the ribosome is at "position" k in the "chemical" state i. The full master equation for the probability to find the ribosome at time t in the chemical state i at codon k reads d dt P 1 (k, t) = k 21 P 2 (k, t) − k 12 P 1 (k, t) The normalization condition is From the full master equation (11) - (17), one obtains the reduced master equation for the probability distribution P i (t) for the internal states by summing over all positions k and defining P i (t) = k P i (k, t). This yields for the probability distribution of the chemical states. In the stationary state the time-dependence drops out from both sides of the reduced master equation (19). For the steady-state probabilities, the master equation can be solved numerically very efficiently with standard computer routines for any choice of the numerical values of the transition rates. However, we are interested in the exact analytical solution, i.e., in the stationary probabilities as functions of the transition rates.
To this end, we adapt the ideas of [37] in which the Markov network shown in Fig. 4 is represented by a graph where each of the vertices represents a distinct state i (i = 1, 2, . . . , 7) and the directed edges i → j represent the possible transitions from the state i to the state j.
From the graph an undirected graph is obtained by replacing the directed edges by undirected edges. A spanning tree of an undirected graph is a sub-graph which is maximal in the sense that it includes all the vertices of the graph, with minimum possible edges which implies the absence of any loop. A directed spanning tree, say the µ-th (µ = 1, 2, . . . , M ), T µ i (G) of a graph G can be obtained by directing all the edges of the undirected spanning tree T µ (G) towards the vertex i. To each of the directed spanning trees T µ i (G), we assign a numerical value, A(T µ i )(G), which is defined as the product of the |V | − 1 transition rates in the tree. The steady state probability distributions are then given by where the normalization factor plays a role similar to that of the partition function. The detailed step-by-step derivation of P i for the network model shown in Fig. 4 is given in the appendix A. For plotting the numerical results graphically we take the concentrations, that determine the rates k 12 , k 45 , k 67 through (3) -(5), to be c aatRNA.EF-Tu.GTP = c aatRNA.EF-G.GTP = c aatRNA.EF-G.GTP = 50µmol. Using the experimentally measured values of the rates listed in Tab. I in the analytical expressions for P i (i = 1, 2, . . . , 7) one obtains the numerical values P 1 = 0.0007 P 2 = 0.0188 P 3 = 0.1464 P 4 = 0.0202 P 5 = 0.8049 P 6 = 0.0003 P 7 = 0.0088.
By ergodicity, the stationary values P i represent the fraction of time the ribosome spends in state i. We point out that the overwhelming amount of time (> 80%) is spent in state 5 (from which translocation, accompanied by GTP hydrolysis and EF-G.GDP dissociation, takes place), followed by state 3 (from which proofreading and elongation, accompanied by EF-Tu.GDP dissociation, take place).

B. Transition flux, cycle flux and their relations
The right hand side of the master equation (19) is the negative sum of the net probability currents from state i to state j. Notice that all pairs i and j that contribute to the master equation are neighbours in the network graph Fig. 4. For the steady state solution P i , the associated stationary probability currents k ij P i − k ji P j are denoted by J ij , without argument t. They are related to the macroscopic mean transition fluxes between states i and j in the direction i → j, where in an ensemble of N identical ribosomes translating an mRNA an average of N i are in state i. Since in the stationary state one has N i = N P i one finds Therefore, we shall refer to the stationary probability currents J ij = −J ji as transition fluxes. If the ribosome would be in full thermal equilibrium (i.e., not only with respect to the temperature), the process would satisfy detailed balance and, consequently, all transition fluxes would vanish. However, as pointed out above, this is not the case because of the non-equilibrium nature of the steady state of the model under investigation here. Next we define the auxiliary variables Q i (t) := k kP i (k, t). With the step length of a translocation from one codon to the next, one obtains from the Q i (t) the mean position X(t) = i Q i (t) and the mean velocity v(t) =Ẋ(t) of the ribosome. From the full master equation (11) -(17) one obtains (by shifting the summation index in the sum over k for the terms involving site k ± 1) the simple expression for the average velocity for the ribosome.
In a similar fashion one obtains the mean hydrolysis rate. One introduces as stochastic variable the net number m(t) of GTP hydrolysis and effective GTP synthesis events. This number is incremented by +1 when any of the transitions 2 → 3, 5 → 1, or 7 → 1 takes place and incremented by −1 when the reverse transitions take place. This yields a master equation for the joint probability P i (k, m, t) similar to (11) -(17), but with terms like k 51 P 5 (k − 1, m − 1, t), k 32 P 3 (k, m + 1, t) or and so on instead of k 51 P 5 (k − 1, t), k 32 P 3 (k, t) (and so on). The net hydrolysis up to time t is then given by H(t) = i k m mP i (k, m, t) and the master equation yields the exact expression for mean hydrolysis rate h(t) = dH(t)/dt. In the steadystate, the time-dependence drops out of both sides of (25) as well as those of (26).
In order to get deeper insight into the non-equilibrium nature of the chemo-mechanical cycle of the ribosome we next express the transition fluxes in terms of cycle fluxes. Six different single loops (cycles regardless of their orientation), labelled by κ ∈ {(a), (b), (c), (d), (e), (f)} in Fig. 5, can arise in the network model shown in 4. It will transpire that transition cycles allow for a deeper understanding the kinetic activity of the network than just by focussing on the transition fluxes. To make the role of cycles quantitative, we first define the cycle products as the products of rates k ij of the edges contributing to cycle κ in clockwise (+) or anticlockwise (−) orientations, respectively. Next we summarize a graph theoretic approach for deriving the analytical expressions for the cycle fluxes. Following Hill [35], we associate to a given oriented cycle (κ±) the cycle rate constants over those directed trees µ and edges (i, j) that contribute to all graphs with cycle (κ±). Notice that adding a new directed edge oriented from i to j to a directed spanning tree T µ i converts the latter into a graph T µ ij that has a single oriented cycle. Thus, from the undirected spanning trees one can construct the flux diagrams each of which has a single undirected cycle and directed branches that feed into this cycle. Then, it follows that where R κ = all the flux diagrams containing cycle κ (i, j) are the directed edges feeding into cycle κ in the flux diagram The expression (29) for J κ,± can be interpreted as the cycle product multiplied by the weight factorR κ /Z where the latter accounts for the flux from the rest of the network onto the cycle. Using the expressions above, we arrive at the expression for the cycle fluxes where R κ is given by (30). Both J κ,+ and J κ,− are positive quantities while J κ can be positive or negative. All the 29 flux diagrams corresponding to the 7state network model shown in Fig.4 are displayed in the appendix B. The unnormalized branch products obtained from these flux diagrams are also given in the same appendix. The expressions for the cycle fluxes J a , J b , J c , J d , J e and J f in terms of the interstate transition rates are given also in the appendix C. Each transition flux through the oriented edge (i, j) can be decomposed into the sum of cycle fluxes. This decomposition for the 7-state model yields Note that this list of decompositions is complete. The two ratios depend only on the rate constants around the cycle κ itself. They define the so-called generalized thermodynamic forces X κ [35,37] generated in a non-equilibrium system when coupled to different reservoirs. In a stationary state, which does not involve any change in internal energy, these forces are equivalent to the heat exchange ∆Q κ that arises from the transitions through a loop κ and proportional to the corresponding entropy change thus exposing the entropic nature of the generalized thermodynamic forces in the stationary regime. Thus the generalized thermodynamic forces highlight the connection between the irreversibility of a nonequilibrium process and its heat dissipation since (36) implies which demonstrates (a) that the heat dissipation and the cycle flux vanish simultaneously (corresponding to thermal equilibrium), and (b) that otherwise (i.e., out of equilibrium) they always have the same sign. In other words, the generalized thermodynamic forces express the direction of the cycle fluxes.
The ratios (36) also provide a link between the kinetics and thermodynamics of the network which can be further developed as follows. During the transition from state i to state j, the internal energy U i of the system in state i can change due to three factors: (i) a chemical potential change ∆µ ij = µ i − µ j arising from the coupling of the states to the particle reservoirs with the chemical potentials µ aatRNA.EF-Tu.GTP , µ EF-Tu.GDP , µ EF-G.GTP , µ EF-G.GDP , and µ Pi introduced above, (ii) the mechanical work W ij which the machine performs in the transition i → j to overcome the external force F ext , and (iii) the heat exchange Q ij with the surrounding medium. Conservation of energy for the transition from i to j therefore reads Next we apply conservation of energy to a cycle. Since the internal energy is a state function, the total change in the internal energy for a cycle must be zero in the steady state. The heat exchange ∆Q κ = T ∆S κ in a cycle (κ, +) is given by (36) in terms of the reaction rates. For a cycle (κ, +), energy conservation (39) thus reads where W κ,+ is the work done against the external force in the complete cycle in positive direction and ∆µ κ,+ denotes the net chemical potential difference in the complete cycle. Using (36) and (37) in (40) we arrive at the equivalent steady state balance condition which yields the relation between the transition rates (through Π κ,± ), the chemical energy input and the mechanical work for any cycle in the network, conveniently expressed through the stationary generalized thermodynamic forces. This relation will be used below to determine the range of normal operation of the ribosome, i.e., with positive mean velocity of the ribosome along the mRNA and positive rate of GTP hydrolysis. The analysis carried out in this subsection for the ribosome is very similar to that reported earlier [42] for the cytoskeletal molecular motor kinesin. As elaborated above, the elongation factors EF-Tu and EF-G catalyze the hydrolysis of the fuel molecules, i.e., GTP, into GDP and P i . The energy released in this reaction is chemical energy input for the ribosome machine in each elongation cycle. Thus the operation of the ribosome depends on the respective chemical potential differences and the external force F ext . Its modes of operation are characterized in terms of the average velocity and the average rate of hydrolysis both of which are positive in the normal mode of operation. In the following, we identify the different modes of operation of the ribosome, normal as well as abnormal, exploiting the cyclic energy balance relations (40).

Sign of cycle fluxes and modes of operation
Substituting (34) and (35) for the average velocity of the ribosome in terms of the cycle fluxes; which yields the numerical value 3.229nm s −1 after substitution of the values of parameters listed in Tab. II. Our result is of the same order of the experimentally observed elongation rates [43]. Note that while our result is in nm/s, the experimentally observed rate is given in aa/s and recall that for every addition of amino acid, the ribosome takes one codon step which is approximately equal to 1 nm.
Likewise, substituting the expressions (32), (34) and (35) into (26) in the steady state we get the rate of GTP hydrolysis (43) in the network model in terms of the cycle fluxes; it predicts the numerical value h = 6.580 s −1 after substitution of the parameter values listed in Tab. II.
To investigate under which external conditions the ribosome functions in normal mode, we make a simplification of the calculation by showing only the GTP molecules explicitly. According to this simplification, we have two GTP molecules hydrolyzed for every mechanical step of the ribosome between the codons, one in the transition 2 → 3 and one in the transition 5 → 1 (or 7 → 1 in case of faulty translation). The hydrolysis is then driven by a chemical potential difference ∆µ that comes into play in these transitions. Since the sign of the transition fluxes does not depend in a straightforward fashion on the chemical potential difference and the external force, we study the process in terms of the cycle fluxes.
For the six individual cycles labelled by κ, as displayed in Fig.5, the analysis of the process discussed in detail in Sec. II A yields ∆µ a,+ = ∆µ (44) with the effective chemical potential difference ∆µ κ,+ = µ GTP κ,+ − µ GDP κ,+ − µ Pi κ,+ . The vanishing of ∆µ f,+ in cycle (f) arises from hydrolysis in the step 5 → 1 and the reverse process in the step 1 → 7.
Recalling that W = F ext is the work performed against the external force in one translocation step, one also derives from the description of the six cycles Thus one gets from (41) The Eq. (38) can now be written explicitly for all the six cycles as Since the cycle flux and the generalized thermodynamic force always have the same sign and must vanish simultaneously, the following conditions must be satisfied: J e > 0 for ∆µ > F ext = 0 for ∆µ = F ext < 0 for ∆µ < F ext (66) The conditions (62)-(67) determine, from (42) and (43), the regions on the F ext − ∆µ-plane where the cycle fluxes are positive; these are painted in blue color in Fig.6.
Combining the information displayed in these figures we identify the various modes of operation of the ribosome in the F ext − ∆µ-plane in terms of v and h, as shown in Fig. 7.
Using Eqs. (43) together with (56) -(61), we obtain the expression for the balanced potential ∆µ b , with constants A, B, C given in Appendix E. As shown in Fig. 8, the conditions of vanishing velocity (blue line) and vanishing hydrolysis rate (red line) divides the (F, ∆µ)-plane into three different regions. In operation mode A, ribosome couples GTP hydrolysis to forward mechanical steps, while in the operation mode B, the ribosome couples GTP synthesis to backward steps. In the operation mode C, the ribosome couples GTP synthesis to forward steps. This region appears only for negative external force (corresponding to a force along the natural direction of motion) when this force is strong enough.
The two functions F s (∆µ) and ∆ b (F ) intersect when there is both mechanical and chemical equilibrium i.e., F = ∆µ = 0. We note that the stall force and the balanced potential approach the straight line F ext = 2∆µ as we move closer to the chemo-mechanical equilibrium, i.e., F ext = ∆µ = 0. This represents the ideal operating curve which directly follows from the linear response theory. Near the chemo-mechanical equilibrium, the ribosome works with 100% efficiency i.e., F ext = 2∆µ. The efficiency is given by the ratio of the mechanical work performed by ribosome against the external force and the chemical energy consumption.

B. Ribosome velocity
We study in more detail the ribosome velocity under normal operation as a function of the rates k 23 and k 51 for the processes that involve GTP hydrolysis, with all other rates kept at their experimental or hypothetical values.
Notice that the velocity becomes a constant even when the rates k 51 and k 23 become large, saturating at v max = α 4 /β 4 nm s −1 = 20.58nm s −1 . This saturation effect arises because even if hydrolysis and translocation would be instantaneous, the velocity would still be limited by the rate of the other processes in the elongation cycle. As seen in Fig. 9, the dependence on the rate k 23 is very weak in the experimentally relevant range around k 23 = 180 s −1 and saturates to a value that is approximately proportional to k 51 in the experimentally relevant range around k 51 = 4 s −1 . This saturation effect indicates that the main limiting factor for the velocity is the second hydrolysis in the elongation cycle.
This is close to the exact formula (73). Plugging in the experimental values for k 23 and k 51 one obtains v toy = 3.32nm s −1 which is also close to the exact value (42).
The dependence of the velocity on the rate k 12 is very weak in the experimentally relevant range of the order 10 3 -10 4 . As k 12 increases (high concentration of aa-tRNA), the velocity becomes limited by the rate k 51 which is not affected by a high concentration of aatRNA.

D. Entropy Production
In order to determine how the entropy change ∆S κ,± := ±∆S κ associated with the completion of an oriented cycle (κ, ±) contributes to the total entropy production of the process we recall that the entropy of a system described by Markovian stochastic dynamics is the usual Gibbs entropy S sys (t) = −k B i P i (t) ln(P i (t)).
(77) Following Schnakenberg [37] we split the time evolution of the system entropy into two parts with the total entropy production and the entropy flux The entropy flux can be interpreted as the entropy production of the environment [41,44]. Using the master equation (19) it is straightforwardly verified that the time-derivatives satisfyṠ(t) =σ tot (t) +σ env (t).
In the steady state, the system entropy does not change which implies In terms of cycle fluxes with the entropy change along a circle in clockwise or anticlockwise direction one gets the decomposition of the entropy production in terms of cycles (see appendix F for detailed derivation). Using ∆S κ,− = −∆S κ,+ , which indicates that the cycle (κ, +) is the time reversed trajectory of the cycle (κ, −), we arrive at the entropy production for cycle κ and at for the total entropy production. From Tab. II it is readily seen that cycle (b) has the overwhelmingly largest contribution to the total entropy production, followed by cycle (c) and then cycle (a). From (3), k 12 is proportional to the concentration of EF-Tu.GTP.aa-tRNA. Therefore, increase of k 12 is easily implemented by the increase of the concentration of EF-Tu.GTP.aa-tRNA. Fig. 12(a) shows how the entropy production increases with the increase of the concentration of the ternary complex EF-Tu.GTP.aa-tRNA. We find that the effect is particularly pronounced at small concentration and gradually flattens out somewhat at higher concentration where the entropy production diverges logarithmically with the further increase of the EF-Tu.GTP.aa-tRNA concentration. Similar trend of variation of the entropy production is observed also the variation of, for example k 23 (see Fig. 12(b)) as well as with the variation of k 51 (Fig. 12(c)). Note that k 23 is the rate of a step that involves the hydrolysis of a molecule of GTP whereas k 51 is associated with translocation.
In order to understand the causes and consequences of this common trend of variation of the entropy production with the rates of interstate transitions, it is instructive to consider also the behaviour of the entropy production as a function of the ribosome velocity. As k 12 increases (i.e., effectively the concentration of EF-Tu.GTP.aatRNA increases), the velocity v(k 12 ) (75) of the ribosome, expressed as a function of k 12 , saturates to a value v * = 3.25nm s −1 as discussed above since in that parameter regime it is limited by the rates along the cycles that involve translocation. These rates are not affected by a high concentration of EF-Tu.GTP.aatRNA. On the other hand, the contribution to the entropy production from the cycles (a), (b) and (c) -which involve the ratio ln (k 12 /k 21 ) from the reaction 1 2 -keeps increasing and diverges at v * since the inverse function k 12 (v) diverges at v * . A similar divergence appears when any of the transition rates k ij becomes large since the entropy production diverges as ln (k ij ) while the velocity saturates for large k ij (see Figs. 12(b) and (c)) .

V. CONCLUSIONS
Using a network approach we solved exactly the stationary master equation for a seven-states model of the kinetics of a ribosome during the elongation stage of translation. This solution is used for a detailed description of stationary properties arising from the stochasticity of the chemo-mechanical cycle of the ribosome. We have identified the various modes of operation of this machine in terms of its average velocity and the mean rate of GTP hydrolysis. Similar analysis have been reported earlier in the literature for cytoskeletal motor proteins. To our knowledge, this paper reports the first analysis, from the perspective of stochastic thermodynamics, of a molecular machine that carries out template-directed polymerization.
Our quantitative predictions can be used as benchmarks for simpler models and thus allow for judging the adequacy of such reduced models that incorporate fewer or other internal states of the ribosome. Moreover, since we used rates obtained from experiments, the comparison of the analytical results with other experimental data al- lows for a detailed quantitative understanding of the microscopic processes underlying translation, particularly those during the elongation stage.
Finally, we would like to point out that the knowledge of exact stationary distribution allows for the construction of exactly solvable models of many interacting ribosomes, as has been demonstrated recently in a mathematically similar setting for a two-states description of transcription elongation by RNA polymerase [45]. This approach can be adapted to more internal states and exact stationary single-motor results open up the path to obtaining exact quantitative results for the elongation kinetics of many simultaneously transcribing or translating molecular motors. In order to find the stationary solution of the master equation (19) we follow [37].

2.
Step 2: Constructing undirected spanning trees from the undirected graph Recall that a spanning tree of an undirected graph is a sub-graph which is a maximal tree that includes all the vertices of the graph, with minimum possible edges. All possible spanning trees of graph G, have the same number of edges and vertices. It doesn't contain any cycle. Adding just one edge will create a cycle and removing one edge will make the graph disconnected. Let T µ (G) (µ = 1, 2, . . . , M ) represent the µ-th undirected spanning tree of graph G.
One can construct the spanning trees by removing |E| − |V | + 1 edges (for our graph, 9-7+1=3 edges) from the graph, where |E| is the number of edges and |V | is the number of vertices. This yields M = 39 distinct undirected spanning trees. For a systematic construction we group the spanning trees into three classes: (I) All spanning trees without edge (1, 2), (II) All spanning trees that have edge (1, 2) but not edge (1,3), and (III) All spanning trees that have edge (1, 2) and edge (1, 3) but not edge (2,3). In total there are 39 spanning trees, see Figs. 15 -17. only in the orientation in which an edge appears. So, finally, for the 7-state model one finds From these exact expressions all stationary properties can be computed analytically or numerically exactly. Using the decomposition (20) of the stationary probabilities into contributions from the directed spanning trees one obtains the decomposition in terms of the unnormalized transition flux contributions J µ ij := k ij A(T µ i ) − k ji A(T µ j ) and the normalization factor (A2).
We observe that the directed trees T µ i and T µ j differ for the same µ only in the orientation of the edges connecting the vertices i and j. Therefore, if vertices i and j are neighbours, i.e., if they are connected by an edge in the undirected spanning tree µ, then the flux contribution J µ ij from T µ i and T µ j vanishes (see Fig. 19(a)). On the other hand, if i and j are not neighbours, then the multiplication of A(T µ i ) by the rate k ij yields a product of rates that can be obtained from a new directed graph by adding to T µ i an oriented edge from i to j, thus converting the oriented tree T µ i into a graph T µ ij with a single oriented cycle (see Fig. 19(b)) whose original arrows are all directed towards vertex i and with a new arrow from i to j. Similarly, the product k ji A(T µ ji ) corresponds to a graph T µ ji with the same cycle, but oriented in the opposite direction. The rest of both the one-cycle graphs (the side branches of the cycles) are identical, so that the product of the rates in the side branches R(T µ ij ) = R(T µ ji ) is the same for both orientations. Notice that directed trees with different indices µ might lead to the same onecycle graphs, see  1 an oriented edge from vertex 1 to vertex 2 generates a cycle (231), while adding to the oriented tree T 9 2 an oriented edge from vertex 2 to vertex 1 generates a cycle (132) where generically J 9 12 = −J 9 21 = 0 (viz. unless k12k23k31 = k21k13k32 for the cycle products of the transition rates). (c) Adding oriented edges between vertices 2 and 3 of the oriented trees T 33 2 and T 33 3 resp., yields identical graphs so that J 9 12 = J 33 23 . Using (27), (30) and (21) in (29) and substituting the resulting expression into (31) , we get the expressions for cycle fluxes in terms of the rates of the interstate transitions:  For equation (56), the coefficients are as follows:  The explicit derivation of the Eq.(83) is given below.