BACKGROUND
the ratio dn/ds  has proven a valuable index of the strength and direction of selection pressure.
because genetic data are typically subject to a diversity of evolutionary constraints, estimating ω as an average over many sites diminishes the effectiveness of this approach  <cit> .
statistical power is substantially improved, however, by accommodating variable selection pressures among sites .
we follow kosakovsky pond and frost  <cit>  by placing such methods in three groups:  the counting methods, which estimate ω from counts of substitutions at individual sites ,  the random-effect models, which assume a parametric distribution of variability in the ω ratio across sites , and  the fixed-effect models, which assume sites can be assigned a priori to different partitions  <cit> .
the most generalized form of the fixed-effect models treats each site as an independent partition  <cit> .
the recent growth of genome scale sequencing projects has sparked interest in using codon models to study mechanisms of innovation and functional divergence in genome-scale datasets  <cit> .
although the fixed-effect models were developed for analysis of multiple partitions of sites within a single gene, they are also appropriate for joint analyses of multi-gene datasets  <cit> .
fixed-effect models categorize codon sites into different classes which are allowed to have heterogeneous evolutionary dynamics, and such partitions are easily delineated on the basis of complete gene sequences.
moreover, by partitioning genes according to criteria such as their functional category, or role in a metabolic pathway, the fixed-effect models provide a statistical framework for making use of such information when analysing multi-gene datasets.
yang and swanson  <cit>  introduced six fixed-effect models  based on the codon model of goldman and yang  <cit> .
the simplest model  assumes that the pattern of substitution is homogeneous over all sites; i.e., there are no partitions under model a. branch lengths are included as parameters of the model.
the most complex model  treats the different site partitions as independent datasets, having independent model parameters.
as it involves a substantial increase in branch length parameters, model f is not recommended for datasets with many partitions  <cit> .
the remaining four models  lie between a and f in complexity.
these four models scale the branch lengths of k partitions according to the parameter ck, which is a multiple of the branch lengths of the first partition; hence c <dig> =  <dig>  models b through e differ in their treatment of parameters ω, κ  and π  among partitions .
we implemented  <dig> more fixed-effect models, which represent all the remaining combinations of heterogeneity or homogeneity among partitions for the parameters c, ω, κ and π .
a full description of the fixed effect models and the details of our implementation are presented in the methods section.
hereafter we refer to the complete set of fixed-effect  models by using the revised notation shown in table  <dig> .
note that a capacity to specify fixed-effects under the alternative formulation of muse and gaut  <cit>  is available through the program hyphy  <cit> , although it has not been documented.
given a related set of fixed-effect models , one is immediately faced with the non-trivial task of selecting the model that best fits the data in hand.
likelihood ratio tests  have been shown to be a powerful and reliable means of testing site specific heterogeneity in selective pressure  <cit> .
however, figure  <dig> illustrates that there are  <dig> possible nested comparisons of models.
it is not desirable to conduct  <dig> lrts because computational costs are expensive for datasets with too many sequences or partitions.
a popular method of model selection based on lrts is "backward elimination"  <cit> .
backward elimination reduces a comparatively complex model to a simpler one in a step-by-step fashion.
an alternative to "backward elimination" is the akaike information criterion   <cit> , where the model with the smallest aic score is chosen as the ideal model.
for a small sample correction, typically when the number of observations is less than  <dig> times the number of parameters in the model  <cit> , we borrowed the corrected akaike information criterion  originally developed by hurvich and tsai  <cit>  for regression settings.
although the statistical issues surrounding model selection are well known within the field of molecular evolution  <cit> , the established statistical techniques have not been applied to the fixed-effect setting.
in this study we used computer simulation to evaluate the performance of backward elimination, aic and aicc for selecting an optimal model from an array of models specifying different levels of heterogeneity among partitions.
we then illustrated the application of these methods on two real datasets.
the first was comprised of the buried and exposed sites of the abalone sperm lysin gene; this lysin partition was one of the original test cases of yang and swanson  <cit> .
for the second case, we examined the evolutionary heterogeneity of a multi-gene dataset; the region of the genome encoding all the components of the flagellar system of listeria species and several proteins of unknown function.
RESULTS
simulated data
a simulation study was used to measure the accuracy of fixed-effect model selection.
we simulated under the  <dig> different scenarios for heterogeneous codon evolution among data partitions shown in table  <dig> , and measured the number of cases where each procedure identified the correct generating model.
the backward elimination procedure uses the likelihood ratio test  to simplify a complex model one parameter at a time; in this case we start at the top of figure  <dig>  and use the lrt to remove non-significant parameters in a step-wise fashion.
a more detailed description is provided in the methods.
when we applied the lrt under a cut-off probability of  <dig> , the backward elimination procedure provided more accurate model specification than either aic or aicc in all the cases except for model  <dig> .
among all  <dig> datasets, the accuracy of backward elimination was 78% whereas the accuracy of aic and aicc was 63% and 64% respectively .
note that each model can be related to all other models by the number of connections, or "steps", between them in figure  <dig>  for all models that are wrongly specified by backward elimination, most were just one step away from the true model .
among these 1-step wrong models, there was a bias in the direction of greater complexity for one of ω, κ or c; replicates heterogeneous for these parameters were never misclassified as homogenous.
taken over all replicates homogenous for ω, κ or c, this bias was generally low, with 1-step error rates of 13%, 9% and 9% respectively.
similar results were observed for aic and aicc.
most misclassifications were 1-step errors , with a bias in the direction of greater complexity for parameter ω, κ or c. again, heterogeneous replicates were not misclassified as homogenous for these parameters.
the 1-step error rates across replicates homogenous for ω, κ or c were 28%, 18% and 26% for aic, and 26%, 17% and 22% for aicc.
as the number of misclassification errors ≥2-steps was much smaller than the number of 1-step errors, we examined these as an average over backward elimination, aic and aicc.
in 90% of the cases these errors resulted in too simple a model.
the involved parameters were ω, c and π; the κ parameter was rarely misclassified.
we simulated under two models of codon frequencies:  unbiased  and  biased frequencies taken from empirical frequencies of the lysin gene.
in composite datasets with a 90: <dig> partition the number of codons in the smaller partition is too low for reliable empirical estimation of  <dig> different codon frequencies .
hence, in only those cases we used the "f <dig> × 4" method, which computes codon frequencies from nucleotide frequencies at the three positions of the codon  <cit> .
in the 50: <dig> and 70: <dig> datasets we used the empirical estimates of codon frequencies  in each partition.
we note that such empirical estimates do not satisfy the requirements of lrt  <cit>  and, hence, the backward elimination procedure.
for backward elimination the 1-step error rate for incorrectly specifying heterogeneous π was 6%, and for incorrectly specifying homogenous π was 14%, indicating a greater tendency towards too simple a model.
for aic and aicc, the misspecification of π was almost entirely for too simple a model.
note that most of these errors were made in the 90: <dig> datasets, suggesting that misspecification of codon frequency heterogeneity is mainly due to large empirical estimation-errors of codon frequencies due to the insufficient information of small partitions.
thus power is lowest to identify heterogeneity in codon frequencies when a partition consists of a small number of codon sites.
we anticipate that power also will be low in larger partitions of real datasets where the difference among partitions is not as great as in our simulations.
next we investigated the possibility of tuning the cut-off p-value of the backward elimination procedure to improve the accuracy of model specification.
we evaluated accuracy for cut-off p-values of  <dig> ,  <dig>  and  <dig> .
substantial improvements were obtained, with average accuracy increasing from 78%  to 83%, 87% and 88%  respectively.
under a cut-off value of  <dig> ,  <dig> models were misspecified, with  <dig> being too simple with respect to codon frequencies in the 90: <dig> datasets.
among the  <dig> remaining misspecified models,  <dig> were too complex for ω and  <dig> were too complex for π. all but one of the misspecified models under cut-off p =  <dig>  were one-step errors.
based on these findings we used a cut-off p =  <dig>  in our application of these models to real data.
abalone sperm lysin gene
abalone sperm lysin is a reproductive protein well known for rapid evolution under strong diversifying selection  <cit> .
we partitioned the lysin dataset into the same set of  <dig> buried sites and  <dig> solvent-exposed sites as in yang and swanson  <cit>  and applied backward elimination , aic and aicc to select among the full set of fixed-effect models.
under backward elimination, we used the likelihood ratio test to compare fe <dig>  which assumes different κ, ω, c, and π's for buried and exposed sites, with those nested models at the next level in figure  <dig> .
each model at the next level assumes one of these four parameters  is homogeneous among site classes.
fe <dig> assumes homogenous κ for both buried and solvent-exposed sites, and the likelihood ratio statistic comparing fe <dig> against fe <dig> is  <dig> ×  =  <dig> , which is not significant .
as all other lrts at this level are significant, we simplified our model according to κ and compared fe <dig> to those models nested at the next level in figure  <dig> .
as subsequent lrts involving fe <dig> were significant, model fe <dig> was selected by backward elimination.
we note that even when we use a cut-off p =  <dig> , we still select fe <dig> by backward elimination.
table  <dig> illustrates that fe <dig> is also selected by using aic or aicc.
yang and swanson  <cit>  conducted lrts of the subset of models shown in table  <dig> and found that model e  provided the best fit to the lysin data.
fe <dig> and fe <dig> are qualitatively similar in suggesting heterogeneity in ω, c and π's among the buried  and solvent exposed  sites.
moreover, these models provide similar quantitative estimates of the strength of selection and rate of evolution in these two partitions .
both models suggest that buried sites are evolving under strong purifying selection and exposed sites under diversifying selection.
note that yang and swanson  <cit>  used a model that specified heterogeneous κ's , as it was not possible to test for heterogeneity in κ's independently of ω's .
as estimates of ω were very similar under fe <dig> and fe <dig>  and κ's for partitions under fe <dig> were very similar , the use of fe <dig> was not problematic in this case.
components of the listeria flagellar system
listeria are gram positive rod shaped bacteria which are motile between 4°c and 30°c, and grow in a wide range of phs, temperatures, and osmotic pressures.
the natural habitat of listeria is thought to be soil rich in decaying matter; however, listeria monocytogenes is an important food-borne pathogen of humans and animals capable of both a free-living and intracellular lifestyle.
interestingly, the motility of listeria monocytogenes is thermoregulated, being reduced above 30°c, and completely shut down above 37°c  <cit> , temperatures which correspond to their host intracellular environment.
the consensus opinion is that the shut down of expression of flagellar related proteins, thereby shutting down motility, is an adaptation to avoid recognition by the hosts innate immune system  <cit> .
specifically, recognition of the flagellin protein, a product of the flaa gene, activates the host inflammatory responses through toll-like receptor  <dig>   <cit> .
twenty-eight genes encoding putative flagellar related proteins, including flaa, are located together in the genome of listeria.
several proteins having functions unrelated to flagellar machinery, or unknown functions, also are encoded in this region of the genome.
we analysed the genes from this region with three issues in mind:  to test for heterogeneous evolutionary dynamics among genes,  to examine the evolutionary dynamics of proteins with unknown function and determine if they have any similarities to flagellar machinery proteins or proteins having unrelated functions, and  to compare selection pressures on flaa with other genes known to encode flagellar related proteins.
we note that thermoregulation of motility is not always perfect, thereby raising the possibility that the host's innate immune system is occasionally able to recognize flagellin  <cit> .
this would set up selection pressure for a "co-evolutionary chase" between host and pathogen, leading to an elevated rate of nonsynonymous evolution in flaa.
our dataset was comprised of  <dig> of the  <dig> genes  located contiguously within the genomes of  <dig> lineages of listeria.
two genes  were excluded because their gene trees were incompatible with the genome-tree.
four genes  were excluded because they were less than  <dig> codons long.
next we partitioned the genes according to functional category:  flagellar machinery ,  non-flagellar functions  and  unknown functions .
we then applied backward elimination , aic and aicc to select among the full set of fixed-effect models .
unlike the lysin example above, the model selected by backward elimination  differed from the model selected by aic and aicc .
both fe <dig> and fe <dig> indicate heterogeneity in c and ω, and homogeneity in κ among partitions.
they differ in that fe <dig> specifies heterogeneous codon frequencies and fe <dig> does not.
clearly, the genes in this region of the listeria genome are subject to heterogeneous evolutionary dynamics.
interestingly, genes encoding proteins of unknown function had levels of selection pressure  highly similar to genes encoding proteins known to comprise the flagellar machinery , whereas those genes that do not encode components of the flagellar machinery were evolving under substantially higher relative rates of amino acid substitution .
genes encoding several components of the flagellar machinery  are present in other bacilli but unaccounted for in listeria.
we used blast to compare the present set of unknown proteins to other bacilli and found one case  that was similar to a known flagellar protein .
we note that the kegg database  <cit>  has annotated lmo <dig> as a putative flagellar assembly protein.
based on genome location and levels of selection pressure, we suggest that the "unknown" genes in this dataset represent the best candidates for the unaccounted components of the listeria flagellar machinery.
genes that evolve at high rates can be difficult to identify  <cit> ; however this is not the case here, as estimates of ω indicate a relatively slow rate of nonsynonymous evolution.
if these genes indeed encode the missing components of the listeria flagellar machinery, we speculate an ancestor of listeria might have acquired them via an lgt event.
the rapidly-evolving non-flagellar genes encoded  a protein involved in regulating chemotaxis ,  a chemotaxis-related sensory protein ,  a cell surface protein , and  a phage-related protein similar to transglycosylase .
to further investigate the evolutionary dynamics of these genes we applied the full set of fixed-effect models to them, with each having a unique partition.
again, the model selected by backward elimination  differed from the model selected by aic and aicc .
results under fe <dig>  and fe <dig> are consistent in suggesting heterogeneous ω among them, with one gene, the cell surface protein, having a substantially higher relative rate of nonsynonymous evolution.
interestingly, a genome wide survey of listeria genes reveals that, in general, cell-surface proteins exhibit accelerated evolutionary rates as compared to housekeeping genes .
lastly, we investigated the evolutionary dynamics of flaa as compared to those genes known to encode flagellar related proteins.
we applied the full set of models to this subset of proteins, with flaa having a unique partition and the remaining  <dig> proteins placed in a second partition.
in this case backward elimination, aic and aicc selected model fe <dig>  this indicates that, despite heterogeneity in both c and π, selection pressure on flaa does not differ significantly from the average for genes encoding a flagellar related protein.
this result supports the hypothesis that thermoregulation of motility remains an effective adaptation to avoid recognition by the host's innate immune system  <cit> , despite sometimes less than perfect control over gene expression.
discussion
the simulation results show that under a cut-off p-value =  <dig>  the likelihood ratio test is more accurate than aic and aicc.
with the exception of the π parameters, aic and aicc chose overly complex models more frequently than did the backward elimination procedure.
for the π parameters, aic and aicc chose overly simple models more frequently than did backward elimination.
the difference lies in the different cut-off values that are used to penalize the more complex model.
take the heterogeneity test of κ as an example , the lrt statistic is defined as twice the difference in log likelihood values between a pair of nested models: Λ =  <dig> ×  - ln l).
based on the lrt under a significance level of  <dig> , we reduce the complexity of the model if Λ is smaller than the critical value  <dig> .
under aic we choose a simpler model only when Λ < 2; hence, aic tends toward more complex models.
however when we reduce a model by more than  <dig> parameters , the critical value becomes  <dig>  for the lrt, which is less than the critical value of Λ under aic,  <dig>  in this case, aic will select the same or simpler model than the lrt.
note that aicc compares Λ with  <dig> × k × n/ which is always greater than  <dig> × k used by aic, hence aicc will always choose the same or simpler model than aic.
this property of aicc had only a small effect on the results of model selection, as aicc performed only slightly better than aic but substantially worse than backward elimination.
lrt statistics involving parameters such as ω appear to be asymptotically χ <dig> distributed for random-effect codon models; such models employ a parametric distribution  to accommodate among site variability in the ω ratio.
however, aagaard and phillips  <cit>  reported that for comparisons of yang and swanson's  <cit>  models c and e , the empirical distribution of lrt statistics deviated from the expected χ <dig> distribution, leading to a type i error rate in excess of that specified by the level of the test.
the results of our simulation study suggest this bias might affect all tests in figure  <dig> involving parameters κ, ω and c. several authors have noted that lrt statistics derived from models that employ empirical estimates of nucleotide or codon frequencies might not be well approximated by a χ <dig> distribution  <cit> .
moreover, when aagaard and phillips  <cit>  repeated their simulation study under equal codon frequencies and computed lrt statistics by using models with frequency parameters fixed to the true values , they found that the lrt statistics matched the χ <dig> expectation.
aagaard and phillips  <cit>  suggested that the approximation of codon frequencies is the source of the observed bias in the lrt.
indeed, empirical estimates do not satisfy the requirements of lrt  <cit> , and consequently the backward elimination procedure.
to further investigate the impact of empirical estimates on model selection, we reanalysed all the simulated datasets under the true codon frequencies; i.e., those used to generate the data.
we note that for a given dataset the empirical codon frequencies yielded higher likelihood scores than did the true frequencies.
this was expected, as empirical estimation will "pick up" some of the sampling errors in each simulation replicate.
we found that the accuracy and bias of backward elimination, aic and aicc under the true codon frequencies were identical to those when empirical codon frequencies were used.
this suggests that bias in the model selection procedures used here did not arise from empirical estimation of π's alone.
there are several possible explanations for the bias of all three model selection methods in the direction of greater complexity for one of ω, κ or c. one possibility is that potential non-independence among the values for different parameters means that aic might not be a good approximation to the kullback-leibler divergence, and that the requirements for the χ <dig> approximation might not be met for the lrt, thus the degree of freedom is not accurate.
also, backward elimination may find a local optimum solution.
under backward elimination the cut-off p-value is subjectively decided before the tests, leading to the possibility that the procedure will stop too early and suggest an overly complex model.
this phenomenon is sometimes seen in the regression context.
clearly, these issues require further attention; in the mean time we explored the possibility of tuning the cut-off p-value in order to improve the performance of backward elimination .
after evaluating several cut-off values for p, we found that a substantial improvement in performance was obtained by using p =  <dig> .
moreover, we found that by using this cut-off, nearly all the tendency to select an overly complex model for ω, κ or c was avoided, and that errors for selecting overly-simplistic models happen mostly for datasets where one of the partitions was comprised of a very small number of codon sites.
our application of fixed-effect models to real data was encouraging, having uncovered previously unrecognized heterogeneity among listeria genes and among sites within the abalone sperm lysin gene.
however, if the objective is only to identify individual positive selection sites within a gene, the a priori structural information is not likely to serve as a perfect proxy for those partitions most relevant to differences in selection pressures.
for example, yang and swanson  <cit>  showed that the exposed sites of lysin likely include both conserved and positively selected codon positions.
hence, averaging ω over all sites in the exposed partition yields a reduced estimate of positive selection pressure.
we note this effect was the same under the best-fit model, fe <dig>  as under fe <dig>  used by yang and swanson  <cit> .
we agree with yang and swanson  <cit>  in anticipating that the power of random-effect models to test the strength and direction of selection pressure at sites within genes will be greater than fixed-effect models in most cases.
if the objective is to investigate heterogeneous evolution among genes, as in genome-scale analyses, then fixed-effect models are useful.
the present set of models represents only a small step towards genome-scale evolutionary models.
for example, decoupling synonymous and nonsynonymous rates, as in the random-effect model of kosakovsky pond and muse  <cit> , would allow users freedom to model gradients in synonymous substitution rates along a genome while allowing independent variability in nonsynonymous rates among genes.
yang and swanson  <cit>  made several suggestions, including the intriguing idea of enforcing a molecular clock for synonymous changes and leaving nonsynonymous changes unconstrained.
we predict that joining fixed-effect codon models and data-mining methods to obtain new methods analogous to model based clustering  <cit>  could provide extremely useful tools for genome-scale data analysis.
lastly, there is growing interest in both the performance of codon models  <cit>  and the impact of heterogeneity among genes  <cit>  in multi-gene phylogenetic analysis; improved ability to model among-gene heterogeneity at the codon level could improve their utility for comparing alternative phylogenomic hypotheses.
CONCLUSIONS
random- and fixed-effect codon models have unique advantages and disadvantages.
random-effect models are desirable when there is no a priori knowledge by which sites might be partitioned, or when only a few sites are expected to comprise a partition of interest .
their disadvantage is that models for heterogeneity among sites in features such as the transition to transversion ratio  and equilibrium codon frequencies  are unavailable.
fixed-effect models are desirable when data partitions are known to exhibit significant heterogeneity in parameters such as c, κ or π, or when a statistical test of such heterogeneity is desired.
the disadvantage here is that any uncertainty in the site partition is not accommodated.
the growing importance of phylogenomics and metagenomics  will lead to a greater need for models suitable for testing hypotheses, and estimating rates and patterns of evolution, in large multi-gene datasets.
although considerable development remains to be done, we believe the present set of models will find many useful applications provided that results are interpreted with the inherent limitations of the methods in mind.
in particular we note:  power can be low , particularly when partitions are small,  the accuracy of the partitions may influence the results of model specification and  the tree topology is assumed to be known without error.
for the time being we make the following recommendations:  select among models by using backward elimination rather than aic or aicc,  use a stringent cut-off p-value; p =  <dig>  seems appropriate, and  sensitivity analysis should be included in an investigation.
sensitivity of results should be investigated for robustness to tree topology and model of codon frequencies.
we note that by using akaike weights  <cit>  to quantify the evidence in favour of a model, estimates of parameters could be obtained that accommodate model uncertainties .
where practical, we recommend that sensitivity to alternative data partitions also should be explored.
lastly, any complex model can have convergence problems or implementation errors; one must always inspect the parameter estimates for atypical results.
with thoughtful application, fixed-effect codon models should provide a useful tool for large scale multi-gene analyses.

 the ratio dn/ds has proven a valuable index of the strength and direction of selection pressure. because genetic data are typically subject to a diversity of evolutionary constraints, estimating ω as an average over many sites diminishes the effectiveness of this approach. statistical power is substantially improved, however, by accommodating variable selection pressures among sites. we follow kosakovsky pond and frost by placing such methods in three groups: the counting methods, which estimate ω from counts of substitutions at individual sites, the random-effect models, which assume a parametric distribution of variability in the ω ratio across sites, and the fixed-effect models, which assume sites can be assigned a priori to different partitions. the most generalized form of the fixed-effect models treats each site as an independent partition. the recent growth of genome scale sequencing projects has sparked interest in using codon models to study mechanisms of innovation and functional divergence in genome-scale datasets. although the fixed-effect models were developed for analysis of multiple partitions of sites within a single gene, they are also appropriate for joint analyses of multi-gene datasets. fixed-effect models categorize codon sites into different classes which are allowed to have heterogeneous evolutionary dynamics, and such partitions are easily delineated on the basis of complete gene sequences. moreover, by partitioning genes according to criteria such as their functional category, or role in a metabolic pathway, the fixed-effect models provide a statistical framework for making use of such information when analysing multi-gene datasets. yang and swanson introduced six fixed-effect models based on the codon model of goldman and yang. the simplest model assumes that the pattern of substitution is homogeneous over all sites; i.e., there are no partitions under model a. branch lengths are included as parameters of the model. the most complex model treats the different site partitions as independent datasets, having independent model parameters. as it involves a substantial increase in branch length parameters, model f is not recommended for datasets with many partitions. the remaining four models lie between a and f in complexity. these four models scale the branch lengths of k partitions according to the parameter ck, which is a multiple of the branch lengths of the first partition; hence c = models b through e differ in their treatment of parameters ω, κ and π among partitions. we implemented more fixed-effect models, which represent all the remaining combinations of heterogeneity or homogeneity among partitions for the parameters c, ω, κ and π. a full description of the fixed effect models and the details of our implementation are presented in the methods section. hereafter we refer to the complete set of fixed-effect models by using the revised notation shown in table. note that a capacity to specify fixed-effects under the alternative formulation of muse and gaut is available through the program hyphy, although it has not been documented. given a related set of fixed-effect models, one is immediately faced with the non-trivial task of selecting the model that best fits the data in hand. likelihood ratio tests have been shown to be a powerful and reliable means of testing site specific heterogeneity in selective pressure. however, figure illustrates that there are possible nested comparisons of models. it is not desirable to conduct lrts because computational costs are expensive for datasets with too many sequences or partitions. a popular method of model selection based on lrts is "backward elimination". backward elimination reduces a comparatively complex model to a simpler one in a step-by-step fashion. an alternative to "backward elimination" is the akaike information criterion, where the model with the smallest aic score is chosen as the ideal model. for a small sample correction, typically when the number of observations is less than times the number of parameters in the model, we borrowed the corrected akaike information criterion originally developed by hurvich and tsai for regression settings. although the statistical issues surrounding model selection are well known within the field of molecular evolution, the established statistical techniques have not been applied to the fixed-effect setting. in this study we used computer simulation to evaluate the performance of backward elimination, aic and aicc for selecting an optimal model from an array of models specifying different levels of heterogeneity among partitions. we then illustrated the application of these methods on two real datasets. the first was comprised of the buried and exposed sites of the abalone sperm lysin gene; this lysin partition was one of the original test cases of yang and swanson. for the second case, we examined the evolutionary heterogeneity of a multi-gene dataset; the region of the genome encoding all the components of the flagellar system of listeria species and several proteins of unknown function.  simulated data a simulation study was used to measure the accuracy of fixed-effect model selection. we simulated under the different scenarios for heterogeneous codon evolution among data partitions shown in table, and measured the number of cases where each procedure identified the correct generating model. the backward elimination procedure uses the likelihood ratio test to simplify a complex model one parameter at a time; in this case we start at the top of figure and use the lrt to remove non-significant parameters in a step-wise fashion. a more detailed description is provided in the methods. when we applied the lrt under a cut-off probability of, the backward elimination procedure provided more accurate model specification than either aic or aicc in all the cases except for model. among all datasets, the accuracy of backward elimination was 78% whereas the accuracy of aic and aicc was 63% and 64% respectively. note that each model can be related to all other models by the number of connections, or "steps", between them in figure for all models that are wrongly specified by backward elimination, most were just one step away from the true model. among these 1-step wrong models, there was a bias in the direction of greater complexity for one of ω, κ or c; replicates heterogeneous for these parameters were never misclassified as homogenous. taken over all replicates homogenous for ω, κ or c, this bias was generally low, with 1-step error rates of 13%, 9% and 9% respectively. similar results were observed for aic and aicc. most misclassifications were 1-step errors, with a bias in the direction of greater complexity for parameter ω, κ or c. again, heterogeneous replicates were not misclassified as homogenous for these parameters. the 1-step error rates across replicates homogenous for ω, κ or c were 28%, 18% and 26% for aic, and 26%, 17% and 22% for aicc. as the number of misclassification errors ≥2-steps was much smaller than the number of 1-step errors, we examined these as an average over backward elimination, aic and aicc. in 90% of the cases these errors resulted in too simple a model. the involved parameters were ω, c and π; the κ parameter was rarely misclassified. we simulated under two models of codon frequencies: unbiased and biased frequencies taken from empirical frequencies of the lysin gene. in composite datasets with a 90: partition the number of codons in the smaller partition is too low for reliable empirical estimation of different codon frequencies. hence, in only those cases we used the "f × 4" method, which computes codon frequencies from nucleotide frequencies at the three positions of the codon. in the 50: and 70: datasets we used the empirical estimates of codon frequencies in each partition. we note that such empirical estimates do not satisfy the requirements of lrt and, hence, the backward elimination procedure. for backward elimination the 1-step error rate for incorrectly specifying heterogeneous π was 6%, and for incorrectly specifying homogenous π was 14%, indicating a greater tendency towards too simple a model. for aic and aicc, the misspecification of π was almost entirely for too simple a model. note that most of these errors were made in the 90: datasets, suggesting that misspecification of codon frequency heterogeneity is mainly due to large empirical estimation-errors of codon frequencies due to the insufficient information of small partitions. thus power is lowest to identify heterogeneity in codon frequencies when a partition consists of a small number of codon sites. we anticipate that power also will be low in larger partitions of real datasets where the difference among partitions is not as great as in our simulations. next we investigated the possibility of tuning the cut-off p-value of the backward elimination procedure to improve the accuracy of model specification. we evaluated accuracy for cut-off p-values of, and. substantial improvements were obtained, with average accuracy increasing from 78% to 83%, 87% and 88% respectively. under a cut-off value of, models were misspecified, with being too simple with respect to codon frequencies in the 90: datasets. among the remaining misspecified models, were too complex for ω and were too complex for π. all but one of the misspecified models under cut-off p = were one-step errors. based on these findings we used a cut-off p = in our application of these models to real data. abalone sperm lysin gene abalone sperm lysin is a reproductive protein well known for rapid evolution under strong diversifying selection. we partitioned the lysin dataset into the same set of buried sites and solvent-exposed sites as in yang and swanson and applied backward elimination, aic and aicc to select among the full set of fixed-effect models. under backward elimination, we used the likelihood ratio test to compare fe which assumes different κ, ω, c, and π's for buried and exposed sites, with those nested models at the next level in figure. each model at the next level assumes one of these four parameters is homogeneous among site classes. fe assumes homogenous κ for both buried and solvent-exposed sites, and the likelihood ratio statistic comparing fe against fe is × =, which is not significant. as all other lrts at this level are significant, we simplified our model according to κ and compared fe to those models nested at the next level in figure. as subsequent lrts involving fe were significant, model fe was selected by backward elimination. we note that even when we use a cut-off p =, we still select fe by backward elimination. table illustrates that fe is also selected by using aic or aicc. yang and swanson conducted lrts of the subset of models shown in table and found that model e provided the best fit to the lysin data. fe and fe are qualitatively similar in suggesting heterogeneity in ω, c and π's among the buried and solvent exposed sites. moreover, these models provide similar quantitative estimates of the strength of selection and rate of evolution in these two partitions. both models suggest that buried sites are evolving under strong purifying selection and exposed sites under diversifying selection. note that yang and swanson used a model that specified heterogeneous κ's, as it was not possible to test for heterogeneity in κ's independently of ω's. as estimates of ω were very similar under fe and fe and κ's for partitions under fe were very similar, the use of fe was not problematic in this case. components of the listeria flagellar system listeria are gram positive rod shaped bacteria which are motile between 4°c and 30°c, and grow in a wide range of phs, temperatures, and osmotic pressures. the natural habitat of listeria is thought to be soil rich in decaying matter; however, listeria monocytogenes is an important food-borne pathogen of humans and animals capable of both a free-living and intracellular lifestyle. interestingly, the motility of listeria monocytogenes is thermoregulated, being reduced above 30°c, and completely shut down above 37°c, temperatures which correspond to their host intracellular environment. the consensus opinion is that the shut down of expression of flagellar related proteins, thereby shutting down motility, is an adaptation to avoid recognition by the hosts innate immune system. specifically, recognition of the flagellin protein, a product of the flaa gene, activates the host inflammatory responses through toll-like receptor. twenty-eight genes encoding putative flagellar related proteins, including flaa, are located together in the genome of listeria. several proteins having functions unrelated to flagellar machinery, or unknown functions, also are encoded in this region of the genome. we analysed the genes from this region with three issues in mind: to test for heterogeneous evolutionary dynamics among genes, to examine the evolutionary dynamics of proteins with unknown function and determine if they have any similarities to flagellar machinery proteins or proteins having unrelated functions, and to compare selection pressures on flaa with other genes known to encode flagellar related proteins. we note that thermoregulation of motility is not always perfect, thereby raising the possibility that the host's innate immune system is occasionally able to recognize flagellin. this would set up selection pressure for a "co-evolutionary chase" between host and pathogen, leading to an elevated rate of nonsynonymous evolution in flaa. our dataset was comprised of of the genes located contiguously within the genomes of lineages of listeria. two genes were excluded because their gene trees were incompatible with the genome-tree. four genes were excluded because they were less than codons long. next we partitioned the genes according to functional category: flagellar machinery, non-flagellar functions and unknown functions. we then applied backward elimination, aic and aicc to select among the full set of fixed-effect models. unlike the lysin example above, the model selected by backward elimination differed from the model selected by aic and aicc. both fe and fe indicate heterogeneity in c and ω, and homogeneity in κ among partitions. they differ in that fe specifies heterogeneous codon frequencies and fe does not. clearly, the genes in this region of the listeria genome are subject to heterogeneous evolutionary dynamics. interestingly, genes encoding proteins of unknown function had levels of selection pressure highly similar to genes encoding proteins known to comprise the flagellar machinery, whereas those genes that do not encode components of the flagellar machinery were evolving under substantially higher relative rates of amino acid substitution. genes encoding several components of the flagellar machinery are present in other bacilli but unaccounted for in listeria. we used blast to compare the present set of unknown proteins to other bacilli and found one case that was similar to a known flagellar protein. we note that the kegg database has annotated lmo as a putative flagellar assembly protein. based on genome location and levels of selection pressure, we suggest that the "unknown" genes in this dataset represent the best candidates for the unaccounted components of the listeria flagellar machinery. genes that evolve at high rates can be difficult to identify; however this is not the case here, as estimates of ω indicate a relatively slow rate of nonsynonymous evolution. if these genes indeed encode the missing components of the listeria flagellar machinery, we speculate an ancestor of listeria might have acquired them via an lgt event. the rapidly-evolving non-flagellar genes encoded a protein involved in regulating chemotaxis, a chemotaxis-related sensory protein, a cell surface protein, and a phage-related protein similar to transglycosylase. to further investigate the evolutionary dynamics of these genes we applied the full set of fixed-effect models to them, with each having a unique partition. again, the model selected by backward elimination differed from the model selected by aic and aicc. results under fe and fe are consistent in suggesting heterogeneous ω among them, with one gene, the cell surface protein, having a substantially higher relative rate of nonsynonymous evolution. interestingly, a genome wide survey of listeria genes reveals that, in general, cell-surface proteins exhibit accelerated evolutionary rates as compared to housekeeping genes. lastly, we investigated the evolutionary dynamics of flaa as compared to those genes known to encode flagellar related proteins. we applied the full set of models to this subset of proteins, with flaa having a unique partition and the remaining proteins placed in a second partition. in this case backward elimination, aic and aicc selected model fe this indicates that, despite heterogeneity in both c and π, selection pressure on flaa does not differ significantly from the average for genes encoding a flagellar related protein. this result supports the hypothesis that thermoregulation of motility remains an effective adaptation to avoid recognition by the host's innate immune system, despite sometimes less than perfect control over gene expression. discussion the simulation results show that under a cut-off p-value = the likelihood ratio test is more accurate than aic and aicc. with the exception of the π parameters, aic and aicc chose overly complex models more frequently than did the backward elimination procedure. for the π parameters, aic and aicc chose overly simple models more frequently than did backward elimination. the difference lies in the different cut-off values that are used to penalize the more complex model. take the heterogeneity test of κ as an example, the lrt statistic is defined as twice the difference in log likelihood values between a pair of nested models: Λ = × - ln l). based on the lrt under a significance level of, we reduce the complexity of the model if Λ is smaller than the critical value. under aic we choose a simpler model only when Λ < 2; hence, aic tends toward more complex models. however when we reduce a model by more than parameters, the critical value becomes for the lrt, which is less than the critical value of Λ under aic, in this case, aic will select the same or simpler model than the lrt. note that aicc compares Λ with × k × n/ which is always greater than × k used by aic, hence aicc will always choose the same or simpler model than aic. this property of aicc had only a small effect on the results of model selection, as aicc performed only slightly better than aic but substantially worse than backward elimination. lrt statistics involving parameters such as ω appear to be asymptotically χ distributed for random-effect codon models; such models employ a parametric distribution to accommodate among site variability in the ω ratio. however, aagaard and phillips reported that for comparisons of yang and swanson's models c and e, the empirical distribution of lrt statistics deviated from the expected χ distribution, leading to a type i error rate in excess of that specified by the level of the test. the results of our simulation study suggest this bias might affect all tests in figure involving parameters κ, ω and c. several authors have noted that lrt statistics derived from models that employ empirical estimates of nucleotide or codon frequencies might not be well approximated by a χ distribution. moreover, when aagaard and phillips repeated their simulation study under equal codon frequencies and computed lrt statistics by using models with frequency parameters fixed to the true values, they found that the lrt statistics matched the χ expectation. aagaard and phillips suggested that the approximation of codon frequencies is the source of the observed bias in the lrt. indeed, empirical estimates do not satisfy the requirements of lrt, and consequently the backward elimination procedure. to further investigate the impact of empirical estimates on model selection, we reanalysed all the simulated datasets under the true codon frequencies; i.e., those used to generate the data. we note that for a given dataset the empirical codon frequencies yielded higher likelihood scores than did the true frequencies. this was expected, as empirical estimation will "pick up" some of the sampling errors in each simulation replicate. we found that the accuracy and bias of backward elimination, aic and aicc under the true codon frequencies were identical to those when empirical codon frequencies were used. this suggests that bias in the model selection procedures used here did not arise from empirical estimation of π's alone. there are several possible explanations for the bias of all three model selection methods in the direction of greater complexity for one of ω, κ or c. one possibility is that potential non-independence among the values for different parameters means that aic might not be a good approximation to the kullback-leibler divergence, and that the requirements for the χ approximation might not be met for the lrt, thus the degree of freedom is not accurate. also, backward elimination may find a local optimum solution. under backward elimination the cut-off p-value is subjectively decided before the tests, leading to the possibility that the procedure will stop too early and suggest an overly complex model. this phenomenon is sometimes seen in the regression context. clearly, these issues require further attention; in the mean time we explored the possibility of tuning the cut-off p-value in order to improve the performance of backward elimination. after evaluating several cut-off values for p, we found that a substantial improvement in performance was obtained by using p =. moreover, we found that by using this cut-off, nearly all the tendency to select an overly complex model for ω, κ or c was avoided, and that errors for selecting overly-simplistic models happen mostly for datasets where one of the partitions was comprised of a very small number of codon sites. our application of fixed-effect models to real data was encouraging, having uncovered previously unrecognized heterogeneity among listeria genes and among sites within the abalone sperm lysin gene. however, if the objective is only to identify individual positive selection sites within a gene, the a priori structural information is not likely to serve as a perfect proxy for those partitions most relevant to differences in selection pressures. for example, yang and swanson showed that the exposed sites of lysin likely include both conserved and positively selected codon positions. hence, averaging ω over all sites in the exposed partition yields a reduced estimate of positive selection pressure. we note this effect was the same under the best-fit model, fe as under fe used by yang and swanson. we agree with yang and swanson in anticipating that the power of random-effect models to test the strength and direction of selection pressure at sites within genes will be greater than fixed-effect models in most cases. if the objective is to investigate heterogeneous evolution among genes, as in genome-scale analyses, then fixed-effect models are useful. the present set of models represents only a small step towards genome-scale evolutionary models. for example, decoupling synonymous and nonsynonymous rates, as in the random-effect model of kosakovsky pond and muse, would allow users freedom to model gradients in synonymous substitution rates along a genome while allowing independent variability in nonsynonymous rates among genes. yang and swanson made several suggestions, including the intriguing idea of enforcing a molecular clock for synonymous changes and leaving nonsynonymous changes unconstrained. we predict that joining fixed-effect codon models and data-mining methods to obtain new methods analogous to model based clustering could provide extremely useful tools for genome-scale data analysis. lastly, there is growing interest in both the performance of codon models and the impact of heterogeneity among genes in multi-gene phylogenetic analysis; improved ability to model among-gene heterogeneity at the codon level could improve their utility for comparing alternative phylogenomic hypotheses.  random- and fixed-effect codon models have unique advantages and disadvantages. random-effect models are desirable when there is no a priori knowledge by which sites might be partitioned, or when only a few sites are expected to comprise a partition of interest. their disadvantage is that models for heterogeneity among sites in features such as the transition to transversion ratio and equilibrium codon frequencies are unavailable. fixed-effect models are desirable when data partitions are known to exhibit significant heterogeneity in parameters such as c, κ or π, or when a statistical test of such heterogeneity is desired. the disadvantage here is that any uncertainty in the site partition is not accommodated. the growing importance of phylogenomics and metagenomics will lead to a greater need for models suitable for testing hypotheses, and estimating rates and patterns of evolution, in large multi-gene datasets. although considerable development remains to be done, we believe the present set of models will find many useful applications provided that results are interpreted with the inherent limitations of the methods in mind. in particular we note: power can be low, particularly when partitions are small, the accuracy of the partitions may influence the results of model specification and the tree topology is assumed to be known without error. for the time being we make the following recommendations: select among models by using backward elimination rather than aic or aicc, use a stringent cut-off p-value; p = seems appropriate, and sensitivity analysis should be included in an investigation. sensitivity of results should be investigated for robustness to tree topology and model of codon frequencies. we note that by using akaike weights to quantify the evidence in favour of a model, estimates of parameters could be obtained that accommodate model uncertainties. where practical, we recommend that sensitivity to alternative data partitions also should be explored. lastly, any complex model can have convergence problems or implementation errors; one must always inspect the parameter estimates for atypical results. with thoughtful application, fixed-effect codon models should provide a useful tool for large scale multi-gene analyses. 
