摘要
Tree comparison metrics are an important tool for the study of phylogenetic trees. Path-difference distances measure the dissimilarity between two phylogenetic trees (on the same set of taxa) by comparing their path-length vectors. Various norms can be applied to this distance. Three important examples are the $l_{1}$-, $l_{2}$, and $l_{infty}$-norms. The previous best algorithms for computing path-difference distances all have $O(n^2)$ running time. In this paper, we show how to compute the l_1-norm path-difference distance in $O(n ext log^2 n)$ time and how to compute the $l_{2}$- and $l_{infty}$-norm path-difference distances in $O(n ext log n)$ time. By extending the presented algorithms, we also show that the $l_{p}$-norm path-difference distance can be computed in $O(pn ext log^2 n)$ time for any positive integer $p$. In addition, when the integer $p$ is even, we show that the distance can be computed in $O(p^2 n ext log n)$ time as well.