BACKGROUND
estimating divergence time of protein sequences is one of the fundamental problems in bioinformatics.
evolutionary distance estimates are used by many of the most commonly used phylogenetic tree reconstruction algorithms  <cit> .
in current research, phylogenetic trees are used for many types of subsequent analysis, e.g.
orthology inference  <cit> .
early models for sequence evolution focussed on nucleotides.
they commonly employ markov chains and assume independent evolution at every site.
each of the four nucleotides is identified by one state and the substitution probability is modelled as a state transition probability from one state to another.
in the most straightforward approach, the same state transition probability is assigned to every substitution  <cit> .
subsequent models take account of more nucleotide specific properties, e.g.
transitional and transversional substitutions as well as gc content .
these more advanced approaches are bound to nucleotide sequences and cannot be directly used with protein sequences.
markov chain models for protein evolution differ from nucleotide approaches in their larger number of states and transitions for which parameters need to be estimated.
the protein sequence jukes-cantor model assigns the same probability to each substitution and is hence a rather poor approximation.
this method essentially takes the observed differences between two sequences and corrects this value to the estimated evolutionary distance using a logarithmic function.
other similar methods exist that also correct observed differences, e.g.
kimura's method  <cit> .
although they produce rather inaccurate distance estimates, correction-based distance estimators are popular because of their simplicity.
more advanced protein evolution models estimate parameters from protein sequence alignments.
assuming the same substitutions for closely and distantly related sequences leads to the construction of the dayhoff matrix series  <cit> .
following this approach, it suffices to collect data from alignments of closely related sequences to build an evolutionary model of amino acid substitution.
dayhoff and co-workers introduced the term percent accepted  mutation , which denotes a commonly used measure for evolutionary distance between two aligned sequences .
in other words, two sequences at a distance of  <dig> pam are related to each other by  <dig>  substitutions per position on average.
as substitution is a stochastic process, some positions will experience multiple substitutions while others will experience none.
it is also possible that secondary substitutions at one site will result in the original residue, making the evolutionary steps invisible.
this is in essence the reason why estimating evolutionary distance is so hard – multiple substitutions cannot be observed directly.
an evolutionary distance of  <dig> pam corresponds roughly to 80% observed differences.
the term pam is found in literature for both the matrix series given by dayhoff et al.
as well as for evolutionary distance unit.
in this publication we refer to the matrices as dayhoff matrices and reserve the term pam for distance units.
there are two major shortcomings connected with the derivation of the dayhoff matrices.
first, potential errors inherent in the experimental data will be magnified by extrapolation.
additionally, it is questionable whether substitution probabilities observed on closely related sequences can accurately reflect the evolution of more distantly related sequences.
the efforts of researchers since the publication of the dayhoff matrices have led to several other matrix series, sharing the idea of an underlying markov chain.
they differ in terms of the data they are built upon and account for the above-mentioned shortcomings in various ways  <cit> .
the approach behind the blosum matrices  <cit>  is different from dayhoff's evolutionary model.
whereas the markov model assumes that any transition probability matrix may be derived from another matrix in the same series, the blosum matrices do not imply any evolutionary time.
there is no direct mathematical relationship between matrices in the blosum series.
sequences with identities above a given identity cutoff are clustered and used to derive score matrices.
the blosum matrices are known as a good general-purpose choice.
especially, blosum <dig> is frequently chosen for the alignment of sequences.
RESULTS
we here introduce scoredist, a novel correction-based distance estimator for protein sequences.
it applies a correction function to an observed reduction in normalised score, rather than to observed differences as other correction-based methods.
this gives a better estimate of the divergence in the well-established pam measure and allows the popular blosum matrix series to be used.
other matrices could in principle be used, but the blosum matrix has proved to be the most universal.
scoredist distance estimates are calculated directly by a simple equation and do not require cumbersome computational approximations, which is needed for e.g.
maximum likelihood  and expected distance  estimates  <cit> .
additional calibration opens the possibility to make scoredist tuned to other evolutionary models.
in order to evaluate our novel protein distance estimator scoredist against other estimators, we generated a large testset of artificial sequence alignments.
simulation is the only way to exactly know an alignment's evolutionary distance.
the substitutions were made by rose  <cit>  according to an evolutionary model that can be chosen arbitrarily.
it is to be expected that a distance estimator based on a particular evolutionary model will perform optimally on a testset generated with the same model.
we therefore generated testsets using four different matrix series: dayhoff  <cit> , mv  <cit> , jtt  <cit> , and wag  <cit> .
for each model,  <dig> alignments were created for evolutionary distances between  <dig> and  <dig> pam units, i.e.
<dig> alignments for each distance.
the scoredist, maximum likelihood, and expected distance estimators can all be tuned towards a particular evolutionary model.
we therefore used three evolutionary models which were also used to generate the testsets for these distance estimators, and use a shorthand to refer to these as "method-model".
for instance, maximum likelihood using the mv model is denoted ml-mv.
the jukes-cantor and kimura estimators can not be tuned to a specific model but were tested on all four datasets.
the jukes-cantor and kimura correction methods are generally less accurate than scoredist and ml estimators.
in some cases they reached higher accuracy than scoredist and ml trained on the "wrong" model.
for instance, on the dayhoff testset kimura was better than scoredist-mv and ml-mv, and on the mv testset jukes-cantor was better than scoredist and ml trained on dayhoff or jtt.
however, jukes-cantor and kimura never came near the scoredist and ml accuracy when trained on the "right" model.
in a real situation, it is of course not known which evolutionary model is most appropriate.
therefore, taking the average rmsd values for each training model reveals the generality and robustness of the method on different testsets.
the average accuracy of scoredist is consistently better than for ml, and jukes-cantor and kimura are even further behind.
implementation
the scoredist estimator was implemented in belvu, which is a general-purpose multiple alignment viewer that allows basic alignment editing.
belvu can calculate and display phylogenetic trees.
the tree reconstruction can be based on scoredist or other common correction-based distance estimators available within belvu.
multiple alignments can be coloured in belvu according to conservation using average blosum <dig> score in the column, or by residue-specific colours.
user-specified cutoffs can be employed to fine-tune the display.
belvu has a range of functions for sorting, colouring, marking up, and printing alignments.
in figure  <dig>  the alignment is coloured according to conservation, and sorted according to the tree.
the effect of distance correction with scoredist is illustrated.
belvu can also be utilised for batch mode operations on the multiple alignment, or for producing distance matrices or phylogenetic trees without graphical output.
it is available for the most common unix operating systems and can be obtained from  <cit> .
a windows version exists but is less frequently maintained.
see  <cit>  for instructions, and  <cit>  for information on the stockholm format, which is used by the pfam project.
discussion
our analysis was based on four different evolutionary models – dayhoff, mv, jtt and wag.
we chose these because they represent the spectrum of models well.
the only tuning done in the scoredist method is the estimation of the calibration factor c. this factor can be seen as a scaling factor for the logarithm base in equation  that needs to be set empirically.
the difference between scoredist and ml becomes particularly apparent in the mv dataset.
there are several hypotheses for this behaviour.
the dayhoff matrices were constructed with the limited data available at the time.
given the substantial increase of research output in this field particularly during the last decade, it is not surprising that the müller-vingron model  reports substantially other results than the dayhoff  and jtt  matrices.
additionally, the calibration factor c can also be interpreted as measure for the similarity of the respective models.
following this argument, jtt and dayhoff are more akin given a Δc ≈  <dig> .
the mv model is more distant to both jtt  and dayhoff .
the expected distance estimator generally overestimates distances.
for instance, among dayhoff-calibrated estimators on the mv testset, expected distance is more than  <dig> pam rmsd units  poorer than the best method scoredist.
similar values are observed for jtt calibrated estimators.
generally, mv-trained estimators are prone to underestimate evolutionary distances .
in combination with the ed higher distance estimation, this rather fortuitously leads to good results for ed – mv.
however, the scope of this research was to identify a robust method that performs well on various data sources.
an estimator which is highly sensitive to the data source or possible incorrect calibration is of less value.
the best single estimator was jtt-calibrated scoredist.
if the method per se is measured by averaging over all calibrations and testsets, scoredist receives  <dig> , ed  <dig> , and ml  <dig>  pam rmsd units.
this highlights scoredist as the most robust estimator, with the distance between scoredist and ed  being  <dig> fold the difference between ed and ml .
we here only present scoredist results using blosum <dig> for calculating the score σ between two sequences.
in principle one could use some other score matrix, but we found that this had little effect on the results.
since the goal was to make a general-purpose method, blosum <dig> was an obvious choice.
the key to scoredist is the usage of scores rather than identities, and the choice of somewhat arbitrary parameters is not of primary concern.
at present, gaps in the alignments are not included in the scoredist calculation.
traditionally, gaps have been difficult to embody in evolutionary models.
in the models used here, they are at best crudely modelled by treating every gap equally.
an inherent problem is that the probabilities for insertions and deletions  are not necessarily synchronized with the substitution probabilities.
some protein families are more prone to indels than others, hence it is hard to make a generalizable model that suits all protein types.
we have experimented with affine gap penalties in the scoredist method , but this resulted in decreased accuracy.
we therefore do not recommend using gaps to estimate protein distances.
CONCLUSIONS
we have developed the score matrix based distance estimator scoredist for aligned protein sequences.
its main advantages are computational simplicity and high robustness.
most other distance estimators produce good results for certain evolutionary models but perform poorly on others.
the maximum likelihood and expected distance were found to overfit their estimates to the evolutionary model so much that the results on testsets generated with other models suffered heavily.
the correction-based methods jukes-cantor and kimura also favoured a particular evolutionary model, but were not competitively accurate on any testset.
it seems that scoredist achieved the best compromise between accuracy and generalization power.

 estimating divergence time of protein sequences is one of the fundamental problems in bioinformatics. evolutionary distance estimates are used by many of the most commonly used phylogenetic tree reconstruction algorithms. in current research, phylogenetic trees are used for many types of subsequent analysis, e.g. orthology inference. early models for sequence evolution focussed on nucleotides. they commonly employ markov chains and assume independent evolution at every site. each of the four nucleotides is identified by one state and the substitution probability is modelled as a state transition probability from one state to another. in the most straightforward approach, the same state transition probability is assigned to every substitution. subsequent models take account of more nucleotide specific properties, e.g. transitional and transversional substitutions as well as gc content. these more advanced approaches are bound to nucleotide sequences and cannot be directly used with protein sequences. markov chain models for protein evolution differ from nucleotide approaches in their larger number of states and transitions for which parameters need to be estimated. the protein sequence jukes-cantor model assigns the same probability to each substitution and is hence a rather poor approximation. this method essentially takes the observed differences between two sequences and corrects this value to the estimated evolutionary distance using a logarithmic function. other similar methods exist that also correct observed differences, e.g. kimura's method. although they produce rather inaccurate distance estimates, correction-based distance estimators are popular because of their simplicity. more advanced protein evolution models estimate parameters from protein sequence alignments. assuming the same substitutions for closely and distantly related sequences leads to the construction of the dayhoff matrix series. following this approach, it suffices to collect data from alignments of closely related sequences to build an evolutionary model of amino acid substitution. dayhoff and co-workers introduced the term percent accepted mutation, which denotes a commonly used measure for evolutionary distance between two aligned sequences. in other words, two sequences at a distance of pam are related to each other by substitutions per position on average. as substitution is a stochastic process, some positions will experience multiple substitutions while others will experience none. it is also possible that secondary substitutions at one site will result in the original residue, making the evolutionary steps invisible. this is in essence the reason why estimating evolutionary distance is so hard – multiple substitutions cannot be observed directly. an evolutionary distance of pam corresponds roughly to 80% observed differences. the term pam is found in literature for both the matrix series given by dayhoff et al. as well as for evolutionary distance unit. in this publication we refer to the matrices as dayhoff matrices and reserve the term pam for distance units. there are two major shortcomings connected with the derivation of the dayhoff matrices. first, potential errors inherent in the experimental data will be magnified by extrapolation. additionally, it is questionable whether substitution probabilities observed on closely related sequences can accurately reflect the evolution of more distantly related sequences. the efforts of researchers since the publication of the dayhoff matrices have led to several other matrix series, sharing the idea of an underlying markov chain. they differ in terms of the data they are built upon and account for the above-mentioned shortcomings in various ways. the approach behind the blosum matrices is different from dayhoff's evolutionary model. whereas the markov model assumes that any transition probability matrix may be derived from another matrix in the same series, the blosum matrices do not imply any evolutionary time. there is no direct mathematical relationship between matrices in the blosum series. sequences with identities above a given identity cutoff are clustered and used to derive score matrices. the blosum matrices are known as a good general-purpose choice. especially, blosum is frequently chosen for the alignment of sequences.  we here introduce scoredist, a novel correction-based distance estimator for protein sequences. it applies a correction function to an observed reduction in normalised score, rather than to observed differences as other correction-based methods. this gives a better estimate of the divergence in the well-established pam measure and allows the popular blosum matrix series to be used. other matrices could in principle be used, but the blosum matrix has proved to be the most universal. scoredist distance estimates are calculated directly by a simple equation and do not require cumbersome computational approximations, which is needed for e.g. maximum likelihood and expected distance estimates. additional calibration opens the possibility to make scoredist tuned to other evolutionary models. in order to evaluate our novel protein distance estimator scoredist against other estimators, we generated a large testset of artificial sequence alignments. simulation is the only way to exactly know an alignment's evolutionary distance. the substitutions were made by rose according to an evolutionary model that can be chosen arbitrarily. it is to be expected that a distance estimator based on a particular evolutionary model will perform optimally on a testset generated with the same model. we therefore generated testsets using four different matrix series: dayhoff, mv, jtt, and wag. for each model, alignments were created for evolutionary distances between and pam units, i.e. alignments for each distance. the scoredist, maximum likelihood, and expected distance estimators can all be tuned towards a particular evolutionary model. we therefore used three evolutionary models which were also used to generate the testsets for these distance estimators, and use a shorthand to refer to these as "method-model". for instance, maximum likelihood using the mv model is denoted ml-mv. the jukes-cantor and kimura estimators can not be tuned to a specific model but were tested on all four datasets. the jukes-cantor and kimura correction methods are generally less accurate than scoredist and ml estimators. in some cases they reached higher accuracy than scoredist and ml trained on the "wrong" model. for instance, on the dayhoff testset kimura was better than scoredist-mv and ml-mv, and on the mv testset jukes-cantor was better than scoredist and ml trained on dayhoff or jtt. however, jukes-cantor and kimura never came near the scoredist and ml accuracy when trained on the "right" model. in a real situation, it is of course not known which evolutionary model is most appropriate. therefore, taking the average rmsd values for each training model reveals the generality and robustness of the method on different testsets. the average accuracy of scoredist is consistently better than for ml, and jukes-cantor and kimura are even further behind. implementation the scoredist estimator was implemented in belvu, which is a general-purpose multiple alignment viewer that allows basic alignment editing. belvu can calculate and display phylogenetic trees. the tree reconstruction can be based on scoredist or other common correction-based distance estimators available within belvu. multiple alignments can be coloured in belvu according to conservation using average blosum score in the column, or by residue-specific colours. user-specified cutoffs can be employed to fine-tune the display. belvu has a range of functions for sorting, colouring, marking up, and printing alignments. in figure the alignment is coloured according to conservation, and sorted according to the tree. the effect of distance correction with scoredist is illustrated. belvu can also be utilised for batch mode operations on the multiple alignment, or for producing distance matrices or phylogenetic trees without graphical output. it is available for the most common unix operating systems and can be obtained from. a windows version exists but is less frequently maintained. see for instructions, and for information on the stockholm format, which is used by the pfam project. discussion our analysis was based on four different evolutionary models – dayhoff, mv, jtt and wag. we chose these because they represent the spectrum of models well. the only tuning done in the scoredist method is the estimation of the calibration factor c. this factor can be seen as a scaling factor for the logarithm base in equation that needs to be set empirically. the difference between scoredist and ml becomes particularly apparent in the mv dataset. there are several hypotheses for this behaviour. the dayhoff matrices were constructed with the limited data available at the time. given the substantial increase of research output in this field particularly during the last decade, it is not surprising that the müller-vingron model reports substantially other results than the dayhoff and jtt matrices. additionally, the calibration factor c can also be interpreted as measure for the similarity of the respective models. following this argument, jtt and dayhoff are more akin given a Δc ≈. the mv model is more distant to both jtt and dayhoff. the expected distance estimator generally overestimates distances. for instance, among dayhoff-calibrated estimators on the mv testset, expected distance is more than pam rmsd units poorer than the best method scoredist. similar values are observed for jtt calibrated estimators. generally, mv-trained estimators are prone to underestimate evolutionary distances. in combination with the ed higher distance estimation, this rather fortuitously leads to good results for ed – mv. however, the scope of this research was to identify a robust method that performs well on various data sources. an estimator which is highly sensitive to the data source or possible incorrect calibration is of less value. the best single estimator was jtt-calibrated scoredist. if the method per se is measured by averaging over all calibrations and testsets, scoredist receives, ed, and ml pam rmsd units. this highlights scoredist as the most robust estimator, with the distance between scoredist and ed being fold the difference between ed and ml. we here only present scoredist results using blosum for calculating the score σ between two sequences. in principle one could use some other score matrix, but we found that this had little effect on the results. since the goal was to make a general-purpose method, blosum was an obvious choice. the key to scoredist is the usage of scores rather than identities, and the choice of somewhat arbitrary parameters is not of primary concern. at present, gaps in the alignments are not included in the scoredist calculation. traditionally, gaps have been difficult to embody in evolutionary models. in the models used here, they are at best crudely modelled by treating every gap equally. an inherent problem is that the probabilities for insertions and deletions are not necessarily synchronized with the substitution probabilities. some protein families are more prone to indels than others, hence it is hard to make a generalizable model that suits all protein types. we have experimented with affine gap penalties in the scoredist method, but this resulted in decreased accuracy. we therefore do not recommend using gaps to estimate protein distances.  we have developed the score matrix based distance estimator scoredist for aligned protein sequences. its main advantages are computational simplicity and high robustness. most other distance estimators produce good results for certain evolutionary models but perform poorly on others. the maximum likelihood and expected distance were found to overfit their estimates to the evolutionary model so much that the results on testsets generated with other models suffered heavily. the correction-based methods jukes-cantor and kimura also favoured a particular evolutionary model, but were not competitively accurate on any testset. it seems that scoredist achieved the best compromise between accuracy and generalization power. 
