Stissing M, Mailund T, Pedersen C N S, Brodal G S, Fagerberg R
Bioinformatics Research Center and Department of Computer Science, University of Aarhus, Denmark.
J Bioinform Comput Biol. 2008 Feb;6(1):37-50. doi: 10.1142/s0219720008003266.
We present two algorithms for calculating the quartet distance between all pairs of trees in a set of binary evolutionary trees on a common set of species. The algorithms exploit common substructure among the trees to speed up the pairwise distance calculations, thus performing significantly better on large sets of trees compared to performing distinct pairwise distance calculations, as we illustrate experimentally, where we see a speedup factor of around 130 in the best case.
我们提出了两种算法，用于计算一组关于共同物种集的二叉进化树中所有树对之间的四重距离。这些算法利用树之间的公共子结构来加速成对距离的计算，因此与进行单独的成对距离计算相比，在大型树集上的性能有显著提升，正如我们通过实验所展示的那样，在最佳情况下我们看到加速因子约为130。
