We present an intuitive visual framework, the generalized skyline plot, to explore the demographic history of sampled DNA sequences. This approach is based on a genealogy inferred from the sequences and provides a nonparametric estimate of effective population size through time. In contrast to previous related procedures, the generalized skyline plot is more applicable to cases where the underlying tree is not fully resolved and the data is not highly variable. This is achieved by the grouping of adjacent coalescent intervals. We employ a small-sample Akaike information criterion to objectively choose the optimal grouping strategy. We investigate the performance of our approach using simulation and subsequently apply it to HIV-1 sequences from central Africa and mtDNA sequences from red pandas.
Contemporary DNA sequences contain information about the demographic history of the population from which they were sampled. As a result, the inference of demographic parameters from genetic data has become an important topic in statistical genetics, with applications in fields as diverse as anthropology, conservation biology, epidemiology, and virology (Harvey et al. 1996<$REFLINK> ). Estimation of effective population size, as well as its rate of change through time, can provide useful information about the evolutionary and demographic history of a population.
Methods for estimating demographic history from gene sequences are mostly based on coalescent theory (Kingman 1982a, 1982b;<$REFLINK> Hudson 1990<$REFLINK> ; Nordborg 2001<$REFLINK> ). They usually rely on a simple parametric model N(t) which describes effective population size through time. Time t is zero at present and increases into the past, hence N(0) is the effective population size at present. Two simple demographic models are frequently used: constant population size N(t) = N(0), with one parameter N(0) and exponential growth N(t) = N(0)e−rt, with two parameters r and N(0). Often, however, there is no prior reason to assume a specific model of demographic history for the data in question. Moreover, the available models may be too simplistic. Hence, nonparametric and model selection tools can play a useful role in the inference of population history from gene sequence data.
Nee et al. (1995)<$REFLINK> proposed the lineage through time (LTT) plot to graphically investigate the demographic history of gene sequences. LTT plots display the rate of coalescence through time in a genealogy which has been reconstructed from an alignment of homologous sequences. Pybus, Rambaut, and Harvey (2000)<$REFLINK> described a simple transformation that converts this rate of coalescence into a plot of estimated effective population size against time, which we call here the classic skyline plot. The LTT and classic skyline plot approaches are closely related and both assume that a fully resolved phylogeny with reliable estimates of divergence times is available. As a consequence, these approaches can only be applied to data that exhibit a strong phylogenetic signal and are not appropriate for alignments which contain identical sequences. In addition, neither method provides an assessment of coalescent error. This is the error that results from the randomness inherent in the coalescent process.
In this paper we introduce the generalized skyline plot, a simple framework for exploring the demographic signal in a sample of DNA sequences. This method extends the classic skyline plot by allowing multiple coalescent events (for which little divergence time information is available) to be grouped together. The classic plot is a special case of the generalized plot, which arises when no coalescent events are grouped. The generalized plot can be applied to data sets which contain identical sequences and has the added benefit of smoothing the classic plot, which typically displays stochastic noise. We show that the most appropriate amount of smoothing can be determined by using a penalized likelihood approach. Furthermore, we derive the skyline plot as a simple method of moments estimator based on standard coalescence distributions, which enables us to compute estimates of the coalescent error. To illustrate our approach, we analyze HIV-1 sequences from central Africa and investigate the demographic history of red pandas using mtDNA sequences.
The coalescent describes the relationship between the shape of an intrapopulation genealogy (representing the ancestry of randomly-sampled, nonrecombining, neutrally evolving sequences) and the demographic history of the sampled population (Kingman 1982a, 1982b<$REFLINK> ). The coalescent process arises as an approximation to a general class of population genetics models (including the Wright-Fisher reproduction model) and is valid when the effective population size is large. In the coalescent model, the sequences sampled at present are traced back in time to a single common ancestor, with coalescent events among lineages occurring according to a nonhomogeneous Poisson process. For a constant effective population size N the rate of coalescence is
The accumulated waiting time wn,k = Σi = 1kwn − i + 1 until k coalescent events have occurred is the sum of k different exponential variables (λi ≠ λj for i ≠ j) and thus follows a hypo-exponential distribution (e.g., Ross 1997<$REFLINK> )
Deterministic changes of N through time can be introduced in the coalescent by a nonlinear scaling factor (Hudson 1990<$REFLINK> ; Griffith and Tavaré 1994<$REFLINK> ; Donnelly and Tavaré 1995<$REFLINK> ; Kuhner, Yamato, and Felsenstein 1998<$REFLINK> ). If selection, recombination, or noncontemporary sequences are present then further adjustments to the coalescent are necessary (e.g., Rodrigo and Felsenstein 1999<$REFLINK> ; Nordborg 2001<$REFLINK> ).
The Classic Skyline Plot
Suppose that we have a fully resolved genealogy Ĝ with m tips, estimated from a given sequence alignment in such a way that Ĝ's internal nodes are dated according to a given time scale. This requires a molecular clock, or more generally, a model of rate correlation among different branches in the tree (Gillespie 1991<$REFLINK> ; Sanderson 1997<$REFLINK> ; Thorne, Kishino, and Painter 1998<$REFLINK> ; Huelsenbeck, Larget, and Swofford 2000<$REFLINK> ). Ĝ defines m − 1 ordered internode intervals Im,Im − 1,…,I2 where the subscript indicates the number of lineages present during each interval. The length of interval In is denoted by ŵn. A simple demographic model can then be constructed as follows. During each interval In we assume that population size is a local constant, Mn, but between different intervals the population size is allowed to change. Hence, for a set of m − 1 intervals, we approximate the demographic history N(t) by a piecewise constant function with m − 1 independent variables Mm,Mm − 1,…,M2.
A method of moments estimator for the population size during each interval In is then constructed by setting the expected waiting time (eq. 2 ) for the next coalescent event equal to ŵn, and solving the resulting equation for Mn. This gives the classic skyline plot estimate<$REFLINK> derived this simple result using an alternative argument based on the variable population size coalescent.
The Generalized Skyline Plot
Generally, we expect the accuracy of the observed intervals ŵ (obtained from a reconstructed genealogy) to be adversely affected by limited genetic variation. The number of substitutions occurring in an internode interval is often modeled by a Poisson distribution. Consequently, the observed number of substitutions is proportional to the time elapsed when either the substitution rate or the internode interval is large. However, this approximation breaks down when the product of interval length and substitution rate is small. Under such circumstances it would be beneficial to pool small intervals together so that all intervals are large enough for time to be proportional to the number of substitutions. Zero-length intervals always occur if the alignment contains identical sequences, and also arise when the branch lengths of a genealogy are estimated using maximum likelihood under a molecular clock. The disadvantage of pooling intervals is that some (but not all) of the temporal structure in the data is lost. When the sequences contain very little or no genetic variation, a Bayesian approach employing prior distributions for the substitution and coalescent parameters is required (Tavaré et al. 1997<$REFLINK> ). However, in these cases a single-tree estimator such as the skyline plot is inappropriate.
Allowing pooled intervals in the skyline plot leads to the derivation of the generalized skyline plot. Consider a composite time interval In,k where n denotes the number of lineages at the start of the interval, and k is the total number of coalescent events taking place during this interval. In,k has observed length ŵn,k = ŵn + ŵn − 1 + ··· + ŵn − k + 1. If we assume a locally constant population size Mn,k during this composite interval we can construct a method of moments estimator for Mn,k using equation (5) , and arrive at
Note that the generalized skyline plot (eq. 8 ) contains the classic skyline plot (eq. 7 ) as a special case when each interval contains only a single coalescent event (k = 1). If there is only a single composite interval Im,m − 1 that contains all m − 1 coalescent events in the genealogy, then equation (8) collapses to M̂m,m − 1 = ŵm,m − 1m/[2(m − 1)]. This is the standard population genetic relationship between effective population size and the time to the most recent common ancestor of a sample of size m.
Grouping Intervals and Model Selection
In order to choose which intervals in genealogy Ĝ should be pooled we adopt the following convention. First, the set of standard internode intervals Im,Im − 1, …,I2 is determined from Ĝ. Next, if an interval is smaller than a certain threshold ϵ then the interval is considered as small. Proceeding from Im to I2, each small interval is pooled with the neighboring interval closer to the root. If the neighboring interval is also small, then pooling continues until the composite interval is larger than ϵ. Note that this approach prevents the occurrence of zero-length intervals at present. Thus ϵ determines how much temporal structure in the data is retained and hence controls the degree to which the skyline plot is smoothed. The choice of ϵ is guided by two opposing objectives. On the one hand, ϵ should be large enough to remove the noise in the data which arises from the randomness of the mutational process. On the other hand, ϵ should be small enough to preserve the actual demographic signal in the data.
How should the most appropriate value of ϵ be chosen? Visual inspection of skyline plots calculated under various ϵ values is helpful, but an objective approach based on statistical model selection would be preferable. Here we outline one possible approach which penalizes skyline plots that overfit the data. As skyline plots represent specific hypotheses of demographic history, we can calculate the likelihood of a skyline plot using standard approaches, given the observed internode interval lengths (Griffith and Tavaré 1994<$REFLINK> ; Pybus, Rambaut, and Harvey 2000<$REFLINK> ). For a skyline plot derived from a genealogy with m sequences the log-likelihood log L reduces to
Note that the estimated population size M̂ for any subinterval in a composite interval In,k is M̂n,k. Now let K be the number of inferred parameters (=number of composite intervals in the skyline plot) and let S = m − 1 be the sample size (=number of coalescent events in the genealogy). We can compare skyline plots with different ϵ values by penalizing the log-likelihood of each plot using the AICc correction<$REFLINK> ). The AICc approach is a second-order extension of Akaike's well-known first-order AIC correction, log LAIC = log L − K (Akaike 1974<$REFLINK> ). However, Akaike's AIC is valid only for large samples with S/K > 40, whereas AICc is also valid for small sample sizes (Burnham and Anderson 1998<$REFLINK> ). As K depends on ϵ, we can use equation (10) to obtain an optimal generalized skyline plot, by choosing the value of ϵ which maximizes log LAICc.
Statistical Properties and Simulations
Here, we investigate the statistical properties of the skyline plot and study its performance using sequence data simulated under known demographic scenarios.
First, we analytically calculate the coalescent variance σC2 of the skyline plot. For the classic skyline plot we use equation (3) and obtaineq. 6 ). The last factor in equation (12) equals 1 if k = 1 (i.e., the classic skyline plot result) and is smaller than 1 otherwise. Note that the coalescent error of the skyline plot is large. This is probably due to the nonparametric nature of the plot, that is, the sample size S is small with respect to the number of parameters K. The variance of the generalized skyline plot (eq. 12 ) becomes smaller as more intervals are pooled because the ratio of data points to parameters increases.
To investigate the bias of the skyline plot we conducted a small simulation study. For various settings of m and k (see table 1 ), simulations were performed as follows: (1) 1,000 genealogies with m tips were simulated using the demographic model N(t) = 0.1, (2) The first k internode intervals were grouped together and the skyline plot estimate M̂ was calculated using equation (8) for each of the 1,000 simulated gene trees, and (3) The expectation E(M̂) and the bias b(M̂) = E(M̂) − M were computed along with the observed variance var(M̂) and the theoretical variance σC2(M̂).
The results are summarized in table 1 . They indicate that the generalized skyline plot is an unbiased estimator of the effective population size during an interval In,k (when the coalescent intervals ŵ are known without error). As expected from the earlier analytical results, the variance of this estimate is large but declines quickly when intervals are pooled (k > 1). Note that the skyline plot (and the above simulation) assumes that the effective population size is locally constant during an interval. If the population size changes within an interval then the skyline plot (as a piecewise constant estimator of N[t]) is, by definition, biased. However, in this case the classic skyline plot provides an estimate of the harmonic mean of N(t) during each interval (Pybus, Rambaut, and Harvey 2000<$REFLINK> ).
Next, we studied the performance of the classic and generalized plots using sequence data simulated under known demographic scenarios. The purpose of these simulations was to determine whether the generalized plot is more reliable than the classic plot when the DNA sequences used are not highly variable. The simulations were performed as follows: (1) Expected coalescent trees, which contain no coalescent error, were obtained under two demographic models, N(t) = 0.05 (constant) and N(t) = e − 1000t (exponential). These models were chosen to approximately represent the history of animal mtDNA sequences. Note that time is measured in substitutions per site, (2) Sequences were simulated down these trees using the HKY (Hasegawa, Kishino, and Yano 1985<$REFLINK> ) model (transition-tranversion ratio = 10; nucleotide frequencies πA = 0.3, πC = 0.25, πG = 0.15, and πT = 0.3) and no rate heterogeneity. The constant-model alignment contained 500 bp and the exponential-model alignment contained 1,500 bp, (3) Genealogies were estimated from the simulated sequences using the TBR search heuristic in PAUP* (Swofford 1998<$REFLINK> ). The substitution model specified earlier was used, and (4) Classic and generalized skyline plots were obtained from the estimated genealogies. The ϵ value was found by optimizing the AICc corrected log-likelihood (see eq. 10 ).
Figures 1 and 2 show the simulation results for the constant and exponential models, respectively. Under the constant-size model, many of the simulated sequences are not unique and many of the internode intervals in the estimated tree are very small (fig. 1a ). Thus the number of observed substitutions provides little information about the true coalescent interval lengths and consequently the classic skyline plot is very noisy (fig. 1b ). In contrast, the generalized skyline plot estimate is smooth and almost identical to the true demographic history (fig. 1c ). The optimal ϵ was 0.1, which resulted in all the observed intervals being pooled into a single composite interval. This should be expected, as the true demographic history contains no changes in population size.
Under the exponential model, only two sequences were identical (fig. 2a ) and both the classic and generalized plots provide a good estimate of the true demographic history, although the generalized plot is less noisy (fig. 2b and c ). The optimal ϵ was 0.00115. Interestingly, both plots appear to slightly overestimate population size in the past, which suggests that, in this set of sequences, the estimated branch lengths near the root of the genealogy are too long.
We illustrate our framework by analyzing two previously published data sets. We investigate the demographic history of HIV-1 using sequences sampled from Central Africa, and we also analyze mtDNA sequences from red pandas (Ailurus fulgens). These examples were chosen for two reasons. First, these data sets have been previously studied using other coalescent methods, so alternative results are available for comparison. Second, the genealogies inferred from these sequences contain a number of short or zero-length branches, which allow us to compare the performance of the generalized and classic plots.
HIV-1 in Central Africa
HIV-1 group M contains the viruses which cause the global HIV pandemic and appears to have arisen in Central Africa during the last 100 years. Vidal et al. (2000)<$REFLINK> investigated the genetic diversity of HIV-1 group M in this region by obtaining viral gene sequences (env gene, V3-V5) in 1997 from 197 infected individuals living in the Democratic Republic of Congo. Yusim et al. (2001)<$REFLINK> used a customized maximum likelihood approach to estimate a phylogeny for this large data set, and it is this phylogeny which we use here (fig. 3a ). Detailed interpretation of the HIV tree and further analysis of this data set can be found in Rambaut et al. (2001)<$REFLINK> and Yusim et al. (2001)<$REFLINK> .
The classic skyline plot for the tree of Yusim et al. (2001)<$REFLINK> is shown in figure 3b. This plot corresponds to the case where ϵ = 0. The tree contains many internode intervals which are zero or near zero in length. Consequently, the plot contains gaps (where the estimated effective population size M̂n is zero) and spikes (where M̂n is close to zero). Figure 3c and d show other generalized plots for the same tree. As ϵ is increased, the generalized plot becomes less noisy than the classic plot, but also becomes less finely resolved. If ϵ is very large then too many intervals are grouped and, as a result, information about demographic history is lost (see fig. 3d ).
The thick curves in figure 3b–d show a maximum likelihood estimate of population size obtained from the HIV tree using a specific parametric model, N(t) = N(0)(α + [1 − α]e − rt), called the expansion model. The parameters of this model were estimated using maximum likelihood (see Yusim et al. 2001<$REFLINK> ). Figure 3c shows the generalized plot with the highest AICc value (ϵ = 0.0119). This plot is neither noisy nor oversimplified, and corresponds closely to the maximum likelihood parametric estimate.
We note that it is very unlikely that this HIV-1 data set has been evolving according to the molecular clock and without recombination. Therefore, statistical estimates of population parameters from these data based on the standard neutral coalescent model must be treated with caution. The quantitative effects of recombination on coalescent-based estimates of demographic history have yet to be determined.
Red Pandas in Southwestern China
The red panda, which inhabits southwestern China, is an endangered species. To investigate the genetic diversity of this species, Su et al. (2001)<$REFLINK> obtained a data set of 53 homologous sequences, 250 bp in length, from the 5′ end of the mtDNA control region. The alignment contains only 25 haplotypes, and thus many sequences are identical. We estimated a genealogy for these sequences by maximum likelihood, using the TBR search heuristic in PAUP (Swofford 1998<$REFLINK> ). The HKY substitution model was used (estimated transition-transversion ratio = 36.5; nucleotide frequencies πA = 0.28, πC = 0.26, πG = 0.14, and πT = 0.32) under the assumption of a molecular clock. Clock-like evolution could not be rejected using a likelihood ratio test (Felsenstein 1981<$REFLINK> ).
Figure 4 shows the classic skyline plot and the optimal generalized skyline plot (AICc estimate of ϵ = 0.0008) obtained from the panda mtDNA genealogy. The generalized skyline plot (fig. 4b ) suggests that the effective population size of red pandas has followed a logistic growth. Su et al. (2001)<$REFLINK> analyzed the same data using pairwise difference distributions and concluded that the red pandas had undergone recent population growth. In contrast, figure 4c suggests an approximately constant population size at present, with growth in the distant past. Pairwise difference distributions do not explicitly incorporate phylogenetic structure and are therefore expected to be less powerful than methods which do, such as the skyline plot (Felsenstein 1992<$REFLINK> ).
The classic skyline plot (fig. 4a ) for the same tree gives a different picture of demographic history, as it suggests that effective population size has increased approximately exponentially in the recent past. This conclusion is a result of the limited phylogenetic signal in the data, which does not permit accurate estimation of the short internode intervals near the tips of the genealogy (as discussed earlier for fig. 1 ).
For a comparison, we also obtained a maximum likelihood estimate of effective population size using the program FLUCTUATE, which assumes a model of exponential growth (Kuhner, Yamato, and Felsenstein 1998<$REFLINK> ). This estimate is shown as a thick line in figure 4b and c. Although the FLUCTUATE estimate only partially matches the skyline plot estimates, it does clearly illustrate the effectiveness of the skyline plot as a model selection tool. If a logistic growth model was implemented in the FLUCTUATE package, then we would expect it to provide a better fit to the red panda data than the exponential model used here.
The generalized skyline plot offers a flexible framework for exploring the demographic history of a sample of DNA sequences, and provides an estimate of effective population size which explicitly incorporates phylogenetic structure. It has three main advantages over the LTT plot and the classic skyline plot, (1) it can be applied to data containing a weaker phylogenetic signal or identical sequences (or both), (2) it provides an estimate of the coalescent error, and (3) it enables the stochastic noise present in the classic plot to be reduced.
The present approach is thus particularly useful as a rapid model selection tool, that is, the generalized skyline plot provides insights with respect to which parametric models may be suitable for a given data set. In the case of the HIV-1 data set (fig. 3 ), it indicates a model of exponential growth with a growth rate that increases through time. For the red panda mtDNA data set, a model of logistic growth appears to be most appropriate (fig. 4 ).
Our method is computationally fast and algorithmically straightforward. Tree estimation is separated from the problem of demographic inference, thus the underlying tree reconstruction method can be adapted to the particular data set in question. If an unusual or complicated substitution model is required, or if a model which permits variation in evolutionary rates among lineages is warranted (e.g., Gillespie 1991<$REFLINK> ; Sanderson 1997<$REFLINK> ; Thorne, Kishino, and Painter 1998<$REFLINK> ; Huelsenbeck, Larget, and Swofford 2000<$REFLINK> ), then these models can be used without altering the skyline plot method.
On the other hand, our approach requires that at least some of the divergence times in a gene tree can be reliably inferred, so it cannot be used on data containing very little variation. It is also important to realize that our approach is a single-tree method. It is therefore complementary to computationally intensive approaches which treat the tree as an unknown nuisance variable and effectively use a collection of trees to infer effective population size (Kuhner, Yamato, and Felsenstein 1995, 1998<$REFLINK> ; Stephens and Donnelly 2000<$REFLINK> ).
In addition to the coalescent error σC2 estimated here, the skyline plot also carries an error introduced by the uncertainty of the phylogenetic estimates of coalescent times. This error has been ignored here and we are currently investigating ways of estimating its effect on the skyline plot.
Several computer programs are available for skyline plot analysis. The approach is implemented in the C++ program GENIE by O.G.P., available from http://evolve.zoo.ox.ac.uk, and in Java in the PAL library (Drummond and Strimmer 2001<$REFLINK> ), available from http://www.pal-project.org. A web interface for skyline plot analysis written by Andrew Rambaut will be online at http://evolve.zoo.ox.ac.uk.
Keith Crandall, Reviewing Editor
Keywords: coalescent process corrected Akaike criterion HIV-1 model selection likelihood red panda skyline plot
Address for correspondence and reprints: Oliver G. Pybus. South Parks Road, Oxford, OX1 3PS, UK. firstname.lastname@example.org .
We thank Andrew Rambaut and Peter Donnelly for discussion, and Bing Su for providing the red panda sequence alignment. We would also like to thank the editor and referees for helpful comments. One referee pointed out the useful simplification of equation (5) . This work was supported by an Emmy-Noether-Fellowship of the Deutsche Forschungsgemeinschaft (K.S.) and by grant 50275 from the Wellcome Trust (O.G.P.).