the jukes-cantor and kimura correction methods were also tested, but were substantially less accurate. we evaluated scoredist and a number of optimal matrix methods using three evolutionary models for both training and testing dayhoff, jones-taylor-thornton, and müller-vingron, as well as whelan and goldman solely for testing. a number of methods exist for estimating distances from sequence alignments, which often involves some sort of correction for multiple substitutions. the evolutionary distance between two aligned sequences is here estimated as the evolutionary distance of the optimal matrix. another problem is that the result may vary substantially depending on the evolutionary model used for the matrices. an ideal distance estimator should produce consistent and accurate distances independent of the evolutionary model used.
 distance-based methods are popular for reconstructing evolutionary trees thanks to their speed and generality. a number of methods exist for estimating distances from sequence alignments, which often involves some sort of correction for multiple substitutions. the problem is to accurately estimate the number of true substitutions given an observed alignment. so far, the most accurate protein distance estimators have looked for the optimal matrix in a series of transition probability matrices, e.g. the dayhoff series. the evolutionary distance between two aligned sequences is here estimated as the evolutionary distance of the optimal matrix. the optimal matrix can be found either by an iterative search for the maximum likelihood matrix, or by integration to find the expected distance. as a consequence, these methods are more complex to implement and computationally heavier than correction-based methods. another problem is that the result may vary substantially depending on the evolutionary model used for the matrices. an ideal distance estimator should produce consistent and accurate distances independent of the evolutionary model used.  we propose a correction-based protein sequence estimator called scoredist. it uses a logarithmic correction of observed divergence based on the alignment score according to the blosum score matrix. we evaluated scoredist and a number of optimal matrix methods using three evolutionary models for both training and testing dayhoff, jones-taylor-thornton, and müller-vingron, as well as whelan and goldman solely for testing. test alignments with known distances between and substitutions per position were simulated using rose. scoredist proved as accurate as the optimal matrix methods, yet substantially more robust. when trained on one model but tested on another one, scoredist was nearly always more accurate. the jukes-cantor and kimura correction methods were also tested, but were substantially less accurate.  the scoredist distance estimator is fast to implement and run, and combines robustness with accuracy. scoredist has been incorporated into the belvu alignment viewer, which is available at. 