Fast algorithms for computing the tripartition-based distance between phylogenetic networks

Consider two phylogenetic networks $${\cal N}$$ and $${\cal N}$$ ’ of size n. The tripartition-based distance finds the proportion of tripartitions which are not shared by $${\cal N}$$ and $${\cal N}$$ ’. This distance is proposed by Moret et al. (2004) and is a generalization of Robinson-Foulds distance, which is orginally used to compare two phylogenetic trees. This paper gives an $$O(\min \{k n \log n, n \log n + hn\})$$ -time algorithm to compute this distance, where h is the number of hybrid nodes in $${\cal N}$$ and $${\cal N}$$ ’ while k is the maximum number of hybrid nodes among all biconnected components in $${\cal N}$$ and $${\cal N}$$ ’. Note that $k \ll h \ll n$ in a phylogenetic network. In addition, we propose algorithms for comparing galled-trees, which are an important, biological meaningful special case of phylogenetic network. We give an $O(n)$-time algorithm for comparing two galled-trees. We also give an $$O(n + kh)$$ -time algorithm for comparing a galled-tree with another general network, where h and k are the number of hybrid nodes in the latter network and its biggest biconnected component respectively.