BACKGROUND: Model violations constitute the major limitation in inferring 
accurate phylogenies. Characterizing properties of the data that are not being 
correctly handled by current models is therefore of prime importance. One of the 
properties of protein evolution is the variation of the relative rate of 
substitutions across sites and over time, the latter is the phenomenon called 
heterotachy. Its effect on phylogenetic inference has recently obtained 
considerable attention, which led to the development of new models of sequence 
evolution. However, thus far focus has been on the quantitative heterogeneity of 
the evolutionary process, thereby overlooking more qualitative variations.
RESULTS: We studied the importance of variation of the site-specific amino-acid 
substitution process over time and its possible impact on phylogenetic 
inference. We used the CAT model to define an infinite mixture of substitution 
processes characterized by equilibrium frequencies over the twenty amino acids, 
a useful proxy for qualitatively estimating the evolutionary process. Using two 
large datasets, we show that qualitative changes in site-specific substitution 
properties over time occurred significantly. To test whether this unaccounted 
qualitative variation can lead to an erroneous phylogenetic tree, we analyzed a 
concatenation of mitochondrial proteins in which Cnidaria and Porifera were 
erroneously grouped. The progressive removal of the sites with the most 
heterogeneous CAT profiles across clades led to the recovery of the monophyly of 
Eumetazoa (Cnidaria+Bilateria), suggesting that this heterogeneity can 
negatively influence phylogenetic inference.
CONCLUSION: The time-heterogeneity of the amino-acid replacement process is 
therefore an important evolutionary aspect that should be incorporated in future 
models of sequence change.