we recommend: selection of models by using backward elimination rather than aic or aicc, use a stringent cut-off, e.g., p =, and conduct sensitivity analysis of results. we evaluate the performance of these model selection methods via a simulation study, and make several recommendations for real data analysis. these are called fixed-effect models, and they require that all codon sites are assigned to one of several partitions which are permitted to have independent parameters for selection pressure, evolutionary rate, transition to transversion ratio or codon frequencies. given a set of related fixed-effect models, the task of selecting the model that best fits the data is not trivial. fixed-effect models have advantages and disadvantages. fixed-effect models are desirable when data partitions are known to exhibit significant heterogeneity or when a statistical test of such heterogeneity is desired. in this study, we implement a set of fixed-effect codon models which allow for different levels of heterogeneity among partitions in the substitution process. they have the disadvantage of requiring a priori knowledge for partitioning sites. for single gene analysis, partitions might be defined according to protein tertiary structure, and for multiple gene analysis partitions might be defined according to a gene's functional category. we also demonstrate the utility of these models by application to a single-gene dataset partitioned according to tertiary structure, and a multi-gene dataset partitioned according to the functional category of the gene. in some cases, a priori biological knowledge has been used successfully to model heterogeneous evolutionary dynamics among codon sites. with thoughtful application, fixed-effect codon models should provide a useful tool for large scale multi-gene analyses. we describe strategies for selecting among these models by a backward elimination procedure, akaike information criterion or a corrected akaike information criterion. our simulation study indicates that the backward elimination procedure can provide a reliable method for model selection in this setting.
 models of codon evolution have proven useful for investigating the strength and direction of natural selection. in some cases, a priori biological knowledge has been used successfully to model heterogeneous evolutionary dynamics among codon sites. these are called fixed-effect models, and they require that all codon sites are assigned to one of several partitions which are permitted to have independent parameters for selection pressure, evolutionary rate, transition to transversion ratio or codon frequencies. for single gene analysis, partitions might be defined according to protein tertiary structure, and for multiple gene analysis partitions might be defined according to a gene's functional category. given a set of related fixed-effect models, the task of selecting the model that best fits the data is not trivial.  in this study, we implement a set of fixed-effect codon models which allow for different levels of heterogeneity among partitions in the substitution process. we describe strategies for selecting among these models by a backward elimination procedure, akaike information criterion or a corrected akaike information criterion. we evaluate the performance of these model selection methods via a simulation study, and make several recommendations for real data analysis. our simulation study indicates that the backward elimination procedure can provide a reliable method for model selection in this setting. we also demonstrate the utility of these models by application to a single-gene dataset partitioned according to tertiary structure, and a multi-gene dataset partitioned according to the functional category of the gene.  fixed-effect models have advantages and disadvantages. fixed-effect models are desirable when data partitions are known to exhibit significant heterogeneity or when a statistical test of such heterogeneity is desired. they have the disadvantage of requiring a priori knowledge for partitioning sites. we recommend: selection of models by using backward elimination rather than aic or aicc, use a stringent cut-off, e.g., p =, and conduct sensitivity analysis of results. with thoughtful application, fixed-effect codon models should provide a useful tool for large scale multi-gene analyses. 15– march first international conference on phylogenomics sainte-adèle, québec, canada 