BACKGROUND
reconstruction of ancestral states aims at discovering the conformation of past proteins, genes or whole genomes from extant species data.
this approach has been successfully utilized to reconstruct ancestral steroid receptors  <cit> , mitochondrial dna  <cit> , antiviral rnase  <cit> , or fluorescent proteins  <cit> .
in a similar fashion, several studies have hypothesized on the evolution of hormone-receptor complexes  <cit> , composition of ancestral genomes  <cit> , thermostability of extinct proteins  <cit> , properties of ancestral promoters  <cit> , expansion of human segmental duplications  <cit> , or ancestral codon usage  <cit> .
parsimony, maximum likelihood or bayesian approaches are commonly utilized to infer ancestral states.
parsimony was originally introduced by edwards and cavalli-sforza  <cit> , but its application to reconstruct ancestral characters was first described by fitch  <cit> .
sankoff later proposed a modification to take into account different rates of change between states  <cit> .
the popularity of likelihood methods in phylogenetics is mostly due to the optimization proposed by felsenstein  <cit> .
yang described its application to infer ancestral sequences  <cit> .
bayesian approaches have also gained favor thanks to their combined used with markov chain monte carlo  methods.
huelsenbeck and bollback have proposed an algorithm for bayesian ancestral reconstruction  <cit> .
each of these approaches has advantages and weaknesses, and it is passionately debated which of them is more accurate.
parsimony is known for being biased when the rate of change per branch is high and tends to reconstruct the wrong tree due to long branch attraction  <cit> , while likelihood does not suffer from these problems  <cit> .
on the other hand, when the characters under study evolve at non-uniform rates over time, maximum likelihood and bayesian methods have been shown to be inconsistent and perform worse than parsimomy  <cit> .
regardless of the preferred method, the computational complexity of ancestral reconstruction algorithms is high and optimizations are required to work with large number of sequences.
in the particular case of parsimony, an algorithm to reduce the the number of computations has been previously proposed  <cit> .
goloboff has introduced diverse optimization strategies  <cit> , and ronquist  <cit>  has further improved some of the previous works.
all these optimizations aim at reducing the calculations in the number of taxa when looking for the most parsimonious tree, that is, when looking for the tree in the search space that minimizes the number of changes.
nevertheless, no correct optimization in the number of states of the weighted parsimony algorithm proposed by sankoff is known.
wheeler and nixon proposed an optimization  <cit>  later proved incorrect by swofford and siddall  <cit> .
in this paper, we present a two-fold optimization of sankoff parsimony.
our algorithm reduces the number of operations in the number of states needed to calculate the parsimony cost of a given phylogeny, as well as the time required to reconstruct the ancestral states.
this optimization can be utilized when the cost matrix for transitions between character states is either ultrametric or additive, and it reduces the original o operations required with n states per node and character.
while the optimization is moderate when the number of states is small, as in the case of nucleotides or amino acids, the optimization is more effective the larger the number of states, with an 8-fold reduction in running time in the case of metabolic enzymes.
the algorithms here presented were originally developed precisely to obtain fast reconstructions of ancestral metabolism, motivated by the recent interest in obtaining phylogenetic signal from metabolic data  <cit> .
in the rest of this paper we will review the original sankoff algorithm, describe our optimization, and analyze its performance for both randomly generated data and biologically well-known cost matrices for nucleotides, amino acids, and metabolic enzymes.
methods
original sankoff parsimony
sankoff parsimony  <cit>  counts the number of evolutionary changes for a specific site in a phylogenetic tree, assuming a set of n character states i =  <dig>  ..., n  for which a cost matrix c =  of changes between states is given.
each node p of the phylogeny has assigned a cost vector, s, which contains the minimal evolutionary cost si for each of the character states.
if node p is assigned state i, the quantity si reflects the minimum cost of events  from p to the root of the tree.
the original sankoff algorithm calculates the cost vectors at each node moving from the leaves upwards to the root.
initially, the s vectors at the inner nodes are unknown and those at the leaves are initialized with cost  <dig> for the observed character state and ∞ for the rest.
for instance, if adenine is observed in a site  for a certain species, the cost vector would be sa =  <dig> and st=sg=sc=∞.
the cost vector of a node p with two children q and r is:
si=min⁡j)+min⁡k)
equation  states that the cost of being in character state i for node p is the cost of moving from character state i to j in child q  plus the cost of having reached state j at node q from the leaves ).
character j is selected to minimize this sum, with the same procedure being applied to character k in child r. algorithm  <dig> presents the original implementation of sankoff parsimony to calculate the cost vector of all nodes in a tree for a single character.
algorithm  <dig> .
a procedure call sankoff_up calculates the cost vector s of all nodes p of the phylogeny t, given a cost matrix c = .
procedure sankoff_up
for all nodes p of t in postorder do
if p is a leaf then
for all i in  <dig>  ..., n do
if state i observed at leaf p then
si ← 0
else
si ← ∞
else
{q, r} ← children of p
for all i in  <dig>  ..., n do
si ← cost + cost
function cost
min ← ∞
for all j in  <dig>  ..., n do
if cij + sj < min then
min ← cij + sj
return min
algorithm  <dig> .
a procedure call sankoff_down calculates the ancestral states sancof all nodes p of the phylogeny t, given the root x of t, a cost matrix c =  of transition costs between states, and the cost vectors s for all nodes p of t as calculated by sankoff_up.
procedure sankoff_down
sanc←arg⁡min⁡isi
for all j in sancdo
for all child y of x do
sankoff_down
procedure sankoff_down
min_states
for all j in sancdo
for all child y of x do
sankoff_down
procedure min_states
min ← ∞
for all j in  <dig>  ..., n do
if x = root then
trans_cost ← sj
else
trans_cost ← cij + sj
if trans_cost < min then
min ← trans_cost
sanc ← {j}
else if trans_cost = min then
sanc ← sanc ∪ {j}
optimized sankoff parsimony
our optimization is based on the observation that not all transition costs between character states need to be computed if the cost matrix is ultrametric or additive.
definition  <dig>  a cost matrix is ultrametric if for every three indices i, j, k, one of the three following inequalities holds :
• cij ⩽ cik = cjk
• cik ⩽ cij = cjk
• cjk ⩽ cij = cik
definition  <dig>  a cost matrix is additive if for every four indices i, j, k, ℓ, one of the three following inequalities holds :
• cij + ckℓ ⩽ cik + cjℓ = ciℓ + cjk
• cik + cjℓ ⩽ cij + ckℓ = ciℓ + cjk
• ciℓ + cjk ⩽ cij + ckℓ = cik + cjℓ
notice that ultrametric matrices are also additive, since they satisfy the four point condition  <cit> .
consider a simple example where the cost matrix c has cii =  <dig> and cij = k for all i ≠ j. when calculating the cost si in equation , we can substitute minj) for min, k + minj≠i sj), and similarly for the other child r of p. in the more general case of ultrametric or additive cost matrices, we can efficiently represent them with a unique rooted weighted cost tree tc using upgma  <cit>  or neighbor-joining  <cit>  respectively.
the length of the path between any two leaves i, j in tc corresponds to the cost cij.
for ultrametric matrices, consider any set of leaves l = {a, b, ...} in the tree that have the same last common ancestor, lca.
by definition, lca is equidistant to any leaf in l, and all leaves in l are at the same distance d to each other ).
for any two leaves a, b in l we can then simplify the expression minl) as d + min sl.
therefore, given the cost tree tc obtained by upgma from the ultrametric matrix, for each state i we only need to compute the minimum costs at the last common ancestor of that state and any other, that is, the inner nodes in the path from i to the root of tc.
with additive matrices, since the distance from an inner node to its descendant leaves can vary, we need to take into consideration the specific length of each branch when calculating the minimum.
therefore, in our algorithm each cost vector sp is replaced by a cost tree tc, whose inner nodes will contain the value that minimizes.
cij + sl for all descendant leaves l. algorithm  <dig> presents the optimized version of sankoff parsimony for the calculations from the leaves to the root of the phylogeny.
algorithm  <dig> .
a procedure call opt_sankoff_up calculates the cost vector s of all nodes p of the phylogeny t, given a cost tree tc representing an ultrametric or additive cost matrix c = .
procedure opt_sankoff_up
for all nodes p of t in postorder do
if p is a leaf then
for all i in  <dig>  ..., n do
if state i observed at leaf p then
si ← 0
else
si ← ∞
update, tc)
else
{q, r} ← children of p
for all i in  <dig>  ..., n do
si ← cost + cost
update, tc)
procedure update
n ← leaf of tccorresponding to state i
cost ← v
min_tags ← {i}
cost ← branch length between n and its parent in tc
repeat
n ← parent of n in tc
if v + cost <cost then
cost ← v + cost
min_tags ← {i}
else if v + cost = cost then
min_tags ← min_tags ∪ {i}
if n ≠ root of tcthen
cost ← cost + branch length between n and its parent in tc
until n = root of tc
function cost
n ← leaf of tccorresponding to state i
min ← cost
cost ← branch length between n and its parent in tc
repeat
n ← parent of n in tc
if cost + cost < min then
min ← cost + cost
if n ≠ root of tcthen
cost ← cost + branch length between n and its parent in tc
until n = root of tc
return min
algorithm  <dig> utilizes a cost tree tc with the same topology as tc for each node p, and where each node is annotated with the minimum value corresponding to cij + sl, as implemented in the function cost.
the function update saves each of these cost trees by moving from the leaves to the root and storing minimum values in the nodes ), as well as the leaf responsible for the value stored in the node ), which will be later used to optimize the reconstruction of ancestral states.
the complexity of algorithm  <dig> depends on the internal path length of tc.
the worst case would be a degenerate tree with linear structure, in which case the complexity for n states is / <dig> per node and character .
notice that in practice this will be a rare case, and most cost trees have a more favourable topology to our optimization , while the original algorithm takes o time no matter the cost matrix used.
algorithm  <dig> presents the optimized version of the reconstruction of ancestral states using sankoff parsimony.
in its original implementation, for each node we had to consider all posible states looking for the one that minimized cij + sj.
since we have already saved the minimum transition costs and the leaves responsible for them as shown in algorithm  <dig>  we can use this information to further speed up computation.
the ancestral states for the root r of the phylogeny t are obtained as in the original algorithm.
for any inner node x of t, and given that its parent had ancestral state k reconstructed, we only need to move from leaf k to the root of tc and keep the state min_tags that has the minimum value cost.
algorithm  <dig> .
a procedure call opt_sankoff_down calculates the ancestral states sancof all nodes p of the phylogeny t, given the root x of t and the cost tree tcfor each node p of t as calculated by opt_sankoff_up.
procedure sankoff_down
sanc←arg⁡min⁡isi
for all j in sancdo
for all child y of x do
opt_sankoff_down
procedure opt_sankoff_down
n ← leaf of tccorresponding to state i
min ← cost
cost ← branch length between n and its parent in tc
repeat
n ← parent of n in tc
if cost + cost < min then
min ← cost + cost
sanc ← {min_tags}
else if cost + cost = min then
sanc ← sanc ∪ {min_tags}
if n ≠ root of tcthen
cost ← cost + branch length between n and its parent in tc
until n = root of tc
for all j in sancdo
for all child y of x do
opt_sankoff_down
algorithm  <dig> reduces the number of operations compared to the original implementation, since we do not have to review all states at each node but only traverse from a leaf to the root of the cost tree.
the original implementation takes o time, while the complexity of our optimization is again a function of the internal path length of tc, which in general will be less than n.
RESULTS
we performed a series of simulations involving a single random site from  <dig> to  <dig> species in a random phylogeny, and  <dig> to  <dig> character states.
sankoff parsimony costs were calculated using randomly generated additive matrices and their associated cost trees.
all experiments were performed in a mac pro with  <dig> ×  <dig>  ghz dual-core intel xeon processor,  <dig> gb of memory, and mac os x  <dig> .
<dig>  figure  <dig> presents running times versus the number of states, with the running time shown for all the generated phylogenies; that is, for each point corresponding to a particular number of states in the horizontal axis, there are  <dig> measurementes  of execution times for both the original and optimized methods.
as it can be observed, times for the optimized algorithm grow linearly in the number of states, while the original implementation has a quadratic growth.
results for ultrametric matrices  were similar to those presented in figure  <dig>
figures  <dig> and  <dig> show results for a single randomly generated nucleotide and phylogeny  using cost matrices based on the dna evolution models proposed by jukes and cantor  <cit>  and kimura  <cit> , both of which are ultrametric.
even though there are only  <dig> character states, the optimized algorithm outperforms the original implementation.
notice that results for these two figures and the previous one are for a single site; calculations for full sequences would further increase the difference between the original and the optimized algorithms.
to provide a better idea of the performance of our optimization in a more realistic setup, we reconstructed the ancestral amino acid chain of elongation factor-1α from the sequence of  <dig> species .
the cost matrices were obtained from works addressing the problem of how to obtain a reduced amino acid alphabet that can still produce a correct folding  <cit> .
figure  <dig> presents the corresponding cost trees.
as it can be seen in figure  <dig>  in this particular example the optimization is approximately 27% faster than the original algorithm.
alternatively, we could have codified the presence or absence of enzymes in each species, and then perform a reconstruction using maximum parsimony.
while this is a commonly used approach, the use of measures of enzymatic similarity has shown a better performance than simple patterns of presence/absence of enzymes in the phylogenetic analysis of metabolism  <cit> , and therefore the election of large state sets is to be preferred.
for this particular example, the number of states is composed of  <dig> reactions annotated to at least one of the twelve species under study, and the number of inner nodes in the cost tree is comparatively small, making our optimization 8-fold faster than the original implementation.
CONCLUSIONS
the optimization here presented provides a computation of sankoff parsimony faster than the original algorithm when the cost matrix is ultrametric or additive, even for a small number of character states.
since our approach reduces the execution time needed to calculate the parsimony cost of a single tree, it could be easily combined with optimizations looking for the most parsimonous tree.
our algorithm takes comparatively less time to execute when the number of states is large, and therefore problems such as ancestral metabolism reconstruction could be especially well-suited for this optimization.
authors' contributions
jc and gv conceived the method and prepared the manuscript.
jc implemented the algorithms and performed the experiments.
all authors contributed to the discussion and have approved the final manuscript.

 reconstruction of ancestral states aims at discovering the conformation of past proteins, genes or whole genomes from extant species data. this approach has been successfully utilized to reconstruct ancestral steroid receptors, mitochondrial dna, antiviral rnase, or fluorescent proteins. in a similar fashion, several studies have hypothesized on the evolution of hormone-receptor complexes, composition of ancestral genomes, thermostability of extinct proteins, properties of ancestral promoters, expansion of human segmental duplications, or ancestral codon usage. parsimony, maximum likelihood or bayesian approaches are commonly utilized to infer ancestral states. parsimony was originally introduced by edwards and cavalli-sforza, but its application to reconstruct ancestral characters was first described by fitch. sankoff later proposed a modification to take into account different rates of change between states. the popularity of likelihood methods in phylogenetics is mostly due to the optimization proposed by felsenstein. yang described its application to infer ancestral sequences. bayesian approaches have also gained favor thanks to their combined used with markov chain monte carlo methods. huelsenbeck and bollback have proposed an algorithm for bayesian ancestral reconstruction. each of these approaches has advantages and weaknesses, and it is passionately debated which of them is more accurate. parsimony is known for being biased when the rate of change per branch is high and tends to reconstruct the wrong tree due to long branch attraction, while likelihood does not suffer from these problems. on the other hand, when the characters under study evolve at non-uniform rates over time, maximum likelihood and bayesian methods have been shown to be inconsistent and perform worse than parsimomy. regardless of the preferred method, the computational complexity of ancestral reconstruction algorithms is high and optimizations are required to work with large number of sequences. in the particular case of parsimony, an algorithm to reduce the the number of computations has been previously proposed. goloboff has introduced diverse optimization strategies, and ronquist has further improved some of the previous works. all these optimizations aim at reducing the calculations in the number of taxa when looking for the most parsimonious tree, that is, when looking for the tree in the search space that minimizes the number of changes. nevertheless, no correct optimization in the number of states of the weighted parsimony algorithm proposed by sankoff is known. wheeler and nixon proposed an optimization later proved incorrect by swofford and siddall. in this paper, we present a two-fold optimization of sankoff parsimony. our algorithm reduces the number of operations in the number of states needed to calculate the parsimony cost of a given phylogeny, as well as the time required to reconstruct the ancestral states. this optimization can be utilized when the cost matrix for transitions between character states is either ultrametric or additive, and it reduces the original o operations required with n states per node and character. while the optimization is moderate when the number of states is small, as in the case of nucleotides or amino acids, the optimization is more effective the larger the number of states, with an 8-fold reduction in running time in the case of metabolic enzymes. the algorithms here presented were originally developed precisely to obtain fast reconstructions of ancestral metabolism, motivated by the recent interest in obtaining phylogenetic signal from metabolic data. in the rest of this paper we will review the original sankoff algorithm, describe our optimization, and analyze its performance for both randomly generated data and biologically well-known cost matrices for nucleotides, amino acids, and metabolic enzymes. methods original sankoff parsimony sankoff parsimony counts the number of evolutionary changes for a specific site in a phylogenetic tree, assuming a set of n character states i =..., n for which a cost matrix c = of changes between states is given. each node p of the phylogeny has assigned a cost vector, s, which contains the minimal evolutionary cost si for each of the character states. if node p is assigned state i, the quantity si reflects the minimum cost of events from p to the root of the tree. the original sankoff algorithm calculates the cost vectors at each node moving from the leaves upwards to the root. initially, the s vectors at the inner nodes are unknown and those at the leaves are initialized with cost for the observed character state and ∞ for the rest. for instance, if adenine is observed in a site for a certain species, the cost vector would be sa = and st=sg=sc=∞. the cost vector of a node p with two children q and r is: si=min⁡j)+min⁡k) equation states that the cost of being in character state i for node p is the cost of moving from character state i to j in child q plus the cost of having reached state j at node q from the leaves ). character j is selected to minimize this sum, with the same procedure being applied to character k in child r. algorithm presents the original implementation of sankoff parsimony to calculate the cost vector of all nodes in a tree for a single character. algorithm. a procedure call sankoff_up calculates the cost vector s of all nodes p of the phylogeny t, given a cost matrix c =. procedure sankoff_up    for all nodes p of t in postorder do       if p is a leaf then          for all i in..., n do             if state i observed at leaf p then                si ← 0             else                si ← ∞       else          {q, r} ← children of p          for all i in..., n do             si ← cost + cost function cost    min ← ∞    for all j in..., n do       if cij + sj < min then          min ← cij + sj    return min algorithm. a procedure call sankoff_down calculates the ancestral states sancof all nodes p of the phylogeny t, given the root x of t, a cost matrix c = of transition costs between states, and the cost vectors s for all nodes p of t as calculated by sankoff_up. procedure sankoff_down    sanc←arg⁡min⁡isi    for all j in sancdo       for all child y of x do          sankoff_down procedure sankoff_down    min_states    for all j in sancdo       for all child y of x do       sankoff_down procedure min_states    min ← ∞    for all j in..., n do       if x = root then          trans_cost ← sj       else          trans_cost ← cij + sj       if trans_cost < min then          min ← trans_cost          sanc ← {j}       else if trans_cost = min then          sanc ← sanc ∪ {j} optimized sankoff parsimony our optimization is based on the observation that not all transition costs between character states need to be computed if the cost matrix is ultrametric or additive. definition a cost matrix is ultrametric if for every three indices i, j, k, one of the three following inequalities holds: • cij ⩽ cik = cjk • cik ⩽ cij = cjk • cjk ⩽ cij = cik definition a cost matrix is additive if for every four indices i, j, k, ℓ, one of the three following inequalities holds: • cij + ckℓ ⩽ cik + cjℓ = ciℓ + cjk • cik + cjℓ ⩽ cij + ckℓ = ciℓ + cjk • ciℓ + cjk ⩽ cij + ckℓ = cik + cjℓ notice that ultrametric matrices are also additive, since they satisfy the four point condition. consider a simple example where the cost matrix c has cii = and cij = k for all i ≠ j. when calculating the cost si in equation, we can substitute minj) for min, k + minj≠i sj), and similarly for the other child r of p. in the more general case of ultrametric or additive cost matrices, we can efficiently represent them with a unique rooted weighted cost tree tc using upgma or neighbor-joining respectively. the length of the path between any two leaves i, j in tc corresponds to the cost cij. for ultrametric matrices, consider any set of leaves l = {a, b,...} in the tree that have the same last common ancestor, lca. by definition, lca is equidistant to any leaf in l, and all leaves in l are at the same distance d to each other ). for any two leaves a, b in l we can then simplify the expression minl) as d + min sl. therefore, given the cost tree tc obtained by upgma from the ultrametric matrix, for each state i we only need to compute the minimum costs at the last common ancestor of that state and any other, that is, the inner nodes in the path from i to the root of tc. with additive matrices, since the distance from an inner node to its descendant leaves can vary, we need to take into consideration the specific length of each branch when calculating the minimum. therefore, in our algorithm each cost vector sp is replaced by a cost tree tc, whose inner nodes will contain the value that minimizes. cij + sl for all descendant leaves l. algorithm presents the optimized version of sankoff parsimony for the calculations from the leaves to the root of the phylogeny. algorithm. a procedure call opt_sankoff_up calculates the cost vector s of all nodes p of the phylogeny t, given a cost tree tc representing an ultrametric or additive cost matrix c =. procedure opt_sankoff_up    for all nodes p of t in postorder do       if p is a leaf then          for all i in..., n do             if state i observed at leaf p then                si ← 0             else                si ← ∞             update, tc)       else          {q, r} ← children of p          for all i in..., n do             si ← cost + cost             update, tc) procedure update    n ← leaf of tccorresponding to state i    cost ← v    min_tags ← {i}    cost ← branch length between n and its parent in tc    repeat       n ← parent of n in tc       if v + cost <cost then          cost ← v + cost          min_tags ← {i}       else if v + cost = cost then          min_tags ← min_tags ∪ {i}       if n ≠ root of tcthen          cost ← cost + branch length between n and its parent in tc    until n = root of tc function cost    n ← leaf of tccorresponding to state i    min ← cost    cost ← branch length between n and its parent in tc    repeat       n ← parent of n in tc       if cost + cost < min then          min ← cost + cost       if n ≠ root of tcthen          cost ← cost + branch length between n and its parent in tc    until n = root of tc    return min algorithm utilizes a cost tree tc with the same topology as tc for each node p, and where each node is annotated with the minimum value corresponding to cij + sl, as implemented in the function cost. the function update saves each of these cost trees by moving from the leaves to the root and storing minimum values in the nodes ), as well as the leaf responsible for the value stored in the node ), which will be later used to optimize the reconstruction of ancestral states. the complexity of algorithm depends on the internal path length of tc. the worst case would be a degenerate tree with linear structure, in which case the complexity for n states is / per node and character. notice that in practice this will be a rare case, and most cost trees have a more favourable topology to our optimization, while the original algorithm takes o time no matter the cost matrix used. algorithm presents the optimized version of the reconstruction of ancestral states using sankoff parsimony. in its original implementation, for each node we had to consider all posible states looking for the one that minimized cij + sj. since we have already saved the minimum transition costs and the leaves responsible for them as shown in algorithm we can use this information to further speed up computation. the ancestral states for the root r of the phylogeny t are obtained as in the original algorithm. for any inner node x of t, and given that its parent had ancestral state k reconstructed, we only need to move from leaf k to the root of tc and keep the state min_tags that has the minimum value cost. algorithm. a procedure call opt_sankoff_down calculates the ancestral states sancof all nodes p of the phylogeny t, given the root x of t and the cost tree tcfor each node p of t as calculated by opt_sankoff_up. procedure sankoff_down    sanc←arg⁡min⁡isi    for all j in sancdo       for all child y of x do          opt_sankoff_down procedure opt_sankoff_down    n ← leaf of tccorresponding to state i    min ← cost    cost ← branch length between n and its parent in tc    repeat       n ← parent of n in tc       if cost + cost < min then          min ← cost + cost          sanc ← {min_tags}       else if cost + cost = min then          sanc ← sanc ∪ {min_tags}       if n ≠ root of tcthen          cost ← cost + branch length between n and its parent in tc    until n = root of tc    for all j in sancdo       for all child y of x do          opt_sankoff_down algorithm reduces the number of operations compared to the original implementation, since we do not have to review all states at each node but only traverse from a leaf to the root of the cost tree. the original implementation takes o time, while the complexity of our optimization is again a function of the internal path length of tc, which in general will be less than n.  we performed a series of simulations involving a single random site from to species in a random phylogeny, and to character states. sankoff parsimony costs were calculated using randomly generated additive matrices and their associated cost trees. all experiments were performed in a mac pro with × ghz dual-core intel xeon processor, gb of memory, and mac os x. figure presents running times versus the number of states, with the running time shown for all the generated phylogenies; that is, for each point corresponding to a particular number of states in the horizontal axis, there are measurementes of execution times for both the original and optimized methods. as it can be observed, times for the optimized algorithm grow linearly in the number of states, while the original implementation has a quadratic growth. results for ultrametric matrices were similar to those presented in figure figures and show results for a single randomly generated nucleotide and phylogeny using cost matrices based on the dna evolution models proposed by jukes and cantor and kimura, both of which are ultrametric. even though there are only character states, the optimized algorithm outperforms the original implementation. notice that results for these two figures and the previous one are for a single site; calculations for full sequences would further increase the difference between the original and the optimized algorithms. to provide a better idea of the performance of our optimization in a more realistic setup, we reconstructed the ancestral amino acid chain of elongation factor-1α from the sequence of species. the cost matrices were obtained from works addressing the problem of how to obtain a reduced amino acid alphabet that can still produce a correct folding. figure presents the corresponding cost trees. as it can be seen in figure in this particular example the optimization is approximately 27% faster than the original algorithm. alternatively, we could have codified the presence or absence of enzymes in each species, and then perform a reconstruction using maximum parsimony. while this is a commonly used approach, the use of measures of enzymatic similarity has shown a better performance than simple patterns of presence/absence of enzymes in the phylogenetic analysis of metabolism, and therefore the election of large state sets is to be preferred. for this particular example, the number of states is composed of reactions annotated to at least one of the twelve species under study, and the number of inner nodes in the cost tree is comparatively small, making our optimization 8-fold faster than the original implementation.  the optimization here presented provides a computation of sankoff parsimony faster than the original algorithm when the cost matrix is ultrametric or additive, even for a small number of character states. since our approach reduces the execution time needed to calculate the parsimony cost of a single tree, it could be easily combined with optimizations looking for the most parsimonous tree. our algorithm takes comparatively less time to execute when the number of states is large, and therefore problems such as ancestral metabolism reconstruction could be especially well-suited for this optimization. authors' contributions jc and gv conceived the method and prepared the manuscript. jc implemented the algorithms and performed the experiments. all authors contributed to the discussion and have approved the final manuscript. 
