{'fraction_non_alphanumeric': 0.03173205491960995, 'fraction_numerical': 0.008740175455761015, 'mean_word_length': 4.563134978229318, 'pattern_counts': {'":': 1, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A large deviation principle linking lineage statistics to fitness in microbial populations

In exponentially proliferating populations of microbes, the population typically doubles at a rate less than the average doubling time of a single-cell due to variability at the single-cell level. It is known that the distribution of generation times obtained from a single lineage is, in general, insufficient to determine a population's growth rate. Is there an explicit relationship between observables obtained from a single lineage and the population growth rate? We show that a population's growth rate can be represented in terms of averages over isolated lineages. This lineage representation is related to a large deviation principle that is a generic feature of exponentially proliferating populations. Due to the large deviation structure of growing populations, the number of lineages needed to obtain an accurate estimate of the growth rate depends exponentially on the duration of the lineages, leading to a non-monotonic convergence of the estimate, which we verify in both synthetic and experimental data sets.

A key determinant of fitness in microbial populations is the population growth rate [1][2][3]. For organisms such as Escherichia coli which undergo binary fission, the exponential growth rate of the population is determined by single-cell properties such as generation time, defined as the time from cell birth to division. In the simplest case where each cell in the population has a generation time of exactly τ d , the number of cells in the population, denoted N (t), will grow as N (t) ∼ e Λt , where the exponential growth rate, Λ is given by Λ = ln(2)/τ d . In reality, any clonal population of bacteria will exhibit a distribution of generation times due to a combination of factors, including intrinsic stochasticity of gene expression [4][5][6][7], asymmetric segregation of growth limiting resources at cell division [8][9][10][11] and environmental fluctuations [12]. Together these factors will result in a distribution of generation times, ψ(τ d ), throughout the history of the population. The relationship between this distribution and the population growth rate, Λ, has been the subject of numerous studies. A key result is the Euler-Lotka equation [1][2][3][13][14][15], which establishes a link between ψ(τ ) and Λ. Equation (1) is a generalization of a relation originally obtained by Euler and later rediscovered by Lotka [16]. Despite the elegant simplicity of the Euler-Lotka equation, it obscures the underlying relationship between the stochastic dynamics along single lineages and the population growth rate. The reason is that ψ(τ d ), like Λ, is a property of the population rather than an intrinsic property of individual cells and it is therefore unclear how differences in single cell dynamics are reflected in ψ(τ d ). Only in the special case where the generation time of a newborn cell is completely uncorrelated with its immediate ancestor, or mother, does ψ(τ ) correspond to the distribution of generation times along a single-lineage [1,14]. In this limit one can, in principle, infer Λ without access to the entire population. In contrast, when generation times are correlated between mother and daughter cells, the distribution of generation times, f (τ ), along a single lineage no longer contains enough information to deduce the growth exponent Λ using equation (1).
Such correlations emerge naturally through feedback mechanisms and are required to maintain homeostasis of cell sizes [17,18]: if intrinsic stochasticity within a cell causes it to grow abnormally large, the daughter cell will tend to have a shorter generation time in order to account for the additional size inherited from its mother. This leads to negative correlations between mother and daughter cells. There are numerous other mechanisms which can generate correlations between mother and daughter cells. For example, environmental fluctuations can induce positive correlations between mother and daughter cells [3,13].
The discrepancy between the statistics of a lineage and those from the entire population, which determine the population's fitness, raises the question of how to quantify fitness from data obtained from a single lineage, or a collection of independent lineages; see Figure 1. Such data is typically obtained from mother machine experiments [19]. In these experiments, independent lineages are tracked for long periods of times in highly controlled conditions. Mother machine experiments enable detailed measurements of single-cell dynamics that would be impossible in bulk conditions. In contrast, bulk experiments can be used to probe population-level dynamics and measure fitness, but are blind to the physiological details at the microscopic level [19]. Here, we present a lineage representation of the population growth rate that connects the population dynamics to the statistics along a single lineage, or a collection of independent lineages. Our lineage representation reveals that a large deviation principle underlies population growth. This generalizes existing variational principles for the population growth rate (e.g. the results of [20]) to the context where generation times are correlated.
Lineage representation. A lineage-based representation of the population growth rate that is independent of the model specifics can be derived using the division distribution, denoted p T (n), which can be obtained from an exponentially growing population as follows. Suppose a population of cells is grown for a time T and assume that we have access to the generation times of individual cells and the genealogical relationships between cells, as shown in Figure 1. We emphasize that our only assumption is that the population grows exponentially as T → ∞. We can randomly sample a lin- The distinction is made between single lineages (highlighted) and a population (black). Lineages can be sampled by traveling down the tree and randomly selecting a daughter cell at the end of each branch. The probability of selecting any specific lineage with n divisions is 2 −n . (b) M independent lineages of length T . For the ith lineage, ni is the number of cell divisions along that lineage. For each lineage we have shown the cell size, which typically increases exponentially between divisions, as a function of time. The lineage division distribution can be approximated from these independent lineages by recording the division events and using the highlighted formula. (c) A growing population of cells from which one can compute the fitness directly by counting the number of cells as a function of time (or utilizing equation (1)). Using the lineage distribution of divisions we can obtain the fitness from independent lineages. eage from the tree by starting from the ancestral cell in the population and randomly selecting one of its daughter cells with equal probability to obtain the next cell in the lineage. Repeating this procedure yields a single lineage, as shown by the highlighted paths in Figure 1.
If N (T ) is the number of cells in the population at time T , then there are exactly N (T ) lineages, as each cell in the final population corresponds to a distinct lineage. However, by randomly selecting a lineage in the forward manner described above, lineages with more divisions are less likely to be selected, since each division decreases the chance that we will travel down that specific path through the tree. In particular, the probability of drawing any specific lineage from the tree is 2 −n . It follows that the empirical division distri-bution, denotedp T (n), of observing exactly n divisions in a lineage sampled using this procedure is given by [20,21] p T (n) = 2 −n N (n, T ), (2) where N (n, T ) is a random variable representing the number of lineages with n divisions in a specific realization of a growing population. Note thatp T (n), is also a random variable, and will therefore differ between different realizations of the population tree. By averaging over many realization of the tree, we obtain the division distribution: It is important to remember that p T (n) is distinct from what has been called the retrospective distribution, defined as the probability of observing n divisions in a lineage obtained by uniformly sampling a cell from the population at time T and following its ancestors back in time [21]. Given a specific realization of the population, the total number of cells can be represented in terms of the empirical division distribution as Averaging over many realization of the population now yields the average population size in terms of the division distribution Importantly, p T (n) is not a random variable that depends on a specific realization of the tree, rather it is an intrinsic property of lineages and has no information about the correlations between sister cells. It can therefore be obtained by running many independent lineages: if we have a collection of M independent lineages of length T and observe n i divisions in the ith lineage, then see Figure 1 (b). The long-time population growth rate, defined as can now be related to an average over independent lineages according to the lineage representation, Here, the angular brackets denote an average over p T (n). The definition of Λ in equation (7) is justified in SM section 1, where we have shown that this limit is self-averaging (i.e. in the long-time limit, only a single realization of the population is needed to obtain Λ). The lineage representation in equation (8) establishes a relationship between the lineage dynamics and the population fitness. A similar formulation was used in [21] to quantify how selection acts on an observable in a growing population; however, our formulation differs in that the average is taken over independent lineages rather than lineages from a single growing population. In order to apply the lineage representation of the population growth rate to real data, we must develop an understanding of how quickly it converges in the number of lineages, M , and the duration of each lineage, T . As we will show below, some care needs to be taken when selecting M and T , as the lineage representation has a non-monotonic convergence in T . However, before presenting our convergence analysis, we establish a relationship between the lineage representation and the large deviation principle underlying the growth process. This structure is best introduced with the simple example below.
Explicit calculation of p T (n) for discrete Langevin model . We now perform an explicit calculation of p T (n) for a specific model in which generation times undergo a discrete Langevin process along a lineage, this model is referred to as the random generation time model in the literature [1,2]. In this model, the generation time τ of a cell is related to its mother's generation time, τ , according to where ξ is a Gaussian with mean zero and variance σ 2 ξ . The parameter c controls the strength of correlations between mother and daughter cells, and for c = 0 we retrieve the classical Bellman-Harris branching process [22]. It can be seen that the average generation time along a lineage is τ = τ 0 . The population growth rate for this model has previously been obtained using a recursive approach in ref [2]. Here, we are able to derive the same result by implementing the lineage representation. Additionally, we obtain the complete distribution of divisions which elucidates the underlying large deviation structure of the population growth process.
We proceed by writing the probability that the nth division will occur along a lineage at time T : Note that this is distinct from p T (n), the probability of observing exactly n divisions before reaching time T . However, since we are interested primarily in the large deviations, the two distributions are interchangeable. By making a change of variables and performing a Gaussian integral (see SM section 2), equation (10) leads to the simple formula where K is a normalization constant independent of n and σ 2 τ = σ 2 ξ /(1 − c 2 ) is the variance in τ taken over a single lineage. Notice that the distribution of divisions is not Gaussian but due to the quadratic dependence of the exponent on T /n, that of the inverse of the number of divisions is approximately Gaussian. We elaborate on this fact in SM section 4.
The exponential form of equation (11) along with equation (8) suggests that the population growth rate is dominated by a particular value of n which maximizes the exponent of 2 n p T (n). Treating n as a continuous variable and solving for n in ∂ ∂n [n ln 2 + ln p T (n)] = 0 yields the dominant number of divisions Note that in the limit where σ 2 τ → 0, we find n c = T / τ , which is the number of divisions corresponding to the average generation time. Substituting only the dominant value of n from equation (12) into equation (8) gives us the formula for the bulk population growth rate: Λ = n c ln(2)/T + ln p(n c , T )/T . After some simplification, we obtain which is in agreement with previous computations using an alternative approach [2]. From equation (13), we can see how the three model parameters, namely τ , σ 2 τ and c, affect population growth. In particular, growth is increased when σ 2 τ and c are increased, while increasing τ decreases growth.
Large deviation principle. In order to connect the observation of the previous section to large deviation theory, we introduce the time averaged division rate γ = n/T , so that the distribution of division rates given by equation (11) can be expressed as with The exponential dependence of p T (γ) on T is known as a large deviation principle and suggests that for large T averages over p T (γ) are dominated by a single value of γ [23].
For the remainder of this paper we will assume this large deviation principle is satisfied. In SM section 3, we show that when I ( γ p ) 1 we can make a Gaussian approximation of p T (γ) to obtain with This illustrates a central result of the large deviation formulation; namely, regardless of the model specifics, corrections to the population growth rate due to variation in generation times scale inversely with the curvature of the large deviation rate function.
Convergence of lineage representation. We now address the question: How accurately can we estimate Λ given M lineages with durations T ? To quantify the accuracy of an estimate, denotedΛ lin , we use the averaged squared deviation Here, the average · E represents the average over many realization of the ensemble of M lineages of duration T , not Here it can clearly be seen that the error initially scales as 1/T , eventually increasing to approach the limit imposed on the sampling error by the large deviation rate function; see equation (19). The inset shows the lineage representationΛ lin as a function of T using M = 80 lineages. This plot is noisy because only a single ensemble of lineages is used, in contrast err in the main plot is computed by averaging over many ensembles of lineages.
to be confused with the averages elsewhere that are taken over lineages within an ensemble. Two distinct factors contribute to the error: First, the estimate of Λ obtained from the lineage representation will be subject to a systematic error resulting from the fact that given an infinite number of lineages each with a finite duration T , the lineage representation approximates the arithmetic mean fitness at time T : Λ T,a = 1/T ln N . This is distinct from Λ. (In fact, it is not even the correct measure of fitness for a population grown over a finite period of time, which is given by the geometric mean 1/T ln N ; see ref. [24] for an explanation of why this is.) We refer to this error as finite duration error, and as we have shown in the SM section 4, it will scale inversely with T . The second factor contributing to err(Λ) is sampling error in the approximation of the average 2 n p from a finite number of lineages. As shown in the SM section 4, when the contribution of the sampling error to err(Λ lin ) will grow exponentially in T for any fixed M , eventually dominating the error resulting from finite lineage durations. As T becomes large, the distribution of γ becomes much more narrow, so an ever-increasing number of lineages are needed to sample the variation in γ; however, as we have seen in equation (16), knowledge of the variation is needed to resolve the effects of generation time variability on population growth. In the long-time limit, all information about the variation is lost for finite M and the lineage representation simply retrieves the zeroth order term in equation (16): This demonstrates that the T and M limits do not commute, because as we have already seen, if we first take M → ∞ the lineage representation converges to the exact population growth rate. As a result, there is a "goldilocks effect": if T is too small the estimate will be inaccurate due to the finite duration error, while if T is too large we encounter the limit given by equation (19). The best estimate is in fact obtained by using an intermediate T where both effects are minimized. This prediction is validated numerically for the Langevin model in Fig. 2. We have also generated the same data for a more biophysically realistic model of cell growth (the cell-size regulation mode [17]), and found the results are qualitatively similar; see SM section 5.
How much data do we need to be confident we are not encountering the limit given by equation (19)? The sampling error will have a negligible effect on the estimate when equation (18) is satisfied. This condition can be rewritten as This implies that the number of lineages needed to avoid encountering the sampling error grows exponentially with the duration of the lineages and the generation time variance. In order to be confident that the finite duration error is small enough to resolve the second term in equation (16), we must select T I (γ c ). This means that T ln(2)/I ( γ p ) is a large quantity. For example, if we want to ensure that the finite duration error is an order of magnitude smaller than the generation time variance, a safe value of M will generally be larger than 2 10×ln(2) ≈ 120. Existing data sets obtained from mother machines contain on the order of one hundred lineages, making the application of the lineage representation plausible. In SM section 6, we have explored the applications of the lineage algorithm to mother machine data, where we have found that the dependence ofΛ lin on T is qualitatively consistent with the theory presented above and Fig. 2.
Discussion. Experimental advances over the last few decades have made it possible to observe the stochastic dynamics of growth and division in bacteria with increasing levels of precision [19,25,26]. These observations have revealed universal principles underlying microbial growth, such as the adder mechanisms for maintaining homeostasis of cell sizes [17,18,[27][28][29]. Bulk experiments in which bacteria are grown exponentially or in competition assays can be used to compare the fitness of different strains, and in principle elucidate how these physiological differences map to fitness. However, the equivalence between growth in bulk experiments and those used to observe single-cell traits remains unclear, because of the different environments which cells are subjected to in these experiments. In this paper, we have presented a lineage representation that links single-lineages to the population growth.
We have also found that a large deviation principle underlies the population dynamics which applies to the distribution of division rates among lineages in a growing population. This implies that the population becomes dominated by lineages with a certain optimal division rate. This idea generalizes an optimal lineage principle introduced by Wakamoto et al. which was used to calculate the population growth rate within the context of a model with uncorrelated generation times [20]. Using the large deviation framework, we have quantified exactly how much data is needed to resolve the effects of cell-to-cell variability on population growth from single lineages. We expect that this work will serve as a guide for future experimental studies seeking to link singlecell observations to fitness.

Argument that Λ is self-averaging
We show that, provided fluctuations in generation times have a finite correlation time, converges to a deterministic value in the large T limit. This will establish that equation (7) is an appropriate definition for the long-term fitness. We begin by defining averages of Λ T in two ways: First, we consider the geometric mean where the average is taken over many realizations of the population. Second, we consider the arithmetic mean fitness: We will say that Λ T is self-averaging if the geometric and mean fitness converge to the same value in the long-time limit. The distinction between mean and geometric fitness has been shown to be important when considering populations growing in the presence of environmental stochasticity. In this context, it is often the case that the two are not equal and that the geometric fitness is the more appropriate measure of the long-term viability of a population; see ref. [24] for a detailed discussion of this point. In the context of branching processes, the fact that Λ T is self-averaging has been established for the Bellman-Harris branching process model; see ref. [22]. For completeness, we provide an argument that is slightly more general, and allows for mother and daughter cells to have correlated generation times. Setting N (T ) = N (T ) + dN , we have where CV 2 N is the coefficient of variation of N (T ). We now argue that CV 2 N converges to a constant as T becomes large. To do this, we write down the differential equation for the probability distribution of N (t), denoted P (N, t). Let α(t) be the per unit time, per capita probability of a cell dividing. The time dependence in α(t) comes from the fact that the distribution of ages will take some time to converge to its steady-state [30,31]. Since the division rates of individual cells are age-dependent, the per capita division rates throughout the population will depend on time. It has previously been shown that if there is any variability in generation times and the fluctuations in generation times have a finite correlation time, the distribution of ages will eventually become time-invariant [3,14]. Hence α(t) will converge to a constant,ᾱ, in the long-time limit. Thus, after a long period of time, the dynamics of P (N, t) are approximated by To proceed we analyze the moments of N taking the initial condition to be N (t 0 ) k = n k . It is important that we are only considering the dynamics after an initial transient, otherwise equation (S5) will not be a valid approximation. For the first moment of N , we find implying N = n 1 e (t−t0)ᾱ andᾱ = Λ T,a . Similarly, =ᾱ n 1 e tᾱ + 2 N 2 .
(S7) Solving this ODE with N 2 gives Since both N 2 and N 2 grow asymptotically as e 2ᾱt , the coefficient of variation of N (t) will converge to a constant. In particular, which implies is non-random. The predictions of this section are verified in Figure S1, where we have shown that the exponential growth rate of N (t) is deterministic and CV N converges to a constant, although our calculation does not give an explicit formula for this constant.  c). This leads to an equivalent form We can complete the square in the integrand and define the constantsb = b + iω2σ 2 ξ /(2(1 − c)) and d = iωc2σ 2 ξ 2/(1 − c). This leads to the integral In order to evaluate this integral, we make the transformation Note that the Jacobian from this change of variables is 1. When the noise in generation times is small enough for the contribution from the negative part of the integral to be negligible, we can make the approximation that integrals are evaluated over the real line. This leads to Also, notice that t n can be expressed as a sum over all the x i s as t n = x n + cx n−1 + c 2 x n+2 + · · · . (S15) For |c| < 1, which is always the case in our model, this only has an affect on a finite number of terms, thus the nth term can be neglected for large n. We find that Using the identityb and computing the integral, we see that the formula for q is given by equation (11) of the main text. To obtain p T (n) from q T (n), we note that q T (n) is the probability of observing n divisions weighted by the frequency of passing through age zero, which is time invariant (see [3,14]), hence in the long time limit the large deviation rate functions for these two distributions will be equivalent.

Variational formulation of population growth rate
Using the large deviation formulation, we can obtain an alternative representation of Λ. First, we can take a Laplace Transform of equation (14) of the main text, yielding e T γβ p = e T (γβ−I(γ)) dγ. (S18) Setting β = ln 2, we see that the population growth rate is given by a saddle point over γ written as This formulation is equivalent to equation (8) of the main text, but makes an explicit connection between the growth rate and the Large deviation rate function. In addition, we can cast equation (S19) as a cumulant expansion of equation (S18) with β = ln (2). This gives where σ 2 γ = 1/T I ( γ p ) is the variance of γ with respect to p T (γ). We see that the first term in equation (S20) is simply the growth rate calculated from the doubling time of a single lineage, ln(2)/ τ , while including the second order term gives us equation (S20) becomes equation (16) of the main text. In the context of the Langevin model, the curvature of the large deviation rate function is given by It is straightforward to check that equation (S20) is consistent with equation (13) to leading order in σ 2 τ / τ 2 and c. If either one of these parameters is large, then the distribution p T (γ) will be too broad for the first term in the cumulant expansion to give a good approximation.

Analysis of convergence
We analyze the convergence of the lineage representation by first considering the limit in which we have an infinite number of lineages (M → ∞), each with a large, but finite duration T . In this case, the lineage representation gives the arithmetic mean fitness, Λ T,a . This can be obtained from the saddle point approximation, Therefore, if we first take the T limit, rather than having a distribution of γ each lineages gives the same value of γ i = γ . As a result, the lineage algorithm simply gives We conclude that for any finite M the lineage representation is not effective for large T . In particular, the representation only gives reasonable results if equation (20) is satisfied. This also establishes that the T and M limits of the lineage representation do not commute, and it is only if we first take the M limit that the estimate converges.

Test of convergence on cell-size regulation model
Here, we test the lineage representation on a more biophysically realistic model of microbial growth. This model has been used previously in the literature to understand how cells maintain homeostasis of their sizes [17,18]. The central assumption of the cell-size regulation model is that cells grow exponentially at the single-cell level and divide when they reach a size v div depending on their size at birth, v birth . Since cells grow exponentially, the generation time of a cell satisfies v div = v birth e λτ , or Here, λ is the single-cell growth rate. For simplicity, we will assume that cells divide symmetrically; thus v birth is obtained by dividing the cell's mother's size at division by 2. Phenotypic variability is introduced in the form of both variability in single-cell growth rates and noise in the division volumes. To implement this, we take the growth rate λ and division volume v div of a cell to obey [2] ln where η λ and η v are independent normally distributed random variables with variances σ 2 λ and σ 2 v , respectively. The first equation captures the fact that growth rates approximately follow a log-normal distribution for small noise, while the second equation tells us how cells decide when to divide based on their volume. The parameter α determines the cell-size regulation strategy. When α = 1 (known as a "sizer" strategy), cells divide at a critical size, while when α = 1/2 (known as an "adder" strategy) cells add a constant size v 0 between birth and division. We refer to refs [1,18] for an in-depth discussion of the cell-size control model and its implications for population growth.
The convergence of the lineage representation for the cell-size regulation model is shown in Figure S3, which should be compared to Figure 2. We see that the behavior of the error in T and M is qualitatively similar to the the Langevin model, with the convergence being non-monotonic in T .

Application to experimental data
Here, we apply the lineage representation to the mother machine data from ref [32]. In these experiments, E. coli were grown in three different temperatures. Each experiment resulted in a collection of roughly M ≈ 80 independent lineages (recordings of division times) with durations on the order of 100 generations. In order to explore how the duration of the lineages affects our estimate, we have computedΛ lin for different values of T by truncating the lineages. Along with the lineage algorithm, we have computed two other measurements of growth: First, we have computed the first order term in equation (16), ln(2)/ τ . Second, we have computed the average single-cell elongation rate along the lineages. If v birth and v div are the initial and final volume of a cell over the course of a cell cycle, then the single-cell elongation rate is defined as λ = 1/τ ln(v div /v birth ). By taking the average of λ over all cells in each experiment, we obtained the average single-cell elongation rates, λ .  The results of our analysis are shown in Figure S4. Here, we see that for large T ,Λ lin ≈ ln(2)/ τ ; therefore, the lineage algorithm is not resolving the higher order effects on the population growth rate. Comparing the trajectories ofΛ lin with those from the insets in Figure 2 of the main text and Figure S3, we see a qualitative agreement. In particular, they seem to decrease initially before fluctuating around a constant, before decreasing to ln(2)/ τ . This indicates that our theory indeed captures the performance of the lineage representation on real data, although without the corresponding population growth rate measurements, we cannot make any claims about the accuracy of the growth estimates.