Comparison with existing algorithms
In Fig. 4 we compare the running time of the new algorithm with the O(n2d2) and O(n3) time algorithms from [11] on random and r8s simulated trees. In Fig. 5 we compare the running time of the new algorithm with the other two algorithms on Buneman and refined Buneman trees built for a range of Pfam [13] derived distance matrices using the tool in [14]. Buneman and refined Buneman trees are not binary unless this is well supported by the input distance matrix, and thus represent the kind of trees which can only be compared by methods which allow for trees of arbitrary degrees. In both experiments, the O(n3) time algorithm is slowest by a large margin for all plotted sizes of n. The new algorithm is consistently faster than the O(n2d2) time algorithm for the r8s (with edge contraction) simulated trees and for the Buneman and refined Buneman trees. For random trees the previous O(n2d2) time algorithm is slightly faster in practice. This difference is most likely caused by the additional overhead of precomputing the sums used by the new O(n2d) time algorithm compared to the previous O(n2d2) time algorithm in order to improve the asymptotic worst case running time (see method section). For trees of low degree, the overhead might dominate the factor d by which the worst case running time of the new algorithm is improved. The observed running times on random trees thus indicate that over selection of random trees consists of trees of low degree, whereas the r8s simulated, Buneman, and refined Buneman trees are trees with a few nodes of high degree which more than compensate for the additional overhead of dealing with nodes of low degree. In conclusion, we find that the experimental comparison of the new algorithm with the previously developed algorithms indicate that the new algorithm not only improves on the theoretical asymptotic running time, but also improves the running time in practice if the input trees contain a few nodes of high degree.
Figure 4  Comparisons with earlier algorithms on random and r8s trees. The running time for the new algorithm compared to the existing O(n2d2) and O(n3) time algorithms for random and r8s trees. The lines are fitted polynomial c. n2, for the case of the new algorithm (denoted n2d in the legend) and the O(n2d2) algorithm, and the polynomial c. n3 for the O(n3) algorithm. The plot is in log-scale on both the x- and y-axis.
Figure 5  Comparisons with earlier algorithms on Buneman and refined Buneman trees. The running time for the new O(n2d) time algorithm compared to the existing O(n2d2) and O(n3) time algorithms on the Buneman and the refined Buneman trees for range of Pfam based distance matrices. The plot is in log-scale on both the x- and y-axis.