we analyzed its performance for randomly generated matrices, jukes-cantor and kimura's two-parameter models of dna evolution, and in the reconstruction of elongation factor-1α and ancestral metabolic states of a group of eukaryotes, showing that in all cases the execution time is significantly less than with the original implementation. although optimizations exist to reduce the computations in the number of taxa, the original algorithm takes time o in the number of states, making it impractical for large values of n. since we are reducing the computations required to calculate the parsimony cost of a single tree, our method can be combined with optimizations in the number of taxa that aim at finding the most parsimonious tree. sankoff parsimony determines the minimum number of changes required in a given phylogeny when a cost is associated to transitions between character states. in this study we introduce an optimization of sankoff parsimony for the reconstruction of ancestral states when ultrametric or additive cost matrices are used. the algorithms here presented provide a fast computation of sankoff parsimony for a given phylogeny. problems where the number of states is large, such as reconstruction of ancestral metabolism, are particularly adequate for this optimization.
 parsimony methods are widely used in molecular evolution to estimate the most plausible phylogeny for a set of characters. sankoff parsimony determines the minimum number of changes required in a given phylogeny when a cost is associated to transitions between character states. although optimizations exist to reduce the computations in the number of taxa, the original algorithm takes time o in the number of states, making it impractical for large values of n.  in this study we introduce an optimization of sankoff parsimony for the reconstruction of ancestral states when ultrametric or additive cost matrices are used. we analyzed its performance for randomly generated matrices, jukes-cantor and kimura's two-parameter models of dna evolution, and in the reconstruction of elongation factor-1α and ancestral metabolic states of a group of eukaryotes, showing that in all cases the execution time is significantly less than with the original implementation.  the algorithms here presented provide a fast computation of sankoff parsimony for a given phylogeny. problems where the number of states is large, such as reconstruction of ancestral metabolism, are particularly adequate for this optimization. since we are reducing the computations required to calculate the parsimony cost of a single tree, our method can be combined with optimizations in the number of taxa that aim at finding the most parsimonious tree. 